×

zbMATH — the first resource for mathematics

Metastability of logit dynamics for coordination games. (English) Zbl 1417.91092
Summary: Logit dynamics (Blume in Games Econ Behav 5:387-424, 1993) are randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. It can happen that the chain is “metastable”, i.e., on a time-scale shorter than the mixing time, it stays close to some probability distribution over the state space, while in a time-scale multiple of the mixing time it jumps from one distribution to another. In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the logit dynamics for some classes of coordination games. We first consider a pure \(n\)-player coordination game that highlights the distinctive features of our metastability notion based on distributions. Then, we study coordination games on the clique without a risk-dominant strategy (which are equivalent to the well-known Glauber dynamics for the Curie-Weiss model) and coordination games on a ring (both with and without risk-dominant strategy).

MSC:
91A22 Evolutionary games
91A26 Rationality and learning in game theory
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alós-Ferrer, C.; Netzer, N., The logit-response dynamics, Games Econ. Behav., 68, 413-427, (2010) · Zbl 1207.91017
[2] Alós-Ferrer, C.; Netzer, N., Robust stochastic stability, Econ. Theory, 58, 31-57, (2015) · Zbl 1319.91033
[3] Asadpour, A., Saberi, A.: On the inefficiency ratio of stable equilibria in congestion games. In: Proceedings of the 5th International Workshop on Internet and Network Economics (WINE’09), Lecture Notes in Computer Science, vol. 5929, Springer, pp. 545-552 (2009)
[4] Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., Persiano, G.: Logit dynamics with concurrent updates for local interaction games. In: Proceedings of 21st Annual European Symposium on Algorithms-ESA 2013, Sophia Antipolis, France, September 2-4, pp. 73-84 (2013a) · Zbl 1395.91073
[5] Auletta, V., Ferraioli, D., Pasquale, F., Persiano, G.: Metastability of logit dynamics for coordination games. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, pp. 1006-1024 (2012)
[6] Auletta, V.; Ferraioli, D.; Pasquale, F.; Persiano, G., Mixing time and stationary expected social welfare of logit dynamics, Theory Comput. Syst., 53, 3-40, (2013) · Zbl 1291.91026
[7] Auletta, V.; Ferraioli, D.; Pasquale, F.; Penna, P.; Persiano, G., Convergence to equilibrium of logit dynamics for strategic games, Algorithmica, 76, 110-142, (2016) · Zbl 1349.91041
[8] Berger, N.; Kenyon, C.; Mossel, E.; Peres, Y., Glauber dynamics on trees and hyperbolic graphs, Probab. Theory Relat. Fields, 131, 311-340, (2005) · Zbl 1075.60003
[9] Bianchi, A., Gaudilliere, A.: Metastable states, quasi-stationary and soft measures, mixing time asymprtotics via variational principles (2011). arXiv preprint arXiv:1103.1143
[10] Blume, LE, The statistical mechanics of strategic interaction, Games Econ. Behav., 5, 387-424, (1993) · Zbl 0797.90123
[11] Borowski, H., Marden, J.R., Frew, E.W.: Fast convergence in semi-anonymous potential games. In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), IEEE, pp. 2418-2423 (2013)
[12] Bovier, A.; Eckhoff, M.; Gayrard, V.; Klein, M., Metastability in stochastic dynamics of disordered mean-field models, Probab. Theory Relat. Fields, 119, 99-161, (2001) · Zbl 1012.82015
[13] Bovier, A.; Eckhoff, M.; Gayrard, V.; Klein, M., Metastability and low lying spectra in reversible Markov chains, Commun. Math. Phys., 228, 219-255, (2002) · Zbl 1010.60088
[14] Camerer, C.: Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press, Princeton (2003) · Zbl 1019.91001
[15] Collet, P., Martínez, S., San Martín, J., Quasi-Stationary Distributions: Markov Chains, Diffusions and Dynamical Systems. Springer, Berlin (2012)
[16] Ding, J.; Lubetzky, E.; Peres, Y., The mixing time evolution of Glauber dynamics for the mean-field Ising model, Commun. Math. Phys., 289, 725-764, (2009) · Zbl 1173.82018
[17] Ding, J.; Lubetzky, E.; Peres, Y., Censored Glauber dynamics for the mean field Ising model, J. Stat. Phys., 137, 407-458, (2009) · Zbl 1267.82110
[18] Ellison, G., Learning, local interaction, and coordination, Econometrica, 61, 1047-1071, (1993) · Zbl 0802.90143
[19] Ellison, G., Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution, Rev. Econ. Stud., 67, 17-45, (2000) · Zbl 0956.91027
[20] Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure nash equilibria. In: STOC, pp. 604-612 (2004) · Zbl 1192.91042
[21] Ferraioli, D., Ventre, C.: Metastability of asymptotically well-behaved potential games. In: Italiano, G., Pighizzini, G., Sannella, D. (eds.) Mathematical Foundations of Computer Science 2015. MFCS 2015. Lecture Notes in Computer Science, vol. 9235, pp. 311-323. Springer, Berlin, Heidelberg (2015) · Zbl 06482818
[22] Freidlin, M., Koralov, L.: Metastable distributions of Markov chains with rare transitions. J. Stat. Phys. 167(6), 1355-1375 (2017) · Zbl 1379.37006
[23] Freidlin, M.I., Wentzell, A.D.: Random Perturbations of Dynamical Systems. Springer, Berlin (1984) · Zbl 0522.60055
[24] Galam, S.; Walliser, B., Ising model versus normal form game, Phys. A Stat. Mech. Appl., 389, 481-489, (2010)
[25] Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988) · Zbl 0693.90098
[26] Keilson, J.: Markov Chain Modelsrarity and Exponentiality, vol. 28. Springer, Berlin (2012)
[27] Kreindler, G.E., Young, H.P.: Rapid innovation diffusion in social networks. In: Proceedings of the National Academy of Sciences, vol. 111, no. Supplement 3, pp. 10881-10888 (2014) · Zbl 1355.91067
[28] Kreindler, GE; Young, HP, Fast convergence in evolutionary equilibrium selection, Games Econ. Behav., 80, 39-67, (2013) · Zbl 1281.91026
[29] Levin, D., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2008)
[30] Levin, D.; Luczak, M.; Peres, Y., Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability, Probab. Theory Relat. Fields, 146, 223-265, (2010) · Zbl 1187.82076
[31] Marden, J.R., Shamma, J.S.: Revisiting log-linear learning: asynchrony, completeness and payoff-based implementation. In: 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE, pp. 1171-1172 (2010) · Zbl 1239.91017
[32] Martinelli, F.: Lectures on Glauber dynamics for discrete spin models. In: Lectures on Probability Theory and Statistics (Saint-Flour, 1997), Lecture Notes in Mathematics, vol. 1717, Springer, pp. 93-191 (1999)
[33] Monderer, D.; Shapley, LS, Potential games, Games Econ. Behav., 14, 124-143, (1996) · Zbl 0862.90137
[34] Montanari, A., Saberi, A.: Convergence to equilibrium in local interaction games. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS’09), IEEE (2009) · Zbl 1292.91036
[35] Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Cambridge (2010) · Zbl 1208.91003
[36] Sandholm, WH; Staudigl, M., Large deviations and stochastic stability in the small noise double limit, Theor. Econ., 11, 279-355, (2016) · Zbl 1395.91055
[37] Shah, D., Shin, J.: Dynamics in congestion games. In: ACM SIGMETRICS Performance Evaluation Review, vol. 38, ACM, pp. 107-118 (2010)
[38] Taylor, H.M., Karlin, S.: An Introduction to Stochastic Modeling. Academic, Cambridge (2014) · Zbl 0796.60001
[39] Young, H.P.: The diffusion of innovations in social networks. Economics Working Paper Archive number 437, Johns Hopkins University, Department of Economics (2000)
[40] Young, H.P.: Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, Princeton (1998)
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.