{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T20:43:56Z","timestamp":1775249036626,"version":"3.50.1"},"reference-count":47,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T00:00:00Z","timestamp":1539302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["NRF-NRFF2018-07"],"award-info":[{"award-number":["NRF-NRFF2018-07"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["Tier 2 Grant 2016-T2-1-170"],"award-info":[{"award-number":["Tier 2 Grant 2016-T2-1-170"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1408635"],"award-info":[{"award-number":["1408635"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer\u2019s (or, in another version Kakutani\u2019s) fixed point theorem, the most sophisticated result in his era\u2019s topology\u2014in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept\u2014this notion of \u201cthe outcome of the game\u201d\u2014every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints\/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games.<\/jats:p>","DOI":"10.3390\/e20100782","type":"journal-article","created":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T10:54:03Z","timestamp":1539341643000},"page":"782","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory"],"prefix":"10.3390","volume":"20","author":[{"given":"Christos","family":"Papadimitriou","sequence":"first","affiliation":[{"name":"Computer Science Department, Columbia University, New York, NY 10027, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6236-3566","authenticated-orcid":false,"given":"Georgios","family":"Piliouras","sequence":"additional","affiliation":[{"name":"Engineering Systems and Design (ESD), Singapore University of Technology and Design, Singapore 487372, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., and Papadimitriou, C.H. (2006). The Complexity of Computing a Nash Equilibrium, ACM Press.","DOI":"10.1145\/1132516.1132527"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0022-0531(03)00078-4","article-title":"From evolutionary to strategic stability","volume":"113","author":"Demichelis","year":"2003","journal-title":"J. Econ. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s13235-012-0040-0","article-title":"Perturbations of set-valued dynamical systems, with applications to game theory","volume":"2","author":"Hofbauer","year":"2012","journal-title":"Dyn. Games Appl."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Conley, C. (1978). Isolated invariant sets and the Morse index; CBMS Regional Conference Series in Mathematics, 38. Am. Math. Soc. Provid. RI, 16.","DOI":"10.1090\/cbms\/038"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Hofbauer, J., and Sigmund, K. (1998). Evolutionary Games and Population Dynamics, Cambridge University Press.","DOI":"10.1017\/CBO9781139173179"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","article-title":"The multiplicative weights update method: A meta algorithm and applications","volume":"8","author":"Arora","year":"2012","journal-title":"Theory Comput."},{"key":"ref_7","unstructured":"Fudenberg, D., and Levine, D.K. (1998). The Theory of Learning in Games, The MIT Press."},{"key":"ref_8","unstructured":"Kleinberg, R., Piliouras, G., and Tardos, \u00c9. (June, January 31). Multiplicative Updates Outperform Generic No-Regret Learning in Congestion Games. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (STOC), Bethesda, MD, USA."},{"key":"ref_9","unstructured":"Koopmans, T.C. (1951). Iterative Solutions of Games by Fictitious Play. Activity Analysis of Production and Allocation, Wiley."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"296","DOI":"10.2307\/1969530","article-title":"An Iterative Method of Solving a Game","volume":"54","author":"Robinson","year":"1951","journal-title":"Ann. Math."},{"key":"ref_11","first-page":"1","article-title":"Some topics in two-person games","volume":"52","author":"Shapley","year":"1964","journal-title":"Adv. Game Theory"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Frongillo, R., Papadimitriou, C.H., Pierrakos, G., and Valiant, G. (2010, January 18\u201320). On learning algorithms for Nash equilibria. Proceedings of the International Symposium on Algorithmic Game Theory, Athens, Greece.","DOI":"10.1007\/978-3-642-16170-4_11"},{"key":"ref_13","unstructured":"Kleinberg, R., Ligett, K., Piliouras, G., and Tardos, \u00c9. (2011, January 7\u20139). Beyond the Nash Equilibrium Barrier. Proceedings of the Symposium on Innovations in Computer Science (ICS), Beijing, China."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/1978721.1978727","article-title":"Beating the best Nash without regret","volume":"10","author":"Ligett","year":"2011","journal-title":"ACM SIGecom Exchang."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Piliouras, G., Nieto-Granda, C., Christensen, H.I., and Shamma, J.S. (2014, January 5\u20139). Persistent Patterns: Multi-agent Learning Beyond Equilibrium and Utility. Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, Paris, France.","DOI":"10.65109\/LFBS3162"},{"key":"ref_16","unstructured":"Mehta, R., Panageas, I., Piliouras, G., and Yazdanbod, S. (2016). The computational complexity of genetic diversity. LIPIcs-Leibniz International Proceedings in Informatics (ESA Conference), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"ref_17","unstructured":"Palaiopanos, G., Panageas, I., and Piliouras, G. (2017). Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. Advances in Neural Information Processing Systems, MIT Press."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. (2018, January 7\u201310). Cycles in adversarial regularized learning. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.172"},{"key":"ref_19","unstructured":"Sandholm, W.H. (2010). Population Games and Evolutionary Dynamics, MIT Press."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jeth.1997.2319","article-title":"Learning Through Reinforcement and Replicator Dynamics","volume":"77","author":"Sarin","year":"1997","journal-title":"J. Econ. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1516512.1516516","article-title":"Settling the Complexity of Computing Two-player Nash Equilibria","volume":"56","author":"Chen","year":"2009","journal-title":"JACM"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., and Piliouras, G. (2016, January 14\u201317). From Nash equilibria to chain recurrent sets: Solution concepts and topology. Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA.","DOI":"10.1145\/2840728.2840757"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Piliouras, G., and Shamma, J.S. (2014, January 5\u20137). Optimization despite chaos: Convex relaxations to complex limit sets via Poincar\u00e9 recurrence. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, Oregon, USA.","DOI":"10.1137\/1.9781611973402.64"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Bailey, J.P., and Piliouras, G. (2018, January 18\u201322). Multiplicative Weights Update in Zero-Sum Games. Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA.","DOI":"10.1145\/3219166.3219235"},{"key":"ref_25","unstructured":"Piliouras, G., and Schulman, L.J. (2018). Learning Dynamics and the Co-Evolution of Competing Sexual Species. Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS), ACM."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Nagarajan, S.G., Mohamed, S., and Piliouras, G. (2018, January 10\u201315). Three Body Problems in Evolutionary Game Dynamics: Convergence, Periodicity and Limit Cycles. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, Stockholm, Sweden.","DOI":"10.65109\/GXGY4690"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Mai, T., Mihail, M., Panageas, I., Ratcliff, W., Vazirani, V., and Yunker, P. (2018, January 18\u201322). Cycles in Zero-Sum Differential Games and Biological Diversity. Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA.","DOI":"10.1145\/3219166.3219227"},{"key":"ref_28","unstructured":"Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. (May, January 30). Training GANs with Optimism. Proceedings of the International Conference on Learning Representations, Vancouver, BC, Canada."},{"key":"ref_29","unstructured":"Mertikopoulos, P., Zenati, H., Lecouat, B., Foo, C.S., Chandrasekhar, V., and Piliouras, G. (arXiv, 2018). Mirror descent in saddle-point problems: Going the extra (gradient) mile, arXiv."},{"key":"ref_30","unstructured":"Balduzzi, D., Racaniere, S., Martens, J., Foerster, J., Tuyls, K., and Graepel, T. (2018, January 10\u201315). The Mechanics of n-Player Differentiable Games. Proceedings of the International Conference on Machine Learning (ICML), Stockholm, Sweden."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0025-5564(78)90077-9","article-title":"Evolutionary stable strategies and game dynamics","volume":"40","author":"Taylor","year":"1978","journal-title":"Math. Biosci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0022-5193(83)90445-9","article-title":"Replicator dynamics","volume":"100","author":"Schuster","year":"1983","journal-title":"J. Theor. Biol."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF00305762","article-title":"Dynamics of Games and Genes: Discrete Versus Continuous Time","volume":"17","author":"Losert","year":"1983","journal-title":"J. Math. Biol."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Young, H.P. (2004). Strategic Learning and Its Limits, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199269181.001.0001"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1673","DOI":"10.3390\/e12071673","article-title":"Principle of Minimum Discrimination Information and Replica Dynamics","volume":"12","author":"Karev","year":"2010","journal-title":"Entropy"},{"key":"ref_36","unstructured":"Weibull, J.W. (1997). Evolutionary Game Theory, MIT Press."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Bhatia, N.P., and Szeg\u00f6, G.P. (1970). Stability Theory of Dynamical Systems, Springer.","DOI":"10.1007\/978-3-642-62006-5"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Alongi, J.M., and Nelson, G.S. (2007). Recurrence and Topology, American Mathematical Society.","DOI":"10.1090\/gsm\/085"},{"key":"ref_39","first-page":"5","article-title":"Sur le probl\u00e8me des trois corps et les \u00e9quations de la dynamique","volume":"13","year":"1890","journal-title":"Acta Math."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Barreira, L. (2006). Poincare recurrence: Old and new. XIVth International Congress on Mathematical Physics, World Scientific.","DOI":"10.1142\/9789812704016_0039"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Meiss, J. (2007). Differential Dynamical Systems, SIAM.","DOI":"10.1137\/1.9780898718232"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/BF02219371","article-title":"Chain Recurrence, Semiflows, and Gradients","volume":"7","author":"Hurley","year":"1995","journal-title":"J. Dyn. Differ. Equat."},{"key":"ref_43","first-page":"1313","article-title":"Unraveling in guessing games: An experimental study","volume":"85","author":"Nagel","year":"1995","journal-title":"Am. Econ. Rev."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"273","DOI":"10.3390\/g6030273","article-title":"Bargaining over strategies of non-cooperative games","volume":"6","author":"Attanasi","year":"2015","journal-title":"Games"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/0167-2681(94)90108-2","article-title":"Learning a mixed strategy equilibrium in the laboratory","volume":"25","author":"Bloomfield","year":"1994","journal-title":"J. Econ. Behav. Organ."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Panageas, I., and Piliouras, G. (2016, January 24\u201328). Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction. Proceedings of the 2016 ACM Conference on Economics and Computation, Maastricht, The Netherlands.","DOI":"10.1145\/2940716.2940784"},{"key":"ref_47","unstructured":"Cover, T.M., and Thomas, J.A. (1991). Elements of Information Theory, Wiley."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/10\/782\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T19:43:55Z","timestamp":1775245435000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/10\/782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,12]]},"references-count":47,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["e20100782"],"URL":"https:\/\/doi.org\/10.3390\/e20100782","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,12]]}}}