SAGT 2021 | 近似纳什均衡的Tsaknakis-Spirakis算法的紧性
关键词：Approximate Nash Equilibrium
导 读
本文是第14届国际算法博弈论研讨会（SAGT 2021）入选论文《近似纳什均衡的Tsaknakis-Spirakis算法的紧性（On Tightness of the Tsaknakis-Spirakis Algorithm for Approximate Nash Equilibrium）》的解读。该论文由北京大学前沿计算研究中心邓小铁课题组主导完成。
论文链接：https://arxiv.org/abs/2107.01471
01
引 言
纳什均衡（Nash equilibrium）是博弈论中最核心的概念，在众多经济学理论中都有举足轻重的地位。所谓博弈，是指一群玩家进行游戏，每个人需要选择一个策略（或者策略的概率分布），每个人会相应获得收益。纳什均衡指的是每个人选择混合策略之后，没有人想改变策略以获得更多收益的状态。1951年，纳什证明了任何正则博弈都存在这样的均衡 [1]，这也是纳什获得诺贝尔奖的重要原因之一。
从计算机科学家的角度看，比纳什均衡存在性更有趣的问题是如何计算它。计算纳什均衡在计算复杂性领域带来了一系列新的概念与挑战，一个重要的结果是由 Daskalakis, Goldberg 和 Papadimitriou [2] 给出的：NASH 的准确复杂度是 PPAD-complete。PPAD 是一个介于 P 和 NP 之间的复杂度类。完整的结果是由陈汐、邓小铁和滕尚华 [3] 给出的：2NASH 的准确复杂度是 PPAD-complete。这些结果让人们普遍相信计算纳什均衡——哪怕是二人博弈的均衡——都是难解的，即不存在多项式时间算法。
这样的结果让人们开始关注近似纳什均衡，一系列近似的概念和算法被提出。一种被广为采纳的定义是加性近似（additive approximation）。首先假设每个人的收益介于0到1之间（正则化），一个 近似纳什均衡指的是任何人单方面偏离当前策略之后最多获益 。在这里我们只关注常数近似，即 是一个常数，不随策略规模变化，这个常数越小近似程度越好。
目前最好的近似算法是由 Tsaknakis 和 Spirakis 在 2007年给出的，他们的算法能够在多项式的时间内找到一个0.3393+ 近似纳什均衡 [4]。他们的结果只给出了算法近似比的上界，即算法找到的解近似比不会大于0.3393，但是后续的若干工作 [5, 6] 表明这个界在实验中非常难达到，此后14年也没有任何理论结果表明这个算法的界会是更小的数字。本篇工作的关注重点即是这个界是否是紧的？如果是紧的，什么样的博弈会是紧实例？
02
Tsaknakis-Spirakis算法
为了描述一个二人博弈，我们可以分别用两个矩阵 和 来表示两个玩家（称为行玩家和列玩家）的收益。行玩家的策略是选择行，列玩家的策略是选择列。在我们的背景下，假设两个矩阵的元素都是0到1之间的数。
TS 算法是一种优化的思路，定义如下的目标函数：
其中 是行玩家和列玩家的混合策略， 和 是行玩家和列玩家偏离后的最大收益， 就是我们的近似比，算法的目标是找一个尽可能小的 。
算法采取了梯度下降的方式，目标是找到一个点，他的所有方向导数都是非负的，这样的点我们称之为稳定点（stationary point）。Tsaknakis 和 Spirakis 两篇工作 [4, 5] 证明了梯度下降可以在多项式时间内找到近似稳定点。
找到稳定点之后，可以证明，在最坏情况下这是一个1/2近似纳什均衡。因此，算法还需要额外的调整步骤。原始的 TS 算法会将稳定点朝着某一对最优应对（best response）调整一定的距离，得到一个调整后的策略。Tsaknakis 和 Spirakis 最初的结果证明了，稳定点和调整后的策略中较好的那个策略对近似比不超过0.3393，即这是一个算法上界 [4]。
03
算法的紧性
本篇工作证明了，在稳定点朝着这个最优应对调整，无论如何选择调整的距离，调整后的策略对和稳定点的策略对中较好的那个近似比不会小于0.3393，即这是推广后的 TS 算法的下界。
证明的方法是分析加构造。先给出一系列验证紧实例的充分必要条件，然后构造一个紧实例，验证在这个博弈下，这一系列条件都成立。下面展示这个紧实例（近似值）：
这个博弈在稳定点 和最优对应对 时达到紧界。精确的收益矩阵可以在论文中找到。事实上，本工作对所有规模的二人博弈都构造了紧实例。
本篇工作进一步利用这些充分必要条件，刻画了所有紧实例的集合：这些紧实例形成了连续统个集合，每一个集合都是某个线性规划的可行解集。因为可以用线性规划来表示，所以本工作设计了一种带输入参数的线性规划算法，它的任何输出都是紧实例。这为后续的实验性工作提供了一个生成器。
本工作最后测试了在生成器产生的紧实例上推广的 TS 算法实际效果如何。实验的工作表明，紧实例的稳定点是非常不稳定的，只要有轻微的扰动就会飞到 很低的地方；此外，随机初始策略下，几乎所有的紧实例都不会下降到达到紧界的稳定点。这说明理论的紧性和现实的紧性是完全不同的两个概念。
04
讨 论
本工作证明了算法的紧界，给出了紧实例的充要性刻画。证明和刻画紧性利用了非常强的几何直观，这样的几何直观导出了一系列不等式，这样的分析过程对于理解 TS 算法会很意义。此工作中展示了理论和实验的巨大差距，期待能够启发后续工作将概率和随机引入分析中，得到一个更符合实际的平滑界。最后，我们希望这篇工作能够让人有所启发，最终提出近似比更小的算法。
参考文献
[1] Nash, John. "Non-cooperative games." Annals of mathematics (1951): 286-295.
[2] Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009).
[3] Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 14:1–14:57 (2009).
[4] Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. Internet Math. 5(4), 365–382 (2008).
[5] Tsaknakis, H., Spirakis, P.G., Kanoulas, D.: Performance evaluation of a descent algorithm for bi-matrix games. In: Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5385, pp. 222–230. Springer (2008).
[6] Fearnley, J., Igwe, T.P., Savani, R.: An empirical study of finding approximate equilibria in bimatrix games. In: Experimental Algorithms - 14th International Symposium, SEA 2015, Paris, France, June 29 - July 1, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9125, pp. 339–351. Springer (2015).
图文 | 李翰禹
PKU daGAME Lab
算法博弈论实验室
Distributed and Automated Games and Managerial Economics Lab
算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。关注计算与通讯技术兴起中应用领域的问题，特别关注互联网广告机制设计、共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。
daGAME近期动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”跳转论文链接