Nash-convergence of Game Dynamics and Complexity
Oliver Biggar, Christos Papadimitriou, Georgios Piliouras · 2026
Read Nash-convergence of Game Dynamics and Complexity by Oliver Biggar, Christos Papadimitriou, Georgios Piliouras (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-16016.txt.
Description
Biggar and colleagues ask whether Nash equilibria can be learned rather than computed, and whether the answer turns on game geometry or on computational hardness. An older impossibility proof used a degenerate game and strong uniform convergence assumptions, leaving ordinary nondegenerate games open.
The authors show that Nash convergent dynamics do exist for all nondegenerate games, and describe two very different families of them. The catch is cost: both families are intractable to compute locally unless complexity classes collapse. They frame this as an impossibility conjecture linking tractable local dynamics to P equalling PPAD, and prove a related barrier for dynamics with tractable Lyapunov functions. A proving game then explains why black box methods cannot settle the general conjecture.
Catalog record
| CREATOR | Oliver Biggar, Christos Papadimitriou, Georgios Piliouras |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-16016