Given a game and a graph (or network), we can identify the vertices of the graph as players, and each player will play the defined game with their neighbours (i.e. the players connected to them by a graph line). This set up is known as a graphical game (Kearns et al, 2001). Graphical games have several applications in multiple fields, such as biology, economics, sociology, and so on (see, for instance: Allen et al, 2019; Leduc et al, 2017; Eger, 2016). Getting all the possible Nash Equilibrium (NE) solutions for a game played on a graph is no easy task. That is why we started with a simple toy model by picking a two-choice two-player game and a highly regular graph.
Our game has two options/strategies: ‘A’ or ‘B’. In this setup with two players, both players get the best payoff when they anti-coordinate their choices (i.e. one chooses ‘A’ and the other chooses ‘B’ and vice versa). As for the choice of graph, we will have two different graphs: a ladder and a circular ladder, both with 4k vertices/nodes (or dots), that represent 4k players. Each player will play pairwise the two-player anti-coordination game we just described, with their neighbours (see picture above). Therefore, after all the games have been played, we will have a list of ‘A’s and ‘B’s: the first letter corresponding to player one’s strategy, the second to player two’s, etc. A list of ‘A’s and ‘B’s in which no player wants to unilaterally change their strategy is known as an NE solution. We will refer to this type of list as ‘a list of NE’. Obviously, given the large number of players (4k) connected with each other as in the ladder and circular ladder graphs/networks, there will be lots of different lists of NE. Our aim is to count how many lists of NE solution we have as a function of the number of players (4k) for both graphs/networks.
The concrete payoff, e.g. the prize money, that the players get when they play the above-defined anti-coordination game are not completely specified. Therefore, depending on the concrete numbers (amount of money) chosen, we can classify the lists of NE solutions in four types. However, it turns out that out of the 4 types of lists of NE, only two are truly different because the remaining two types of lists can be made up from the other two by interchanging ‘A’ and ‘B’. For example, the lists ABAB and AAAB can be recovered by swapping ‘A’ and ‘B’ in the lists BABA and BBBA, respectively. Thus, we only need to look at 2 types of lists of NE.
For the first list type, we found that we were able to work with a much shorter list (with k symbols) made out of four numbers: ‘0’, ‘1’, ‘2’ and ‘3’ and certain rules to write the sequence of numbers, instead of working with a list of 4k ‘A’’s and ‘B’’s. For instance, after a ‘0’, there cannot be a ‘3’, and other similar restrictions. That can be thought of as having four numbered Lego building blocks, in which the blocks need to be attached to each other in certain ways (see the picture above). By using the building blocks instead of the large original list of NE with ‘A’’s and ‘B’’s we have turned the counting of the number of NE into a much easier task, which is possible to be done by hand using some combinatorics. After doing so, we found an analytical formula to count the number of lists of NE for both graphs with 4k players. In those two formulae, one for the ladder and the other for the circular ladder, we found that, surprisingly enough, the golden ratio φ=(1+√5)/2 is the base of the exponential growth of the number of NE for both graphs.
In the second type of list, we have more Lego blocks: six instead of four, and other rules to attach them. Nevertheless, the procedure and techniques used to count the number of lists of NE is the same as before. Again, we found similar formulae to do the counting with the omnipresence of the golden ratio.
Our work presents a novelty in the sense that we derived an analytical formula to count the number of NE in the ladder and the circular ladder, as opposed to the algorithmic or computational approach usually employed for such problems. Due to this fact we were able to find the starring role of the golden ratio to set the number of NE for both graphs, which was surprising to us. That allowed us also to directly compare the number of NE between the two graphs, and between the two different analysed types of lists to draw some conclusions. Our results could be the basis for further work on other real-world interactions that can be modelled as a game and a graph/network.
