×

Persistent homology and the shape of evolutionary games. (English) Zbl 1471.91039

Summary: For nearly three decades, spatial games have produced a wealth of insights to the study of behavior and its relation to population structure. However, as different rules and factors are added or altered, the dynamics of spatial models often become increasingly complicated to interpret. To tackle this problem, we introduce persistent homology as a rigorous framework that can be used to both define and compute higher-order features of data in a manner which is invariant to parameter choices, robust to noise, and independent of human observation. Our work demonstrates its relevance for spatial games by showing how topological features of simulation data that persist over different spatial scales reflect the stability of strategies in 2D lattice games. To do so, we analyze the persistent homology of scenarios from two games: a prisoner’s dilemma and a SIRS epidemic model. The experimental results show how the method accurately detects features that correspond to real aspects of the game dynamics. Unlike other tools that study dynamics of spatial systems, persistent homology can tell us something meaningful about population structure while remaining neutral about the underlying structure itself. Regardless of game complexity, since strategies either succeed or fail to conform to shapes of a certain topology there is much potential for the method to provide novel insights for a wide variety of spatially extended systems in biology, social science, and physics.

MSC:

91A22 Evolutionary games
55N31 Persistent homology and applications, topological data analysis
92D30 Epidemiology
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agapie, A.; Andreica, A.; Giuclea, M., Probabilistic cellular automata, J. Comput. Biol., 21, 699-708 (2014)
[2] Ai, S.; Albashaireh, R., Traveling waves in spatial sirs models, J. Dyn. Differ. Equ., 26, 143-164 (2014) · Zbl 1293.35069
[3] Alexander, J.; Skyrms, B., Bargaining with neighbors: Is justice contagious?, J. Philos., 96, 588-598 (1999)
[4] Alexander, J. M., The Stanford Encyclopedia of Philosophy, (Zalta, E. N., Evolutionary Game Theory (2019), Metaphysics Research Lab, Stanford University)
[5] Almgren, K.; Kim, M.; Lee, J., Extracting knowledge from the geometric shape of social network data using topological data analysis, Entropy, 19, 360 (2017)
[6] Antonovsky, M., Ter-Mikhaelian, M., Furyaev, V., 1989. A Spatial Model of Long-Term Forest Fire Dynamics and Its Application to Forests in Western Siberia. IIASA Working Paper. IIASA, Laxenburg, Austria. URL: http://pure.iiasa.ac.at/id/eprint/3235/.
[7] Axelrod, R.; Axelrod, R., The Evolution of Cooperation (1984), Basic books
[8] van Ballegooijen, W.M., Boerlijst, M.C., 2004. Emergent trade-offs and selection for outbreak frequency in spatial epidemics. Proceedings of the National Academy of Sciences of the United States of America 101, 18246-18250. URL: https://pubmed.ncbi.nlm.nih.gov/15604150, doi: 10.1073/pnas.0405682101.
[9] Bauer, U., 2019. Ripser: efficient computation of vietoris-rips persistence barcodes. arXiv:1908.02518. preprint. · Zbl 1476.55012
[10] Bishop, D. T.; Cannings, C.; Smith, J. M., The war of attrition with random rewards, J. Theor. Biol., 74, 377-388 (1978)
[11] Bonilla, L. L.; Carpio, A.; Trenado, C., Tracking collective cell motion by topological data analysis, PLOS Comput. Biol., 16, Article e1008407 pp. (2020)
[12] Bos, N.; Shami, N. S.; Olson, J. S.; Cheshin, A.; Nan, N., In-group/out-group effects in distributed teams: An experimental simulation, (Proceedings of the 2004 ACM Conference on Computer Supported Cooperative Work (2004), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 429-436
[13] Cámara, P. G.; Levine, A. J.; Rabadán, R., Inference of ancestral recombination graphs through topological data analysis, PLOS Comput. Biol., 12, 1-25 (2016)
[14] Cameron, D. D.; White, A.; Antonovics, J., Parasite-grass-forb interactions and rock-paper– scissor dynamics: predicting the effects of the parasitic plant rhinanthus minor on host plant communities, J. Ecol., 97, 1311-1319 (2009)
[15] Carlsson, G., Topology and data, Bull. Am. Math. Soc., 46, 255-308 (2009) · Zbl 1172.62002
[16] Cason, T. N.; Friedman, D.; Hopkins, E., Testing the tasp: An experimental investigation of learning in games with unstable equilibria, J. Econ. Theory, 145, 2309-2331 (2010) · Zbl 1203.91049
[17] Caswell, H.; Cohen, J. E., Communities in patchy environments: a model of disturbance, competition, and heterogeneity, (Ecological Heterogeneity (1991), Springer), 97-122
[18] Chan, J. M.; Carlsson, G.; Rabadan, R., Topology of viral evolution, Proc. Natl. Acad. Sci., 110, 18566-18571 (2013) · Zbl 1292.92014
[19] Chen, X.; Szolnoki, A.; Perc, M., Probabilistic sharing solves the problem of costly punishment, New J. Phys., 16, Article 083016 pp. (2014)
[20] Crawford, L.; Monod, A.; Chen, A. X.; Mukherjee, S.; Rabadán, R., Predicting clinical outcomes in glioblastoma: An application of topological and functional data analysis, J. Am. Stat. Assoc., 115, 1139-1150 (2020) · Zbl 1441.62316
[21] Cressman, R.; Vickers, G., Spatial and density effects in evolutionary game theory, J. Theor. Biol., 184, 359-369 (1997)
[22] van Damme, E., Evolutionary game theory, Eur. Econ. Rev., 38, 847-858 (1994)
[23] DeForest, R.; Belmonte, A., Spatial pattern dynamics due to the fitness gradient flux in evolutionary games, Phys. Rev. E, 87, Article 062138 pp. (2013)
[24] DeWoskin, D.; Climent, J.; Cruz-White, I.; Vazquez, M.; Park, C.; Arsuaga, J., Applications of computational homology to the analysis of treatment response in breast cancer patients, Topol. Appl., 157, 157-164 (2010) · Zbl 1176.92026
[25] Durrett, R., Stochastic spatial models, SIAM Rev., 41, 677-718 (1999) · Zbl 0940.60086
[26] Durrett, R.; Levin, S., The importance of being discrete (and spatial), Theor. Popul. Biol., 46, 363-394 (1994) · Zbl 0846.92027
[27] Durrett, R., Ma, R., 2018. A heterogeneous spatial model in which savanna and forest coexist in a stable equilibrium. arXiv preprint arXiv:1808.08159.
[28] Edelsbrunner, Letscher, Zomorodian, 2002. Topological persistence and simplification. Discr. Comput. Geom. 28, 511-533. doi: 10.1007/s00454-002-2885-2. · Zbl 1011.68152
[29] Edelsbrunner, H.; Harer, J., Computational Topology: An Introduction (2010), American Mathematical Soc · Zbl 1193.55001
[30] Edelsbrunner, H.; Morozov, D., Persistent homology: theory and practice, Eur. Congr. Math., 31-50 (2014) · Zbl 1364.55008
[31] Emmett, K.; Schweinhart, B.; Rabadan, R., Multiscale topology of chromatin folding, (Proceedings of the 9th EAI International Conference on Bio-Inspired Information and Communications Technologies (Formerly BIONETICS), ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) Brussels, BEL (2016)), 177-180
[32] Friedman, D., Evolutionary games in economics, Econometrica, 59, 637-666 (1991) · Zbl 0745.90012
[33] Gameiro, M.; Hiraoka, Y.; Izumi, S.; Kramár, M.; Mischaikow, K.; Nanda, V., A topological measurement of protein compressibility, Jpn. J. Ind. Appl. Math., 32, 1-17 (2015) · Zbl 1320.55004
[34] Gan, Q.; Xu, R.; Yang, P., Travelling waves of a delayed sirs epidemic model with spatial diffusion, Nonlinear Anal. Real World Appl., 12, 52-68 (2011) · Zbl 1202.35046
[35] Ghrist, R., Barcodes: The persistent topology of data, Bull. Am. Math. Soc., 45 (2008) · Zbl 1391.55005
[36] Goeree, J. K.; Holt, C. A., Stochastic game theory: For playing games, not just for doing theory, Proc. Natl. Acad. Sci., 96, 10564-10567 (1999) · Zbl 0962.91008
[37] Green, J. B.; Sharpe, J., Positional information and reaction-diffusion: two big ideas in developmental biology combine, Development, 142, 1203-1211 (2015)
[38] Grim, P., Spatialization and greater generosity in the stochastic prisoner’s dilemma, Biosystems, 37, 3-17 (1996)
[39] Gutowitz, H. A.; Victor, J. D.; Knight, B. W., Local structure theory for cellular automata, Phys. D, 28, 18-48 (1987) · Zbl 0634.92022
[40] Hanski, I., Single-species metapopulation dynamics: concepts, models and observations, Biol. J. Linnean Soc., 42, 17-38 (1991)
[41] Hassell, M. P.; Comins, H. N.; Mayt, R. M., Spatial structure and chaos in insect population dynamics, Nature, 353, 255-258 (1991)
[42] Hauert, C., Fundamental clusters in spatial \(2 \times 2\) games, Proc. R. Soc. London. Ser. B: Biol. Sci., 268, 761-769 (2001)
[43] Hauert, C., Spatial effects in social dilemmas, J. Theor. Biol., 240, 627-636 (2006) · Zbl 1447.92517
[44] Hauert, C.; Doebeli, M., Spatial structure often inhibits the evolution of cooperation in the snowdrift game, Nature, 428, 643-646 (2004)
[45] Hauert, C.; Szabo, G., Prisoner’s dilemma and public goods games in different geometries: Compulsory versus voluntary interactions, Complexity, 8, 31-38 (2003)
[46] Helbing, D., Pattern formation, social forces, and diffusion instability in games with success-driven motion, Eur. Phys. J. B, 67, 345-356 (2009) · Zbl 1188.91035
[47] Helbing, D.; Szolnoki, A.; Perc, M.; Szabó, G., Punish, but not too hard: how costly punishment spreads in the spatial public goods game, New J. Phys., 12, Article 083005 pp. (2010)
[48] Hiebeler, D., Stochastic spatial models: From simulations to mean field and local structure approximations, J. Theor. Biol., 187, 307-319 (1997)
[49] Hiraoka, Y.; Nakamura, T.; Hirata, A.; Escolar, E. G.; Matsue, K.; Nishiura, Y., Hierarchical structures of amorphous solids characterized by persistent homology, Proc. Natl. Acad. Sci., 113, 7035-7040 (2016)
[50] Hoffman, M.; Suetens, S.; Gneezy, U.; Nowak, M. A., An experimental investigation of evolutionary dynamics in the rock-paper-scissors game, Sci. Rep., 5, 8817 (2015)
[51] Holt, C. A.; Roth, A. E., The nash equilibrium: A perspective, Proc. Natl. Acad. Sci., 101, 3999-4002 (2004) · Zbl 1064.01017
[52] Hwang, S. H.; Katsoulakis, M.; Rey-Bellet, L., Deterministic equations for stochastic spatial evolutionary games, Theor. Econ., 8, 829-874 (2013) · Zbl 1395.91052
[53] Khasawneh, F. A.; Munch, E., Stability determination in turning using persistent homology and time series analysis, in, (Proceedings of the ASME 2014 International Mechanical Engineering Congress and Exposition (2014))
[54] Killingback, T.; Bieri, J.; Flatt, T., Evolution in group-structured populations can resolve the tragedy of the commons, Proc. Biol. Sci., 273, 1477-1481 (2006)
[55] Killingback, T.; Doebeli, M.; Knowlton, N., Variable investment, the continuous prisoner’s dilemma, and the origin of cooperation, Proc. Biol. Sci., 266, 1723-1728 (1999)
[56] Kondo, S.; Miura, T., Reaction-diffusion model as a framework for understanding biological pattern formation, Science, 329, 1616-1620 (2010) · Zbl 1226.35077
[57] Kovacev-Nikolic, V.; Bubenik, P.; Nikolić, D.; Heo, G., Using persistent homology and dynamical distances to analyze protein binding, Stat. Appl. Genet. Mol. Biol., 15, 19-38 (2016) · Zbl 1343.92380
[58] Kriegel, H. P.; Kröger, P.; Sander, J.; Zimek, A., Density-based clustering, Wiley Interdisc. Rew.: Data Min. Knowl. Discovery, 1, 231-240 (2011)
[59] Landge, A. N.; Jordan, B. M.; Diego, X.; Müller, P., Pattern formation mechanisms of self-organizing reaction-diffusion systems, Develop. Biol., 460, 2-11 (2020), (systems Biology of Pattern Formation)
[60] Levin, S. A.; Paine, R. T., Disturbance, patch formation, and community structure, Proc. Natl. Acad. Sci., 71, 2744-2747 (1974) · Zbl 0289.92008
[61] Li, M.; Duncan, K.; Topp, C.; Chitwood, D., Persistent homology and the branching topologies of plants, Am. J. Botany, 104 (2017)
[62] Li, R. H.; Yu, J. X.; Lin, J., Evolution of cooperation in spatial traveler’s dilemma game, PLOS ONE, 8, 1-11 (2013)
[63] Li, T.; Li, Y.; Hethcote, H. W., Periodic traveling waves in sirs endemic models, Math. Comput. Model., 49, 393-401 (2009) · Zbl 1165.35311
[64] Lieberman, E.; Hauert, C.; Nowak, M. A., Evolutionary dynamics on graphs, Nature, 433, 312-316 (2005)
[65] Lindgren, K.; Nordahl, M. G., Evolutionary dynamics of spatial games, Physica D: Nonlinear Phenom., 75, 292-309 (1994) · Zbl 0860.90139
[66] Masuda, N.; Aihara, K., Spatial prisoner’s dilemma optimally played in small-world networks, Phys. Lett. A, 313, 55-61 (2003) · Zbl 1098.91566
[67] Mathiesen, J.; Mitarai, N.; Sneppen, K.; Trusina, A., Ecosystems with mutually exclusive interactions self-organize to a state of high diversity, Phys. Rev. Lett., 107, Article 188101 pp. (2011)
[68] May, R. M.; Leonard, W. J., Nonlinear aspects of competition between three species, SIAM J. Appl. Math., 29, 243-253 (1975) · Zbl 0314.92008
[69] McGuirl, M. R.; Volkening, A.; Sandstede, B., Topological data analysis of zebrafish patterns, Proc. Natl. Acad. Sci., 117, 5113-5124 (2020) · Zbl 1456.92004
[70] Meloni, S.; Buscarino, A.; Fortuna, L.; Frasca, M.; Gómez-Gardeñes, J.; Latora, V.; Moreno, Y., Effects of mobility in a population of prisoner’s dilemma players, Phys. Rev. E, 79, Article 067101 pp. (2009)
[71] Moyano, L. G.; Sánchez, A., Evolving learning rules and emergence of cooperation in spatial prisoner’s dilemma, J. Theor. Biol., 259, 84-95 (2009) · Zbl 1402.91052
[72] Nash, J. F., Equilibrium points in n-person games, Proc. Natl. Acad. Sci., 36, 48-49 (1950) · Zbl 0036.01104
[73] Neill, D. B., Evolutionary stability for large populations, J. Theor. Biol., 227, 397-401 (2004), URL: https://www.sciencedirect.com/science/article/pii/S0022519303004363 · Zbl 1434.92023
[74] Nicolau, M.; Levine, A. J.; Carlsson, G., Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival, Proc. Natl. Acad. Sci., 108, 7265-7270 (2011)
[75] Nowak, M., Stochastic strategies in the prisoner’s dilemma, Theor. Popul. Biol., 38, 93-112 (1990) · Zbl 0726.92015
[76] Nowak, M.; May, R., The spatial dilemma of evolution, Int. J. Bifur. Chaos - IJBC, 3 (1993) · Zbl 0870.92011
[77] Nowak, M. A.; Bonhoeffer, S.; May, R. M., More spatial games, Int. J. Bifur. Chaos, 4, 33-56 (1994) · Zbl 0884.90147
[78] Nowak, M. A.; May, R. M., Evolutionary games and spatial chaos, Nature, 359, 826-829 (1992)
[79] Nowak, M. A.; Sasaki, A.; Taylor, C.; Fudenberg, D., Emergence of cooperation and evolutionary stability in finite populations, Nature, 428, 646-650 (2004), URL: https://doi.org/10.1038/nature02414
[80] Otter, N.; Porter, M. A.; Tillmann, U.; Grindrod, P.; Harrington, H. A., A roadmap for the computation of persistent homology, EPJ Data Sci., 6, 17 (2017)
[81] Parisi, G., Statistical Field Theory (1988), Addison-Wesley · Zbl 0984.81515
[82] Perc, M.; Jordan, J. J.; Rand, D. G.; Wang, Z.; Boccaletti, S.; Szolnoki, A., Statistical physics of human cooperation, Phys. Rep., 687, 1-51 (2017), (statistical physics of human cooperation) · Zbl 1366.80006
[83] Perc, M.; Szolnoki, A., Coevolutionary games—a mini review, Bio Syst., 99, 109-125 (2009)
[84] Perc, M.c.v., Szolnoki, A., 2008. Social diversity and promotion of cooperation in the spatial prisoner’s dilemma game. Phys. Rev. E 77, 011904. doi: 10.1103/PhysRevE.77.011904. · Zbl 1189.91034
[85] Pereira, C. M.; de Mello, R. F., Persistent homology for time series and spatial data clustering, Expert Syst. Appl., 42, 6026-6038 (2015)
[86] Reichenbach, T.; Mobilia, M.; Frey, E., Mobility promotes and jeopardizes biodiversity in rock-paper-scissors games, Nature, 448, 1046-1049 (2007)
[87] Rizvi, A. H.; Camara, P. G.; Kandror, E. K.; Roberts, T. J.; Schieren, I.; Maniatis, T.; Rabadan, R., Single-cell topological rna-seq analysis reveals insights into cellular differentiation and development, Nat. Biotechnol., 35, 551-560 (2017)
[88] Samuelson, L., Evolutionary Games and Equilibrium Selection, vol. 1 (1997), MIT press · Zbl 0953.91500
[89] Sinervo, B.; Lively, C. M., The rock-paper-scissors game and the evolution of alternative male strategies, Nature, 380, 240-243 (1996)
[90] Skyrms, B., Evolution of the Social Contract (2014), Cambridge University Press
[91] Smith, J. M.; Price, G. R., The logic of animal conflict, Nature, 246, 15-18 (1973) · Zbl 1369.92134
[92] Szabó, G.; Tke, C., Evolutionary prisoner’s dilemma game on a square lattice, Phys. Rev. E, 58, 69-73 (1998)
[93] Szolnoki, A.; Perc, M., Reward and cooperation in the spatial public goods game, EPL (Europhysics Letters), 92, 38003 (2010)
[94] Szolnoki, A.; Perc, M., Antisocial pool rewarding does not deter public cooperation, Proc. R. Soc. B: Biol. Sci., 282, 20151975 (2015)
[95] Taylor, P. D.; Jonker, L. B., Evolutionary stable strategies and game dynamics, Math. Biosci., 40, 145-156 (1978) · Zbl 0395.90118
[96] Topaz, C. M.; Ziegelmeier, L.; Halverson, T., Topological data analysis of biological aggregation models, PLOS ONE, 10, 1-26 (2015)
[97] Turing, A. M., The chemical basis of morphogenesis, Bull. Math. Biol., 52, 153-197 (1990)
[98] Vittadello, S.T., Stumpf, M.P., 2020. Model comparison via simplicial complexes and persistent homology. arXiv preprint arXiv:2012.13039.
[99] Wadhwa, R.; Williamson, D.; Dhawan, A.; Scott, J., Tdastats: R pipeline for computing persistent homology in topological data analysis, J. Open Sour. Softw., 3, 860 (2018)
[100] Wakano, J. Y.; Nowak, M. A.; Hauert, C., Spatial dynamics of ecological public goods, Proc. Natl. Acad. Sci., 106, 7910-7914 (2009)
[101] Wasserman, L., Topological data analysis, Annu. Rev. Stat. Appl., 5, 501-532 (2018)
[102] Weibull, J. W., Evolutionary Game Theory (1997), MIT press
[103] Wolpert, L., Positional information and the spatial pattern of cellular differentiation, J. Theor. Biol., 25, 1-47 (1969)
[104] Xia, K.; Feng, X.; Tong, Y.; Wei, G. W., Persistent homology for the quantitative prediction of fullerene stability, J. Comput. Chem., 36, 408-422 (2015)
[105] Xia, K.; Wei, G. W., Persistent homology analysis of protein structure, flexibility, and folding, Int. J. Numer. Method Biomed. Eng., 30, 814-844 (2014)
[106] Yi, S. D.; Baek, S. K.; Choi, J. K., Combination with anti-tit-for-tat remedies problems of tit-for-tat, J. Theor. Biol., 412, 1-7 (2017) · Zbl 1368.91028
[107] Zomorodian, A.; Carlsson, G., Computing persistent homology, Discr. Comput. Geom., 33, 249-274 (2005) · Zbl 1069.55003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.