利用大型语言模型发现专家级别的纳什均衡算法

摘要

为近似纳什均衡（ANE）设计具有可证明最坏情况保证的多项式时间算法是算法博弈论中的一个基本未解决问题。尽管大型语言模型（LLMs）能够大规模生成候选算法，但验证最坏情况保证需要对所有游戏实例进行形式化分析——此前尚不存在自动化系统能够完成这项任务。在这里，我们提出了LegoNE框架，该框架将专家证明策略编码成一种符号语言，并能自动将任何候选算法编译成一个有限的优化问题，从而验证其最坏情况保证。通过将LegoNE与推理型LLM集成，我们重新发现了一种适用于两人游戏的算法，其多项式时间保证达到了最佳水平；同时我们还发现了一种三人游戏算法，将该算法的最坏情况保证从0.6 + δ提升到了0.5 + δ——这明显超出了之前已知的多人ANE设计范式（即扩展技术）的实现能力。这些结果表明，将特定领域的证明策略编码成机器可处理的语言，可以支持LLM驱动的算法发现过程，从而突破已知的人类设计范式。