×

Riemannian game dynamics. (English) Zbl 1417.91102

Summary: We study a class of evolutionary game dynamics defined by balancing a gain determined by the game’s payoffs against a cost of motion that captures the difficulty with which the population moves between states. Costs of motion are represented by a Riemannian metric, i.e., a state-dependent inner product on the set of population states. The replicator dynamics and the (Euclidean) projection dynamics are the archetypal examples of the class we study. Like these representative dynamics, all Riemannian game dynamics satisfy certain basic desiderata, including positive correlation, local stability of interior ESSs, and global convergence in potential games. When the underlying Riemannian metric satisfies a Hessian integrability condition, the resulting dynamics preserve many further properties of the replicator and projection dynamics. We examine the close connections between Hessian game dynamics and reinforcement learning in normal form games, extending and elucidating a well-known link between the replicator dynamics and exponential reinforcement learning.

MSC:

91A22 Evolutionary games
91A26 Rationality and learning in game theory
58D17 Manifolds of metrics (especially Riemannian)

Software:

ABED
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Akin, E., The geometry of population genetics, Lecture Notes in Biomathematics, vol. 31, (1979), Springer-Verlag · Zbl 0437.92016
[2] Akin, E., Domination or equilibrium, Math. Biosci., 50, 239-250, (1980) · Zbl 0452.92020
[3] Aliprantis, C. D.; Border, K. C., Infinite dimensional analysis: A Hitchhiker’s guide, (1999), Springer Berlin · Zbl 0938.46001
[4] Alvarez, F.; Bolte, J.; Brahic, O., Hessian Riemannian gradient flows in convex programming, SIAM J. Control Optim., 43, 2, 477-501, (2004) · Zbl 1077.34050
[5] Aubin, J.-P.; Cellina, A., Differential inclusions, (1984), Springer Berlin
[6] Bayer, D. A.; Lagarias, J. C., The nonlinear geometry of linear programming I. affine and projective scaling trajectories, Trans. Am. Math. Soc., 314, 499-526, (1989) · Zbl 0671.90045
[7] Benaïm, M.; Weibull, J. W., Deterministic approximation of stochastic evolution in games, Econometrica, 71, 3, 873-903, (2003) · Zbl 1152.91350
[8] Björnerstedt, J.; Weibull, J. W., Nash equilibrium and evolution by imitation, (Arrow, K. J.; Colombatto, E.; Perlman, M.; Schmidt, C., The Rational Foundations of Economic Behavior, (1996), St. Martin’s Press New York, NY), 155-181
[9] Bolte, J.; Teboulle, M., Barrier operators and associated gradient-like dynamical systems for constrained minimization problems, SIAM J. Control Optim., 42, 4, 1266-1292, (2003) · Zbl 1051.49010
[10] Börgers, T.; Sarin, R., Learning through reinforcement and replicator dynamics, J. Econ. Theory, 77, 1-14, (1997) · Zbl 0892.90198
[11] Bravo, M.; Mertikopoulos, P., On the robustness of learning in games with stochastically perturbed payoff observations, John Nash Memorial Issue, Games Econ. Behav., 103, 41-66, (2017) · Zbl 1393.91016
[12] Bregman, L. M., The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys., 7, 3, 200-217, (1967) · Zbl 0186.23807
[13] Brown, G. W., Iterative solutions of games by fictitious play, (Koopmans, T. C.; etal., Activity Analysis of Production and Allocation, (1951), Wiley New York), 374-376
[14] Coucheney, P.; Gaujal, B.; Mertikopoulos, P., Penalty-regulated dynamics and robust learning procedures in games, Math. Oper. Res., 40, 3, 611-633, (2015) · Zbl 1377.91033
[15] Demichelis, S.; Ritzberger, K., From evolutionary to strategic stability, J. Econ. Theory, 113, 51-75, (2003) · Zbl 1102.91308
[16] Duistermaat, J. J., On hessian Riemannian structures, Asian J. Math., 5, 79-91, (2001) · Zbl 1021.53021
[17] Fisher, R. A., The genetical theory of natural selection, (1930), Clarendon Press Oxford · JFM 56.1106.13
[18] Friedberg, S. H.; Insel, A. J.; Spence, L. E., Linear algebra, (2002), Pearson
[19] Friedman, D., Evolutionary games in economics, Econometrica, 59, 3, 637-666, (1991) · Zbl 0745.90012
[20] Friesz, T. L.; Bernstein, D.; Mehta, N. J.; Tobin, R. L.; Ganjalizadeh, S., Day-to-day dynamic network disequilibria and idealized traveler information systems, Oper. Res., 42, 1120-1136, (1994) · Zbl 0823.90037
[21] Fudenberg, D.; Levine, D. K., The theory of learning in games, Economic Learning and Social Evolution, vol. 2, (1998), MIT Press Cambridge, MA · Zbl 0939.91004
[22] Harper, M., Escort evolutionary game theory, Phys. D: Nonlinear Phenom., 240, 1411-1415, (2011) · Zbl 1231.91026
[23] Hart, S.; Mas-Colell, A., A general class of adaptive strategies, J. Econ. Theory, 98, 26-54, (2001) · Zbl 0994.91007
[24] 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 Berlin), 330-348
[25] Hines, W. G.S., Three characterizations of population strategy stability, J. Appl. Probab., 17, 333-340, (1980), Correction, R. Cressman and W.G.S. Hines, 21 (1984), 213-214 · Zbl 0439.92021
[26] Hiriart-Urruty, J.-B.; Lemaréchal, C., Fundamentals of convex analysis, (2001), Springer Berlin · Zbl 0998.49001
[27] Hofbauer, J.; Sandholm, W. H., On the global convergence of stochastic fictitious play, Econometrica, 70, 6, 2265-2294, (2002) · Zbl 1141.91336
[28] Hofbauer, J.; Sandholm, W. H., Evolution in games with randomly disturbed payoffs, J. Econ. Theory, 132, 47-69, (2007) · Zbl 1142.91343
[29] Hofbauer, J.; Sandholm, W. H., Stable games and their dynamics, J. Econ. Theory, 144, 1710-1725, (2009) · Zbl 1170.91316
[30] Hofbauer, J.; Schuster, P.; Sigmund, K., A note on evolutionarily stable strategies and game dynamics, J. Theor. Biol., 81, 609-612, (1979)
[31] Hofbauer, J.; Sigmund, K., Adaptive dynamics and evolutionary stability, Appl. Math. Lett., 3, 75-79, (1990) · Zbl 0709.92015
[32] Hofbauer, J.; Sigmund, K., Evolutionary games and population dynamics, (1998), Cambridge University Press Cambridge, UK · Zbl 0914.90287
[33] Hofbauer, J.; Sorin, S.; Viossat, Y., Time average replicator and best reply dynamics, Math. Oper. Res., 34, 2, 263-269, (2009) · Zbl 1232.91046
[34] Hopkins, E., A note on best response dynamics, Games Econ. Behav., 29, 138-150, (1999) · Zbl 1131.91307
[35] Hopkins, E., Two competing models of how people learn in games, Econometrica, 70, 2141-2166, (2002) · Zbl 1142.91357
[36] Izquierdo, L.R., Izquierdo, S.S., Sandholm, W.H., 2018. An introduction to ABED: agent-based simulation of evolutionary game dynamics. Universidad de Burgos, Universidad de Valladolid, and University of Wisconsin. Unpublished manuscript.; Izquierdo, L.R., Izquierdo, S.S., Sandholm, W.H., 2018. An introduction to ABED: agent-based simulation of evolutionary game dynamics. Universidad de Burgos, Universidad de Valladolid, and University of Wisconsin. Unpublished manuscript.
[37] Kimura, M., On the change of population fitness by natural selection, Heredity, 12, 145-167, (1958)
[38] Lahkar, R.; Sandholm, W. H., The projection dynamic and the geometry of population games, Games Econ. Behav., 64, 565-590, (2008) · Zbl 1152.91355
[39] Laraki, R.; Mertikopoulos, P., Inertial game dynamics and applications to constrained optimization, SIAM J. Control Optim., 53, 5, 3141-3170, (2015) · Zbl 1335.91018
[40] Lee, J. M., Riemannian manifolds: an introduction to curvature, Graduate Texts in Mathematics, vol. 176, (1997), Springer · Zbl 0905.53001
[41] Lee, J. M., Introduction to smooth manifolds, Graduate Texts in Mathematics, vol. 218, (2003), Springer-Verlag New York, NY
[42] Maynard Smith, J.; Price, G. R., The logic of animal conflict, Nature, 246, 15-18, (1973) · Zbl 1369.92134
[43] Mertikopoulos, P.; Moustakas, A. L., The emergence of rational behavior in the presence of stochastic perturbations, Ann. Appl. Probab., 20, 4, 1359-1388, (2010) · Zbl 1195.91011
[44] Mertikopoulos, P.; Sandholm, W. H., Learning in games via reinforcement and regularization, Math. Oper. Res., 41, 4, 1297-1324, (2016) · Zbl 1349.91063
[45] Mertikopoulos, P., Sandholm, W.H., 2018. Discrete choice and game dynamics with lattice-structured traits. CNRS and University of Wisconsin. Unpublished manuscript.; Mertikopoulos, P., Sandholm, W.H., 2018. Discrete choice and game dynamics with lattice-structured traits. CNRS and University of Wisconsin. Unpublished manuscript.
[46] Mertikopoulos, P.; Staudigl, M., On the convergence of gradient-like flows with noisy gradient input, SIAM J. Optim., 28, 1, 163-197, (2018) · Zbl 1387.90187
[47] Mertikopoulos, P.; Zhou, Z., Learning in games with continuous action sets and unknown payoff functions, Math. Program., (2018)
[48] Monderer, D.; Shapley, L. S., Potential games, Games Econ. Behav., 14, 1, 124-143, (1996) · Zbl 0862.90137
[49] Nagurney, A.; Zhang, D., Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria, Transp. Sci., 31, 147-158, (1997) · Zbl 0886.90072
[50] Nemirovski, A. S.; Yudin, D. B., Problem complexity and method efficiency in optimization, (1983), Wiley New York, NY
[51] Posch, M., Cycling in a stochastic learning algorithm for normal form games, J. Evol. Econ., 7, 193-207, (1997)
[52] Rockafellar, R. T., Convex analysis, (1970), Princeton University Press Princeton, NJ · Zbl 0229.90020
[53] Roth, G.; Sandholm, W. H., Stochastic approximations with constant step size and differential inclusions, SIAM J. Control Optim., 51, 1, 525-555, (2013) · Zbl 1302.62182
[54] Rustichini, A., Optimal properties of stimulus-response learning models, Games Econ. Behav., 29, 230-244, (1999) · Zbl 1131.91308
[55] Sandholm, W. H., Potential games with continuous player sets, J. Econ. Theory, 97, 81-108, (2001) · Zbl 0990.91005
[56] Sandholm, W. H., Excess payoff dynamics and other well-behaved evolutionary dynamics, J. Econ. Theory, 124, 149-170, (2005) · Zbl 1116.91019
[57] Sandholm, W. H., Local stability under evolutionary game dynamics, Theor. Econ., 5, 27-50, (2010) · Zbl 1194.91046
[58] Sandholm, W. H., Population games and evolutionary dynamics, Economic Learning and Social Evolution, (2010), MIT Press Cambridge, MA · Zbl 1208.91003
[59] Sandholm, W. H., Probabilistic interpretations of integrability for game dynamics, Dyn. Games Appl., 4, 95-106, (2014) · Zbl 1300.91012
[60] Sandholm, W. H., Population games and deterministic evolutionary dynamics, (Young, H. P.; Zamir, S., Handbook of Game Theory, vol. 4, (2015), Elsevier), 703-778
[61] Sandholm, W. H.; Dokumacı, E.; Lahkar, R., The projection dynamic and the replicator dynamic, Games Econ. Behav., 64, 666-683, (2008) · Zbl 1152.91357
[62] 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
[63] Schuster, P.; Sigmund, K., Replicator dynamics, J. Theor. Biol., 100, 3, 533-538, (1983)
[64] Schuster, P.; Sigmund, K.; Hofbauer, J.; Wolff, R., Self-regulation of behaviour in animal societies I: symmetric contests, Biol. Cybern., 40, 1-8, (1981) · Zbl 0465.92016
[65] Shahshahani, S., A new mathematical framework for the study of linkage and selection, Memoirs of the American Mathematical Society, vol. 211, (1979) · Zbl 0473.92008
[66] Shalev-Shwartz, S., Online learning and online convex optimization, Found. Trends Mach. Learn., 4, 2, 107-194, (2011) · Zbl 1253.68190
[67] Swinkels, J. M., Adjustment dynamics and rational play in games, Games Econ. Behav., 5, 455-484, (1993) · Zbl 0805.90132
[68] Taylor, P. D.; Jonker, L. B., Evolutionary stable strategies and game dynamics, Math. Biosci., 40, 1-2, 145-156, (1978) · Zbl 0395.90118
[69] Tsakas, E.; Voorneveld, M., The target projection dynamic, Games Econ. Behav., 67, 708-719, (2009) · Zbl 1190.91009
[70] Tsallis, C., Possible generalization of Boltzmann-Gibbs statistics, J. Stat. Phys., 52, 479-487, (1988) · Zbl 1082.82501
[71] Weibull, J. W., Evolutionary game theory, (1995), MIT Press Cambridge, MA · Zbl 0879.90206
[72] Zusai, D., 2018. Gains in evolutionary dynamics: a unifying approach to stability for contractive games and ESS. Temple University. Unpublished manuscript.; Zusai, D., 2018. Gains in evolutionary dynamics: a unifying approach to stability for contractive games and ESS. Temple University. Unpublished manuscript.
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.