doi: 10.3934/jdg.2021015
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

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

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.

Citation: Ryoji Sawa. Stochastic stability in the large population and small mutation limits for coordination games. Journal of Dynamics & Games, doi: 10.3934/jdg.2021015
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

K. Binmore and L. Samuelson, Muddling through: Noisy equilibrium selection, J. Econom. Theory, 74 (1997), 235-265.  doi: 10.1006/jeth.1996.2255.  Google Scholar

[5]

K. G. BinmoreL. Samuelson and R. Vaughan, Musical chairs: Modeling noisy evolution, Games Econom. Behav., 11 (1995), 1-35.  doi: 10.1006/game.1995.1039.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

D. FudenbergM. A. NowakC. 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.  Google Scholar

[11]

S. Hart, Evolutionary dynamics and backward induction, Games Econom. Behav., 41 (2002), 227-264.  doi: 10.1016/S0899-8256(02)00502-X.  Google Scholar

[12]

W. Hoeffding, Asymptotically optimal tests for multinomial distributions, Ann. Math. Statist., 36 (1965), 369-401.  doi: 10.1214/aoms/1177700150.  Google Scholar

[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.  Google Scholar

[14]

M. KandoriG. J. Mailath and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), 29-56.  doi: 10.2307/2951777.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

H. OhtsukiP. 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.  Google Scholar

[18]

L. Samuelson, Stochastic stability in games with alternative best replies, J. Econom. Theory, 64 (1994), 35-65.  doi: 10.1006/jeth.1994.1053.  Google Scholar

[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.  Google Scholar

[20] W. H. Sandholm, Population Games and Evolutionary Dynamics, Economic Learning and Social Evolution, MIT Press, Cambridge, MA, 2010.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

M. Staudigl, S. Arigapudi and W. H. Sandholm, Large deviations and stochastic stability in population games, to appear, J. Dyn. Games. Google Scholar

[31]

C. TaylorD. FudenbergA. 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.  Google Scholar

[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.  Google Scholar

[33]

X.-J. WangC.-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.  Google Scholar

[34]

H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84.  doi: 10.2307/2951778.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

K. Binmore and L. Samuelson, Muddling through: Noisy equilibrium selection, J. Econom. Theory, 74 (1997), 235-265.  doi: 10.1006/jeth.1996.2255.  Google Scholar

[5]

K. G. BinmoreL. Samuelson and R. Vaughan, Musical chairs: Modeling noisy evolution, Games Econom. Behav., 11 (1995), 1-35.  doi: 10.1006/game.1995.1039.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

D. FudenbergM. A. NowakC. 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.  Google Scholar

[11]

S. Hart, Evolutionary dynamics and backward induction, Games Econom. Behav., 41 (2002), 227-264.  doi: 10.1016/S0899-8256(02)00502-X.  Google Scholar

[12]

W. Hoeffding, Asymptotically optimal tests for multinomial distributions, Ann. Math. Statist., 36 (1965), 369-401.  doi: 10.1214/aoms/1177700150.  Google Scholar

[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.  Google Scholar

[14]

M. KandoriG. J. Mailath and R. Rob, Learning, mutation, and long run equilibria in games, Econometrica, 61 (1993), 29-56.  doi: 10.2307/2951777.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

H. OhtsukiP. 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.  Google Scholar

[18]

L. Samuelson, Stochastic stability in games with alternative best replies, J. Econom. Theory, 64 (1994), 35-65.  doi: 10.1006/jeth.1994.1053.  Google Scholar

[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.  Google Scholar

[20] W. H. Sandholm, Population Games and Evolutionary Dynamics, Economic Learning and Social Evolution, MIT Press, Cambridge, MA, 2010.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

M. Staudigl, S. Arigapudi and W. H. Sandholm, Large deviations and stochastic stability in population games, to appear, J. Dyn. Games. Google Scholar

[31]

C. TaylorD. FudenbergA. 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.  Google Scholar

[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.  Google Scholar

[33]

X.-J. WangC.-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.  Google Scholar

[34]

H. P. Young, The evolution of conventions, Econometrica, 61 (1993), 57-84.  doi: 10.2307/2951778.  Google Scholar

Figure 1.  The literature on stochastic stability in the large population limit
Figure 2.  the best response regions
[1]

Mathias Staudigl, Srinivas Arigapudi, William H. Sandholm. Large deviations and Stochastic stability in Population Games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021021

[2]

Yueling Li, Yingchao Xie, Xicheng Zhang. Large deviation principle for stochastic heat equation with memory. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5221-5237. doi: 10.3934/dcds.2015.35.5221

[3]

Ran Wang, Jianliang Zhai, Shiling Zhang. Large deviation principle for stochastic Burgers type equation with reflection. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021175

[4]

Anna Amirdjanova, Jie Xiong. Large deviation principle for a stochastic navier-Stokes equation in its vorticity form for a two-dimensional incompressible flow. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 651-666. doi: 10.3934/dcdsb.2006.6.651

[5]

Masayuki Asaoka, Kenichiro Yamamoto. On the large deviation rates of non-entropy-approachable measures. Discrete & Continuous Dynamical Systems, 2013, 33 (10) : 4401-4410. doi: 10.3934/dcds.2013.33.4401

[6]

Kazuo Yamazaki. Large deviation principle for the micropolar, magneto-micropolar fluid systems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 913-938. doi: 10.3934/dcdsb.2018048

[7]

Boling Guo, Yan Lv, Wei Wang. Schrödinger limit of weakly dissipative stochastic Klein--Gordon--Schrödinger equations and large deviations. Discrete & Continuous Dynamical Systems, 2014, 34 (7) : 2795-2818. doi: 10.3934/dcds.2014.34.2795

[8]

Salah-Eldin A. Mohammed, Tusheng Zhang. Large deviations for stochastic systems with memory. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 881-893. doi: 10.3934/dcdsb.2006.6.881

[9]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[10]

Yongqiang Suo, Chenggui Yuan. Large deviations for neutral stochastic functional differential equations. Communications on Pure & Applied Analysis, 2020, 19 (4) : 2369-2384. doi: 10.3934/cpaa.2020103

[11]

Jan Sieber, Matthias Wolfrum, Mark Lichtner, Serhiy Yanchuk. On the stability of periodic orbits in delay equations with large delay. Discrete & Continuous Dynamical Systems, 2013, 33 (7) : 3109-3134. doi: 10.3934/dcds.2013.33.3109

[12]

Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195

[13]

King-Yeung Lam, Wei-Ming Ni. Limiting profiles of semilinear elliptic equations with large advection in population dynamics. Discrete & Continuous Dynamical Systems, 2010, 28 (3) : 1051-1067. doi: 10.3934/dcds.2010.28.1051

[14]

Feimin Huang, Yeping Li. Large time behavior and quasineutral limit of solutions to a bipolar hydrodynamic model with large data and vacuum. Discrete & Continuous Dynamical Systems, 2009, 24 (2) : 455-470. doi: 10.3934/dcds.2009.24.455

[15]

Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete & Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071

[16]

Freddy Dumortier. Sharp upperbounds for the number of large amplitude limit cycles in polynomial Lienard systems. Discrete & Continuous Dynamical Systems, 2012, 32 (5) : 1465-1479. doi: 10.3934/dcds.2012.32.1465

[17]

Shige Peng. Law of large numbers and central limit theorem under nonlinear expectations. Probability, Uncertainty and Quantitative Risk, 2019, 4 (0) : 4-. doi: 10.1186/s41546-019-0038-2

[18]

Martino Bardi, Annalisa Cesaroni, Daria Ghilli. Large deviations for some fast stochastic volatility models by viscosity methods. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 3965-3988. doi: 10.3934/dcds.2015.35.3965

[19]

Qiang Tao, Ying Yang. Exponential stability for the compressible nematic liquid crystal flow with large initial data. Communications on Pure & Applied Analysis, 2016, 15 (5) : 1661-1669. doi: 10.3934/cpaa.2016007

[20]

Michael Winkler. Emergence of large population densities despite logistic growth restrictions in fully parabolic chemotaxis systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2777-2793. doi: 10.3934/dcdsb.2017135

 Impact Factor: 

Metrics

  • PDF downloads (120)
  • HTML views (286)
  • Cited by (0)

Other articles
by authors

[Back to Top]