{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T02:16:08Z","timestamp":1791425768772,"version":"4.3.3"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T00:00:00Z","timestamp":1557187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2019,5,7]]},"abstract":"<jats:p>\n            Learning dynamics have traditionally taken a secondary role to Nash equilibria in game theory. We propose a new approach that places the understanding of game dynamics over mixed strategy profiles as the central object of inquiry. We focus on the stable recurrent points of the dynamics,\n            <jats:italic>i.e.<\/jats:italic>\n            states which are likely to be revisited infinitely often; obviously, pure Nash equilibria are a special case of such behavior. We propose a new solution concept, the Markov-Conley Chain (MCC), which has several favorable properties: It is a simple randomized generalization of the pure Nash equilibrium, just like the mixed Nash equilibrium; every game has at least one MCC; an MCC is invariant under additive constants and positive multipliers of the players' utilities; there is a polynomial number of MCCs in any game, and they can be all computed in polynomial time; the MCCs can be shown to be, in a well defined sense, surrogates or traces of an important but elusive topological object called the sink chain component of the dynamics; finally, it can be shown that a natural game dynamics surely ends up at one of the MCCs of the game.\n          <\/jats:p>","DOI":"10.1145\/3331041.3331048","type":"journal-article","created":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T14:11:11Z","timestamp":1557324671000},"page":"53-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Game dynamics as the meaning of a game"],"prefix":"10.1145","volume":"16","author":[{"given":"Christos","family":"Papadimitriou","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgios","family":"Piliouras","sequence":"additional","affiliation":[{"name":"Singapore University of Technology and Design"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,5,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1765(91)90179-O"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993253534"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP816"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0717"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13235-012-0040-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0500"},{"key":"e_1_2_1_8_1","volume-title":"Isolated invariant sets and the morse index. cbms regional conference series in mathematics, 38","author":"Conley C.","unstructured":"Conley , C. 1978. Isolated invariant sets and the morse index. cbms regional conference series in mathematics, 38 . American Mathematical Society , Providence, RI 16. Conley, C. 1978. Isolated invariant sets and the morse index. cbms regional conference series in mathematics, 38. American Mathematical Society, Providence, RI 16."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.68"},{"key":"e_1_2_1_10_1","unstructured":"Harsanyi J. C. and Selten R. 1988. A general theory of equilibrium selection in games. MIT Press Books 1.  Harsanyi J. C. and Selten R. 1988. A general theory of equilibrium selection in games. MIT Press Books 1."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322655581"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2772366.2772368"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Hirsch M. W. Smale S. and Devaney R. L. 2012. Differential equations dynamical systems and an introduction to chaos. Academic press.  Hirsch M. W. Smale S. and Devaney R. L. 2012. Differential equations dynamical systems and an introduction to chaos. Academic press.","DOI":"10.1016\/B978-0-12-382010-5.00015-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00376"},{"key":"e_1_2_1_15_1","volume-title":"Evolutionary Games and Population Dynamics","author":"Hofbauer J.","unstructured":"Hofbauer , J. and sigmund, K. 1998. Evolutionary Games and Population Dynamics . Cambridge University Press , Cambridge . Hofbauer, J. and sigmund, K. 1998. Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175476"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0573"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1257\/jel.37.3.1067"},{"key":"e_1_2_1_20_1","volume-title":"et al","author":"Nash J. F.","year":"1950","unstructured":"Nash , J. F. et al . 1950 . Equilibrium points in n-person games. Proceedings of the national academy of sciences 36, 1, 48--49. Nash, J. F. et al. 1950. Equilibrium points in n-person games. Proceedings of the national academy of sciences 36, 1, 48--49."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940784"},{"key":"e_1_2_1_22_1","unstructured":"Papadimitriou C. and piliouras G. 2018. Games are algorithms: Game dynamics chain components and markov-conley chains. Arxiv Preprints.  Papadimitriou C. and piliouras G. 2018. Games are algorithms: Game dynamics chain components and markov-conley chains. Arxiv Preprints."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 861--873","author":"Piliouras G.","unstructured":"Piliouras , G. and Shamma , J. S . 2014. Optimization despite chaos: Convex relaxations to complex limit sets via poincar\u00e9 recurrence . In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 861--873 . Piliouras, G. and Shamma, J. S. 2014. Optimization despite chaos: Convex relaxations to complex limit sets via poincar\u00e9 recurrence. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 861--873."},{"key":"e_1_2_1_24_1","volume-title":"Population Games and Evolutionary Dynamics","author":"Sandholm W. H.","unstructured":"Sandholm , W. H. 2010. Population Games and Evolutionary Dynamics . MIT Press . Sandholm, W. H. 2010. Population Games and Evolutionary Dynamics. MIT Press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032086299"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(83)90445-9"},{"key":"e_1_2_1_27_1","volume-title":"Evolution and the Theory of Games","author":"Smith J. M.","unstructured":"Smith , J. M. 1982. Evolution and the Theory of Games . Cambridge university press . Smith, J. M. 1982. Evolution and the Theory of Games. Cambridge university press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(78)90077-9"},{"key":"e_1_2_1_29_1","volume-title":"Evolutionary Game Theory","author":"Weibull J. W.","unstructured":"Weibull , J. W. 1995. Evolutionary Game Theory . MIT Press ; Cambridge, MA : Cambridge University Press . Weibull, J. W. 1995. Evolutionary Game Theory. MIT Press; Cambridge, MA: Cambridge University Press."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951778"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331041.3331048","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3331041.3331048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:05Z","timestamp":1750206365000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331041.3331048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,7]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,5,7]]}},"alternative-id":["10.1145\/3331041.3331048"],"URL":"https:\/\/doi.org\/10.1145\/3331041.3331048","relation":{},"ISSN":["1551-9031"],"issn-type":[{"value":"1551-9031","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,7]]},"assertion":[{"value":"2019-05-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}