Games on Directed Graphs Sample Clauses

Games on Directed Graphs. ‌ In this section, we will seek to try to understand what is behind the approaches and strategies defined in the previous section and how to generalise them. In sum, we are looking into the following questions: C1 Bipartite graphs in generalised consensus games as seen so far in this chapter might lead to loops of states that will never lead to consensus. These loops have length 2. Is there any set of games in a graph G that might enter in a loop of size 3 instead? If so, are they tripartite graphs? How would these graphs be defined? C2 What would be a characterisation of graphs that admit state-loops of given size? C3 If the situation in Question C2 happens in a graph G and initial state S0, is there an analogous version of our split function that would generate 3 (instead of 2) single-partition games from S0? C4 In these conditions, what is the probability of generalised consensus games that admit such loops to be winning games? C5 Are there graphs in which losing games might not include loops? C6 Finally, what is the probability of success of these more general games? The answer for the questions above boils down to the algorithm use by the agents, as well as the graph they are in. In order to answer Question C1, consider the example below in which, although there are only two possible consensus states, neither one can be achieved.