Computer Science Review 2024 | 有限正则博弈纳什均衡算法综述

关键词：近似纳什均衡，有限正则博弈，均衡计算

导  读

本文是对发表在计算机顶级综述期刊计算机科学评论（Computer Science Review）上的综述论文 A survey on algorithms for Nash equilibria in finite normal-form games 的解读。

这篇综述从理论和实验方面全面总结介绍了有限正则博弈纳什均衡算法的结果。理论上，对文献中关于纳什均衡算法的进行分类，介绍了他们基本的设计和分析思想。实验上，本文对不同类型博弈上不同纳什均衡算法进行了全面的比较，基于此提出了关于纳什均衡算法实现和应用的实用建议。

← 扫码跳转论文

论文地址：

https://arxiv.org/abs/2312.11063

01

引  言

纳什均衡是博弈论中的一个核心概念，它描述了一种状态，在这种状态下，没有任何玩家可以通过单方面改变策略来获得额外的收益。这一概念由约翰·纳什提出，已被广泛应用于解释和分析人类行为中的竞争和合作情况，如军备竞赛和环境保护等。随着21世纪人工智能研究的兴起，纳什均衡在指导机器学习算法寻找现实世界博弈的均衡策略方面发挥了重要作用，例如在星际争霸2（AlphaStar）、MOBA 游戏（OpenAI Five）和日本麻将（Suphx）等游戏中击败高水平人类玩家的 AI。

尽管纳什均衡的数学基础已经相当成熟，但其计算问题在计算机科学领域仍是一个挑战。事实上，即使是限制在两人博弈中，计算纳什均衡也几乎没有多项式时间的算法。因此，研究者们转而寻找近似解，并在文献中提出了多种近似算法。然而，这些算法的实证研究相对较少，理论与实践之间的差距逐渐扩大。

本综述旨在填补这一空缺，通过对文献中代表性方法的回顾和比较，提供对这些方法的更完整的理论与实证理解。我们将综述分为理论部分和实证部分：理论部分回顾不同的近似概念，并对文献中的算法进行分类；实证部分则基于不同的性能标准，全面比较了文献中不同类型游戏上的算法。这些标准主要关注实际考虑，包括实际近似、效率和精度要求。通过这些比较，我们揭示了以前实证研究中未观察到的新的现象，并提出了新的理论挑战。最后，本文还提供了关于这些算法实际应用的实用建议，并从理论和实践的角度提出了开放性问题。

02

纳什均衡、近似和它们的复杂度

纳什均衡是指每个玩家选择的策略使得其在其他玩家策略不变的情况下无法通过改变自己的策略获得更高的收益。在文献中，纳什均衡通常有两个近似概念：  -纳什均衡和  -强支撑纳什均衡。这两个概念分别允许玩家通过改变策略获得最多  的额外收益和当玩家采用某个纯策略时，允许玩家通过改变策略获得最多  的额外收益。强支撑纳什均衡是纳什均衡的更强近似概念。在文献中，  -纳什均衡是一个被更加广泛使用和接受的近似概念。

从复杂度的角度来说，计算纳什均衡是相当困难的。即使在以下情况下，纳什均衡也很难有一个多项式时间算法：

1. 限制在二人博弈中，

2. 允许输入有小的随机扰动，

3. 只寻求小的常数近似。

然而，另一方面，平均情况下（即输入的博弈服从某种随机分布），纳什均衡计算有多项式时间算法，因此更容易解决。

03

近似纳什均衡的算法

现有算法可分为以下几类：

1. 暴力搜索算法：通过枚举所有可能的策略组合，计算纳什均衡，适用于两玩家零和博弈。对于  -纳什均衡，存在准多项式时间算法。

2. 线性规划法：用于计算两玩家零和博弈的精确纳什均衡。此算法利用了冯·诺伊曼最小最大定理，通过解线性规划得到精确纳什均衡。

3. Lemke-Howson 算法：用于计算一般两玩家博弈的精确纳什均衡。该算法通过路径跟踪的方式搜索纳什均衡，存在指数时间复杂度的情况。

4.  搜索-混合方法：这类算法通过搜索多项式时间可解的策略，并对这些策略进行进一步的凸组合混合，计算  -纳什均衡。代表性算法包括 KPS06-0.75、DMP06-0.5、BBM07-0.36、CDFFJS15-0.38、TS07-0.3393等。

5. 基于零和博弈的方法：用于计算  -支持纳什均衡。代表性算法包括 KS07-2/3、FGSS12-0.6607、CDFFJS15-0.6528、DFM22-1/2 等。

6. 启发式算法：这类算法基于学习动态，通过重复博弈进行自适应调整策略，计算纳什均衡。代表性算法包括虚构游戏、无遗憾学习和双预言者算法等。

7. 其他算法：针对多玩家博弈，存在少量算法可以计算精确纳什均衡或近似纳什均衡。代表性算法包括 Lemke-Howson 算法的扩展和多玩家博弈的搜索-混合方法等。

这些算法在理论上有优劣之分。搜索-混合方法、基于零和博弈的方法提供了一定常数近似保证的多项式时间算法，但在实际中计算量通常会很大。此外，改进这些算法理论近似界似乎变得愈发困难，说明我们非常需要新的技术来做这些改进。另一方面，启发式算法的主要优点是易于实现，可以在线运行，并且能够处理大规模博弈。然而，它们的缺点在于缺乏收敛性和近似性的理论保证，因此在实际应用中需要谨慎使用。尽管如此，这些算法为纳什均衡的计算提供了有益的启发。最后，多玩家精确纳什均衡的计算仍然没有任何已知算法。

04

算法的实证比较与理解

在现有文献中有非常有限的实证研究，主要分为两类：一类是比较寻找精确/任意近似纳什均衡的算法，另一类是比较寻找常数  -纳什均衡/  -支持纳什均衡的算法。结果表明，许多算法的实际表现优于其理论最坏情况保证，并且在不同类型的博弈中表现差异很大。

这篇综述文章提出了进行算法比较的研究问题，包括实际近似性能、随机与结构化博弈下的表现、效率以及数值求解器可能遇到的精度误差。

在实验设置部分，文章评估了基于枚举的算法、Lemke-Howson 算法、5种学习动态、6种近似纳什均衡算法和4种近似支持纳什均衡算法在不同基准博弈场景下的性能。测试场景包括随机零和博弈、随机一般博弈以及 GAMUT 基准中的9种不同场景。

实验结果显示：

1. 基于枚举的算法和 Lemke-Howson 算法在实际应用中不太实用，前者运行太慢，后者存在精度问题。

2. 具体近似保证的算法在实际近似性能上优于理论保证，尤其在结构化博弈中表现更好。运行时间上，KPS06-0.75 和 DMP06-0.50 最快，其次是 TS07-0.3393 和 DFM22-1/3，BBM07-0.36 和 CDFFJS15-0.38 较慢。CDFFJS15-0.38 算法混合后的策略比混合前差，这是由于其“阈值混合”策略所致。

3. 学习动态算法没有统一的近似性能描述。在随机一般博弈中，平均策略的近似值远大于随机零和博弈。Hedge 和后悔匹配算法在随机零和博弈的最终迭代策略上表现较好。而在结构化博弈中，学习动态算法通常收敛到纯纳什均衡。

05

建议与展望

文章还就具有近似保证的算法、学习动态的算法实现和使用的建议进行了说明。对于具体近似保证的算法，大多数这些近似算法都涉及线性规划子程序，实现这些算法时需要仔细处理数值困难，特别是由 LP 子程序引起的困难。学习动态在结构化博弈上的表现远优于随机博弈，因此建议在结构化博弈上使用学习动态。

文章最后提出了开放问题和未来研究方向，主要聚焦于以下几个方面：

1. 理论改进：提升算法理论保证，扩展至更复杂多玩家场景，探索新的二矩阵博弈类别以实现多项式时间内纳什均衡计算，以及确定学习动态算法的收敛性。

2. 实证优化：克服数值困难，加速学习动态算法收敛，利用机器学习选择最佳算法，提出更有效的二矩阵博弈基准，并开发完整的纳什均衡计算算法库。

本文期刊链接：

https://www.sciencedirect.com/science/article/pii/S1574013723000801

图文 | 李翰禹

PKU daGAME Lab

算法博弈论实验室

Distributed and Automated Games and Managerial Economics Lab

算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。关注计算与通讯技术兴起中应用领域的问题，特别关注互联网广告机制设计、共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。

↑↑扫码转实验室主页↑↑

实验室 PI 简介：邓小铁 讲席教授

实验室相关新闻：#PKU daGAME

daGAME近期动态

• AAAI 2024 | 重复二价拍卖中的动态预算节流方法

• NeurIPS 2023 Spotlight | 仿射最大化拍卖机制设计的可拓展神经网络方法

• ICML 2023 | 重复二价拍卖下有预算约束的协同竞价在线算法

• ICML 2023 | 排列等价的均衡近似器的优势与局限

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转论文链接