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

CREATOROliver Biggar, Christos Papadimitriou, Georgios Piliouras
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-16016

Browse the full library · About the Tower of Babel