Games on graphs.

*(English)*Zbl 1303.91040This paper offers an excellent survey over recent developments in the field of evolutionary game theory on graphs. Though the paper has been written from a biological perspective and thus includes some terms (neutral drift, fixation probability) with which non-biologists may be unfamiliar, it is accessible to readers from other sciences. An understanding of the paper requires some analytical familiarity with the mathematical tools used (such as pair approximation), but does not necessitate a previous knowledge of the literature.

The paper determines the conditions for long-term equilibria for symmetric \(2 \times 2\) games on finite and weighted graphs under the condition of weak selection, for the following updating rules: birth-death (BD), death-birth (DB), pairwise-comparison (PC), imitation (IM), birth-death with payoff affecting death (BD-D), and death-birth with payoff affecting death (DB-D).

For the simplified prisoner’s dilemma (CC: \(b-c\); CD: \(-c\); DC: \(b\); and DD: \(0\)), and BD, PC, and DB-D updating, cooperation is only favored if and only if self-interaction occurs and grants a payoff exceeding the cost \(c\). In the case of DB and BD-D updating, the cooperative equilibrium does not require self-interaction and will prevail in the long-run (i.e. to cooperate has a higher fixation rate) if the condition \(b/c>\kappa\) is met, with \(\kappa\) being the Simpson degree.

The paper also extends results to nonzero mutation rates for BD and DB updating, as well as for cases in which the replacement graph and interaction graph of a game are not identical. At the end, the paper generally and shortly discusses asymmetric games, games with more than two players or strategies, and graphs with an endogenous topology but does not provide explicit results for these cases.

The paper determines the conditions for long-term equilibria for symmetric \(2 \times 2\) games on finite and weighted graphs under the condition of weak selection, for the following updating rules: birth-death (BD), death-birth (DB), pairwise-comparison (PC), imitation (IM), birth-death with payoff affecting death (BD-D), and death-birth with payoff affecting death (DB-D).

For the simplified prisoner’s dilemma (CC: \(b-c\); CD: \(-c\); DC: \(b\); and DD: \(0\)), and BD, PC, and DB-D updating, cooperation is only favored if and only if self-interaction occurs and grants a payoff exceeding the cost \(c\). In the case of DB and BD-D updating, the cooperative equilibrium does not require self-interaction and will prevail in the long-run (i.e. to cooperate has a higher fixation rate) if the condition \(b/c>\kappa\) is met, with \(\kappa\) being the Simpson degree.

The paper also extends results to nonzero mutation rates for BD and DB updating, as well as for cases in which the replacement graph and interaction graph of a game are not identical. At the end, the paper generally and shortly discusses asymmetric games, games with more than two players or strategies, and graphs with an endogenous topology but does not provide explicit results for these cases.

Reviewer: Sebastian Ille (Pisa)

##### MSC:

91A22 | Evolutionary games |

91A43 | Games involving graphs |

60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |

05C57 | Games on graphs (graph-theoretic aspects) |

91A05 | 2-person games |

##### Keywords:

evolutionary game theory on graphs; symmetric \(2 \times 2\) games; finite and weighted graphs; updating rules; cooperation
PDF
BibTeX
XML
Cite

\textit{B. Allen} and \textit{M. A. Nowak}, EMS Surv. Math. Sci. 1, No. 1, 113--151 (2014; Zbl 1303.91040)

Full Text:
DOI

##### References:

[1] | R. Albert and A.-L. Barabási, Statistical mechanics of complex networks. Rev. Modern Phys. 74 (2002), 47-97. · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47 · arxiv:cond-mat/0106096 |

[2] | B. Allen, J. Gore, and M. A. Nowak, Spatial dilemmas of diffusible public goods. eLife 2 (2013). · doi:10.7554/eLife.01169 |

[3] | B. Allen and M. A. Nowak, Evolutionary shift dynamics on a cycle. J. Theoret. Biol. 311 (2012), 28-39. · Zbl 1337.92166 |

[4] | B. Allen and C. E. Tarnita, Measures of success in a class of evolutionary models with fixed population size and structure. J. Math. Biol. 68 (2014), 109-143. · Zbl 1280.92045 · doi:10.1007/s00285-012-0622-x |

[5] | B. Allen, A. Traulsen, C. E. Tarnita, and M. A. Nowak, How mutation affects evolutionary games on graphs. J. Theoret. Biol. 299 (2012), 97-105. · Zbl 1337.91016 |

[6] | T. Antal, H. Ohtsuki, J. Wakeley, P. D. Taylor, and M. A. Nowak, Evolution of coop- eration by phenotypic similarity. Proc. Nat. Acad. Sci. U.S.A. 106 (2009), 8597-8600. · Zbl 1355.92145 · doi:10.1073/pnas.0902528106 |

[7] | S. Assenza, J. Gómez-Gardeñes, and V. Latora, Enhancement of cooperation in highly clustered scale-free networks. Phys. Rev. E 78 (2008), 017101. · doi:10.1103/PhysRevE.78.017101 |

[8] | R. Axelrod and W. D. Hamilton, The evolution of cooperation. Science 211 (1981), 1390-1396. · Zbl 1225.92037 · doi:10.1126/science.7466396 |

[9] | M. van Baalen and D. A. Rand, The unit of selection in viscous populations and the evolution of altruism. J. Theoret. Biol. 193 (1998), 631-648. · doi:10.1006/jtbi.1998.0730 |

[10] | D. B. Borenstein, Y. Meir, J. W. Shaevitz, and N. S. Wingreen, Non-local interaction via diffusible resource prevents coexistence of cooperators and cheaters in a lattice model. PloS ONE 8 (2013), e63304. |

[11] | M. Broom, C. Hadjichrysanthou, and J. Rychtár, Evolutionary games on graphs and the speed of the evolutionary process. Proc. Roy. Soc. London Ser. A 466 (2010), 1327-1346. · Zbl 1202.91027 · doi:10.1098/rspa.2009.0487 |

[12] | M. Broom and J. Rychtá\check r, Game-theoretical models in biology . Chapman & Hall/CRC Math. Comput. Biol. Ser., CRC Press, Boca Raton, FL, 2013. · Zbl 1264.92002 |

[13] | M. Cavaliere, S. Sedwards, C. E. Tarnita, M. A. Nowak, and A. Csikász-Nagy, Prosperity is associated with instability in dynamical networks. J. Theoret. Biol. 299 (2012), 126-138. · Zbl 1337.91018 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.