Stochastic stability in the large population and small mutation limits for coordination games

Ryoji Sawa

doi:10.3934/jdg.2021015

Article Contents

2022, Volume 9, Issue 4: 547-567. Doi: 10.3934/jdg.2021015 open access

This issue Previous Article Stochastic dynamics and Edmonds' algorithm Next Article Large deviations and Stochastic stability in Population Games

Stochastic stability in the large population and small mutation limits for coordination games

Ryoji Sawa^*,

University of Tsukuba, Tennoudai 1-1-1, Tsukuba, Ibaraki 305-8573, Japan

^* I dedicate this paper to William H. Sandholm.

Received: October 2020

Early access: April 2021

Published: October 2022

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

Abstract

We consider a model of stochastic evolution in symmetric coordination games with $ K\ge 2 $ strategies played by myopic agents. Agents employ the best response with mutations choice rule and simultaneously revise strategies in each period. We form the dynamic process as a Markov chain with state space being the set of best responses in order to overcome difficulties that arise with the large population. We examine the long run equilibria for both orders of limits where the small noise limit and the large population limit are taken sequentially. We characterize an equilibrium refinement criterion that is common among both orders of limits.

Keywords:

Mathematics Subject Classification: Primary: 91A22, 60F10, 60J10; Secondary: 91A11, 91D15.

Citation:

FullText(HTML)

Figure 1. The literature on stochastic stability in the large population limit

Download: Full-size image PowerPoint slide

Figure 2. the best response regions

Download: Full-size image PowerPoint slide

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. Benaïm and J. W. Weibull, Deterministic approximation of stochastic evolution in games, Econometrica, 71 (2003), 873-903. doi: 10.1111/1468-0262.00429.
[4]	K. Binmore and L. Samuelson, Muddling through: Noisy equilibrium selection, J. Econom. Theory, 74 (1997), 235-265. doi: 10.1006/jeth.1996.2255.
[5]	K. G. Binmore, L. Samuelson and R. Vaughan, Musical chairs: Modeling noisy evolution, Games Econom. Behav., 11 (1995), 1-35. doi: 10.1006/game.1995.1039.
[6]	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.
[7]	M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Fundamental Principles of Mathematical Sciences, 260, Springer-Verlag, New York, 1998. doi: 10.1007/978-1-4612-0611-8.
[8]	D. Fudenberg and L. A. Imhof, Imitation processes with small mutations, J. Econom. Theory, 131 (2006), 251-262. doi: 10.1016/j.jet.2005.04.006.
[9]	D. Fudenberg and L. A. Imhof, Monotone imitation dynamics in large populations, J. Econom. Theory, 140 (2008), 229-245. doi: 10.1016/j.jet.2007.08.002.
[10]	D. Fudenberg, M. A. Nowak, C. Taylor and L. A. Imhof, Evolutionary game dynamics in finite populations with strong selection and weak mutation, Theoretical Population Biology, 70 (2006), 352-363. doi: 10.1016/j.tpb.2006.07.006.
[11]	S. Hart, Evolutionary dynamics and backward induction, Games Econom. Behav., 41 (2002), 227-264. doi: 10.1016/S0899-8256(02)00502-X.
[12]	W. Hoeffding, Asymptotically optimal tests for multinomial distributions, Ann. Math. Statist., 36 (1965), 369-401. doi: 10.1214/aoms/1177700150.
[13]	L. A. Imhof and M. A. Nowak, Evolutionary game dynamics in a Wright-Fisher process, J. Math. Biol., 52 (2006), 667-681. doi: 10.1007/s00285-005-0369-8.
[14]	M. Kandori, G. J. Mailath and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), 29-56. doi: 10.2307/2951777.
[15]	C. Kuzmics, On the elimination of dominated strategies in stochastic models of evolution with large populations, Games Econom. Behav., 72 (2011), 452-466. doi: 10.1016/j.geb.2010.10.002.
[16]	C. Kuzmics, Stochastic evolutionary stability in extensive form games of perfect information, Games Econom. Behav., 48 (2004), 321-336. doi: 10.1016/j.geb.2003.10.001.
[17]	H. Ohtsuki, P. Bordalo and M. A. Nowak, The one-third law of evolutionary dynamics, J. Theoret. Biol., 249 (2007), 289-295. doi: 10.1016/j.jtbi.2007.07.005.
[18]	L. Samuelson, Stochastic stability in games with alternative best replies, J. Econom. Theory, 64 (1994), 35-65. doi: 10.1006/jeth.1994.1053.
[19]	W. H. Sandholm, Orders of limits for stationary distributions, stochastic dominance, and stochastic stability, Theor. Econ., 5 (2010), 1-26. doi: 10.3982/TE554.
[20]	W. H. Sandholm, Population Games and Evolutionary Dynamics, Economic Learning and Social Evolution, MIT Press, Cambridge, MA, 2010.
[21]	W. H. Sandholm, Simple formulas for stationary distributions and stochastically stable states, Games Econom. Behav., 59 (2007), 154-162. doi: 10.1016/j.geb.2006.07.001.
[22]	W. H. Sandholm, Stochastic imitative game dynamics with committed agents, J. Econom. Theory, 147 (2012), 2056-2071. doi: 10.1016/j.jet.2012.05.018.
[23]	W. H. Sandholm and A. Pauzner, Evolution, population growth, and history dependence, Games Econom. Behav., 22 (1998), 84-120. doi: 10.1006/game.1997.0575.
[24]	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.
[25]	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.
[26]	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, to appear, Math. Oper. Res. . Available from: http://www.math.wisc.edu/ hung/hjld.pdf.
[27]	R. Sawa, Mutation rates and equilibrium selection under stochastic evolutionary dynamics, Internat. J. Game Theory, 41 (2012), 489-496. doi: 10.1007/s00182-011-0299-1.
[28]	H. Shafiey and D. Waxman, Exact results for the probability and stochastic dynamics of fixation in the Wright-Fisher model, J. Theoret. Biol., 430 (2017), 64-77. doi: 10.1016/j.jtbi.2017.06.026.
[29]	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.
[30]	M. Staudigl, S. Arigapudi and W. H. Sandholm, Large deviations and stochastic stability in population games, to appear, J. Dyn. Games.
[31]	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.
[32]	A. Traulsen, J. M. Pacheco and L. A. Imhof, Stochasticity and evolutionary stability, Phys. Rev. E (3), 74 (2006), 6pp. doi: 10.1103/PhysRevE. 74.021905.
[33]	X.-J. Wang, C.-L. Gu and J. Quan, Evolutionary game dynamics of the Wright-Fisher process with different selection intensities, J. Theoret. Biol., 465 (2019), 17-26. doi: 10.1016/j.jtbi.2019.01.006.
[34]	H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84. doi: 10.2307/2951778.