On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games
On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games
作者：Zhengyang Liu, Jiawei Li, Xiaotie Deng
DOI：https://doi.org/10.1609/aaai.v35i6.16699
问题：
- SWLP游戏现有研究有什么不足？此研究如何填补现有的空白？
- 如何构建SWLP游戏模型？算法基于什么理论基础？为何此算法适用于SWLP游戏？
- 实验结果支持哪些假设？如何解释实验中观察到的异常或意外结果？
- 在实现算法时有什么技术难题？如何解决？
论文概述
1. 简介
论文研究了稀疏输赢多玩家博弈（Sparse Win-Lose Polymatrix Games, SWLP）中纳什均衡的近似问题。SWLP是一种特殊的多玩家博弈，其中每个玩家有两种策略选择，且博弈的支付矩阵非常稀疏，大部分元素为零。
论文里通过构建一个多项式时间近似方案（PTAS）证明了在某些情况下，寻找纳什均衡是PPAD-hard的，即在多项式时间内无法找到一个近似解。为了解决这项问题，算法在多项式时间内为特定类型的SWLP游戏找到了纳什均衡。这个算法的核心在于利用了SWLP游戏的稀疏性和赢-输特性，通过迭代改进策略来逐步逼近纳什均衡。
在本篇论文里探讨了SWLP游戏对于(n,1)和(1, n)两种特殊情况，并证明了这两种情况下纳什均衡可以被精确的找到，且所需的计算复杂度较低。
2. 准备知识
2.1纳什均衡
这篇论文最核心的概念，在多玩家博弈中扮演很重要的角色。
定义：在一个非合作博弈中，每个玩家都选择了自己的最优策略，并且在其他玩家策略不变的情况下，没有任何一个玩家能够通过改变自己的策略来提高自己的收益。
纳什均衡例子参考上一章[1-1 Game Theory Intro - TCP Backoff]
纳什均衡在SWLP中的贡献
- 复杂性分析：作者证明了在某些SWLP游戏中，找到纳什均衡是一个PPAD-hard问题，这意味着在多项式时间内找到一个近似解是困难的。
- 算法设计：尽管存在计算难度，作者提出了一个高效的算法，能够在多项式时间内为特定类型的SWLP游戏找到纳什均衡。
- 理论贡献：这些结果不仅挑战了纳什均衡在多玩家设置中的可预测性，也为理解博弈论中的计算难题提供了新的视角。
在SWLP游戏中，寻找纳什均衡意味着确定每个玩家在给定其他玩家策略的情况下的最优策略。纳什均衡在这篇论文中是评估和优化玩家策略选择的关键标准，论文通过分析纳什均衡的计算复杂性和设计有效的求解算法。
2.2 计算复杂性
计算复杂性（Computational Complexity）是计算机科学中的一个核心领域，它研究解决特定问题所需的计算资源，尤其是时间资源和空间资源。
flowchart LR id1([计算复杂性的关注点]) --> id2(时间复杂性) & id3(空间复杂性)
复杂性理论类型
计算复杂性理论中，问题通常被归类为以下几种类型：
- P类问题（Polynomial Time）：这些问题可以在多项式时间内解决，即算法的运行时间与输入大小的多项式成正比。
- NP类问题（Nondeterministic Polynomial Time）：这些问题可以在多项式时间内验证一个给定解是否正确，但找到这个解可能需要指数级时间。NP问题包括了许多实际中遇到的优化问题。
- NP-hard问题：这些问题至少和NP类问题一样难。如果一个问题是NP-hard，那么任何NP问题都可以通过多项式时间的转换归约到它。
- NP-complete问题：这些问题既是NP-hard也是NP类问题。这意味着如果任何一个NP-complete问题可以在多项式时间内解决，那么所有的NP问题都可以在多项式时间内解决。
- P = NP问题：这是一个未解决的数学问题，询问是否存在一个多项式时间算法可以解决所有NP类问题。如果P = NP，那么所有的NP问题都可以在多项式时间内解决。
2.3 PPAD-hardness
什么是PPAD-hard
PPAD-hard（Polynomial Parity Argument, Hard）是一个描述问题难度的术语。PPAD是一类问题，这些问题可以通过多项式时间的归约来证明其难度。PPAD-hard意味着一个问题至少和PPAD类中的问题一样难，也就是说，如果一个问题是PPAD-hard，那么它不能在多项式时间内被解决，除非P = NP，这是一个著名的未解决的数学问题。
我们需要寻找近似算法或者在特定情况下的特例来处理这类问题。在多玩家博弈论中，PPAD-hard问题通常涉及到寻找纳什均衡，这是一个在博弈论中寻找稳定策略配置的问题。
在论文中，“Make It Sparse”、“Make It ‘Win-Lose’” 和 “Reduction to (2, 2)-SWLP Games” 是构建和证明 SWLP 游戏模型 PPAD-hardness 的关键步骤。这些步骤的目的是通过简化和转换原始问题，使其更容易理解和处理，同时保持问题的困难性质。
- Make It Sparse：
- 目的：通过减少支付矩阵中的非零元素数量，使得模型更加稀疏。这有助于简化后续的分析和计算过程。
- 方法：通过设计游戏小玩意（gadgets）来模拟复杂的逻辑门（gates），同时保持每个玩家的策略矩阵中非零元素的数量有限。
- Make It “Win-Lose”：
- 目的：将游戏的支付结构简化为赢或输，即每个玩家的收益要么是 1（赢），要么是 0 或 -1（输）。这种简化有助于将问题转化为一个更易于处理的形式。
- 方法：通过引入新的游戏小玩意，将非赢即输的策略转换为赢-输策略，同时保持游戏的等价性。
- Reduction to (2, 2)-SWLP Games：
- 目的：将问题归约到一个更小、更简单的实例，即 (2, 2)-SWLP 游戏，其中每个玩家只有两种策略，且每个玩家的策略矩阵中只有两行两列。
- 方法：通过构造一个映射，将原始的复杂问题转化为一个 (2, 2)-SWLP 游戏的实例，这个映射保持了问题的困难性，即如果原始问题是 PPAD-hard，那么归约后的 (2, 2)-SWLP 游戏也是 PPAD-hard。
步骤的目的是为了证明 SWLP 游戏的纳什均衡问题是 PPAD-hard，即在多项式时间内找到一个近似解是困难的。通过这些简化和归约，作者能够清晰地展示问题的复杂性，并为后续的研究和算法设计提供理论基础。这些步骤展示了将一个复杂的计算问题简化为一个更易于处理的形式，同时保持其核心困难性质的方法。
3.模型与算法
3.1 SWLP游戏模型构建
classDiagram
class Player {
+int playerID
+int strategy
+int payoff
}
class Strategy {
+int strategyID
+String description
}
class Game {
+List<Player> players
+List<Strategy> strategies
+Map<String, int[]> payoffMatrix
}
class GameModel {
+Game game
}
class PlayerStrategy {
+Player player
+Strategy strategy
}
GameModel --> Game
Game --> Player : contains
Game --> Strategy : contains
Game --> PlayerStrategy : uses
Player --> Strategy : selects
在这个类图中：
- Player 类表示游戏中的每个玩家，包含玩家ID、策略和收益等属性。
- Strategy 类表示游戏中的策略，包含策略ID和描述等属性。
- Game 类表示整个游戏，包含玩家列表、策略列表以及一个收益矩阵（payoffMatrix），这是一个映射，将玩家ID和策略ID的组合映射到相应的收益。
- GameModel 类表示游戏模型，它包含一个Game实例。
- PlayerStrategy 类表示玩家选择的策略，它关联了Player和Strategy。
类之间的关系如下：
- 聚合（Aggregate）：
Game类聚合了Player和Strategy类，意味着游戏包含玩家和策略。 - 关联（Association）：
Player类与Strategy类之间存在关联关系，表示玩家可以选择策略。 - 使用（Usage）：
Game类使用PlayerStrategy类，表示游戏使用玩家策略的实例。 - 包含（Composition）：
Game类包含Player类和Strategy类，表示玩家和策略是游戏的一部分。
3.2 Algorithm 5
graph TD A[初始化 r[i] 和 S] --> B[开始循环] B --> C[检查 flag] C -->|flag 为 true| D[重置 flag] C -->|flag 为 false| E[结束循环] D --> F[对于所有 l ∈ [2n]] F --> G[如果 l 是玩家 v 的一个行动] G --> H[如果 v 不在 S 中] H --> I[继续] G --> J[标记 l' 为玩家 v 的另一个行动] J --> K[如果 r[l] + Count(P, l) ≤ r[l'] 且 l ≠ l'] K --> L[设置 flag 为 true] K --> M[设置 x*[l] ← 0, x*[l'] ← 1] K --> N[对于所有 j ∈ [2n], 如果 P[l'][j] = 1] N --> O[增加 r[j] ← r[j] + 1] B --> P[如果 flag 为 false] P --> Q[对于所有玩家 v ∈ S] Q --> R[设置 x*[l], x*[l'] ← 1/2] R --> S[返回 x*]
.jpeg)
