×

zbMATH — the first resource for mathematics

An introduction to ABED: agent-based simulation of evolutionary game dynamics. (English) Zbl 1429.91048
Summary: ABED is free and open-source software for simulating evolutionary game dynamics in finite populations. We explain how ABED can be used to simulate a wide range of dynamics considered in the literature and many novel dynamics. In doing so, we introduce a general model of revisions for dynamic evolutionary models, one that decomposes strategy updates into selection of candidate strategies, payoff determination, and choice among candidates. Using examples, we explore ways in which simulations can complement theory in increasing our understanding of strategic interactions in finite populations.

MSC:
91A22 Evolutionary games
91-08 Computational methods for problems pertaining to game theory, economics, and finance
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adami, C.; Schossau, J.; Hintze, A., Evolutionary game theory using agent-based methods, Phys. Life Rev., 19, 1-26 (2016)
[2] Adami, C.; Schossau, J.; Hintze, A., The reasonable effectiveness of agent-based simulations in evolutionary game theory: reply to comments on “Evolutionary game theory using agent-based methods”, Phys. Life Rev., 19, 38-42 (2016)
[3] Balkenborg, D.; Schlag, K. H., Evolutionarily stable sets, Int. J. Game Theory, 29, 571-595 (2001) · Zbl 1060.91023
[4] Barreto, C., Population dynamics toolbox (PDToolbox) (2014), Software
[5] Bellomo, N.; Elaiw, A., Space dynamics and stochastic features of evolutionary game dynamics. Comment on “Evolutionary game theory using agent-based methods”, Phys. Life Rev., 19, 27-28 (2016)
[6] Benaïm, M.; Weibull, J. W., Deterministic approximation of stochastic evolution in games, Econometrica, 71, 873-903 (2003) · Zbl 1152.91350
[7] Binmore, K.; Samuelson, L., Muddling through: noisy equilibrium selection, J. Econ. Theory, 74, 235-265 (1997) · Zbl 0887.90191
[8] Binmore, K.; Samuelson, L.; Vaughan, R., Musical chairs: modeling noisy evolution, Games Econ. Behav.. Games Econ. Behav., Games Econ. Behav., 21, 325-35 (1997), Erratum: · Zbl 0839.90140
[9] Björnerstedt, J.; Weibull, J. W., Nash equilibrium and evolution by imitation, (Arrow, K. J.; etal., The Rational Foundations of Economic Behavior (1996), St. Martin’s Press: St. Martin’s Press New York), 155-181
[10] Blume, L. E., Population games, (Arthur, W. B.; Durlauf, S. N.; Lane, D. A., The Economy as an Evolving Complex System II (1997), Addison-Wesley: Addison-Wesley Reading, MA), 425-460
[11] Cárdenas, J. C.; Mantilla, C.; Sethi, R., Stable sampling equilibrium in common pool resource games, Games, 6, 299-317 (2015) · Zbl 1403.91088
[12] Darroch, J. N.; Seneta, E., On quasi-stationary distributions in absorbing discrete-time finite Markov chains, J. Appl. Probab., 2, 1, 88-100 (1965) · Zbl 0134.34704
[13] Durrett, R., Stochastic Calculus: A Practical Introduction (1996), CRC Press: CRC Press Boca Raton, FL · Zbl 0856.60002
[14] Dzonsons, K.; Weibull, J., Birds: game theory simulator (2013), Software
[15] Eigen, M.; Schuster, P., The Hypercycle: A Principle of Natural Self-Organization (1979), Springer: Springer Berlin
[16] Ellison, G., Basins of attraction, long run equilibria, and the speed of step-by-step evolution, Rev. Econ. Stud., 67, 17-45 (2000) · Zbl 0956.91027
[17] Foster, D. P.; Young, H. P., Stochastic evolutionary game dynamics, Theor. Popul. Biol.. Theor. Popul. Biol., Theor. Popul. Biol., 51, 77-78 (1997), Corrigendum:
[18] Franchetti, F.; Sandholm, W. H., An introduction to Dynamo: diagrams for evolutionary game dynamics, Biol. Theory, 8, 2, 167-178 (2013)
[19] Friedman, D.; Sinervo, B., Evolutionary Games in Natural, Social, and Virtual Worlds (2016), Oxford University Press · Zbl 1337.91007
[20] Friedman, D.; Sinervo, B., Evolutionary game theory: simulations (2015), Software
[21] Fudenberg, D.; Imhof, L. A., Imitation processes with small mutations, J. Econ. Theory, 131, 251-262 (2006) · Zbl 1142.91342
[22] Fudenberg, D.; Imhof, L. A., Monotone imitation dynamics in large populations, J. Econ. Theory, 140, 229-245 (2008) · Zbl 1136.91328
[23] Fudenberg, D.; Levine, D. K., The Theory of Learning in Games (1998), MIT Press: MIT Press Cambridge · Zbl 0939.91004
[24] Fudenberg, D.; Nowak, M. A.; Taylor, C.; Imhof, L. A., Evolutionary game dynamics in finite populations with strong selection and weak mutation, Theor. Popul. Biol., 70, 352-363 (2006) · Zbl 1112.92044
[25] García, J.; van Veelen, M., Evolution and games. Interactive tutorials (2012)
[26] García, J.; van Veelen, M., In and out of equilibrium I: evolution of strategies in repeated games with discounting, J. Econ. Theory, 161, 161-189 (2016) · Zbl 1369.91019
[27] García, J.; van Veelen, M., No strategy can win in the repeated prisoner’s dilemma: linking game theory and computer simulations, Front. Robot. AI, 5, 102 (2018)
[28] Gaunersdorfer, A.; Hofbauer, J., Fictitious play, Shapley polygons, and the replicator equation, Games Econ. Behav., 11, 279-303 (1995) · Zbl 0841.90143
[29] Gilboa, I.; Matsui, A., Social stability and equilibrium, Econometrica, 59, 859-867 (1991) · Zbl 0728.90099
[30] Hauert, C., Evoludo. Interactive tutorials in evolutionary games (2018)
[31] Helbing, D., A mathematical model for behavioral changes by pair interactions, (Haag, G.; Mueller, U.; Troitzsch, K. G., Economic Evolution and Demographic Change: Formal Models in Social Sciences (1992), Springer: Springer Berlin), 330-348
[32] Hilbe, C.; Traulsen, A., Only the combination of mathematics and agent-based simulations can leverage the full potential of evolutionary modeling. Comment on “Evolutionary game theory using agent-based methods”, Phys. Life Rev., 19, 29-31 (2016)
[33] Hofbauer, J.; Mallet-Paret, J.; Smith, H. L., Stable periodic solutions for the hypercycle system, J. Dyn. Differ. Equ., 3, 423-436 (1991) · Zbl 0729.34032
[34] Hofbauer, J.; Sandholm, W. H., Evolution in games with randomly disturbed payoffs, J. Econ. Theory, 132, 47-69 (2007) · Zbl 1142.91343
[35] Hofbauer, J.; Sandholm, W. H., Stable games and their dynamics, J. Econ. Theory, 144, 1665-1693 (2009) · Zbl 1175.91036
[36] Hofbauer, J.; Schuster, P.; Sigmund, K., A note on evolutionarily stable strategies and game dynamics, J. Theor. Biol., 81, 609-612 (1979)
[37] Hofbauer, J.; Schuster, P.; Sigmund, K., Competition and cooperation in catalytic self-replication, J. Math. Biol., 11, 155-168 (1981) · Zbl 0448.92011
[38] Hofbauer, J., Imitation Dynamics for Games (1995), University of Vienna, Unpublished manuscript
[39] Hofbauer, J., Stability for the Best Response Dynamics (1995), University of Vienna, Unpublished manuscript
[40] Imhof, L. A.; Fudenberg, D.; Nowak, M. A., Evolutionary cycles of cooperation and defection, Proc. Natl. Acad. Sci., 31, 10797-10800 (2005)
[41] Imhof, L. A.; Nowak, M. A., Evolutionary game dynamics in a Wright-Fisher process, J. Math. Biol., 52, 5, 667-681 (2006) · Zbl 1110.92028
[42] Izquierdo, S. S.; Izquierdo, L. R., Stochastic approximation to understand simple simulation models, J. Stat. Phys., 151, 1, 254-276 (2013) · Zbl 1329.60335
[43] Izquierdo, L. R.; Izquierdo, S. S.; Galán, J. M.; Santos, J. I., Combining mathematical and simulation approaches to understand the dynamics of computer models, (Edmonds, B.; Meyer, R., Simulating Social Complexity: a Handbook (2013), Springer: Springer Berlin), 235-271, Chapter 11
[44] Izquierdo, L. R.; Izquierdo, S. S.; Sandholm, W. H., Evodyn-3s: a mathematica computable document to analyze evolutionary dynamics in 3-strategy games, SoftwareX, 7, 226-233 (2018)
[45] Izquierdo, L. R.; Izquierdo, S. S.; Sandholm, W. H., Agent-Based Evolutionary Game Dynamics (2019), University of Wisconsin Pressbooks
[46] Kandori, M.; Mailath, G. J.; Rob, R., Learning, mutation, and long run equilibria in games, Econometrica, 61, 29-56 (1993) · Zbl 0776.90095
[47] Kandori, M.; Rob, R., Evolution of equilibria in the long run: a general theory and applications, J. Econ. Theory, 65, 383-414 (1995) · Zbl 0837.90139
[48] Karatzas, I.; Shreve, S. E., Brownian Motion and Stochastic Calculus (1991), Springer: Springer New York · Zbl 0734.60060
[49] Kosfeld, M.; Droste, E.; Voorneveld, M., A myopic adjustment process leading to best reply matching, J. Econ. Theory, 40, 270-298 (2002) · Zbl 1033.91034
[50] Kreindler, G. E.; Young, H. P., Fast convergence in evolutionary equilibrium selection, Games Econ. Behav., 80, 39-67 (2013) · Zbl 1281.91026
[51] Loginov, G., Ordinal Imitative Dynamics (2019), Unpublished manuscript
[52] Mantilla, C.; Sethi, R.; Cárdenas, J. C., Efficiency and stability of sampling equilibrium in public good games, J. Public Econ. Theory (2019), Forthcoming.
[53] Maynard Smith, J., Evolution and the Theory of Games (1982), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0526.90102
[54] Monderer, D.; Shapley, L. S., Potential games, Games Econ. Behav., 14, 124-143 (1996) · Zbl 0862.90137
[55] Moran, P. A.P., Random processes in genetics, Math. Proc. Camb. Philos. Soc., 54, 1, 60-71 (1958) · Zbl 0091.15701
[56] Moran, P. A.P., The Statistical Processes of Evolutionary Theory (1962), Clarendon Press: Clarendon Press Oxford · Zbl 0119.35901
[57] Newton, J., Evolutionary game theory: a renaissance, Games, 9, 2 (2018) · Zbl 1402.91053
[58] Nowak, M. A., Evolutionary Dynamics: Exploring the Equations of Life (2006), Belknap/Harvard: Belknap/Harvard Cambridge · Zbl 1115.92047
[59] Nowak, M. A.; Sasaki, A.; Taylor, C.; Fudenberg, D., Emergence of cooperation and evolutionary stability in finite populations, Nature, 428, 646-650 (2004)
[60] Osborne, M. J.; Rubinstein, A., Games with procedurally rational players, Am. Econ. Rev., 88, 834-847 (1998)
[61] Oyama, D.; Sandholm, W. H.; Tercieux, O., Sampling best response dynamics and deterministic equilibrium selection, Theor. Econ., 10, 243-281 (2015) · Zbl 1395.91054
[62] Pacheco, J. M.; Traulsen, A.; Nowak, M. A., Coevolution of strategy and structure in complex networks with dynamical linking, Phys. Rev. Lett., 97, Article 258103 pp. (2006)
[63] Perc, M., Stability of subsystem solutions in agent-based models, Eur. J. Phys., 39, 1, Article 014001 pp. (2018)
[64] Perc, M.; Gómez-Gardeñes, J.; Szolnoki, A.; Floría, L. M.; Moreno, Y., Evolutionary dynamics of group interactions on structured populations: a review, J. R. Soc. Interface, 10, 80, Article 20120997 pp. (2013)
[65] Perc, M.; Szolnoki, A., Coevolutionary games—a mini review, Biosystems, 99, 2, 109-125 (2010)
[66] Robson, A.; Vega-Redondo, F., Efficient equilibrium selection in evolutionary games with random matching, J. Econ. Theory, 70, 65-92 (1996) · Zbl 0859.90138
[67] Roca, C. P.; Cuesta, J. A.; Sánchez, A., Time scales in evolutionary dynamics, Phys. Rev. Lett., 97, Article 158701 pp. (2006)
[68] Roca, C. P.; Cuesta, J. A.; Sánchez, A., Effect of spatial structure on the evolution of cooperation, Phys. Rev. E, 80, Article 046106 pp. (2009)
[69] 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)
[70] Rosenthal, R. W., Games of perfect information, predatory pricing and the chain-store paradox, J. Econ. Theory, 25, 92-100 (1981) · Zbl 0467.90084
[71] Roth, G.; Sandholm, W. H., Stochastic approximations with constant step size and differential inclusions, SIAM J. Control Optim., 51, 525-555 (2013) · Zbl 1302.62182
[72] Sample, C.; Allen, B., The limits of weak selection and large population size in evolutionary game theory, J. Math. Biol., 75, 5, 1285-1317 (2017) · Zbl 1378.91029
[73] Sánchez, A.; Cuesta, J. A., Altruism may arise from individual selection, J. Theor. Biol., 235, 2, 233-240 (2005)
[74] Sandholm, W. H., Almost global convergence to p-dominant equilibrium, Int. J. Game Theory, 30, 107-116 (2001) · Zbl 1060.91024
[75] Sandholm, W. H., Potential games with continuous player sets, J. Econ. Theory, 97, 81-108 (2001) · Zbl 0990.91005
[76] Sandholm, W. H., Evolution and equilibrium under inexact information, Games Econ. Behav., 44, 343-378 (2003) · Zbl 1089.91007
[77] Sandholm, W. H., Pairwise comparison dynamics and evolutionary foundations for Nash equilibrium, Games, 1, 3-17 (2010) · Zbl 1311.91034
[78] Sandholm, W. H., Population Games and Evolutionary Dynamics (2010), MIT Press: MIT Press Cambridge · Zbl 1208.91003
[79] Sandholm, W. H.; Dokumacı, E.; Franchetti, F., Dynamo: diagrams for evolutionary game dynamics (2012), Software
[80] Sandholm, W. H., Population games and deterministic evolutionary dynamics, (Young, H. P.; Zamir, S., Handbook of Game Theory with Economic Applications, vol. 4 (2015), Elsevier: Elsevier Amsterdam), 703-778, Chapter 13
[81] Sandholm, W. H.; Izquierdo, S. S.; Izquierdo, L. R., Stability for Best Experienced Payoff Dynamics (2018), University of Wisconsin, Universidad de Valladolid, and Universidad de Burgos, Unpublished manuscript
[82] Sandholm, W. H.; Izquierdo, S. S.; Izquierdo, L. R., Best experienced payoff dynamics and cooperation in the Centipede game, Theor. Econ (2019), Forthcoming
[83] Sandholm, W. H.; Staudigl, M., Large deviations and stochastic stability in the small noise double limit, Theor. Econ., 11, 279-355 (2016) · Zbl 1395.91055
[84] Sandholm, W. H.; Staudigl, M., Sample path large deviations for stochastic evolutionary game dynamics, Math. Oper. Res., 43, 4, 1348-1377 (2018)
[85] Schlag, K. H., Why imitate, and if so, how? A boundedly rational approach to multi-armed bandits, J. Econ. Theory, 78, 130-156 (1998) · Zbl 0895.90003
[86] Schlag, K. H., Which one should I imitate?, J. Math. Econ., 31, 493-522 (1999) · Zbl 0947.91025
[87] Schuster, P., Models of evolution and evolutionary game theory. A comment on “Evolutionary game theory using agent based models”, Phys. Life Rev., 19, 32-35 (2016)
[88] Schuster, P.; Sigmund, K., Replicator dynamics, J. Theor. Biol., 100, 533-538 (1983)
[89] Schuster, P.; Sigmund, K.; Wolff, R., Dynamical systems under constant organization I: topological analysis of a family of nonlinear differential equations—a model for catalytic hypercycles, Bull. Math. Biol., 40, 743-769 (1978) · Zbl 0384.34028
[90] Sethi, R., Stability of equilibria in games with procedurally rational players, Games Econ. Behav., 32, 85-104 (2000) · Zbl 0956.91025
[91] Smith, M. J., The stability of a dynamic model of traffic assignment—an application of a method of Lyapunov, Transp. Sci., 18, 245-252 (1984)
[92] Stroock, D. W.; Varadhan, S. R.S., Multidimensional Diffusion Processes (1979), Springer: Springer New York · Zbl 0426.60069
[93] Szabó, G.; Fáth, G., Evolutionary games on graphs, Phys. Rep., 446, 97-216 (2007)
[94] Szolnoki, A.; Mobilia, M.; Jiang, L.-L.; Szczesny, B.; Rucklidge, A. M.; Perc, M., Cyclic dominance in evolutionary games: a review, J. R. Soc. Interface, 11, 100, Article 20140735 pp. (2014)
[95] Tarnita, C. E., Mathematical approaches or agent-based methods? Comment on “Evolutionary game theory using agent-based methods”, Phys. Life Rev., 19, 36-37 (2016)
[96] Taylor, C.; Fudenberg, D.; Sasaki, A.; Nowak, M. A., Evolutionary game dynamics in finite populations, Bull. Math. Biol., 66, 1621-1644 (2004) · Zbl 1334.92372
[97] Taylor, P. D.; Jonker, L., Evolutionarily stable strategies and game dynamics, Math. Biosci., 40, 145-156 (1978) · Zbl 0395.90118
[98] Thomas, B., On evolutionarily stable sets, J. Math. Biol., 22, 105-115 (1985) · Zbl 0589.92011
[99] Traulsen, A.; Hauert, C., Stochastic evolutionary game dynamics, (Schuster, H. G., Reviews of Nonlinear Dynamics and Complexity, vol. 2 (2009), Wiley: Wiley New York), 25-61 · Zbl 1206.37056
[100] Traulsen, A.; Nowak, M. A.; Pacheco, J. M., Stochastic payoff evaluation increases the temperature of selection, J. Theor. Biol., 244, 2, 349-356 (2007)
[101] van Veelen, M., Robustness against indirect invasions, Games Econ. Behav., 74, 382-393 (2012) · Zbl 1279.91032
[102] Vega-Redondo, F., The evolution of Walrasian behavior, Econometrica, 65, 375-384 (1997) · Zbl 0874.90049
[103] Weibull, J. W., Evolutionary Game Theory (1995), MIT Press: MIT Press Cambridge · Zbl 0879.90206
[104] Wilensky, U.; Shargel, B., BehaviorSpace (2002), Northwestern University: Northwestern University Evanston, IL, Software. Center for Connected Learning and Computer-Based Modeling
[105] Wilensky, U., Netlogo (1999), Northwestern University: Northwestern University Evanston, IL, Software. Center for Connected Learning and Computer-Based Modeling
[106] Woelfing, B.; Traulsen, A., Stochastic sampling of interaction partners versus deterministic payoff assignment, J. Theor. Biol., 257, 4, 689-695 (2009) · Zbl 1400.91083
[107] Wu, B.; Altrock, P. M.; Wang, L.; Traulsen, A., Universality of weak selection, Phys. Rev. E, 82, Article 046106 pp. (2010)
[108] Wu, B.; García, J.; Hauert, C.; Traulsen, A., Extrapolating weak selection in evolutionary games, PLoS Comput. Biol., 9, 12, 1-7 (2013)
[109] Young, H. P., The evolution of conventions, Econometrica, 61, 57-84 (1993) · Zbl 0773.90101
[110] Young, H. P., Individual Strategy and Social Structure (1998), Princeton University Press: Princeton University Press Princeton
[111] Zeeman, E. C., Population dynamics from game theory, (Nitecki, Z.; Robinson, C., Global Theory of Dynamical Systems. Global Theory of Dynamical Systems, Evanston, 1979. Global Theory of Dynamical Systems. Global Theory of Dynamical Systems, Evanston, 1979, Lecture Notes in Mathematics, vol. 819 (1980), Springer: Springer Berlin), 472-497
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.