Imagine a group of robots who behave as follows…
We can represent this game as a graph, in which robots are nodes, and an edge between them represents that they are neighbours!
How to play
All nodes start as “inactive”, coloured grey. Two players, each with their own colour (green or purple), decide to activate a number of vertices at the start. They take turns selecting vertices by selecting “assign green node” or “assign purple node” and then selecting an “inactive” vertex from the graph that they want to be their colour.
Once vertices are chosen, the game begins. You can select “simulate” to see the game unfold by itself. Alternatively, you can select “iterate 1 step” to see a single round of the game play out.
The game may go through hundreds of iterations per run, be patient!
The game ends once all vertices are showing the same colour - this means consensus is reached and the player with that colour wins!
How to increase your chances of winning
Explore the documentation page to explore what tools you can use to your advantage!
At the start of the game, a clever you will choose vertices that are most ‘influential’. But what makes a vertex influential?
Is it better to be the player to make the first move or to be the second?
For a initial starting configuration of a graph, what is the probability that a game ends with all robots showing a particular colour, e.g. green?
Remember, although the players’ initial choice is important, there is also some randomness involved, as if the vertices were rolling a die to make decisions.
These motivations and considerations serve as a good connection to the next section, in which we introduce a demo of this problem for you to do some hands-on exploration.
The graph to the left represents a Consensus. game with five nodes and with the probability of taking no action being zero (i.e., p=0). 1 is green, 2 is off, 3, 4, and 5 are purple. Inactive can become active but not vice-versa. If a node selects an inactive neighbour, it keep its current colour. Node 1 has 50% chance of not changing or becoming blue. Whereas, 3 has 75% chance of staying blue and 25% of becoming red.
This is a physical version of the game Consensus. Coded and wired by Bruna Rodrigues da Silva, Gabriel da Silva Navarro and Jhuann Piedro Alves Nogueira. As undergraduate students at University of São Paulo, they created the physical consensus object from stratch to be presented at the Oxford Maths Festival.
This is a physical version of the game Consensus. Coded and wired by Bruna Rodrigues da Silva, Gabriel da Silva Navarro and Jhuann Piedro Alves Nogueira. As undergraduate students at University of São Paulo, they created the physical consensus object from stratch to be presented at the Oxford Maths Festival.
The graph to the left represents a Consensus. game with five nodes and with the probability of taking no action being zero (i.e., p=0). 1 is green, 2 is off, 3, 4, and 5 are purple. Inactive can become active but not vice-versa. If a node selects an inactive neighbour, it keep its current colour. Node 1 has 50% chance of not changing or becoming blue. Whereas, 3 has 75% chance of staying blue and 25% of becoming red.
This is a physical version of the game Consensus. Coded and wired by Bruna Rodrigues da Silva, Gabriel da Silva Navarro and Jhuann Piedro Alves Nogueira. As undergraduate students at University of São Paulo, they created the physical consensus object from stratch to be presented at the Oxford Maths Festival.
As with the analogy with robots, consensus problems appear in several different domains. For example, one may be interested in the spreading of rumours (or diseases!). Or even to study fixation of mutations in a population. This problem has applications in autonomous systems that need to coordinate as a group while also making decisions independently.
One can look at an example problem in consensus and wonder: which node is the most influential in a given scenario? More precisely, we can define `influence' as the contribution in probability that a node being, say, blue, contributes to the probability of blue consensus to take place in the entire network.
Consider a simpler version of this problem in which there are no inactive nodes. Hassin and Peleg (2001) solved the problem of determining the probability of consensus for pretty much all types of network. The magic in that solution is that the influence of a node does not depend on its colours nor the colours of the other nodes in the network.
For situations with inactive nodes, however, that is not the case. The influence of each node does change depending on the colours of the rest and whether they are active or not. Take into account a drastic example in which only one node is active and the rest is inactive. In that case, the colour of the active node has 100% influence on the consensus colour of the network!
Consider then a game in which 2 (or more!) players select one node each in an initially inactive network to turn active and to their colour. Is it better to choose first or last? What are the best nodes to choose?