×

zbMATH — the first resource for mathematics

Metastability of logit dynamics for coordination games. (English) Zbl 1422.91095
Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1006-1024 (2012).

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: Link
References:
[1] Arash Asadpour , Amin Saberi, On the Inefficiency Ratio of Stable Equilibria in Congestion Games, Proceedings of the 5th International Workshop on Internet and Network Economics, December 14-18, 2009, Rome, Italy  [doi>10.1007/978-3-642-10841-9_54] · Zbl 1232.68178
[2] Vincenzo Auletta , Diodato Ferraioli , Francesco Pasquale , Paolo Penna , Giuseppe Persiano, Convergence to equilibrium of logit dynamics for strategic games, Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, June 04-06, 2011, San Jose, California, USA  [doi>10.1145/1989493.1989522] · Zbl 1349.91041
[3] Vincenzo Auletta , Diodato Ferraioli , Francesco Pasquale , Giuseppe Persiano, Mixing time and stationary expected social welfare of logit dynamics, Proceedings of the Third international conference on Algorithmic game theory, p.54-65, October 18-20, 2010, Athens, Greece · Zbl 1310.91031
[4] Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, and Giuseppe Persiano. Metastability of Logit Dynamics for Coordination Games, http://arxiv.org/abs/1107.4537, 2011. · Zbl 1417.91092
[5] Joel Beltran and Claudio Landim. Metastability of reversible finite state Markov processes. Stochastic Processes and their Applications, 121:1633–1677, 2011. · Zbl 1223.60060
[6] Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres. Glauber dynamics on trees and hyperbolic graphs. Probability Theory and Related Fields, 131:311–340, 2005. · Zbl 1075.60003
[7] Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5:387–424, 1993. · Zbl 0797.90123
[8] Anton Bovier. Metastability: a potential theoretic approach. In Proc. of the International Congress of Mathematicians, volume III, pages 499–518. European Mathematical Society, 2006. · Zbl 1099.60052
[9] Anton Bovier, Michael Eckhoff, Véronique Gayrard, and Markus Klein. Metastability in stochastic dynamics of disordered mean-field models. Probability Theory and Related Fields, 119:99–161, 2001. · Zbl 1012.82015
[10] Anton Bovier, Michael Eckhoff, Véronique Gayrard, and Markus Klein. Metastability and low lying spectra in reversible Markov chains. Communications in Mathematical Physics, 228:219–255, 2002. · Zbl 1010.60088
[11] Anton Bovier and Francesco Manzo. Metastability in Glauber dynamics in the low-temperature limit: Beyond exponential asymptotics. Journal of Statistical Physics, 107:757–779, 2002. · Zbl 1067.82041
[12] Xi Chen , Xiaotie Deng , Shang-Hua Teng, Settling the complexity of computing two-player Nash equilibria, Journal of the ACM (JACM), v.56 n.3, p.1-57, May 2009  [doi>10.1145/1516512.1516516] · Zbl 1325.68095
[13] Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The Complexity of Computing a Nash Equilibrium, SIAM Journal on Computing, v.39 n.1, p.195-259, May 2009  [doi>10.1137/070699652] · Zbl 1185.91019
[14] Jian Ding, Eyal Lubetzky, and Yuval Peres. Censored Glauber dynamics for the mean field Ising model. Journal of Statistical Physics, 137:407–458, 2009. · Zbl 1267.82110
[15] Jian Ding, Eyal Lubetzky, and Yuval Peres. The mixing time evolution of Glauber dynamics for the mean-field Ising model. Communications in Mathematical Physics, 289:725–764, 2009. · Zbl 1173.82018
[16] Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):1047–1071, 1993. · Zbl 0802.90143
[17] Henry Eyring. The activated complex in chemical reactions. Journal of Chemical Physics, 3:107–115, 1935.
[18] Mark Iosifovich Freidlin and Alexander D. Wentzell. Random Perturbations of Dynamical Systems. Springer, 1984.
[19] Serge Galam and Bernard Walliser. Ising model versus normal form game. Physica A: Statistical Mechanics and its Applications, 389(3):481–489, 2010.
[20] John C. Harsanyi and Reinhard Selten. A General Theory of Equilibrium Selection in Games. MIT Press, 1988. · Zbl 0693.90098
[21] Frank den Hollander. Metastability under stochastic dynamics. Stochastic Processes and their Applications, 114(1):1–26, 2004. · Zbl 1075.60127
[22] Frank den Hollander. Three lectures on metastability under stochastic dynamics. In Methods of Contemporary Mathematical Statistical Physics, volume 1970 of Lecture Notes in Mathematics, pages 1–24. Springer Berlin/Heidelberg, 2009.
[23] Hendrik Anthony Kramers. Brownian motion in a field of force and the diffusion model of chemical reactions. Physica, 7(4):284–304, 1940. · Zbl 0061.46405
[24] Hernán Larralde, Francois Leyvraz, and David P. Sanders. Metastability in Markov processes. Journal of Statistical Mechanics: Theory and Experiment, 2006(8):1–29, 2006.
[25] David Levin, Malwina Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probability Theory and Related Fields, 146:223–265, 2010. · Zbl 1187.82076
[26] David Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2008.
[27] Fabio Martinelli. Lectures on Glauber dynamics for discrete spin models. In Lectures on Probability Theory and Statistics (Saint-Flour, 1997), volume 1717 of Lecture Notes in Math., pages 93–191. Springer, 1999. · Zbl 1051.82514
[28] Andrea Montanari , Amin Saberi, Convergence to Equilibrium in Local Interaction Games, Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, p.303-312, October 25-27, 2009  [doi>10.1109/FOCS.2009.64] · Zbl 1292.91036
[29] Enzo Olivieri and Maria Eulália Vares. Large deviation and metastability. Cambridge University Press, 2005.
[30] H. Peyton Young. Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, 1998.
[31] H. Peyton Young. The diffusion of innovations in social networks. Economics Working Paper Archive number 437, Johns Hopkins University, Department of Economics, 2000.
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.