# Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 69 references that are in the map.
- First posted on arXiv 16 Aug 2025.

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

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2](https://mlsanity.com/paper/2502.03544/) (2025)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Steering Language Models with Game-Theoretic Solvers](https://mlsanity.com/paper/2402.01704/) (2024)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Estimating Approximate Incentive Compatibility](https://mlsanity.com/paper/1902.09413/) (2019)
- [Pure-Circuit: Tight Inapproximability for PPAD](https://mlsanity.com/paper/2209.15149/) (2022)
- [From Natural Language to Extensive-Form Game Representations](https://mlsanity.com/paper/2501.17282/) (2025)
- [Computing Approximate Nash Equilibria in Polymatrix Games](https://mlsanity.com/paper/1409.3741/) (2014)
- [A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games](https://mlsanity.com/paper/2204.11525/) (2022)
- [Distributed Methods for Computing Approximate Equilibria](https://mlsanity.com/paper/1512.03315/) (2015)
- [A survey on algorithms for Nash equilibria in finite normal-form games](https://mlsanity.com/paper/2312.11063/) (2023)
- [A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games](https://mlsanity.com/paper/2207.07007/) (2022)
- [Verifying Approximate Equilibrium in Auctions](https://mlsanity.com/paper/2408.11445/) (2024)

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

- [An Information-Theoretic Criterion for Efficient Data Synthesis](https://mlsanity.com/paper/2605.16379/) (2026)

## Abstract (arXiv)

Designing polynomial-time algorithms for approximate Nash equilibria (ANE) with provable worst-case guarantees is a fundamental open problem in algorithmic game theory. While large language models (LLMs) can generate candidate algorithms at scale, certifying worst-case guarantees requires formal analysis over all game instances -- a task for which no automated system previously existed. Here, we present LegoNE, a framework encoding expert proof strategies into a symbolic language that automatically compiles any candidate algorithm into a finite optimization problem certifying its worst-case guarantee. Integrating LegoNE with a reasoning LLM, we rediscovered an algorithm matching the best polynomial-time guarantee for two-player games, and discovered a three-player algorithm improving the best guarantee from 0.6+δ to 0.5+δ -- provably beyond the reach of the extension technique, the only previously known multi-player ANE design paradigm. These results show that encoding domain-specific proof strategies into a machine-tractable language can support LLM-driven discovery of algorithms outside known human design paradigms.