arxiv: 2602.16016 · v2 · submitted 2026-02-17 · 💻 cs.GT · cs.CC

Recognition: no theorem link

On the Complexity of Learning Nash Equilibria

Oliver Biggar , Christos Papadimitriou , Georgios Piliouras

Authors on Pith no claims yet

Pith reviewed 2026-05-15 21:27 UTC · model grok-4.3

classification 💻 cs.GT cs.CC

keywords Nash equilibriumlearning dynamicscomputational complexityPPADLyapunov functiongame theorylocal tractability

0 comments

The pith

If a locally tractable dynamic converges to Nash equilibria then P equals PPAD.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks whether there exist dynamics that players can compute locally at each strategy profile and that are guaranteed to converge to Nash equilibria. Earlier impossibility results required degenerate games and uniform convergence, so the authors construct two families of convergent dynamics that work for all non-degenerate games. These families, however, cannot be computed locally in polynomial time unless P equals PPAD. The authors therefore state a complexity-theoretic Impossibility Conjecture: any locally tractable Nash-convergent dynamic implies P equals PPAD. They strengthen the picture by showing that the same local-tractability assumption plus a locally tractable Lyapunov function collapses PPAD to CLS, and they introduce a Proving Game to explain why black-box reductions cannot separate convergent from non-convergent dynamics in polynomial time.

Core claim

While Nash-convergent dynamics exist for non-degenerate games, any such dynamic whose local steps are polynomial-time computable would imply P equals PPAD. The paper proves this by exhibiting two explicit families of convergent dynamics, showing each family is locally intractable unless complexity classes collapse, establishing a related collapse for dynamics equipped with tractable Lyapunov functions, and supplying a Proving Game that demonstrates why black-box reductions fail to distinguish convergence properties in polynomial time.

What carries the argument

The Impossibility Conjecture, which states that local tractability of a Nash-convergent dynamic at each step forces P to equal PPAD.

If this is right

No polynomial-time local update rule can guarantee convergence to Nash equilibria unless P equals PPAD.
Any locally tractable dynamic possessing a locally tractable Lyapunov function cannot exist unless PPAD equals CLS.
Black-box polynomial-time algorithms cannot reliably distinguish convergent from non-convergent dynamics.
Convergent dynamics for non-degenerate games still require super-polynomial local computation in the worst case unless the complexity collapse occurs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical equilibrium learning may therefore need either global coordination or exponential local effort in the worst case.
The Proving Game technique may extend to other questions about proving convergence properties of dynamics in algorithmic game theory.
The result ties the topological character of equilibrium sets directly to local computational hardness without requiring uniform convergence assumptions.

Load-bearing premise

The dynamics are allowed to take exponentially many steps so long as each individual step remains polynomial-time computable, and the argument applies only to non-degenerate games.

What would settle it

An explicit description of a dynamic whose local update rule at any strategy profile runs in polynomial time and whose trajectories reach a Nash equilibrium from every starting point in every non-degenerate game.

read the original abstract

We know that the Nash equilibria of a game cannot be computed efficiently unless $P = PPAD$. But can they be learned? Are there dynamics that (1) can be computed efficiently by the players at each strategy profile and (2) are guaranteed to converge to the Nash equilibria? This is a question as ancient as the Nash equilibrium itself, and antedates by many decades current complexity considerations about it. It was recently proved in MPPS23 that no such dynamics can exist in general; however, the game used in that proof is degenerate, and a strong assumption of uniform convergence to a continuum of Nash equilibria is employed. We point out that both assumptions are necessary for that proof, because Nash-convergent dynamics do exist, which converge to all Nash equilibria in non-degenerate games; in fact we describe two very different families of such dynamics. However, we show that both of these families are intractable to compute locally, unless complexity classes collapse. We formulate a complexity theoretic Impossibility Conjecture: if a locally tractable Nash-convergent dynamic exists then $P=PPAD$. This is a novel kind of conjecture, combining topology and complexity, because the dynamic is only required to be tractable locally -- it could take exponentially many steps to converge, so long as the work done at each step is polynomial. Next, we show that any locally tractable dynamic which possesses a locally tractable Lyapunov function cannot exist unless $PPAD = CLS$. Finally, for the most general impossibility conjecture, we provide a complexity-theoretic explanation why it may be difficult to settle: we introduce a Proving Game to demonstrate that black-box reductions cannot distinguish between convergent and non-convergent dynamics in polynomial time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows that Nash-convergent dynamics exist for non-degenerate games but are locally intractable unless P=PPAD, and conjectures this holds in general.

read the letter

The core contribution is that earlier impossibility results for locally computable Nash-convergent dynamics needed degenerate games and uniform convergence, so the authors build two explicit families that converge on non-degenerate games. They then show both families require solving PPAD-hard problems at each step unless the classes collapse. The new Impossibility Conjecture ties local tractability directly to P=PPAD, and they add a reduction to CLS for dynamics with tractable Lyapunov functions plus a Proving Game argument for why black-box separations are hard in polynomial time. This last piece is useful because it explains why the general question may resist quick resolution even though the specific families are settled. The constructions and reductions look internally consistent with standard techniques in the area. The main limitation is that the conjecture itself is left open, and the local-tractability definition allows exponential total steps, which weakens the negative result relative to a fully polynomial-time guarantee. Still, the distinction between existence and local computability is cleanly drawn. This work is aimed at people working on dynamics in games and the complexity of equilibria. It refines the existing PPAD picture without overclaiming, so it deserves a serious referee.

Referee Report

3 major / 2 minor

Summary. The paper examines whether Nash equilibria can be learned through dynamics that are locally computable at each strategy profile and guaranteed to converge to equilibria. It notes that prior impossibility results (MPPS23) rely on degenerate games and uniform convergence assumptions, then constructs two families of Nash-convergent dynamics that work on non-degenerate games. It proves these families are locally intractable unless P=PPAD, formulates the Impossibility Conjecture that any locally tractable Nash-convergent dynamic implies P=PPAD, shows that dynamics possessing a locally tractable Lyapunov function cannot exist unless PPAD=CLS, and introduces a Proving Game to argue that black-box reductions cannot distinguish convergent from non-convergent locally tractable dynamics in polynomial time.

Significance. If the intractability results and conjecture hold, the work establishes a novel link between the topological structure of games and complexity classes, showing that local tractability of convergent dynamics is unlikely even when exponential convergence time is permitted. The explicit families of dynamics, the Lyapunov-function collapse, and the Proving Game construction are concrete contributions that clarify barriers to general impossibility proofs and extend prior negative results beyond degenerate cases.

major comments (3)

[Existence of Nash-convergent dynamics] The section constructing the two families of Nash-convergent dynamics states that they converge to all equilibria in non-degenerate games, but the argument for convergence (and why it evades the MPPS23 negative result) is load-bearing for the subsequent intractability claims; an explicit verification or proof outline that both families reach every equilibrium, not merely some, is required.
[Impossibility Conjecture] The Impossibility Conjecture is formulated for locally tractable dynamics (polynomial work per step, exponential steps allowed). The reduction showing intractability of the two explicit families must be checked to confirm it does not inadvertently assume polynomial total time rather than per-step tractability, as this distinction is central to the conjecture's novelty.
[Proving Game] In the Proving Game construction, the claim that black-box reductions cannot separate convergent from non-convergent dynamics in polynomial time is used to explain why the general conjecture may be difficult to settle. The argument should explicitly identify the class of oracles or query models under which indistinguishability holds, to rule out the possibility that non-black-box techniques could still separate the cases.

minor comments (2)

[References] The citation to MPPS23 appears only in abbreviated form; the bibliography entry should be expanded to full author names, title, venue, and year for standard scholarly completeness.
[Preliminaries] The definition of 'locally tractable' (polynomial-time computation at each profile) is used repeatedly but should be stated once in a dedicated preliminary subsection with precise complexity parameters to avoid ambiguity in later reductions.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and the recommendation for minor revision. We address each of the major comments below, providing clarifications and agreeing to incorporate necessary revisions to strengthen the manuscript.

read point-by-point responses

Referee: [Existence of Nash-convergent dynamics] The section constructing the two families of Nash-convergent dynamics states that they converge to all equilibria in non-degenerate games, but the argument for convergence (and why it evades the MPPS23 negative result) is load-bearing for the subsequent intractability claims; an explicit verification or proof outline that both families reach every equilibrium, not merely some, is required.

Authors: We agree that making the convergence argument more explicit would strengthen the paper. In the revised version, we will include a detailed proof outline verifying that both families converge to all Nash equilibria (not just some) in non-degenerate games. This outline will also clarify how the construction avoids the degeneracy and uniform convergence assumptions used in MPPS23, ensuring the intractability claims rest on solid ground. revision: yes
Referee: [Impossibility Conjecture] The Impossibility Conjecture is formulated for locally tractable dynamics (polynomial work per step, exponential steps allowed). The reduction showing intractability of the two explicit families must be checked to confirm it does not inadvertently assume polynomial total time rather than per-step tractability, as this distinction is central to the conjecture's novelty.

Authors: The reduction establishes PPAD-hardness for computing a single step of each dynamic at a given profile, with no assumption that the total number of steps is polynomial. The local intractability holds even when convergence requires exponentially many steps, which is precisely the setting of the conjecture. We will add a clarifying remark to emphasize this distinction and its centrality to the conjecture's novelty. revision: yes
Referee: [Proving Game] In the Proving Game construction, the claim that black-box reductions cannot separate convergent from non-convergent dynamics in polynomial time is used to explain why the general conjecture may be difficult to settle. The argument should explicitly identify the class of oracles or query models under which indistinguishability holds, to rule out the possibility that non-black-box techniques could still separate the cases.

Authors: We will revise the Proving Game section to explicitly state that the indistinguishability result holds in the black-box query model, where a polynomial-time reduction has oracle access only to the next-step function of the dynamic (receiving the subsequent profile from the current one) but no direct access to the underlying payoff matrix. We will note that this leaves open the possibility of non-black-box techniques. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper cites MPPS23 only for the known negative result on degenerate games, then explicitly constructs two new families of Nash-convergent dynamics that work on non-degenerate games and proves their local intractability via fresh reductions to PPAD. The Impossibility Conjecture is stated as an open claim, not derived from any self-definition or fitted parameter. The Proving Game is introduced as a new gadget to explain why black-box separations are hard, without reducing any central claim to prior inputs by construction. All load-bearing steps rely on standard topological properties of games and established complexity assumptions external to the present derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard results from game theory and complexity without introducing new free parameters or invented entities; it uses Nash's existence theorem and PPAD-completeness as background.

axioms (2)

standard math Nash equilibria exist for all finite games
Invoked as the target of convergence for the dynamics.
domain assumption Finding Nash equilibria is PPAD-complete
Basis for the intractability reductions and the formulated conjecture.

pith-pipeline@v0.9.0 · 5618 in / 1289 out tokens · 20561 ms · 2026-05-15T21:27:58.086916+00:00 · methodology