EMS Surveys in Mathematical Sciences
Full-Text PDF (397 KB) | Metadata | Table of Contents | EMSS summary
Games on graphsBenjamin Allen and Martin A. Nowak (1) Program for Evolutionary Dynamics, Harvard University, One Brattle Square, suite 6, MA 02138-3758, Cambridge, USA
Evolution occurs in populations of reproducing individuals. The trajectories and outcomes of evolutionary processes depend on the structure of the population. Evolutionary graph theory is a powerful approach to studying the consequences of spatial or social population structure. The vertices of the graph represent individuals. The edges determine who interacts with whom for game payoff and who competes with whom for reproduction. Interaction and competition can be governed by the same graph or by two different graphs. In this paper, we review the basic approach for evolutionary games on graphs and provide new proofs for key results. We formalize the method of identity by descent to derive conditions for strategy selection on finite, weighted graphs. We generalize our results to nonzero mutation rates, and to the case where the interaction and competition graphs do not coincide. We conclude with a perspective of open problems and future directions.
Keywords: Game theory, graph theory, evolution, Markov chain, cooperation
Allen Benjamin, Nowak Martin: Games on graphs. EMS Surv. Math. Sci. 1 (2014), 113-151. doi: 10.4171/EMSS/3