Article citationsMore>>

F. Santos, J. Pacheco and T. Lenaerts, “Evolutionary Dynamics of Social Dilemas in Structured Heterogeneous Populations,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 103, No. 9, 2006, pp. 3490-3494. doi:10.1073/pnas.0508201103

has been cited by the following article:

• TITLE: Best Response Games on Regular Graphs

  AUTHORS: Richard Southwell, Chris Cannings

  KEYWORDS: Games on Graphs; Cellular Automata; Best Response Games; Social Networks

  JOURNAL NAME: Applied Mathematics, Vol.4 No.6, June 20, 2013

  ABSTRACT: With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.