N-联盟博弈的分布式纳什均衡求解：一种基于记忆的加速算法

《Systems & Control Letters》：Distributed Nash equilibrium seeking for N-coalition games: A memory-based accelerated algorithm

　　

摘要
本文考虑了 N-联盟博弈中的纳什均衡求解问题，其中同一联盟内的智能体试图合作最小化其私有成本之和。针对该问题，我们为每个智能体设计了一个动作估计器和一个平均梯度估计器，并提出了一种基于这些估计器的具有局部记忆的分布式纳什均衡求解算法。然后，我们提出了一个保证算法收敛到纳什均衡的充分条件。此外，我们给出了算法收敛率的上界。在一定条件下，我们证明了基于记忆的算法的上界小于无记忆算法的上界，并且随着记忆系数的增加而减小。我们还比较了梯度记忆和动作记忆对上界的影响。最后，提供了一个仿真验证所提算法的有效性。

引言
有许多关于多智能体系统（例如 [1]，[2]）的研究，仅关注群体内部的竞争或合作行为（例如 [3]，[4]）。然而，竞争行为与合作行为的共存是人工和社会群体中常见的现象，如医疗网络 [5]、两群无人机之间的对抗 [6] 等。为了建模这些现象，文献 [7] 的作者提出了 N-联盟博弈，其中同一联盟内的智能体是合作的，而每个联盟则以自利的方式行事，以最小化自身成本而不顾其他联盟。因此，这种设置自然地导致了多个联盟之间的非合作博弈 [8]，这种博弈被称为 N-联盟非合作博弈。在 N-联盟博弈中，存在一种特殊的均衡，即没有任何智能体可以通过单方面改变自己的动作来降低其联盟的总成本，这被称为纳什均衡。

为了求解 N-联盟博弈的纳什均衡，文献 [7] 基于动态平均一致性协议设计了一种连续时间算法。然而，该算法依赖于完整的决策信息，这是一种集中式方法，占用了大量的通信和计算资源。因此，提出了许多用于 N-联盟博弈的分布式纳什均衡求解算法 [9]，[10]，[11]，[12]，[13]，[14]，[15]，[16]，[17]，[18]，[19]，[20]。

为 N-联盟博弈设计了连续时间算法 [9]，[10]，[11]，[13]，[16]。由于物理设备的限制，每个智能体无法确保持续通信，这使得连续时间算法在实际中难以应用。因此，设计了离散时间算法来解决这个问题，并且能够线性收敛到纳什均衡 [12]，[14]，[15]，[17]，[18]，[19]。文献 [12] 中提出的用于求解一致性约束 N-联盟博弈纳什均衡的算法基于一致性协议和平均梯度跟踪方法。在 [14] 中，作者将该设置扩展为具有边协议约束的 N-联盟博弈，这比一致性约束更一般。当每个智能体的局部成本函数不可用时，文献 [15] 的作者使用无梯度方法设计了一种分布式算法。在 [17] 中，使用投影和平均梯度跟踪方法为局部凸约束下的 N-联盟博游戏设计了一种分布式算法。文献 [18]，[19] 的作者都将联盟决策的估计和平均梯度跟踪集成到了算法设计中。

值得注意的是，在上述针对 N-联盟博弈的纳什均衡求解算法中，一旦智能体更新其局部信息，每个智能体的历史迭代信息就被遗忘了。近年来，许多研究报告表明，过去信息的记忆可以加速分布式算法的收敛率。文献 [21] 表明，如果选择了适当的记忆系数，具有局部记忆的分布式一致性算法比经典一致性算法 [22] 实现了更快的收敛率。此外，文献 [23] 的作者声称记忆信息可以提高一致性网络的鲁棒性和可扩展性。在 [24]，[25]，[26]，[27]，[28] 中，使用记忆信息来加速分布式优化算法的收敛率。此外，文献 [20] 的作者开发了一种基于 Nesterov 方法的用于 N-联盟博弈的加速分布式纳什均衡求解算法，其中当前和未来智能体的动作被用来构建下一次更新的 Nesterov 动量。尽管如此，文献 [20] 的作者仅获得了其算法收敛率的上界，并没有进一步研究 Nesterov 动量如何影响这个上界。据我们所知，如何利用局部记忆信息为 N-联盟博游戏设计高效的纳什均衡求解尚未得到解决，尽管这是一个非常有趣的问题。

受上述观察的启发，我们旨在设计一种基于局部记忆的用于 N-联盟博弈的加速分布式纳什均衡求解算法，并研究记忆信息对算法收敛率的影响。本文的贡献总结如下：
•我们设计了一种新颖的用于 N-联盟博弈的加速分布式纳什均衡求解算法，利用了局部记忆和平均梯度跟踪方法。具体来说，该算法基于当前和历史动作及梯度信息的线性组合进行更新。此外，我们提供了一个确保算法找到纳什均衡的充分条件。
•我们推导了所提算法收敛率的上界。在一定条件下，证明该上界小于相应的无记忆算法的上界。此外，证明了该上界在一定区间内关于记忆系数单调递减。这些结果有助于分析其对算法收敛性能的影响。
•我们研究了动作记忆和梯度记忆如何影响所提算法的收敛率，并建立了评估哪种记忆机制在降低收敛率上界方面更有效的标准。

本文的组织结构如下：在第 2 节中介绍了预备知识。问题描述在第 3 节中给出。第 4 节展示了本文的结果。我们在第 5 节中给出了一个数值例子，第 6 节对本文进行了总结。

章节片段
符号说明
记 ?、?、??? 和 ???×?? 分别为自然数集、实数集、?? 维实列向量集和 ??×?? 实矩阵集。令 ???(??) 表示方阵 ?? 的谱半径。对于矩阵 ??∈???×??，令 ??? 和 [??]???? 分别表示其转置和位于第 ?? 行第 ?? 列的元素。令 ??,??、‖?‖2 和 ‖?‖?? 分别表示欧几里得内积、欧几里得范数和弗罗贝尼乌斯范数，其定义为 ???,???=??????、‖??‖2=√?????? 和 ‖??‖??=√∑????=1

问题描述
本文考虑一个 N-联盟（??≥2）博弈。博弈中有 ???=∑????=1???? 个智能体，其中 ???? 表示联盟 ?? 中的智能体数量。令 ????,?? 表示第 ?? 个联盟中的第 ?? 个智能体，令 ????,???(?????(??),??????(??)) 为 ????,?? 的私有成本函数，其中 ?????(??)=col?(????,1?(??),…,????,?????(??))∈?????，且 ????,???(??)∈? 表示 ????,?? 在时间 ?? 的动作，??????(??)=col?(??1?(??),…,?????1?(??),????+1?(??),…,?????(??))∈????????? 表示联盟 ?? 之外所有智能体的聚合动作。此外，???(??)=col?(??1?(??)…

主要结果
在本节中，我们为具有局部记忆的 N-联盟博游戏设计分布式纳什均衡求解算法。随后，我们展示其收敛性分析。

仿真
在本节中，我们考虑一个 N-联盟博游戏，其中 ??=20，且对于 ??=1,…?? 有 ????=4。在 20-联盟博游戏中，内部网络和外部网络如图 2 所示，其中 ??0 是一个循环图。联盟 ?? 的内部网络的加权邻接矩阵如下：????=?? ? ? ??1/31/301/31/31/31/3001/31/31/31/301/31/3?? ? ? ??。外部网络的加权邻接矩阵如下：??0=?? ? ? ? ??1/31/30?1/31/31/31/3?001/31/3?0?????1/300?1/3?? ? ? ? ??，其中 ??0∈?80×80。令 ????=2????21，对于 ??=1,…,??。令 ??0,1=????,1，????+1,1=

结论
在本文中，利用局部记忆为具有内部和外部网络的 N-联盟博游戏设计了一种加速分布式纳什均衡求解算法，并提出了该算法收敛的充分条件。此外，我们获得了算法的线性收敛率上界，并证明了当记忆系数位于区间 (0,min?{??2,msub

作者贡献声明
Daning Lei: 写作 – 初稿，调查。Jiamin Wang: 写作 – 审查与编辑，方法论。Jian Liu: 写作 – 审查与编辑，监督，项目管理，方法论。Yuanshi Zheng: 写作 – 审查与编辑，项目管理，方法论。

利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。

Daning Lei|Jiamin Wang|Jian Liu|Yuanshi Zheng