{"ID":2881569,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.11874","arxiv_id":"2508.11874","title":"Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models","abstract":"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.","short_abstract":"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 instan...","url_abs":"https://arxiv.org/abs/2508.11874","url_pdf":"https://arxiv.org/pdf/2508.11874v1","authors":"[\"Hanyu Li\",\"Dongchen Li\",\"Xiaotie Deng\"]","published":"2025-08-16T02:18:43Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.AI\",\"cs.DS\",\"cs.LO\",\"cs.PL\"]","methods":"[\"Language Model\"]","has_code":false}