{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:03:04Z","timestamp":1783789384475,"version":"3.55.0"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,6,14]],"date-time":"2023-06-14T00:00:00Z","timestamp":1686700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,14]],"date-time":"2023-06-14T00:00:00Z","timestamp":1686700800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000913","name":"James S. McDonnell Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000913","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Baillie Gifford"},{"DOI":"10.13039\/501100015754","name":"Stiftung der Deutschen Wirtschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100015754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V007327\/1"],"award-info":[{"award-number":["EP\/V007327\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Game Theory"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We analyze the performance of the best-response dynamic across all normal-form games using a random games approach. The playing sequence\u2014the order in which players update their actions\u2014is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly small fraction of all (large) games when players take turns according to a fixed cyclic order. By contrast, when the playing sequence is random, the dynamic converges to a pure Nash equilibrium if one exists in almost all (large) games.<\/jats:p>","DOI":"10.1007\/s00182-023-00837-4","type":"journal-article","created":{"date-parts":[[2023,6,14]],"date-time":"2023-06-14T14:04:00Z","timestamp":1686751440000},"page":"703-735","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Best-response dynamics, playing sequences, and convergence to equilibrium in random games"],"prefix":"10.1007","volume":"52","author":[{"given":"Torsten","family":"Heinrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoojin","family":"Jang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Mungo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9966-1674","authenticated-orcid":false,"given":"Marco","family":"Pangallo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bassel","family":"Tarbush","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Wiese","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,14]]},"reference":[{"key":"837_CR1","doi-asserted-by":"crossref","unstructured":"Alon N, Rudov K, Yariv L (2021) Dominance solvability in random games. arXiv:2105.10743 (arXiv preprint)","DOI":"10.2139\/ssrn.3850992"},{"issue":"2","key":"837_CR2","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.orl.2021.01.009","volume":"49","author":"B Amiet","year":"2021","unstructured":"Amiet B, Collevecchio A, Hamza K (2021) When better is better than best. Oper Res Lett 49(2):260\u2013264","journal-title":"Oper Res Lett"},{"key":"837_CR3","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1504\/IJMOR.2021.117631","volume":"20","author":"B Amiet","year":"2021","unstructured":"Amiet B, Collevecchio A, Scarsini M, Zhong Z (2021) Pure nash equilibria and best-response dynamics in random games. Math Oper Res 20:20","journal-title":"Math Oper Res"},{"issue":"4","key":"837_CR4","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s11238-014-9436-1","volume":"78","author":"KR Apt","year":"2015","unstructured":"Apt KR, Simon S (2015) A classification of weakly acyclic games. Theory Decis 78(4):501\u2013524","journal-title":"Theory Decis"},{"key":"837_CR5","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/j.jet.2016.09.010","volume":"166","author":"I Arieli","year":"2016","unstructured":"Arieli I, Babichenko Y (2016) Random extensive form games. J Econ Theory 166:517\u2013535","journal-title":"J Econ Theory"},{"issue":"1","key":"837_CR6","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1214\/aop\/1176991491","volume":"17","author":"R Arratia","year":"1989","unstructured":"Arratia R, Goldstein L, Gordon L et al (1989) Two moments suffice for Poisson approximations: the Chen-Stein method. Ann Probab 17(1):9\u201325","journal-title":"Ann Probab"},{"key":"837_CR7","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.geb.2013.04.007","volume":"81","author":"Y Babichenko","year":"2013","unstructured":"Babichenko Y (2013) Best-reply dynamics in large binary-choice anonymous games. Games Econ Behav 81:130\u2013144","journal-title":"Games Econ Behav"},{"issue":"2","key":"837_CR8","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1209\/epl\/i1999-00456-2","volume":"48","author":"J Berg","year":"1999","unstructured":"Berg J, Weigt M (1999) Entropy and typical properties of nash equilibria in two-player games. EPL (Europhys Lett) 48(2):129\u2013135","journal-title":"EPL (Europhys Lett)"},{"key":"837_CR9","doi-asserted-by":"crossref","unstructured":"Berger N, Feldman M, Neiman O, Rosenthal M (2011) Dynamic inefficiency: Anarchy without stability. In: International symposium on algorithmic game theory. Springer, pp 57\u201368","DOI":"10.1007\/978-3-642-24829-0_7"},{"issue":"3","key":"837_CR10","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1006\/game.1993.1023","volume":"5","author":"LE Blume","year":"1993","unstructured":"Blume LE et al (1993) The statistical mechanics of strategic interaction. Games Econ Behav 5(3):387\u2013424","journal-title":"Games Econ Behav"},{"issue":"4","key":"837_CR11","first-page":"2728","volume":"37","author":"V Boucher","year":"2017","unstructured":"Boucher V (2017) Selecting equilibria using best-response dynamics. Econ Bull 37(4):2728\u20132734","journal-title":"Econ Bull"},{"key":"837_CR12","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.geb.2013.07.001","volume":"82","author":"O Candogan","year":"2013","unstructured":"Candogan O, Ozdaglar A, Parrilo PA (2013) Dynamics in near-potential games. Games Econo Behav 82:66\u201390","journal-title":"Games Econo Behav"},{"key":"837_CR13","doi-asserted-by":"crossref","unstructured":"Chauhan A, Lenzner P, Melnichenko A, Molitor L (2017) Selfish network creation with non-uniform edge cost. In: International symposium on algorithmic game theory. Springer, pp 160\u2013172","DOI":"10.1007\/978-3-319-66700-3_13"},{"key":"837_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2012.02.033","volume":"438","author":"G Christodoulou","year":"2012","unstructured":"Christodoulou G, Mirrokni VS, Sidiropoulos A (2012) Convergence and approximation in potential games. Theoret Comput Sci 438:13\u201327","journal-title":"Theoret Comput Sci"},{"issue":"17","key":"837_CR15","doi-asserted-by":"publisher","first-page":"9724","DOI":"10.1073\/pnas.95.17.9724","volume":"95","author":"JE Cohen","year":"1998","unstructured":"Cohen JE (1998) Cooperation and self-interest: pareto-inefficiency of Nash equilibria in finite random games. Proc Natl Acad Sci 95(17):9724\u20139731","journal-title":"Proc Natl Acad Sci"},{"key":"837_CR16","unstructured":"Coucheney P, Durand S, Gaujal B, Touati C (2014) General revision protocols in best response algorithms for potential games. In: 2014 7th international conference on NETwork Games, COntrol and OPtimization (NetGCoop). IEEE, pp 239\u2013246"},{"issue":"3","key":"837_CR17","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1214\/10-AAP715","volume":"21","author":"C Daskalakis","year":"2011","unstructured":"Daskalakis C, Dimakis AG, Mossel E et al (2011) Connectivity and equilibrium in random games. Ann Appl Probab 21(3):987\u20131016","journal-title":"Ann Appl Probab"},{"issue":"2","key":"837_CR18","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.geb.2004.12.001","volume":"54","author":"M Dindo\u0161","year":"2006","unstructured":"Dindo\u0161 M, Mezzetti C (2006) Better-reply dynamics and global convergence to Nash equilibrium in aggregative games. Games Econ Behav 54(2):261\u2013292","journal-title":"Games Econ Behav"},{"issue":"1","key":"837_CR19","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/S0021-9800(70)80015-1","volume":"8","author":"M Dresher","year":"1970","unstructured":"Dresher M (1970) Probability of a pure equilibrium point in $$n$$-person games. J Combin Theory 8(1):134\u2013145","journal-title":"J Combin Theory"},{"key":"837_CR20","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.peva.2018.09.007","volume":"129","author":"S Durand","year":"2019","unstructured":"Durand S, Garin F, Gaujal B (2019) Distributed best response dynamics with high playing rates in potential games. Perform Eval 129:40\u201359","journal-title":"Perform Eval"},{"key":"837_CR21","doi-asserted-by":"crossref","unstructured":"Durand S, Gaujal B (2016) Complexity and optimality of the best response algorithm in random potential games. In: International symposium on algorithmic game theory. Springer, pp 40\u201351","DOI":"10.1007\/978-3-662-53354-3_4"},{"issue":"1","key":"837_CR22","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s00224-013-9457-0","volume":"53","author":"A Fabrikant","year":"2013","unstructured":"Fabrikant A, Jaggard AD, Schapira M (2013) On the structure of weakly acyclic games. Theory Comput Syst 53(1):107\u2013122","journal-title":"Theory Comput Syst"},{"key":"837_CR23","doi-asserted-by":"crossref","unstructured":"Feldman M, Snappir Y, Tamir T (2017) The efficiency of best-response dynamics. In: International symposium on algorithmic game theory. Springer, pp 186\u2013198","DOI":"10.1007\/978-3-319-66700-3_15"},{"key":"837_CR24","doi-asserted-by":"crossref","unstructured":"Feldman M, Tamir T (2012) Convergence of best-response dynamics in games with conflicting congestion effects. In: International workshop on internet and network economics. Springer, pp 496\u2013503","DOI":"10.1007\/978-3-642-35311-6_38"},{"issue":"1","key":"837_CR25","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1006\/jeth.2000.2694","volume":"98","author":"JW Friedman","year":"2001","unstructured":"Friedman JW, Mezzetti C (2001) Learning in games by random sampling. J Econ Theory 98(1):55\u201384","journal-title":"J Econ Theory"},{"issue":"4","key":"837_CR26","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1073\/pnas.1109672110","volume":"110","author":"T Galla","year":"2013","unstructured":"Galla T, Farmer JD (2013) Complex dynamics in learning complicated games. Proc Natl Acad Sci 110(4):1232\u20131236","journal-title":"Proc Natl Acad Sci"},{"key":"837_CR27","doi-asserted-by":"crossref","unstructured":"Goemans M, Mirrokni V, Vetta A (2005) Sink equilibria and convergence. In: 46th annual IEEE symposium on foundations of computer science (FOCS\u201905). IEEE, pp 142\u2013151","DOI":"10.1109\/SFCS.2005.68"},{"issue":"2","key":"837_CR28","first-page":"93","volume":"72","author":"K Goldberg","year":"1968","unstructured":"Goldberg K, Goldman A, Newman M (1968) The probability of an equilibrium point. J Res Natl Bureau Standards 72(2):93\u2013101","journal-title":"J Res Natl Bureau Standards"},{"issue":"10","key":"837_CR29","doi-asserted-by":"publisher","first-page":"729","DOI":"10.2307\/2309755","volume":"64","author":"A Goldman","year":"1957","unstructured":"Goldman A (1957) The probability of a saddlepoint. Am Math Mon 64(10):729\u2013730","journal-title":"Am Math Mon"},{"key":"837_CR30","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1613\/jair.3213","volume":"40","author":"IA Kash","year":"2011","unstructured":"Kash IA, Friedman EJ, Halpern JY (2011) Multiagent learning in large anonymous games. J Artif Intell Res 40:571\u2013598","journal-title":"J Artif Intell Res"},{"key":"837_CR31","unstructured":"Kultti K, Salonen H, Vartiainen H (2011) Distribution of pure Nash equilibria in n-person games with random best responses. Technical Report\u00a071, Aboa Centre for Economics. Discussion Papers"},{"issue":"1","key":"837_CR32","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1111\/j.1468-0262.2005.00567.x","volume":"73","author":"A McLennan","year":"2005","unstructured":"McLennan A (2005) The expected number of Nash equilibria of a normal form game. Econometrica 73(1):141\u2013174","journal-title":"Econometrica"},{"issue":"2","key":"837_CR33","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.geb.2004.10.008","volume":"51","author":"A McLennan","year":"2005","unstructured":"McLennan A, Berg J (2005) Asymptotic expected number of Nash equilibria of two-player normal form games. Games Econ Behav 51(2):264\u2013295","journal-title":"Games Econ Behav"},{"key":"837_CR34","doi-asserted-by":"crossref","unstructured":"Mirrokni VS, Skopalik A (2009) On the complexity of Nash dynamics and sink equilibria. In: Proceedings of the 10th ACM conference on Electronic commerce, pp 1\u201310","DOI":"10.1145\/1566374.1566376"},{"issue":"1","key":"837_CR35","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14(1):124\u2013143","journal-title":"Games Econ Behav"},{"key":"837_CR36","doi-asserted-by":"crossref","unstructured":"Nisan N, Schapira M, Valiant G, Zohar A (2011) Best-response auctions. In: Proceedings of the 12th ACM conference on Electronic Commerce, pp 351\u2013360","DOI":"10.1145\/1993574.1993633"},{"key":"837_CR37","doi-asserted-by":"crossref","unstructured":"Pangallo M, Heinrich T, Farmer JD (2019) Best reply structure and equilibrium convergence in generic games. Sci Adv 5(2):eaat1328","DOI":"10.1126\/sciadv.aat1328"},{"key":"837_CR38","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.geb.2019.08.011","volume":"118","author":"T Pei","year":"2019","unstructured":"Pei T, Takahashi S (2019) Rationalizable strategies in random games. Games Econ Behav 118:110\u2013125","journal-title":"Games Econ Behav"},{"issue":"3","key":"837_CR39","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01755478","volume":"19","author":"IY Powers","year":"1990","unstructured":"Powers IY (1990) Limiting distributions of the number of pure strategy Nash equilibria in $$n$$-person games. Int J Game Theory 19(3):277\u2013286","journal-title":"Int J Game Theory"},{"key":"837_CR40","unstructured":"Quattropani M, Scarsini M (2020) Efficiency of equilibria in games with random payoffs. arXiv:2007.08518 (arXiv preprint)"},{"key":"837_CR41","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-60495-9_15","volume-title":"Understanding strategic interaction","author":"T Quint","year":"1997","unstructured":"Quint T, Shubik M, Yan D (1997) Dumb bugs vs. bright noncooperative players: a comparison. In: Albers W, G\u00fcth W, Hammerstein P, Moldvanu B, van Damme E (eds) Understanding strategic interaction. Springer, Berlin, pp 185\u2013197"},{"issue":"2","key":"837_CR42","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1006\/game.1999.0775","volume":"33","author":"Y Rinott","year":"2000","unstructured":"Rinott Y, Scarsini M (2000) On the number of pure strategy Nash equilibria in random games. Games Econ Behav 33(2):274\u2013293","journal-title":"Games Econ Behav"},{"issue":"1","key":"837_CR43","doi-asserted-by":"publisher","first-page":"4902","DOI":"10.1038\/s41598-018-22013-5","volume":"8","author":"JB Sanders","year":"2018","unstructured":"Sanders JB, Farmer JD, Galla T (2018) The prevalence of chaotic dynamics in games with many players. Sci Rep 8(1):4902","journal-title":"Sci Rep"},{"key":"837_CR44","volume-title":"Population games and evolutionary dynamics","author":"WH Sandholm","year":"2010","unstructured":"Sandholm WH (2010) Population games and evolutionary dynamics. MIT Press, New York"},{"issue":"2","key":"837_CR45","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/game.1995.1019","volume":"9","author":"W Stanford","year":"1995","unstructured":"Stanford W (1995) A note on the probability of $$k$$ pure Nash equilibria in matrix games. Games Econ Behav 9(2):238\u2013246","journal-title":"Games Econ Behav"},{"issue":"3","key":"837_CR46","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1287\/moor.21.3.726","volume":"21","author":"W Stanford","year":"1996","unstructured":"Stanford W (1996) The limit distribution of pure strategy Nash equilibria in symmetric bimatrix games. Math Oper Res 21(3):726\u2013733","journal-title":"Math Oper Res"},{"issue":"2","key":"837_CR47","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0165-4896(96)00826-8","volume":"33","author":"W Stanford","year":"1997","unstructured":"Stanford W (1997) On the distribution of pure strategy equilibria in finite games with vector payoffs. Math Soc Sci 33(2):115\u2013127","journal-title":"Math Soc Sci"},{"issue":"1","key":"837_CR48","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0165-1765(98)00219-5","volume":"62","author":"W Stanford","year":"1999","unstructured":"Stanford W (1999) On the number of pure strategy Nash equilibria in finite common payoffs games. Econ Lett 62(1):29\u201334","journal-title":"Econ Lett"},{"issue":"4","key":"837_CR49","doi-asserted-by":"publisher","first-page":"2734","DOI":"10.1137\/17M1139461","volume":"56","author":"B Swenson","year":"2018","unstructured":"Swenson B, Murray R, Kar S (2018) On best-response dynamics in potential games. SIAM J Control Optim 56(4):2734\u20132767","journal-title":"SIAM J Control Optim"},{"issue":"1","key":"837_CR50","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/j.geb.2007.10.003","volume":"63","author":"S Takahashi","year":"2008","unstructured":"Takahashi S (2008) The number of pure Nash equilibria in a random game with nondecreasing best responses. Games Econ Behav 63(1):328\u2013340","journal-title":"Games Econ Behav"},{"issue":"22","key":"837_CR51","first-page":"1","volume":"3","author":"S Takahashi","year":"2002","unstructured":"Takahashi S, Yamamori T (2002) The pure Nash equilibrium property and the quasi-acyclic condition. Econ Bull 3(22):1\u20136","journal-title":"Econ Bull"},{"issue":"2","key":"837_CR52","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/s13235-021-00401-3","volume":"12","author":"SC Wiese","year":"2022","unstructured":"Wiese SC, Heinrich T (2022) The frequency of convergent games under best-response dynamics. Dyn Games Appl 12(2):689\u2013700","journal-title":"Dyn Games Appl"},{"key":"837_CR53","doi-asserted-by":"publisher","DOI":"10.1515\/9780691214252","volume-title":"Individual strategy and social structure","author":"HP Young","year":"1998","unstructured":"Young HP (1998) Individual strategy and social structure. Princeton University Press, Princeton"}],"container-title":["International Journal of Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00182-023-00837-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00182-023-00837-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00182-023-00837-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T15:03:52Z","timestamp":1693580632000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00182-023-00837-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,14]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["837"],"URL":"https:\/\/doi.org\/10.1007\/s00182-023-00837-4","relation":{},"ISSN":["0020-7276","1432-1270"],"issn-type":[{"value":"0020-7276","type":"print"},{"value":"1432-1270","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,14]]},"assertion":[{"value":"20 February 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}