用大模型发现突破人类设计范式的纳什均衡算法
Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models
- 将专家证明策略转为符号语言，自动验证算法最坏情况性能
- 在两人博弈中复现最优多项式时间算法，三人博弈提升至0.5+δ
- 适合对博弈论算法创新感兴趣的学者与AI辅助研发人员
设计具有可证明最坏情况保证的多项式时间近似纳什均衡（ANE）算法，是算法博弈论中的一个基础开放问题。尽管大型语言模型（LLM）能大规模生成候选算法，但要对所有博弈实例进行形式化分析以验证最坏情况保证，此前尚无自动化系统。本文提出LegoNE框架，将专家证明策略编码为符号语言，可自动将任意候选算法转化为有限优化问题，从而验证其最坏情况性能。结合推理型LLM，我们重新发现了适用于两人博弈的最佳多项式时间算法，并发现了一种三人博弈算法，将最优保证从$0.6+δ$提升至$0.5+δ$——该结果已超出以往唯一的多玩家算法设计范式“扩展技术”的能力范围。这些成果表明，将领域特定的证明策略编码为机器可处理的语言，可支持大模型发现超越现有认知的人类设计范式之外的算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。