北京大学计算机学院邓小铁团队在近似纳什均衡算法研究取得重要进展

近日，计算机学院前沿计算研究中心邓小铁教授团队在近似纳什均衡算法研究取得重要进展。研究团队提出面向近似纳什均衡算法自动设计与分析的LegoNE框架，将领域专家多年积累的算法组件和证明策略编码为机器可操作的符号语言，并与大语言模型结合，发现了新的多人博弈近似纳什均衡算法。相关成果以《大语言模型发现专家级别纳什均衡算法》（“Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models”）为题在线发表于国际知名期刊《自然-通讯》（Nature Communications）。

图1 论文截图

纳什均衡是博弈论、经济学和计算机科学中的基础概念，用于刻画多个参与者在相互影响下达到的稳定状态。精确计算纳什均衡在一般情形下十分困难，因此，如何在多项式时间内计算带有理论保证的近似纳什均衡，长期以来是算法博弈论中的核心问题。

近似纳什均衡算法的难点在于，算法不能只在若干样例上表现良好，而必须对所有可能输入给出最坏情况保证。算法设计者需要在提出候选算法的同时预判其证明结构，将策略、收益函数和玩家偏离收益等对象组织成严密的不等式分析。随着近似界不断改进，算法设计与性能证明之间的耦合日益加深，人工推进的认知负担和证明复杂度显著增加。

过去20多年中，二人博弈近似纳什均衡算法的近似保证从0.75逐步推进到0.5、0.3393+δ，并在近年达到1/3+δ；多人博弈的进展则更为有限。此前主要方法依赖扩展技术，即把较少玩家的算法递归扩展到更多玩家。基于当前最佳二人博弈算法，该技术在三人博弈中只能得到0.6+δ的保证。

针对近似纳什均衡算法设计与证明高度耦合的问题，研究团队提出了LegoNE。该框架包含一套面向近似纳什均衡的专用符号语言，能够将“最佳响应”“策略混合”“最优混合”等文献中长期使用的算法组件抽象为可组合的基本块。候选算法可以像Python程序一样被简洁描述，同时每个基本模块都带有明确的数学语义。

LegoNE的自动分析器进一步将候选算法编译为有限维约束优化问题。该优化问题的最优值对应算法在最坏情况下能够达到的近似保证，因此求解过程本身构成了算法正确性的证明。通过这一方式，研究团队把原本需要大量手工推导的证明过程，转化为可自动检查、可反复调用的分析流程。

图2 LegoNE分析器将近似纳什均衡算法的符号化描述编译为优化问题，并据此给出可证明的性能保证

在LegoNE的基础上，研究团队构建了大语言模型驱动的算法发现闭环：人类专家提供符号语言、基本模块和高层设计约束，大语言模型在这一可验证空间中组合模块、提出候选算法，LegoNE自动计算其理论保证并将结果反馈给模型继续迭代。该流程将人类专家的抽象能力、机器的大规模搜索能力和自动分析器的严格验证能力结合起来。

图3 LegoNE支持的人机协同算法发现流程

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

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

该工作的意义首先体现在算法理论本身。三人博弈近似纳什均衡此前主要依赖扩展技术，即把二人算法递归扩展到更多玩家；论文给出的0.5+δ算法已经超过这一范式在多项式时间内能够达到的边界，说明多人近似纳什均衡算法并不只能沿着既有扩展路线推进，也为该方向打开了新的算法设计空间。

更广泛地看，该工作揭示了一种新的人机合作方式：人类专家承担“冷启动”职责，将多年积累的理论直觉、算法组件和证明经验压缩为机器可处理的符号空间；以大语言模型为核心的智能体系统则在这一空间中快速、大量地产生候选算法并根据可证明反馈持续迭代。由此，理论算法发现不再只是依赖少数专家的低频试错，而可以发展为一个人类洞见、机器搜索和自动证明相互配合的过程。

北京大学博士生李翰禹、香港大学博士生李东晨（本科为北京大学）和邓小铁为论文作者。该研究得到了国家自然科学基金的支持。这一成果的奠基性内容来自3位作者围绕近似纳什均衡算法开展的多年持续研究，他们围绕近似纳什均衡算法的共同结构、策略混合方法和计算机辅助分析开展了一系列工作：关于搜索-混合范式的研究系统抽象了一类近似纳什均衡算法的共同结构；关于最优混合问题的研究获IJTCS-FAW 2024最佳论文奖，并发表于Theoretical Computer Science期刊；关于二人博弈算法近似界自动分析的工作发表于Information and Computation期刊，并进一步扩展为多人博弈的自动分析框架，发表于WINE 2024。这些积累从算法结构、关键子问题和自动化证明三个层面，为LegoNE框架和大模型发挥作用奠定了基础。