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.
Cite this paper
R. Southwell and C. Cannings, "Best Response Games on Regular Graphs," Applied Mathematics, Vol. 4 No. 6, 2013, pp. 950-962. doi: 10.4236/am.2013.46131.
 J. von Neumann and O. Morgenstern, “Theory of Games and Economic Behavior,” Princeton University Press, Princeton, 1944.
 J. Nash, “Non-Cooperative Games,” The Annals of Mathematics, Vol. 54, No. 2, 1951, pp. 286-295.
 J. Maynard Smith, “Evolution and the Theory of Games,” Cambridge University Press, Cambridge, 1982.
 G. Szabo and J. Fath, “Evolutionary Games on Graphs,” Physics Reports, Vol. 446, No. 4, 2007, pp. 97-216.
 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
 M. Nowak and R. May, “Evolutionary Games and Spatial Chaos,” Nature, Vol. 359, No. 6398, 1992, pp. 826-829.
 R. Southwell, J. Huang and B. Shou, “Modelling Frequency Allocation with Generalized Spatial Congestion Games,” IEEE ICCS, 2012.
 R. Southwell and J. Huang, “Convergence Dynamics of Resource-Homogeneous Congestion Games,” GameNets, 2011.
 R. Southwell, Y. Chen, J. Huang and Q. Zhang, “Convergence Dynamics of Graphical Congestion Games,” Springer, Berlin, Heidelberg, 2012, pp. 31-46.
 R. Southwell, X. Chen and J. Huang, “Quality of Service Satisfaction Games for Spectrum Sharing,” IEEE INFOCOM—Mini Conference, 2013.
 R. Southwell and C. Cannings, “Games on Graphs That Grow Deterministically,” GameNets, 2009, pp. 347-356.
 R. Southwell and C. Cannings, “Some Models of Reproducing Graphs: I Pure Reproduction,” Applied Mathematics, Vol. 1, No. 3, 2010, pp. 137-145.
 R. Southwell and J. Huang, “Complex Networks from Simple Rewrite Systems,” arXiv Preprint arXiv:1205. 0596, 2012.
 R. Southwell and C. Cannings, “Exploring the Space of Substitution Systems,” Complex Systems, 2013.
 R. Southwell and C. Cannings, “Some Models of Reproducing Graphs: III Game Based Reproduction,” Applied Mathematics, Vol. 1, No. 5, 2010, pp. 335-343.
 R. Southwell and C. Cannings, “Some Models of Reproducing Graphs: Ii Age Capped Vertices,” Applied Mathematics, Vol. 1, No. 4, 2010, pp. 251-259.
 S. Berninghaus and U. Schwable, “Conventions, Local Interaction, and Automata Networks,” Evolutionary Economics, Vol. 6, No. 3, 1996, pp. 297-312.
 S. Berninghaus and U. Schwable, “Evolution, Interaction, and Nash Equilibria,” Journal of Economic Behavior and Organization, Vol. 29, No. 1, 1996, pp. 57-85.
 C. Cannings, “The Majority Game on Regular and Random Networks,” GameNets, 2009, pp. 1-16.
 S. Wolfram, “A New Kind of Science,” Wolfram Media, 2002.
 P. Kurka, “Topological and Symbolic Dynamics,” Societe Mathematique de France, 2003.