Nash Equilibria in Certain Two-Choice Multi-Player Games Played on the Ladder Graph

In this paper, we compute analytically the number of Nash Equilibria (NE) for a two-choice game played on a (circular) ladder graph with 2 #119899; players. We consider a set of games with generic payoff parameters, with the only requirement that a NE occurs if the players choose opposite strategies (anti-coordination game). The results show that for both, the ladder and circular ladder, the number of NE grows exponentially with (half) the number of players #119899;, as #119873;NE(2 #119899;) #8764; #119862;( #120593;) #119899;, where #120593;=1.618.. is the golden ratio and #119862;circ #119862;ladder. In addition, the value of the scaling factor #119862;ladder depends on the value of the payoff parameters. However, that is no longer true for the circular ladder (3-degree graph), that is, #119862;circ is constant, which might suggest that the topology of the graph indeed plays an important role for setting the number of NE.