EMS Surveys in Mathematical Sciences


Full-Text PDF (397 KB) | Metadata | Table of Contents | EMSS summary
Volume 1, Issue 1, 2014, pp. 113–151free sample!
DOI: 10.4171/EMSS/3

Games on graphs

Benjamin Allen and Martin A. Nowak[1]

(1) Program for Evolutionary Dynamics, Harvard University, One Brattle Square, suite 6, MA 02138-3758, CAMBRIDGE, UNITED STATES

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