{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:13:53Z","timestamp":1761293633139,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T00:00:00Z","timestamp":1505779200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0371-8","type":"journal-article","created":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T14:59:44Z","timestamp":1505833184000},"page":"3078-3131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Metastability of Logit Dynamics for Coordination Games"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7875-3366","authenticated-orcid":false,"given":"Vincenzo","family":"Auletta","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7962-5200","authenticated-orcid":false,"given":"Diodato","family":"Ferraioli","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1595-5291","authenticated-orcid":false,"given":"Francesco","family":"Pasquale","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6579-4807","authenticated-orcid":false,"given":"Giuseppe","family":"Persiano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"issue":"2","key":"371_CR1","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/j.geb.2009.08.004","volume":"68","author":"C Al\u00f3s-Ferrer","year":"2010","unstructured":"Al\u00f3s-Ferrer, C., Netzer, N.: The logit-response dynamics. Games Econ. Behav. 68(2), 413\u2013427 (2010)","journal-title":"Games Econ. Behav."},{"issue":"1","key":"371_CR2","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00199-014-0809-z","volume":"58","author":"C Al\u00f3s-Ferrer","year":"2015","unstructured":"Al\u00f3s-Ferrer, C., Netzer, N.: Robust stochastic stability. Econ. Theory 58(1), 31\u201357 (2015)","journal-title":"Econ. Theory"},{"key":"371_CR3","doi-asserted-by":"crossref","unstructured":"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\u201909), Lecture Notes in Computer Science, vol. 5929, Springer, pp. 545\u2013552 (2009)","DOI":"10.1007\/978-3-642-10841-9_54"},{"key":"371_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013ESA 2013, Sophia Antipolis, France, September 2\u20134, pp. 73\u201384 (2013a)","DOI":"10.1007\/978-3-642-40450-4_7"},{"key":"371_CR5","doi-asserted-by":"crossref","unstructured":"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\u201319, pp. 1006\u20131024 (2012)","DOI":"10.1137\/1.9781611973099.80"},{"issue":"1","key":"371_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00224-013-9458-z","volume":"53","author":"V Auletta","year":"2013","unstructured":"Auletta, V., Ferraioli, D., Pasquale, F., Persiano, G.: Mixing time and stationary expected social welfare of logit dynamics. Theory Comput. Syst. 53(1), 3\u201340 (2013b)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"371_CR7","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/s00453-015-0025-7","volume":"76","author":"V Auletta","year":"2016","unstructured":"Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., Persiano, G.: Convergence to equilibrium of logit dynamics for strategic games. Algorithmica 76(1), 110\u2013142 (2016)","journal-title":"Algorithmica"},{"key":"371_CR8","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s00440-004-0369-4","volume":"131","author":"N Berger","year":"2005","unstructured":"Berger, N., Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields 131, 311\u2013340 (2005)","journal-title":"Probab. Theory Relat. Fields"},{"key":"371_CR9","unstructured":"Bianchi, A., Gaudilliere, A.: Metastable states, quasi-stationary and soft measures, mixing time asymprtotics via variational principles (2011). arXiv preprint arXiv:1103.1143"},{"key":"371_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1006\/game.1993.1023","volume":"5","author":"LE Blume","year":"1993","unstructured":"Blume, L.E.: The statistical mechanics of strategic interaction. Games Econ. Behav. 5, 387\u2013424 (1993)","journal-title":"Games Econ. Behav."},{"key":"371_CR11","doi-asserted-by":"crossref","unstructured":"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\u20132423 (2013)","DOI":"10.1109\/CDC.2013.6760242"},{"key":"371_CR12","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/PL00012740","volume":"119","author":"A Bovier","year":"2001","unstructured":"Bovier, A., Eckhoff, M., Gayrard, V., Klein, M.: Metastability in stochastic dynamics of disordered mean-field models. Probab. Theory Relat. Fields 119, 99\u2013161 (2001)","journal-title":"Probab. Theory Relat. Fields"},{"key":"371_CR13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s002200200609","volume":"228","author":"A Bovier","year":"2002","unstructured":"Bovier, A., Eckhoff, M., Gayrard, V., Klein, M.: Metastability and low lying spectra in reversible Markov chains. Commun. Math. Phys. 228, 219\u2013255 (2002)","journal-title":"Commun. Math. Phys."},{"key":"371_CR14","volume-title":"Behavioral Game Theory: Experiments in Strategic Interaction","author":"C Camerer","year":"2003","unstructured":"Camerer, C.: Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press, Princeton (2003)"},{"key":"371_CR15","doi-asserted-by":"crossref","unstructured":"Collet, P., Mart\u00ednez, S., San Mart\u00edn, J., Quasi-Stationary Distributions: Markov Chains, Diffusions and Dynamical Systems. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33131-2"},{"key":"371_CR16","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1007\/s00220-009-0781-9","volume":"289","author":"J Ding","year":"2009","unstructured":"Ding, J., Lubetzky, E., Peres, Y.: The mixing time evolution of Glauber dynamics for the mean-field Ising model. Commun. Math. Phys. 289, 725\u2013764 (2009a)","journal-title":"Commun. Math. Phys."},{"key":"371_CR17","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/s10955-009-9859-1","volume":"137","author":"J Ding","year":"2009","unstructured":"Ding, J., Lubetzky, E., Peres, Y.: Censored Glauber dynamics for the mean field Ising model. J. Stat. Phys. 137, 407\u2013458 (2009b)","journal-title":"J. Stat. Phys."},{"issue":"5","key":"371_CR18","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.2307\/2951493","volume":"61","author":"G Ellison","year":"1993","unstructured":"Ellison, G.: Learning, local interaction, and coordination. Econometrica 61(5), 1047\u20131071 (1993)","journal-title":"Econometrica"},{"issue":"1","key":"371_CR19","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1111\/1467-937X.00119","volume":"67","author":"G Ellison","year":"2000","unstructured":"Ellison, G.: Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution. Rev. Econ. Stud. 67(1), 17\u201345 (2000)","journal-title":"Rev. Econ. Stud."},{"key":"371_CR20","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure nash equilibria. In: STOC, pp. 604\u2013612 (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"371_CR21","doi-asserted-by":"crossref","unstructured":"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\u2013323. Springer, Berlin, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48054-0_26"},{"key":"371_CR22","unstructured":"Freidlin, M., Koralov, L.: Metastable distributions of Markov chains with rare transitions. J. Stat. Phys. 167(6), 1355\u20131375 (2017)"},{"key":"371_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-0176-9","volume-title":"Random Perturbations of Dynamical Systems","author":"MI Freidlin","year":"1984","unstructured":"Freidlin, M.I., Wentzell, A.D.: Random Perturbations of Dynamical Systems. Springer, Berlin (1984)"},{"issue":"3","key":"371_CR24","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.physa.2009.09.029","volume":"389","author":"S Galam","year":"2010","unstructured":"Galam, S., Walliser, B.: Ising model versus normal form game. Phys. A Stat. Mech. Appl. 389(3), 481\u2013489 (2010)","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"371_CR25","volume-title":"A General Theory of Equilibrium Selection in Games","author":"JC Harsanyi","year":"1988","unstructured":"Harsanyi, J.C., Selten, R.: A General Theory of Equilibrium Selection in Games. MIT Press, Cambridge (1988)"},{"key":"371_CR26","volume-title":"Markov Chain Modelsrarity and Exponentiality","author":"J Keilson","year":"2012","unstructured":"Keilson, J.: Markov Chain Modelsrarity and Exponentiality, vol. 28. Springer, Berlin (2012)"},{"key":"371_CR27","doi-asserted-by":"crossref","unstructured":"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\u201310888 (2014)","DOI":"10.1073\/pnas.1400842111"},{"key":"371_CR28","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.geb.2013.02.004","volume":"80","author":"GE Kreindler","year":"2013","unstructured":"Kreindler, G.E., Young, H.P.: Fast convergence in evolutionary equilibrium selection. Games Econ. Behav. 80, 39\u201367 (2013)","journal-title":"Games Econ. Behav."},{"key":"371_CR29","doi-asserted-by":"crossref","DOI":"10.1090\/mbk\/058","volume-title":"Markov Chains and Mixing Times","author":"D Levin","year":"2008","unstructured":"Levin, D., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2008)"},{"key":"371_CR30","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s00440-008-0189-z","volume":"146","author":"D Levin","year":"2010","unstructured":"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\u2013265 (2010)","journal-title":"Probab. Theory Relat. Fields"},{"key":"371_CR31","doi-asserted-by":"crossref","unstructured":"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\u20131172 (2010)","DOI":"10.1109\/ALLERTON.2010.5707044"},{"key":"371_CR32","doi-asserted-by":"crossref","unstructured":"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\u2013191 (1999)","DOI":"10.1007\/978-3-540-48115-7_2"},{"key":"371_CR33","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14, 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"key":"371_CR34","doi-asserted-by":"crossref","unstructured":"Montanari, A., Saberi, A.: Convergence to equilibrium in local interaction games. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS\u201909), IEEE (2009)","DOI":"10.1109\/FOCS.2009.64"},{"key":"371_CR35","volume-title":"Population Games and Evolutionary Dynamics","author":"WH Sandholm","year":"2010","unstructured":"Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Cambridge (2010)"},{"issue":"1","key":"371_CR36","doi-asserted-by":"crossref","first-page":"279","DOI":"10.3982\/TE1905","volume":"11","author":"WH Sandholm","year":"2016","unstructured":"Sandholm, W.H., Staudigl, M.: Large deviations and stochastic stability in the small noise double limit. Theor. Econ. 11(1), 279\u2013355 (2016)","journal-title":"Theor. Econ."},{"key":"371_CR37","doi-asserted-by":"crossref","unstructured":"Shah, D., Shin, J.: Dynamics in congestion games. In: ACM SIGMETRICS Performance Evaluation Review, vol.\u00a038, ACM, pp. 107\u2013118 (2010)","DOI":"10.1145\/1811039.1811052"},{"key":"371_CR38","volume-title":"An Introduction to Stochastic Modeling","author":"HM Taylor","year":"2014","unstructured":"Taylor, H.M., Karlin, S.: An Introduction to Stochastic Modeling. Academic, Cambridge (2014)"},{"key":"371_CR39","unstructured":"Young, H.P.: The diffusion of innovations in social networks. Economics Working Paper Archive number 437, Johns Hopkins University, Department of Economics (2000)"},{"key":"371_CR40","doi-asserted-by":"crossref","DOI":"10.1515\/9780691214252","volume-title":"Individual Strategy and Social Structure: An Evolutionary Theory of Institutions","author":"HP Young","year":"1998","unstructured":"Young, H.P.: Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, Princeton (1998)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0371-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0371-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0371-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,17]],"date-time":"2020-10-17T22:51:52Z","timestamp":1602975112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0371-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["371"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0371-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,9,19]]}}}