Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models
This work addresses a fundamental problem in theoretical computer science by enabling automated algorithm discovery with provable guarantees, representing a new human-machine collaborative paradigm rather than an incremental improvement.
The paper tackled the challenge of automating the discovery of general algorithms with provable performance guarantees, specifically for computing approximate Nash equilibria, by proposing LegoNE, a framework that integrates algorithm design and formal analysis; using this, a large language model rediscovered a state-of-the-art algorithm for two-player games in hours (versus 15 years for humans) and discovered a novel algorithm for three-player games surpassing existing ones.
Algorithm design and analysis is a cornerstone of computer science, but it confronts a major challenge. Proving an algorithm's performance guarantee across all inputs has traditionally required extensive and often error-prone human effort. While AI has shown great success in finding solutions to specific problem instances, automating the discovery of general algorithms with such provable guarantees has remained a significant barrier. This challenge stems from the difficulty of integrating the creative process of algorithm design with the rigorous process of formal analysis. To address this gap, we propose LegoNE, a framework that tightly fuses these two processes for the fundamental and notoriously difficult problem of computing approximate Nash equilibria. LegoNE automatically translates any algorithm written by a simple Python-like language into a constrained optimization problem. Solving this problem derives and proves the algorithm's approximation bound. Using LegoNE, a state-of-the-art large language model rediscovered the state-of-the-art algorithm for two-player games within hours, a feat that had taken human researchers 15 years to achieve. For three-player games, the model discovered a novel algorithm surpassing all existing human-designed ones. This work demonstrates a new human-machine collaborative paradigm for theoretical science: humans reason at a higher-abstract level, using symbols to compress the search space, and AI explores within it, achieving what neither could alone.