×

zbMATH — the first resource for mathematics

Evolution in games with randomly disturbed payoffs. (English) Zbl 1142.91343
Summary: We consider a simple model of stochastic evolution in population games. In our model, each agent occasionally receives opportunities to update his choice of strategy. When such an opportunity arises, the agent selects a strategy that is currently optimal, but only after his payoffs have been randomly perturbed. We prove that the resulting evolutionary process converges to approximate Nash equilibrium in both the medium run and the long run in three general classes of population games: stable games, potential games, and supermodular games. We conclude by contrasting the evolutionary process studied here with stochastic fictitious play.

MSC:
91A22 Evolutionary games
37N40 Dynamical systems in optimization and economics
91A15 Stochastic games, stochastic differential games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akin, E., The general topology of dynamical systems, (1993), American Mathematical Society Providence, RI · Zbl 0781.54025
[2] Benaı¨m, M., Recursive algorithms, urn processes, and chaining number of chain recurrent sets, Ergod. theory dynam. systems, 18, 53-87, (1998)
[3] Benaı¨m, M., Dynamics of stochastic approximation algorithms, ()
[4] Benaı¨m, M., Convergence with probability one of stochastic approximation algorithms whose average is cooperative, Nonlinearity, 13, 601-616, (2000)
[5] Benaı¨m, M.; Hirsch, M.W., Mixed equilibria and dynamical systems arising from repeated games, Games econ. behav., 29, 36-72, (1999)
[6] Benaı¨m, M.; Hirsch, M.W., On stochastic approximation algorithms with constant step size whose average is cooperative, Ann. appl. prob., 30, 850-869, (1999)
[7] Benaı¨m, M.; Weibull, J., Deterministic approximation of stochastic evolution in games, Econometrica, 71, 873-903, (2003) · Zbl 1152.91350
[8] Binmore, K.J.; Samuelson, L., Evolutionary drift and equilibrium selection, Rev. econ. stud., 66, 363-393, (1999) · Zbl 0948.91007
[9] Blume, L.E., The statistical mechanics of strategic interaction, Games econ. behav., 5, 387-424, (1993) · Zbl 0797.90123
[10] Blume, L.E., Population games, ()
[11] Brown, G.W., Iterative solutions of games by fictitious play, () · Zbl 0045.09902
[12] Conley, C.C., Isolated invariant sets and the Morse index, (1978), American Mathematical Society Providence, RI · Zbl 0397.34056
[13] Cooper, R.W., Coordination games: complementarities and macroeconomics, (1999), Cambridge University Press Cambridge · Zbl 0941.91018
[14] Cressman, R.; Garay, J.; Hofbauer, J., Evolutionary stability concepts for \(N\)-species frequency-dependent interactions, J. theoretical biol., 211, 1-10, (2001)
[15] Durrett, R., Probability: theory and examples, (2005), Thomson Brooks/Cole Belmont, CA · Zbl 1202.60002
[16] Foster, D.; Young, H.P., Stochastic evolutionary game dynamics, Theoretical population biol., 38, 219-232, (1990) · Zbl 0703.92015
[17] Fudenberg, D.; Kreps, D.M., Learning mixed equilibria, Games econ. behav., 5, 320-367, (1993) · Zbl 0790.90092
[18] Gilboa, I.; Matsui, A., Social stability and equilibrium, Econometrica, 59, 859-867, (1991) · Zbl 0728.90099
[19] Harsanyi, J.C., Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points, Int. J. game theory, 2, 1-23, (1973) · Zbl 0255.90084
[20] Hirsch, M.W., Systems of differential equations that are competitive or cooperative III: competing species, Nonlinearity, 1, 51-71, (1988) · Zbl 0658.34024
[21] J. Hofbauer, Stability for the best response dynamics, unpublished manuscript, Universität Wien, 1995.
[22] Hofbauer, J., From Nash and Brown to maynard Smith: equilibria, dynamics, and ESS, Selection, 1, 81-88, (2000)
[23] J. Hofbauer, Remarks on stable games, unpublished manuscript, Universität Wien, 2003.
[24] Hofbauer, J.; Hopkins, E., Learning in perturbed asymmetric games, Games econ. behav., 52, 133-152, (2005) · Zbl 1099.91028
[25] Hofbauer, J.; Sandholm, W.H., On the global convergence of stochastic fictitious play, Econometrica, 70, 2265-2294, (2002) · Zbl 1141.91336
[26] Hofbauer, J.; Sigmund, K., The theory of evolution and dynamical systems, (1988), Cambridge University Press Cambridge
[27] Kandori, M.; Mailath, G.J.; Rob, R., Learning, mutation, And long run equilibria in games, econometrica, 61, 29-56, (1993) · Zbl 0776.90095
[28] Kandori, M.; Rob, R., Evolution of equilibria in the long run: a general theory and applications, J. econ. theory, 65, 383-414, (1995) · Zbl 0837.90139
[29] Kaniovski, Y.; Young, H.P., Learning dynamics in games with stochastic perturbations, Games econ. behav., 11, 330-363, (1995) · Zbl 0841.90124
[30] Kurtz, T.G., Solutions of ordinary differential equations as limits of pure jump Markov processes, J. appl. prob., 7, 49-58, (1970) · Zbl 0191.47301
[31] Milgrom, P.; Roberts, J., Rationalizability, learning, And equilibrium in games with strategic complementarities, econometrica, 58, 1255-1278, (1990) · Zbl 0728.90098
[32] Monderer, D.; Shapley, L.S., Potential games, Games econ. behav., 14, 124-143, (1996) · Zbl 0862.90137
[33] Nemytskii, V.V.; Stepanov, V.V., Qualitative theory of differential equations, (1960), Princeton University Press Princeton · Zbl 0089.29502
[34] Robinson, C., Dynamical systems: stability, symbolic dynamics, and chaos, (1995), CRC Press Boca Raton, FL · Zbl 0853.58001
[35] Sandholm, W.H., Potential games with continuous player sets, J. econ. theory, 97, 81-108, (2001) · Zbl 0990.91005
[36] Sandholm, W.H., Evolution and equilibrium under inexact information, Games econ. behav., 44, 343-378, (2003) · Zbl 1089.91007
[37] W.H. Sandholm, Stable games, unpublished manuscript, University of Wisconsin, 2004.
[38] Sandholm, W.H., Negative externalities and evolutionary implementation, Rev. econ. stud., 72, 885-915, (2005) · Zbl 1136.91329
[39] Smith, H.L., Monotone dynamical systems: an introduction to the theory of competitive and cooperative systems, (1995), American Mathematical Society Providence, RI · Zbl 0821.34003
[40] Topkis, D., Equilibrium points in nonzero-sum \(n\)-person submodular games, SIAM J. control opt., 17, 773-787, (1979) · Zbl 0433.90091
[41] van Damme, E., Stability and perfection of Nash equilibria, (1991), Springer Berlin · Zbl 0833.90126
[42] Vives, X., Nash equilibrium with strategic complementarities, J. math. econ., 19, 305-321, (1990) · Zbl 0708.90094
[43] Young, H.P., The evolution of conventions, Econometrica, 61, 57-84, (1993) · Zbl 0773.90101
[44] Young, H.P., Individual strategy and social structure, (1998), Princeton University Press Princeton
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.