{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T12:27:08Z","timestamp":1768134428404,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T00:00:00Z","timestamp":1634601600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T00:00:00Z","timestamp":1634601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Dyn Games Appl"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We calculate the frequency of games with a unique pure strategy Nash equilibrium in the ensemble of<jats:italic>n<\/jats:italic>-player,<jats:italic>m<\/jats:italic>-strategy normal-form games. To obtain the ensemble, we generate payoff matrices at random. Games with a unique pure strategy Nash equilibrium converge to the Nash equilibrium. We then consider a wider class of games that converge under a best-response dynamic, in which each player chooses their optimal pure strategy successively. We show that the frequency of convergent games with a given number of pure Nash equilibria goes to zero as the number of players or the number of strategies goes to infinity. In the 2-player case, we show that for large games with at least 10 strategies, convergent games with multiple pure strategy Nash equilibria are more likely than games with a unique Nash equilibrium. Our novel approach uses an<jats:italic>n<\/jats:italic>-partite graph to describe games.<\/jats:p>","DOI":"10.1007\/s13235-021-00401-3","type":"journal-article","created":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T21:40:44Z","timestamp":1634679644000},"page":"689-700","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["The Frequency of Convergent Games under Best-Response Dynamics"],"prefix":"10.1007","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5387-3169","authenticated-orcid":false,"given":"Samuel C.","family":"Wiese","sequence":"first","affiliation":[]},{"given":"Torsten","family":"Heinrich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,19]]},"reference":[{"key":"401_CR1","doi-asserted-by":"crossref","unstructured":"Alon N, Rudov K, Yariv L (2020) Dominance solvability in random Games, preprint","DOI":"10.2139\/ssrn.3850992"},{"key":"401_CR2","doi-asserted-by":"publisher","first-page":"535","DOI":"10.4153\/CJM-1960-047-1","volume":"12","author":"TL Austin","year":"1960","unstructured":"Austin TL (1960) The enumeration of point labelled chromatic graphs and trees. Can J Math 12:535\u2013545","journal-title":"Can J Math"},{"key":"401_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.cor.2017.01.008","volume":"89","author":"S Babu","year":"2018","unstructured":"Babu S, Mohan U (2018) An integrated approach to evaluating sustainability in supply chains using evolutionary game theory. Comput Oper Res 89:269\u2013283","journal-title":"Comput Oper Res"},{"key":"401_CR4","doi-asserted-by":"crossref","unstructured":"Challet D, Marsili M, Zhang Y (2004) Minority games. Oxford University Press","DOI":"10.1093\/oso\/9780198566403.001.0001"},{"key":"401_CR5","doi-asserted-by":"crossref","unstructured":"Cheng L, Liu G, Huang H, Wang X, Chen Y, Zhang J, Meng A, Yang R, Yu T (2020) Equilibrium analysis of general N-population multi-strategy games for generation-side long-term bidding: An evolutionary game perspective, J Clean Prod, 276","DOI":"10.1016\/j.jclepro.2020.124123"},{"key":"401_CR6","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 Comb Theory 8:134\u2013145","journal-title":"J Comb Theory"},{"issue":"6\u20137","key":"401_CR7","doi-asserted-by":"publisher","first-page":"1727","DOI":"10.1007\/s00285-016-1010-8","volume":"73","author":"MH Duong","year":"2016","unstructured":"Duong MH, Han TA (2016) Analysis of the expected density of internal equilibria in random evolutionary multi-player multi-strategy games. J Math Biol 73(6\u20137):1727\u20131760","journal-title":"J Math Biol"},{"key":"401_CR8","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/s13235-015-0148-0","volume":"6","author":"MH Duong","year":"2016","unstructured":"Duong MH, Han TA (2016) On the expected number of equilibria in a multi-player multi-strategy evolutionary game. Dyn Games Appl 6:324\u2013346","journal-title":"Dyn Games Appl"},{"issue":"12","key":"401_CR9","doi-asserted-by":"publisher","first-page":"5500","DOI":"10.1073\/pnas.0912214107","volume":"107","author":"CS Gokhale","year":"2010","unstructured":"Gokhale CS, Traulsen A (2010) Evolutionary games in the multiverse. Proc Nat Acad Sci USA 107(12):5500\u20135504","journal-title":"Proc Nat Acad Sci USA"},{"key":"401_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.6028\/jres.072B.012","volume":"72B","author":"K Goldberg","year":"1968","unstructured":"Goldberg K, Goldman AJ, Newman M (1968) The probability of an equilibrium point. J Res Nat Bur Standards Sect B 72B:93\u2013101","journal-title":"J Res Nat Bur Standards Sect B"},{"key":"401_CR11","doi-asserted-by":"publisher","first-page":"729","DOI":"10.2307\/2309755","volume":"64","author":"AJ Goldman","year":"1957","unstructured":"Goldman AJ (1957) The probability of a saddlepoint. Am Math Monthly 64:729\u2013730","journal-title":"Am Math Monthly"},{"key":"401_CR12","doi-asserted-by":"crossref","unstructured":"Heinrich T et\u00a0al. (2021) Best-response dynamics, playing sequences, and convergence to equilibrium in random games. arXiv: 2101.04222","DOI":"10.2139\/ssrn.3764151"},{"issue":"1","key":"401_CR13","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"},{"key":"401_CR14","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0165-4896(84)90090-8","volume":"7","author":"H Moulin","year":"1984","unstructured":"Moulin H (1984) Dominance solvability and Cournot stability. Math Soc Sci 7:83\u2013102","journal-title":"Math Soc Sci"},{"key":"401_CR15","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash JF (1950) Equilibrium points in n-person games. Proc Nat Acad Sci USA 36:48\u201349","journal-title":"Proc Nat Acad Sci USA"},{"issue":"2","key":"401_CR16","first-page":"286","volume":"54","author":"JF Nash","year":"1951","unstructured":"Nash JF (1951) Non-cooperative games. Ann Math 54(2):286\u2013295","journal-title":"Non-cooperative games. Ann Math"},{"issue":"2","key":"401_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1126\/sciadv.aat1328","volume":"5","author":"M Pangallo","year":"2019","unstructured":"Pangallo M, Heinrich T, Farmer JD (2019) Best reply structure and equilibrium convergence in generic games. Sci Adv 5(2):1\u201313","journal-title":"Sci Adv"},{"key":"401_CR18","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":"401_CR19","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. Internat J Game Theory 19(3):277\u2013286","journal-title":"Internat J Game Theory"},{"issue":"2","key":"401_CR20","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":"401_CR21","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"}],"container-title":["Dynamic Games and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13235-021-00401-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13235-021-00401-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13235-021-00401-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,11]],"date-time":"2023-11-11T11:20:38Z","timestamp":1699701638000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13235-021-00401-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,19]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["401"],"URL":"https:\/\/doi.org\/10.1007\/s13235-021-00401-3","relation":{},"ISSN":["2153-0785","2153-0793"],"issn-type":[{"value":"2153-0785","type":"print"},{"value":"2153-0793","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,19]]},"assertion":[{"value":"3 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}