# Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics

arXiv: https://arxiv.org/abs/2203.14129 · HTML: https://mlsanity.com/paper/2203.14129/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 96 references that are in the map.
- First posted on arXiv 26 Mar 2022.

## Builds on (most cited first, 24 of 24)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Differentiable Game Mechanics](https://mlsanity.com/paper/1905.04926/) (2019)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Chaos, Extremism and Optimism: Volume Analysis of Learning in Games](https://mlsanity.com/paper/2005.13996/) (2020)
- [The route to chaos in routing games: When is Price of Anarchy too optimistic?](https://mlsanity.com/paper/1906.02486/) (2019)
- [Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System](https://mlsanity.com/paper/1903.01720/) (2019)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions](https://mlsanity.com/paper/2008.00540/) (2020)
- [From Darwin to Poincar'e and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory](https://mlsanity.com/paper/1910.01334/) (2019)
- [Smooth markets: A basic mechanism for organizing gradient-based learners](https://mlsanity.com/paper/2001.04678/) (2020)

## Built on by (most cited first, 4 of 4)

- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [The Replicator Dynamic, Chain Components and the Response Graph](https://mlsanity.com/paper/2209.15230/) (2022)
- [Fixed Point Computation: Beating Brute Force with Smoothed Analysis](https://mlsanity.com/paper/2501.10884/) (2025)
- [On algorithmically boosting fixed-point computations](https://mlsanity.com/paper/2304.04665/) (2023)

## Abstract (arXiv)

Under what conditions do the behaviors of players, who play a game repeatedly, converge to a Nash equilibrium? If one assumes that the players' behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this becomes a problem in the theory of dynamical systems. We apply this theory, and in particular the concepts of chain recurrence, attractors, and Conley index, to prove a general impossibility result: there exist games for which any dynamics is bound to have starting points that do not end up at a Nash equilibrium. We also prove a stronger result for ε-approximate Nash equilibria: there are games such that no game dynamics can converge (in an appropriate sense) to ε-Nash equilibria, and in fact the set of such games has positive measure. Further numerical results demonstrate that this holds for any ε between zero and 0.09. Our results establish that, although the notions of Nash equilibria (and its computation-inspired approximations) are universally applicable in all games, they are also fundamentally incomplete as predictors of long term behavior, regardless of the choice of dynamics.