Large deviations and Stochastic stability in Population Games

Mathias Staudigl; Srinivas Arigapudi; William H. Sandholm

doi:10.3934/jdg.2021021

Article Contents

2022, Volume 9, Issue 4: 569-595. Doi: 10.3934/jdg.2021021

This issue Previous Article Stochastic stability in the large population and small mutation limits for coordination games Next Article

Large deviations and Stochastic stability in Population Games

1.
Maastricht University, Department of Data Science and Knowledge Engineering, Paul-Henri-Spaaklaan 1, 6229 EN Maastricht, The Netherlands
2.
Technion-Israel Institute of Technology, Faculty of Industrial Engineering and Management, Haifa, 32000003, Israel
3.
University of Wisconsin, Department of Economics, 1180 Observatory Drive, Madison, WI 53706, USA

^* Corresponding author: Mathias Staudigl
^* Corresponding author: Mathias Staudigl

Received: October 2020

Early access: July 2021

Published: October 2022

M. Staudigl is supported by the COST Action CA-16228.Srinivas Arigapudi is supported in part at the Technion by a Fine Fellowship

Abstract Full Text(HTML) Figure(4) / Table(2) Related Papers Cited by

Abstract

In this article we review a model of stochastic evolution under general noisy best-response protocols, allowing the probabilities of suboptimal choices to depend on their payoff consequences. We survey the methods developed by the authors which allow for a quantitative analysis of these stochastic evolutionary game dynamics. We start with a compact survey of techniques designed to study the long run behavior in the small noise double limit (SNDL). In this regime we let the noise level in agents' decision rules to approach zero, and then the population size is formally taken to infinity. This iterated limit strategy yields a family of deterministic optimal control problems which admit an explicit analysis in many instances. We then move in by describing the main steps to analyze stochastic evolutionary game dynamics in the large population double limit (LPDL). This regime refers to the iterated limit in which first the population size is taken to infinity and then the noise level in agents' decisions vanishes. The mathematical analysis of LPDL relies on a sample-path large deviations principle for a family of Markov chains on compact polyhedra. In this setting we formulate a set of conjectures and open problems which give a clear direction for future research activities.

Keywords:

Mathematics Subject Classification: Primary: 91A22, 60F10, 60J10; Secondary: 35F21, 90B20.

Citation:

Full Text(HTML)

Figure 1. Optimal exit paths with non-binding state constraints

Download: Full-size image PowerPoint slide

Figure 2. Optimal exit paths with indirect exit and binding state constraints

Download: Full-size image PowerPoint slide

Figure 3. Optimal transition paths in Bilingual games

Download: Full-size image PowerPoint slide

Figure 4. Phase portrait of the logit dynamics $ V^{0.1} $ for example (46)

Download: Full-size image PowerPoint slide

Table 1. Coordination Game

| Show Table

DownLoad: CSV

Table 2. Bilingual Game

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Arigapudi, Exit from equilibrium in coordination games under probit choice, Games Econom. Behav., 122 (2020), 168-202. doi: 10.1016/j.geb.2020.04.003.
[2]	S. Arigapudi, Transitions between equilibria in bilingual games under logit choice, J. Math. Econom., 86 (2020), 24-34. doi: 10.1016/j.jmateco.2019.10.004.
[3]	M. Beckmann, C. B. McGuire and C. B. Winsten, Studies in the Economics of Transportation, Yale University Press, New Haven, CT, 1956.
[4]	M. Benaïm, Recursive algorithms, urn processes, and chaining number of chain recurrent sets, Ergodic Theory Dynam. Systems, 18 (1998), 53-87. doi: 10.1017/S0143385798097557.
[5]	M. Benaïm and J. W. Weibull, Deterministic approximation of stochastic evolution in games, Econometrica, 71 (2003), 873-903. doi: 10.1111/1468-0262.00429.
[6]	M. Benaïm and J. W. Weibull, Mean-Field Approximation of Stochastic Population Processes in Games, Université de Neuchâtel and Stockholm School of Economics, 2009. Available from: https://hal.archives-ouvertes.fr/hal-00435515/document.
[7]	L. E. Blume, How noise matters, Games Econom. Behav., 44 (2003), 251-271. doi: 10.1016/S0899-8256(02)00554-7.
[8]	L. E. Blume, The statistical mechanics of strategic interaction, Games Econom. Behav., 5 (1993), 387-424. doi: 10.1006/game.1993.1023.
[9]	I. M. Bomze, Regularity versus degeneracy in dynamics, games, and optimization: A unified approach to different aspects, SIAM Rev., 44 (2002), 394-414. doi: 10.1137/S00361445003756.
[10]	A. Bovier and F. den Hollander, Metastability. A Potential-Theoretic Approach, Grundlehren der Mathematischen Wissenschaften, 351, Springer, Cham, 2015. doi: 10.1007/978-3-319-24777-9.
[11]	O. Catoni, Simulated annealing algorithms and {M}arkov chains with rare transitions, in Séminaire de Probabilités XXXIII, Lecture Notes in Math., 1709, Springer, Berlin, 1999, 69–119. doi: 10.1007/BFb0096510.
[12]	G. C. Chasparis, Stochastic stability of perturbed learning automata in positive-utility games, IEEE Trans. Automat. Control, 64 (2019), 4454-4469. doi: 10.1109/TAC.2019.2895300.
[13]	I.-K. Cho, N. Williams and T. J. Sargent, Escaping Nash inflation, Rev. Econom. Stud., 69 (2002), 1-40. doi: 10.1111/1467-937X.00196.
[14]	E. Dokumacı and W. H. Sandholm, Large deviations and multinomial probit choice, J. Econom. Theory, 146 (2011), 2151-2158. doi: 10.1016/j.jet.2011.06.013.
[15]	P. Dupuis and R. S. Ellis, A Weak Convergence Approach to the Theory of Large Deviations, Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1997. doi: 10.1002/9781118165904.
[16]	G. Ellison, Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution, Rev. Econom. Stud., 67 (2000), 17-45. doi: 10.1111/1467-937X.00119.
[17]	D. Foster and P. Young, Stochastic evolutionary game dynamics, Theoret. Population Biol., 38 (1990), 219-232. doi: 10.1016/0040-5809(90)90011-J.
[18]	M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Grundlehren der Mathematischen Wissenschaften, 260, Springer, New York, 1998. doi: 10.1007/978-1-4612-0611-8.
[19]	J. C. Harsanyi and R. Selten, A General Theory of Equilibrium Selection in Games, MIT Press, Cambridge, MA, 1988.
[20]	S. Hart and A. Mas-Colell, Uncoupled dynamics do not lead to Nash equilibrium, Amer. Econom. Rev., 93 (2003), 1830-1836. doi: 10.1257/000282803322655581.
[21]	J. Hofbauer, Deterministic evolutionary game dynamics, in Evolutionary Game Dynamics, Proc. Sympos. Appl. Math., 69, AMS Short Course Lecture Notes, Amer. Math. Soc., Providence, RI, 2011, 61–79. doi: 10.1090/psapm/069/2882634.
[22]	J. Hofbauer, Stability for the Best Response Dynamics, unpublished manuscript, University of Vienna, 1995.
[23]	J. Hofbauer, J. Oechssler and F. Riedel, Brown-von Neumann-Nash dynamics: The continuous strategy case, Games Econom. Behav., 65 (2009), 406-429. doi: 10.1016/j.geb.2008.03.006.
[24]	J. Hofbauer and W. H. Sandholm, Evolution in games with randomly disturbed payoffs, J. Econom. Theory, 132 (2007), 47-69. doi: 10.1016/j.jet.2005.05.011.
[25]	J. Hofbauer and W. H. Sandholm, Survival of dominated strategies under evolutionary dynamics, Theor. Econ., 6 (2011), 341-377. doi: 10.3982/TE771.
[26]	J. Hofbauer and K. Sigmund, Evolutionary game dynamics, Bull. Amer. Math. Soc. (N.S.), 40 (2003), 479-519. doi: 10.1090/S0273-0979-03-00988-1.
[27]	J. Hofbauer and S. Sorin, Best response dynamics for continuous zero-sum games, Discrete Contin. Dyn. Syst. Ser. B, 6 (2006), 215-224. doi: 10.3934/dcdsb.2006.6.215.
[28]	Y. Kifer, A discrete-time version of the Wentzell-Freidlin theory, Ann. Probab, 18 (1990), 1676-1692. doi: 10.1214/aop/1176990641.
[29]	Y. Kifer, Random Perturbations of Dynamical Systems, Progress in Probability and Statistics, 16, Birkhäuser Boston, Inc., Boston, MA, 1988. doi: 10.1007/978-1-4615-8181-9.
[30]	H. J. Kushner and G. G. Yin, Stochastic Approximation Algorithms and Applications, Applications of Mathematics (New York), 35, Springer-Verlag, New York, 1997. doi: 10.1007/978-1-4899-2696-8.
[31]	J. R. Marden and J. S. Shamma, Game-Theoretic Learning in Distributed Control, Handbook of Dynamic Game Theory, Springer, Cham, 2018,511–546. doi: 10.1007/978-3-319-44374-4_9.
[32]	J. R. Marden, H. P. Young and L. Y. Pao, Achieving pareto optimality through distributed learning, SIAM J. Control Optim., 52 (2014), 2753-2770. doi: 10.1137/110850694.
[33]	J. Maynard Smith and G. R. Price, The logic of animal conflict, Nature, 246 (1973), 15-18. doi: 10.1038/246015a0.
[34]	P. Mertikopoulos and M. Staudigl, On the convergence of gradient-like flows with noisy gradient input, SIAM J. Optim., 28 (2018), 163-197. doi: 10.1137/16M1105682.
[35]	K. Michihiro and R. Rob, Bandwagon effects and long run technology choice, Games Econom. Behav., 22 (1998), 30-60. doi: 10.1006/game.1997.0563.
[36]	J. F. Nash Jr., Non-Cooperative Games, Ph.D thesis, Princeton University, 1950.
[37]	D. Oyama and S. Takahashi, Contagion and uninvadability in local interaction games: The bilingual game and general supermodular games, J. Econom. Theory, 157 (2015), 100-127. doi: 10.1016/j.jet.2014.12.012.
[38]	N. Quijano, C. Ocampo-Martinez, J. Barreiro-Gomez, G. Obando, A. Pantoja and E. Mojica-Nava, The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory, IEEE Control Syst., 37 (2017), 70-97. doi: 10.1109/MCS.2016.2621479.
[39]	R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, 28, Princeton University Press, Princeton, NJ, 1970.
[40]	R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, Internat. J. Game Theory, 2 (1973), 65-67. doi: 10.1007/BF01737559.
[41]	W. H Sandholm, Evolution and equilibrium under inexact information, Games Econom. Behav., 44 (2003), 343-378. doi: 10.1016/S0899-8256(03)00026-5.
[42]	W. H. Sandholm, Orders of limits for stationary distributions, stochastic dominance, and stochastic stability, Theor. Econ., 5 (2010), 1-26. doi: 10.3982/TE554.
[43]	W. H. Sandholm, Population Games and Evolutionary Dynamics, Economic Learning and Social Evolution, MIT Press, Cambridge, MA, 2010.
[44]	W. H. Sandholm, Potential games with continuous player sets, J. Econom. Theory, 97 (2001), 81-108. doi: 10.1006/jeth.2000.2696.
[45]	W. H. Sandholm, Stochastic evolutionary game dynamics: Foundations, deterministic approximation, and equilibrium selection, in Evolutionary Game Dynamics, Proc. Sympos. Appl. Math., 69, AMS Short Course Lecture Notes, Amer. Math. Soc., Providence, RI, 2011,111–141. doi: 10.1090/psapm/069/2882636.
[46]	W. H. Sandholm and M. Staudigl, Large deviations and stochastic stability in the small noise double limit, Theor. Econ., 11 (2016), 279-355. doi: 10.3982/TE1905.
[47]	W. H. Sandholm and M. Staudigl, Sample path large deviations for stochastic evolutionary game dynamics, Math. Oper. Res., 43 (2018), 1348-1377. doi: 10.1287/moor.2017.0908.
[48]	W. H. Sandholm, H. V. Tran and S. Arigapudi, Hamilton-Jacobi equations with semilinear costs and state constraints, with applications to large deviations in games, Math. Oper. Res.. doi: 10.1287/moor.2020.1114.
[49]	K. Satsukawa, K. Wada and T. Iryo, Stochastic stability of dynamic user equilibrium in unidirectional networks: Weakly acyclic game approach, Trans. Res. Part B: Methodological, 125 (2019), 229-247. doi: 10.1016/j.trb.2019.05.015.
[50]	D. Shah and J. Shin, Dynamics in congestion games, in Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '10, New York, 2010,107–118. doi: 10.1145/1811039.1811052.
[51]	M. Staudigl, Co-evolutionary dynamics and Bayesian interaction games, Internat. J. Game Theory, 42 (2013), 179-210. doi: 10.1007/s00182-012-0331-0.
[52]	M. Staudigl, Potential games in volatile environments, Games Econom. Behav., 72 (2011), 271-287. doi: 10.1016/j.geb.2010.08.004.
[53]	M. Staudigl, Stochastic stability in asymmetric binary choice coordination games, Games Econom. Behav., 75 (2012), 372-401. doi: 10.1016/j.geb.2011.11.003.
[54]	C. Taylor, D. Fudenberg, A. Sasaki and M. A. Nowak, Evolutionary game dynamics in finite populations, Bull. Math. Biol., 66 (2004), 1621-1644. doi: 10.1016/j.bulm.2004.03.004.
[55]	P. D. Taylor and L. B. Jonker, Evolutionary stable strategies and game dynamics, Math. Biosci., 40 (1978), 145-156. doi: 10.1016/0025-5564(78)90077-9.
[56]	A. Traulsen and C. Hauert, Stochastic evolutionary game dynamics, in Reviews of Nonlinear Dynamics and Complexity. Vol. 2, Wiley-VCH Verlag, Weinheim, 2009, 25–61.
[57]	N. Vielle, Small perturbations and stochastic games, Israel J. Math., 119 (2000), 127-142. doi: 10.1007/BF02810665.
[58]	J. W. Weibull, The mass action interpretation, J. Econom. Theory, 69 (1996), 165-171.
[59]	H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84. doi: 10.2307/2951778.
[60]	D. Zhou and H. Qian, Fixation, transient landscape, and diffusion dilemma in stochastic evolutionary game dynamics, Phys. Rev. E, 84 (2011). doi: 10.1103/PhysRevE.84.031907.