本文是 ICML 2023 入选论文 Are Equivariant Equilibrium Approximators Beneficial? 的解读。该论文作者为北京大学前沿计算研究中心算法博弈论实验室的博士生段志健、本科生马允轩以及邓小铁教授。

　　本文是该课题组 AAMAS 2023 论文 Is Nash Equilibrium Approximator Learnable? * 讨论纳什均衡函数近似器可学习性之后的改进工作，进一步讨论满足排列等价性的纳什均衡、相关均衡、粗相关均衡近似器的优势与局限。

　　论文链接：https://arxiv.org/abs/2301.11481

01 引 言

　　纳什均衡（Nash Equilibrium, NE）满足排列等价性：将博弈的效用矩阵和它的一组纳什均衡策略进行相同的随机排列打乱，打乱后的策略恰好是打乱后博弈的一组纳什均衡。同样地，相关均衡（Correlated Equilibrium, CE）和粗相关均衡（Coarse Correlated Equilibrium, CCE）也满足上述排列等价性。受此启发，现有文献[2,3]中关于均衡近似器（以效用矩阵为输入来预测近似均衡的神经网络）的网络结构设计通常都会引入排列等价性，即要求近似器输出的联合策略关于输入的效用矩阵满足排列等价。

　　本文通过理论方法分析排列等价性为纳什均衡、相关均衡、粗相关均衡近似器所带来的优势与局限。我们发现，排列等价性为三种均衡近似器带来了更好的泛化性保障，并且在很多场景下可以提高这些近似器的表现性能。但是于此同时，由于排列等价性限制了均衡近似器的表达能力，导致三种近似器都无法找到所有的均衡点，而且排列等价的纳什均衡近似器可能会损失社会福利。

02 均衡近似器

　　我们考虑计算正则博弈（两人情况下的正则博弈又称矩阵博弈）的三种均衡：纳什均衡、相关均衡与粗相关均衡。当存在大量相似正则博弈需要求解时，利用函数近似的方法学习一个均衡近似器[1,2,3]是有效的解决方法。均衡近似器以博弈的表示（在本文中我们用效用矩阵表示一个正则博弈）作为输入，预测博弈的近似均衡解。如下图所示为一个纳什均衡近似器的例子：

　　现有均衡近似器的工作[2,3]在构建模型时偏好排列等价的近似器。这里的排列等价性具体是指：

　　1. 对于相关均衡与粗相关均衡近似器，模型输出f(u)为与效用矩阵u相同维度的联合策略。它们的排列等价性（Permutation-Equivariance, PE）定义为：

　　其中ρ表示效用矩阵的一个排列。

　　对于纳什均衡近似器，由于纳什均衡为乘积联合策略，因此模型输出f(u)=(f(u)_{1}, f(u)_{2}, ... , f(u)_{n})为n个玩家的边缘策略。它的等价性分为两种：第一种是玩家排列等价性（Player-Permutation-Equivariance, PPE），即对玩家i的动作空间的排列，会对输出的该玩家边缘策略f(u)_{i}产生相同的排列：

　　其中ρ_{i}表示玩家i的动作空间的排列；第二种是对手排列不变性（Opponent-Permutation-Invariance, OPI），即对玩家i的动作空间的排列，不会对输出的其他玩家边缘策略产生任何影响：

03 理论结果：优势

　　在理论推导方面，我们通过近似值（approximation）ε(π, u)来衡量在博弈u中联合策略π对均衡的近似程度，其定义为所有玩家通过改变策略能获得的最大效用增加量。根据近似均衡的定义，我们有：

联合策略π是博弈u的∈近似（纳什、相关、粗相关）均衡↔ε(π, u)≤∈

　　为了对比等价近似器与普通近似器，我们利用轨道平均（orbit average）操作将一个普通近似器映射成一个等价近似器。对于等价近似器，轨道平均操作会得到它自己。如果作用于整个函数类，轨道平均操作能够在保证映射后函数满足等价性的同时，最大化保留函数类的表达能力。

　　基于轨道平均操作，我们发现映射后的函数类具备更小的覆盖数（covering number），结合我们在定理5.2和定理5.4中推导的所有三种均衡近似器的泛化误差和样本复杂性，更小的覆盖数可以得到更强的泛化能力。

　　此外，我们在定理5.6-5.9中刻画了当效用矩阵分布满足排列不变性时，轨道平均后的等价近似器在很多情况下可以取得更好的期望近似表现。

04 理论结果：局限

　　我们首先通过构造发现三种等价近似器的一个局限是不能够寻找所有的均衡点。为了衡量该缺陷的负面影响，我们计算等价近似器可寻均衡点的最大社会福利与所有均衡点的最大社会福利的比值，其中社会福利的定义为联合策略下所有玩家的效用之和。

　　我们发现，对于相关均衡与粗相关均衡的等价近似器，该社会福利比值可以达到1。但是对于纳什均衡的等价近似器，该社会福利比值可以无限趋近于0。这一局限告诉我们等价的纳什均衡近似器可能会带来社会福利上的损失。

参考文献

[1] Duan, Zhijian, Wenhan Huang, Dinghuai Zhang, Yali Du, Jun Wang, Yaodong Yang, and Xiaotie Deng. "Is Nash Equilibrium Approximator Learnable?." AAMAS 2023.

[2] Marris, Luke, Ian Gemp, Thomas Anthony, Andrea Tacchetti, Siqi Liu, and Karl Tuyls. "Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers." NeurIPS 2022.

[3] Feng, Xidong, Oliver Slumbers, Yaodong Yang, Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen, and Jun Wang. "Discovering multi-agent auto-curricula in two-player zero-sum games." NeurIPS 2021.