×

zbMATH — the first resource for mathematics

How mutation affects evolutionary games on graphs. (English) Zbl 1337.91016
Summary: Evolutionary dynamics are affected by population structure, mutation rates and update rules. Spatial or network structure facilitates the clustering of strategies, which represents a mechanism for the evolution of cooperation. Mutation dilutes this effect. Here we analyze how mutation influences evolutionary clustering on graphs. We introduce new mathematical methods to evolutionary game theory, specifically the analysis of coalescing random walks via generating functions. These techniques allow us to derive exact identity-by-descent (IBD) probabilities, which characterize spatial assortment on lattices and Cayley trees. From these IBD probabilities we obtain exact conditions for the evolution of cooperation and other game strategies, showing the dual effects of graph topology and mutation rate. High mutation rates diminish the clustering of cooperators, hindering their evolutionary success. Our model can represent either genetic evolution with mutation, or social imitation processes with random strategy exploration.

MSC:
91A22 Evolutionary games
91A43 Games involving graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Antal, T.; Ohtsuki, H.; Wakeley, J.; Taylor, P.D.; Nowak, M.A., Evolution of cooperation by phenotypic similarity, Proc. natl. acad. sci. USA, 106, 21, 8597, (2009) · Zbl 1355.92145
[2] Beineke, L.W.; Wilson, R.J., Topics in algebraic graph theory, (2004), Cambridge University Press Cambridge, UK · Zbl 1052.05003
[3] Berestycki, N., Recent progress in coalescent theory, Ensaios mate., 16, 1-193, (2009) · Zbl 1204.60002
[4] Bonsall, M.B.; French, D.R.; Hassell, M.P., Metapopulation structures affect persistence of predator – prey interactions, J. anim. ecol., 71, 6, 1075-1084, (2002)
[5] Boots, M.; Sasaki, A., ‘small worlds’ and the evolution of virulence: infection occurs locally and at a distance, Proc. R. soc. B, 266, 1432, 1933, (1999)
[6] Cox, J.T., Coalescing random walks and voter model consensus times on the torus in \(\mathbb{Z}^d\), Ann. prob., 17, 4, 1333-1366, (1989) · Zbl 0685.60100
[7] Cox, J.T.; Durrett, R., The stepping stone model: new formulas expose old myths, Ann. appl. prob., 12, 4, 1348-1377, (2002) · Zbl 1016.60089
[8] Durrett, R., Stochastic spatial models, (), 39-94 · Zbl 1002.92565
[9] Fehl, K., van der Post, D.J., Semmann, D. Co-evolution of behavior and social network structure promotes human cooperation. Ecol. Lett., in press.
[10] Fu, F.; Chen, X.; Liu, L.; Wang, L., Social dilemmas in an online social network: the structure and evolution of cooperation, Phys. lett. A, 371, 1-2, 58-64, (2007) · Zbl 1209.91143
[11] Fu, F.; Hauert, C.; Nowak, M.A.; Wang, L., Reputation-based partner choice promotes cooperation in social networks, Phys. rev. E, 78, 2, 026117, (2008)
[12] Gilpin, M.E., Group selection in predator – prey communities, (1975), Princeton University Press Princeton, NJ, USA
[13] Grafen, A., An inclusive fitness analysis of altruism on a cyclical network, J. evol. biol., 20, 6, 2278-2283, (2007)
[14] Grafen, A.; Archetti, M., Natural selection of altruism in inelastic viscous homogeneous populations, J. theor. biol., 252, 4, 694-710, (2008)
[15] Granovsky, B.L.; Madras, N., The noisy voter model, Stochas. process. appl., 55, 1, 23-43, (1995) · Zbl 0813.60096
[16] Hassell, M.P.; Comins, H.N.; May, R.M., Species coexistence and self-organizing spatial dynamics, Nature, 370, 6487, 290-292, (1994)
[17] Helbing, D.; Yu, W., The outbreak of cooperation among success-driven individuals under noisy conditions, Proc. natl. acad. sci., 106, 10, 3680-3685, (2009)
[18] Holme, P.; Trusina, A.; Kim, B.; Minnhagen, P., Prisoners’ dilemma in real-world acquaintance networks: spikes and quasiequilibria induced by the interplay between structure and dynamics, Phys. rev. E, 68, 3, 30901, (2003)
[19] Iwasa, Y., Lattice models and pair approximation in ecology, (), 227-251
[20] Killingback, T., Doebeli, M., 1996. Spatial evolutionary game theory: Hawks and Doves revisited. Proc. R. Soc. B, pp. 1135-1144.
[21] Kimura, M.; Weiss, G.H., The stepping stone model of population structure and the decrease of genetic correlation with distance, Genetics, 49, 4, 561, (1964)
[22] Kingman, J.F.C., The coalescent, Stochast. process. appl., 13, 3, 235-248, (1982) · Zbl 0491.60076
[23] Lawler, G.F.; Limic, V., Random walk: A modern introduction, (2010), Cambridge University Press Cambridge, UK · Zbl 1210.60002
[24] Le Galliard, J.F.; Ferrière, R.; Dieckmann, U.; Tonsor, S., The adaptive dynamics of altruism in spatially heterogeneous populations, Evolution, 57, 1, 1-17, (2003)
[25] Lieberman, E.; Hauert, C.; Nowak, M.A., Evolutionary dynamics on graphs, Nature, 433, 7023, 312-316, (2005)
[26] Malécot, G., The decrease of relationship with distance, In: cold spring harbor symposium on quantitative biology, 20, 52-53, (1955)
[27] Matsuda, H.; Ogita, N.; Sasaki, A.; Sato, K., Statistical mechanics of population, Prog. theor. phys., 88, 6, 1035-1049, (1992)
[28] Mitteldorf, J.; Wilson, D.S., Population viscosity and the evolution of altruism, J. theor. biol., 204, 4, 481-496, (2000)
[29] Montroll, E.W.; Weiss, G.H., Random walks on lattices: II, J. math. phys., 6, 167, (1965) · Zbl 1342.60067
[30] Nakamaru, M.; Matsuda, H.; Iwasa, Y., The evolution of cooperation in a lattice-structured population, J. theor. biol., 184, 1, 65-81, (1997)
[31] Nowak, M.; Sasaki, A.; Taylor, C.; Fudenberg, D., Emergence of cooperation and evolutionary stability in finite populations, Nature, 428, 6983, 646-650, (2004)
[32] Nowak, M.A., Five rules for the evolution of cooperation, Science, 314, 5805, 1560-1563, (2006)
[33] Nowak, M.A.; May, R.M., Evolutionary games and spatial chaos, Nature, 359, 6398, 826-829, (1992)
[34] Nowak, M.A.; Tarnita, C.E.; Antal, T., Evolutionary dynamics in structured populations, Philos. trans. R. soc. B: biol. sci., 365, 1537, 19, (2010)
[35] Nowak, M.A.; Tarnita, C.E.; Wilson, E.O., The evolution of eusociality, Nature, 466, 7310, 1057-1062, (2010)
[36] Ohtsuki, H.; Hauert, C.; Lieberman, E.; Nowak, M.A., A simple rule for the evolution of cooperation on graphs and social networks, Nature, 441, 502-505, (2006)
[37] Ohtsuki, H.; Nowak, M.A., Evolutionary stability on graphs, J. theor. biol., 251, 4, 698-707, (2008)
[38] Pacheco, J.M.; Traulsen, A.; Nowak, M.A., Coevolution of strategy and structure in complex networks with dynamical linking, Phys. rev. lett., 97, 25, 258103, (2006)
[39] Perc, M.; Szolnoki, A., Social diversity and promotion of cooperation in the spatial Prisoner’s dilemma game, Phys. rev. E, 77, 1, 11904, (2008)
[40] Perc, M.; Szolnoki, A., Coevolutionary games—a mini review, Biosystems, 99, 2, 109-125, (2010)
[41] Rauch, E.M.; Bar-Yam, Y., Theory predicts the uneven distribution of genetic diversity within species, Nature, 431, 7007, 449-452, (2004)
[42] Roca, C.P.; Cuesta, J.A.; Sánchez, A., Effect of spatial structure on the evolution of cooperation, Phys. rev. E, 80, 4, 046106, (2009)
[43] Roca, C.P.; Cuesta, J.A.; Sánchez, A., Evolutionary game theory: temporal and spatial effects beyond replicator dynamics, Phys. life rev., 6, 4, 208-249, (2009)
[44] Rousset, F., Genetic structure and selection in subdivided populations, (2004), Princeton University Press Princeton, NJ, USA
[45] Santos, F.C.; Pacheco, J.M., Scale-free networks provide a unifying framework for the emergence of cooperation, Phys. rev. lett., 95, 9, 98104, (2005)
[46] Santos, F.C.; Santos, M.D.; Pacheco, J.M., Social diversity promotes the emergence of cooperation in public goods games, Nature, 454, 7201, 213-216, (2008)
[47] Seshadri, G., 2007. Consanguinity on weighted digraphs. Undergraduate Thesis, Harvard University.
[48] Shore, T.R., Tyler, D.B., 1993. Recurrence of simple random walk in the plane. American Mathematical Monthly, pp. 144-149. · Zbl 0793.60081
[49] Szabó, G.; Fáth, G., Evolutionary games on graphs, Phys. rep., 446, 4-6, 97-216, (2007)
[50] Tarnita, C.E.; Antal, T.; Ohtsuki, H.; Nowak, M.A., Evolutionary dynamics in set structured populations, Proc. natl. acad. sci. USA, 106, 21, 8601, (2009)
[51] Tarnita, C.E.; Ohtsuki, H.; Antal, T.; Fu, F.; Nowak, M.A., Strategy selection in structured populations, J. theor. biol., 259, 3, 570-581, (2009)
[52] Taylor, P.D.; Day, T.; Wild, G., Evolution of cooperation in a finite homogeneous graph, Nature, 447, 7143, 469-472, (2007)
[53] Taylor, P.D.; Frank, S.A., How to make a kin selection model, J. theor. biol., 180, 1, 27-37, (1996)
[54] Traulsen, A.; Hauert, C.; De Silva, H.; Nowak, M.A.; Sigmund, K., Exploration dynamics in evolutionary games, Proc. natl. acad. sci. USA, 106, 3, 709, (2009) · Zbl 1202.91029
[55] Traulsen, A.; Semmann, D.; Sommerfeld, R.; Krambeck, H.; Milinski, M., Human strategy updating in evolutionary games, Proc. natl. acad. sci. USA, 107, 7, 2962, (2010)
[56] Traulsen, A.; Shoresh, N.; Nowak, M.A., Analytical results for individual and group selection of any intensity, Bull. math. biol., 70, 5, 1410-1424, (2008) · Zbl 1144.92035
[57] van Baalen, M.; Rand, D.A., The unit of selection in viscous populations and the evolution of altruism, J. theor. biol., 193, 4, 631-648, (1998)
[58] Wakeley, J., Coalescent theory: an introduction, (2009), Roberts & Co Greenwood Village, CO · Zbl 1366.92001
[59] Woess, W., 2009. Denumerable Markov chains: generating functions, boundary theory, random walks on trees. European Mathematical Society, Zurich, Switzerland. · Zbl 1219.60001
[60] Wu, B.; Altrock, P.M.; Wang, L.; Traulsen, A., Universality of weak selection, Phys. rev. E, 82, 4, 046106, (2010)
[61] Wu, B.; Zhou, D.; Fu, F.; Luo, Q.; Wang, L.; Traulsen, A., Evolution of cooperation on stochastic dynamical networks, Plos one, 5, 6, e11187, (2010)
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.