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 and 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.

[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. BinmoreL. 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. 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.

[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. KandoriG. 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. 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.

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

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

[34]

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

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.

[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. BinmoreL. 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. 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.

[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. KandoriG. 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. 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.

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

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

[34]

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

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 and Games, 2021  doi: 10.3934/jdg.2021021

[2]

Yueling Li, Yingchao Xie, Xicheng Zhang. Large deviation principle for stochastic heat equation with memory. Discrete and 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 and Applied Analysis, 2022, 21 (1) : 213-238. 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 and Continuous Dynamical Systems - B, 2006, 6 (4) : 651-666. doi: 10.3934/dcdsb.2006.6.651

[5]

Xiaomin Huang, Yanpei Jiang, Wei Liu. Freidlin-Wentzell's large deviation principle for stochastic integral evolution equations. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022091

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

 Impact Factor: 

Metrics

  • PDF downloads (407)
  • HTML views (533)
  • Cited by (0)

Other articles
by authors

[Back to Top]