纳什均衡（NE）是博弈论中最深入研究的概念之一。几十年来，NE 已经成为理论界的一块研究基石，受到了经济学、计算机、人工智能、逻辑学等领域的广泛关注，它的计算复杂性和算法问题被大量研究过。

在复杂性问题方面，过去二十年中，通过一系列里程碑的工作，我们已经发展出一套深刻的理论来揭示 NE 计算之难。在不同博弈场景下，NE 计算都被证明是很困难的，即不太可能有多项式时间算法。这些场景包括图上的博弈、多项式矩阵（polymatrix）博弈、三人博弈和二人博弈。NE 不仅精确计算是难的，对于常数近似，我们也知道它是困难的。

与 NE 的复杂性结果大为不同的是，常数近似的 NE 算法（ANE）进展非常有限。对于多人博弈，用概率方法，我们可以得到已知的唯一的准多项式时间算法。而在多项式时间范围内，进展主要集中在二人博弈，近似界的结果从  开始改进到了  。

然而，这些技术有很大的局限性，无法得到有效扩展。在这些技术中，Tsaknakis 和 Spirakis 提出的梯度下降方法给这一问题的研究带来了重要的影响。梯度下降法是当前和之前最佳近似界算法设计的核心，这一方法还可以扩展到多项式矩阵博弈，这是我们唯二知道的多人博弈上的算法结果。另一个已知的多人博弈技术是扩展技术，它把一个  人博弈的 ANE 算法扩展到  人博弈。

算法结果的停滞不前，似乎可以从下面的观察略窥一二：即便是二人博弈，近似界的改进也变得越来越困难，并且需要更长的证明。对于多人博弈，文献几乎空白。这表明，当前的算法分析可能具有内在的“证明复杂性”，已经超出了人类的能力范围。

为了解决这一挑战，文章提出了一个新的框架，LegoNE 来设计和分析 ANE 算法。LegoNE 借鉴了模块化算法设计的概念：算法可以通过更小的、可重用的基本块来构建——就像使用乐高积木来搭建复杂的结构一样。

LegoNE 具有以下关键特点：

LegoNE 编程语言允许用户采用乐高风格的设计模式，为  人博弈设计算法，这适用于任何固定的  。首先，用户可以自定义基本块，然后，再将它们组合起来构建一个完整的算法。LegoNE 编程语言中能够定义所有现有算法中的基本块，甚至是文献之外的基本块。

在定义完算法后，LegoNE 框架可以读入这个算法，然后自动计算该算法的近似界，并证明其正确性。

LegoNE 非常强大，它能够复现文献中所有的二人博弈算法，计算并证明相同的近似界。对于三人博弈，在 LegoNE 的辅助下，文章作者得以在更高的视角思考问题，获得新的见解，进而提出了一种新的算法，其近似界为  ，相比之前通过扩展技术得到的  有所提高。这是人类史上第一次能够直接对三人博弈设计和分析算法，并改进近似界。

接下来，我们以文献中经典的 DMP 算法为例，简要介绍 LegoNE 的原理。这是一个二人博弈的算法，文献已经证明，它的近似界是  。

首先，我们介绍一些基本符号，玩家  的收益是一个函数  ，策略是  ，于是玩家  的损失可以被定义为： 

策略组合  的近似值可以被定义为 当  时，我们称  是一个  -NE。

接下来，我们给出 DMP 算法的基本块和 DMP 算法本身：

有了 DMP 算法的描述，我们现在来阐述 LegoNE 如何自动分析 DMP 算法的近似界。

首先，思考一下我们人类是如何做算法分析的。关键的一步是，我们需要知道算法的性质。这可以用逻辑公式来描述，即逻辑嵌入。例如算法第二步  ，等价的一种写法是 我们可以对每一步都这样做，那么整个算法的逻辑嵌入就是这些步骤逻辑嵌入的与。

最后，我们的证明目标是，对任意实例，我们都可以证明输出  的  值不小于近似界  ，这也可以用逻辑公式表示出来。总体上的过程图如下，我们把整个逻辑嵌入用映射  来表示。

于是，对近似界的证明目标就变成了一个一阶实数算术理论的公式。这个公式的有效性（即它是否恒真）是可以用柱形代数分解算法（CAD）让计算机去判断的，于是，我们就可以自动证明 DMP 算法有  的近似界。

同样的方法可以用来做任何一种 LegoNE 写成的算法，特别地，我们可以用来做如下三人博弈算法。尽管这一算法非常复杂，LegoNE 依然可以顺利完成这一算法的分析，并证明它改进了近似界。

图文 | 李翰禹

PKU daGAME Lab