LegoNE: How AI Solved a 15-Year-Old Game Theory Problem in Nash Equilibrium Approximation

> Core intuition: Nash equilibrium is the holy grail of game theory, but proving an algorithm works "in all cases" is harder than designing the algorithm itself. LegoNE's trick: let an AI assemble algorithms from human-curated "LEGO bricks", while an automated verifier instantly scores each candidate's worst-case guarantee.

1. A Problem Stalled for 15 Years

In the classic Prisoner's Dilemma, two suspects each do better by confessing regardless of the other's choice, so both confess — a worse outcome than mutual silence. This stable state is a Nash equilibrium: no player can improve by unilaterally deviating. Nash equilibria appear everywhere — traffic, pricing, auctions, TCP congestion control — but computing them exactly is PPAD-hard, a complexity class as hopeless as NP-hard.

Researchers therefore seek approximations: strategies where no player's regret exceeds ε. Progress has been a long marathon:

| Year | Two-player guarantee | Researchers | |------|----------------------|-------------| | 2006 | 0.75 | KPS | | 2006 | 0.5 | DMP | | 2006 | 0.38197 | DMP refined | | 2007 | 0.36392 | BBM-2 | | 2007 | 0.33933 | TS | | 2022 | 1/3 + δ (≈0.333) | DFM |

For three-player games, the only known approach was the extension technique, which yields ε₃ = 1/(2 − ε₂). With the best two-player guarantee (ε₂ = 1/3), this gives ε₃ = 0.6 — stuck for years.

2. LegoNE: Compiling Proofs into Optimization

The hardest part of designing approximate Nash equilibrium algorithms is proving the worst-case bound: for all game instances, all players, and all unilateral deviations, regret must be ≤ ε — an infinite-dimensional proof obligation. LegoNE converts it into a finite optimization problem via two techniques:

• Instantiation: parameterize payoffs and strategy probabilities as symbolic variables; worst-case structures reduce to finitely many constraint patterns.
• Forgetting: abstract away concrete payoff values, keeping only algebraic relations (e.g., "player 1's payoff ≤ best-response payoff + ε").

The result: a fixed-size mathematical program solvable by Mathematica in ~80 seconds, verifying proofs that would take human researchers years.

3. The LegoNE Language

LegoNE offers a DSL of building blocks drawn from two decades of literature: BestResponse(i, s), UniformMixing(s1, s2), StationaryPoint(f), OptimalMixing(...), GradientDescent(...). Each block carries precise mathematical semantics, so the analyzer knows exactly what inequalities each call implies — connecting code → math → optimization problem.

4. LLM + LegoNE: A Human-Machine Discovery Loop

• Humans define the search space (building blocks, design constraints).
• The LLM composes blocks into candidate algorithms.
• LegoNE verifies each candidate and returns a numeric guarantee (not "looks good", but "ε = 0.53"), guiding the LLM's next iteration.

The division works because LLMs are weak at inventing new proof techniques and guaranteeing rigor, while humans are weak at exhaustive combinatorial search and instant verification.

5. Two Striking Results

1. Two rounds to replicate 16 years of progress. Given pre-2007 building blocks, the LLM-LegoNE system rediscovered a two-player algorithm matching the 2022 state of the art (1/3 + δ) in two iterations — structurally different from the human DFM algorithm, but with the same verified guarantee.

2. Breaking the extension-technique ceiling for three-player games. The extension technique mathematically cannot reach ε₃ ≤ 0.5 in polynomial time (that would require ε₂ = 0, i.e., an exact PPAD-hard equilibrium). In round 11, the system found a fundamentally new algorithm: fix player 3's strategy, use gradient descent to find a stationary point for players 1 and 2, then apply optimal mixing. LegoNE verified a guarantee of 0.5 + δ. As the paper states: *"The discovered algorithm therefore achieves a guarantee that is provably beyond what the extension technique can deliver in polynomial time."*

6. Why It Matters

• New algorithm design space: multiplayer approximate equilibria are no longer confined to the extension technique — a change of principle, not an incremental tweak.
• A new role for AI in mathematics: not replacing mathematicians, but amplifying them via "human insight + machine search + automated proof".
• Reusable methodology: LegoNE also reproduced the 1/2 + δ guarantee for polymatrix games and proved the approximation ratio of 2 for LP-rounding Vertex Cover algorithms.

7. Limitations

• Depends on human-provided building blocks; it cannot invent wholly new mathematical tools (e.g., Nash's fixed-point theorem).
• Instantiation + forgetting only works where universal quantifiers can be parameterized and worst cases reduce to finite optimization.
• Designing the right set of blocks is itself an art: too many explode the search space, too few miss good algorithms.
• Verification relies on numerical solvers (validated to 10⁻⁵), so it is not a fully formal proof.

8. A Philosophical Question

Is an AI-discovered algorithm really "new"? Structurally yes — it avoids the extension technique — yet every component came from human literature. The paper is pragmatic: *"The structure of the final 0.5+δ algorithm was not anticipated by the human experts who designed the building blocks."* Humans invented the atoms; the AI explored molecules; the verifier confirmed stability.

Conclusion

LegoNE (LEGO + Nash Equilibrium) turns mathematical proofs from handcraft into compilable code. Humans went from 0.5 to 0.333 in 15 years; the AI matched it in two rounds and broke the three-player barrier in eleven. This does not make mathematicians obsolete — the LegoNE building blocks themselves came from decades of expertise by the Peking University team. AI's value lies in encoding expert tacit knowledge into explicit rules, then searching that space at superhuman scale. Automated proof is not the end of mathematics, but a new beginning.

Reference: Li, H., Li, D., Deng, X. "Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models." Nature Communications. arXiv:2508.11874.