# Swim till You Sink: Computing the Limit of a Game

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 20 Aug 2024.

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

- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [A Generalized Training Approach for Multiagent Learning](https://mlsanity.com/paper/1909.12823/) (2019)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [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)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [The route to chaos in routing games: When is Price of Anarchy too optimistic?](https://mlsanity.com/paper/1906.02486/) (2019)
- [Multiagent Evaluation under Incomplete Information](https://mlsanity.com/paper/1909.09849/) (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)
- [Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs](https://mlsanity.com/paper/1611.00755/) (2016)
- [Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow](https://mlsanity.com/paper/2311.18295/) (2023)
- [Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence](https://mlsanity.com/paper/2106.04748/) (2021)
- [The Replicator Dynamic, Chain Components and the Response Graph](https://mlsanity.com/paper/2209.15230/) (2022)
- [Optimality Despite Chaos in Fee Markets](https://mlsanity.com/paper/2212.07175/) (2022)
- [No-Regret Learning in Games is Turing Complete](https://mlsanity.com/paper/2202.11871/) (2022)
- [The Attractor of the Replicator Dynamic in Zero-Sum Games](https://mlsanity.com/paper/2302.00253/) (2023)

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

- [Sink equilibria and the attractors of learning in games](https://mlsanity.com/paper/2502.07975/) (2025)

## Abstract (arXiv)

During 2023, two interesting results were proven about the limit behavior of game dynamics: First, it was shown that there is a game for which no dynamics converges to the Nash equilibria. Second, it was shown that the sink equilibria of a game adequately capture the limit behavior of natural game dynamics. These two results have created a need and opportunity to articulate a principled computational theory of the meaning of the game that is based on game dynamics. Given any game in normal form, and any prior distribution of play, we study the problem of computing the asymptotic behavior of a class of natural dynamics called the noisy replicator dynamics as a limit distribution over the sink equilibria of the game. When the prior distribution has pure strategy support, we prove this distribution can be computed efficiently, in near-linear time to the size of the best-response graph. When the distribution can be sampled -- for example, if it is the uniform distribution over all mixed strategy profiles -- we show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.