Nature Communications | 大语言模型发现专家级纳什均衡算法

可以先从一个简单类比理解。假设几个人在玩一个策略游戏，每个人都希望自己的收益更高。一个稳定状态意味着：在其他人策略不变时，没有人能靠自己单方面改变策略获得明显更多收益。近似纳什均衡放宽了这个要求：允许每个人最多只能再多获得一点点收益。这个“一点点”越小，算法保证越强。

难点在于，算法不能只在几个游戏样例上表现好。理论算法研究要求的是最坏情况保证：无论输入的博弈有多少策略、收益结构怎样变化，算法都必须输出满足某个近似界的结果。换句话说，算法证明面对的是所有可能的实例，而不是一个固定测试集。

过去二十多年里，二人博弈的近似保证从 0.75 推进到 0.5，再到 0.3393+δ，之后长期停滞，直到近年达到 1/3+δ。多人博弈更难，已有方法长期主要依赖扩展技术，也就是把较少玩家的算法递归扩展到更多玩家。基于当前最佳二人算法，这条路线在三人博弈中只能得到 0.6+δ 的保证。

近似纳什均衡算法的困难，主要在于算法设计与分析的高度耦合，以及写分析本身的证明复杂度。由于需要保证算法的近似比，在所有实例上都有一个上界，这件事情本身会对算法设计提出挑战：人类专家需要边考虑算法设计边去预演后续的算法分析过程。随着改进的不断深入，这一高度耦合的过程带来了很高的认知负担和非常复杂、容易出错的证明。人类找到的第一个非平凡二人博弈算法，只需要半页就可以证明 0.75 的界，却花了 13 页数学证明才能得到二人博弈上最好的结果是1/3+δ。

多人博弈尤其如此。已有路线长期依赖扩展技术，把二人算法递归扩展到三人或更多玩家；这条路清楚、可证明，但也把搜索限制在既有范式里。要跳出它，需要一边保留严格证明，一边更大规模地探索算法构件的组合方式。这其中的复杂性已经超出了人类专家的能力范围。

图1：LegoNE 用接近 Python 的专用符号语言描述近似纳什均衡算法。

LegoNE 的自动分析器负责把候选算法转化为一个有限维约束优化问题。直观地说，原本的证明要讨论所有可能的策略和所有可能的收益函数，看起来是无限维的；分析器通过实例化和抽象，把需要验证的条件变成有限个代数不等式。

这个优化问题的最优值，就是算法在最坏情况下能够保证的近似界。求解它，并不是单纯给出一个经验分数，而是在给出一个对所有输入都成立的证明。也就是说，在 LegoNE 里，计算近似界本身就是证明过程的一部分。

图2：LegoNE 分析器将算法代码转化为有限维优化问题，从而自动得到可证明的最坏情况保证。

在这个框架下，分工变成了三件事。人类专家定义哪些操作是有意义、可证明的；大模型在这些操作之间做高强度组合，提出大量候选算法；LegoNE 负责逐一分析，返回每个候选算法的近似保证。大模型在设计、反馈的信息中不断学习和积累，研究如何改进自己过去生成的算法。

关键不是让机器替代人的理论判断，而是把人的判断前移到语言和构件设计中，把机器的优势用在大规模组合搜索上，再用自动分析器把每次尝试转化为可证明的反馈。原本高成本、低频率的人工试错，由此变成一个可以反复迭代的发现闭环。

图3：人类专家、大语言模型与 LegoNE 分析器共同构成算法发现闭环。

论文展示了两项主要结果。

第一，在二人博弈任务中，LLM-LegoNE 系统仅经过两轮交互，就重新发现了达到当前最佳多项式时间保证的近似纳什均衡算法。这个结果从上一代最好界限发展到当前水平，曾经历约15年的人工研究积累。

第二，在三人博弈中，系统发现了一个新的近似纳什均衡算法，将此前已知最佳多项式时间保证从 0.6+δ 改进到 0.5+δ。更重要的是，这个算法不是沿着传统扩展技术继续改进。论文证明，0.5+δ 的保证是不可能通过扩展技术得到的；因而，大模型揭示了多人博弈全新的一种算法设计思路。

图4：大语言模型发现的三人博弈近似纳什均衡算法核心结构。

这项工作的意义首先落在算法理论本身：它说明多人近似纳什均衡并不只能沿着把二人算法递归扩展到更多玩家的路线往前走。此前最佳三人结果来自扩展技术，而论文给出的 0.5+δ 算法已经超过这一范式在多项式时间内能达到的边界，因此打开的是新的算法设计空间。

更广泛地来看，这个工作揭示了一个新的人机合作方式。人类专家是冷启动的职责，为机器提供一个相对压缩凝练的空间，并且赋予它人类所积累的直觉和经验；而以大模型为核心的 agent 系统则负责在这个空间中探索，以人类专家的冷启动为起点，快速、大量地产生新的想法并进行实验，不断积累经验，最终超越人类和 agent 本身各自的局限性。

图文 | 李翰禹

PKU daGAME Lab