{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:56Z","timestamp":1750221116593,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T00:00:00Z","timestamp":1549411200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M018113\/1"],"award-info":[{"award-number":["EP\/M018113\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"GNCS-INdAM"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>Convergence rate and stability of a solution concept are classically measured in terms of \u201ceventually\u201d and \u201cforever,\u201d respectively. In the wake of recent computational criticisms to this approach, we study whether these timeframes can be updated to have states computed \u201cquickly\u201d and stable for \u201clong enough\u201d.<\/jats:p>\n          <jats:p>\n            Logit dynamics allows irrationality in players\u2019 behavior and may take time exponential in the number of players\n            <jats:italic>n<\/jats:italic>\n            to converge to a stable state (i.e., a certain distribution over pure strategy profiles). We prove that every potential game, for which the behavior of the logit dynamics is not chaotic as\n            <jats:italic>n<\/jats:italic>\n            increases, admits distributions stable for a super-polynomial number of steps in\n            <jats:italic>n<\/jats:italic>\n            no matter the players\u2019 irrationality and the starting profile of the dynamics. The convergence rate to these\n            <jats:italic>metastable distributions<\/jats:italic>\n            is polynomial in\n            <jats:italic>n<\/jats:italic>\n            when the players are not too rational.\n          <\/jats:p>\n          <jats:p>\n            Our proofs build upon the new concept of\n            <jats:italic>partitioned Markov chains<\/jats:italic>\n            , which might be of independent interest, and a number of involved technical contributions.\n          <\/jats:p>","DOI":"10.1145\/3301315","type":"journal-article","created":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T19:17:28Z","timestamp":1549480648000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Metastability of the Logit Dynamics for Asymptotically Well-Behaved Potential Games"],"prefix":"10.1145","volume":"15","author":[{"given":"Diodato","family":"Ferraioli","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Salerno, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmine","family":"Ventre","sequence":"additional","affiliation":[{"name":"University of Essex, Colchester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.08.004"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_54"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0025-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9458-z"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0371-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.75"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1023"},{"key":"e_1_2_1_9_1","volume-title":"Proc. of the International Congress of Mathematicians","author":"Bovier A.","year":"2006","unstructured":"A. Bovier . 2006 . Metastability: A potential theoretic approach . In Proc. of the International Congress of Mathematicians , Vol. III . European Mathematical Society, 499--518. A. Bovier. 2006. Metastability: A potential theoretic approach. In Proc. of the International Congress of Mathematicians, Vol. III. European Mathematical Society, 499--518."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.20"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.05.004"},{"key":"e_1_2_1_12_1","unstructured":"E. Cruciani E. Natale and G. Scornavacca. 2018. On the metastability of quadratic majority dynamics on clustered graphs and its biological implications. ArXiv e-prints (2018). arxiv:1805.01406  E. Cruciani E. Natale and G. Scornavacca. 2018. On the metastability of quadratic majority dynamics on clustered graphs and its biological implications. ArXiv e-prints (2018). arxiv:1805.01406"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746618"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483703"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-009-9859-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-009-0781-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951493"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.08.011"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201915)","volume":"9235","author":"Ferraioli D.","unstructured":"D. Ferraioli and C. Ventre . 2015. Metastability of asymptotically well-behaved potential games - (extended abstract) . In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201915) , Milan, Italy, August 24-28, Part II (Lecture Notes in Computer Science) , Vol. 9235 . Springer, 311--323. D. Ferraioli and C. Ventre. 2015. Metastability of asymptotically well-behaved potential games - (extended abstract). In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201915), Milan, Italy, August 24-28, Part II (Lecture Notes in Computer Science), Vol. 9235. Springer, 311--323."},{"key":"e_1_2_1_21_1","volume-title":"Metastability under stochastic dynamics. Stochastic Processes and their Applications 114, 1","author":"Hollander F.","year":"2004","unstructured":"F. Hollander . 2004. Metastability under stochastic dynamics. Stochastic Processes and their Applications 114, 1 ( 2004 ), 1--26. F. Hollander. 2004. Metastability under stochastic dynamics. Stochastic Processes and their Applications 114, 1 (2004), 1--26."},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Mathematics","volume-title":"Methods of Contemporary Mathematical Statistical Physics","author":"Hollander F.","unstructured":"F. Hollander . 2009. Three lectures on metastability under stochastic dynamics . In Methods of Contemporary Mathematical Statistical Physics . Lecture Notes in Mathematics , Vol. 1970 . Springer Berlin\/Heidelberg , 1--24. F. Hollander. 2009. Three lectures on metastability under stochastic dynamics. In Methods of Contemporary Mathematical Statistical Physics. Lecture Notes in Mathematics, Vol. 1970. Springer Berlin\/Heidelberg, 1--24."},{"key":"e_1_2_1_23_1","unstructured":"R. A. Horn and C. R. Johnson. 1990. Matrix Analysis. Cambridge University Press.   R. A. Horn and C. R. Johnson. 1990. Matrix Analysis. Cambridge University Press."},{"volume-title":"Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI'02)","author":"Kearns M. J.","key":"e_1_2_1_24_1","unstructured":"M. J. Kearns and Y. Mansour . 2002. Efficient Nash computation in large population games with bounded influence . In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI'02) . AUAI, 259--266. M. J. Kearns and Y. Mansour. 2002. Efficient Nash computation in large population games with bounded influence. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI'02). AUAI, 259--266."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-008-0189-z"},{"key":"e_1_2_1_26_1","volume-title":"Markov Chains and Mixing Times","volume":"107","author":"Levin D.","unstructured":"D. Levin , Y. Peres , and E. L. Wilmer . 2008 . Markov Chains and Mixing Times , Vol. 107 . American Mathematical Society. D. Levin, Y. Peres, and E. L. Wilmer. 2008. Markov Chains and Mixing Times, Vol. 107. American Mathematical Society."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1995.1023"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.64"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_32_1","volume-title":"Large Deviation and Metastability","volume":"100","author":"Olivieri E.","unstructured":"E. Olivieri and M. E. Vares . 2005 . Large Deviation and Metastability , Vol. 100 . Cambridge University Press. E. Olivieri and M. E. Vares. 2005. Large Deviation and Metastability, Vol. 100. Cambridge University Press."},{"key":"e_1_2_1_33_1","first-page":"145","article-title":"On rank one matrices and invariant subspaces","volume":"10","author":"Osnaga S.","year":"2005","unstructured":"S. Osnaga . 2005 . On rank one matrices and invariant subspaces . Balkan Journal of Geometry and Its Applications 10 , 1 (2005), 145 . S. Osnaga. 2005. On rank one matrices and invariant subspaces. Balkan Journal of Geometry and Its Applications 10, 1 (2005), 145.","journal-title":"Balkan Journal of Geometry and Its Applications"},{"volume-title":"The Economy as a Complex Evolving System","author":"Young H. Peyton","key":"e_1_2_1_34_1","unstructured":"H. Peyton Young . 2003. The diffusion of innovations in social networks . In The Economy as a Complex Evolving System , Lawrence E. Blume and Steven N. Durlauf (Eds.), Vol. III . Oxford University Press . H. Peyton Young. 2003. The diffusion of innovations in social networks. In The Economy as a Complex Evolving System, Lawrence E. Blume and Steven N. Durlauf (Eds.), Vol. III. Oxford University Press."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_36_1","volume-title":"Irrational exuberance: Revised and expanded","author":"Shiller R. J.","unstructured":"R. J. Shiller . 2015. Irrational exuberance: Revised and expanded ( 3 rd edition). Princeton University Press . R. J. Shiller. 2015. Irrational exuberance: Revised and expanded (3rd edition). Princeton University Press.","edition":"3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374428"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9531.2006.00176.x"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:04Z","timestamp":1750208524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,6]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3301315"],"URL":"https:\/\/doi.org\/10.1145\/3301315","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,2,6]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}