448 lines
13 KiB
Markdown
448 lines
13 KiB
Markdown
---
|
||
title: 00-博弈论
|
||
draft: false
|
||
tags:
|
||
- 博弈论
|
||
- 纳什均衡
|
||
- 数学基础
|
||
- 强化学习
|
||
---
|
||
|
||
# 博弈论基础
|
||
|
||
> 本笔记面向深度学习与强化学习科研人员，系统阐述博弈论的核心概念、数学基础与算法。
|
||
> 更新日期：2026-05-14
|
||
|
||
---
|
||
|
||
## 1. 博弈论基础概念
|
||
|
||
### 1.1 基本元素
|
||
|
||
**定义 1.1（博弈）** 一个博弈由三元组 $G = (N, A, u)$ 构成：
|
||
- $N = \{1, 2, \ldots, n\}$：玩家集合
|
||
- $A = A_1 \times A_2 \times \cdots \times A_n$：策略空间，其中 $A_i$ 为玩家 $i$ 的可行策略集
|
||
- $u = (u_1, u_2, \ldots, u_n)$：收益函数，其中 $u_i : A \rightarrow \mathbb{R}$ 为玩家 $i$ 的效用函数
|
||
|
||
**定义 1.2（正常形博弈）** 当博弈描述为玩家同时选择策略时，称为正常形博弈（Normal Form Game），其收益矩阵为：
|
||
|
||
$$
|
||
u_i(a_1, a_2, \ldots, a_n) \quad \forall i \in N, \forall a_i \in A_i
|
||
$$
|
||
|
||
### 1.2 扩展形博弈
|
||
|
||
**定义 1.3（扩展形博弈）** 扩展形博弈（Extensive Form Game）通过博弈树描述时序决策：
|
||
|
||
$$
|
||
\Gamma = (H, Z, A, P, I, u)
|
||
$$
|
||
|
||
其中：
|
||
- $H$：非终止节点集合（决策节点）
|
||
- $Z$：终止节点集合（终点）
|
||
- $A$：所有可行行动集合
|
||
- $P: H \rightarrow N \cup \{c\}$：玩家函数，将每个节点分配给某玩家或 chance（随机事件）
|
||
- $I = \{I_1, I_2, \ldots, I_n\}$：信息分割，其中 $I_i$ 为玩家 $i$ 的信息集
|
||
- $u_i: Z \rightarrow \mathbb{R}$：玩家 $i$ 在终点 $z \in Z$ 的收益
|
||
|
||
**完美回忆（Perfect Recall）** 若玩家在博弈过程中始终记得其历史决策，则称该博弈满足完美回忆条件：
|
||
|
||
$$
|
||
h, h' \in I_i \implies \text{历史完全一致}
|
||
$$
|
||
|
||
### 1.3 最优响应与效用
|
||
|
||
**定义 1.4（最优响应）** 给定其他玩家的策略 $a_{-i}^*$，玩家 $i$ 的最优响应为：
|
||
|
||
$$
|
||
BR_i(a_{-i}^*) = \arg\max_{a_i \in A_i} u_i(a_i, a_{-i}^*)
|
||
$$
|
||
|
||
**定义 1.5（严格优势）** 策略 $a_i$ 严格优于策略 $a_i'$，若对 $\forall a_{-i} \in A_{-i}$：
|
||
|
||
$$
|
||
u_i(a_i, a_{-i}) > u_i(a_i', a_{-i})
|
||
$$
|
||
|
||
---
|
||
|
||
## 2. 纳什均衡（Nash Equilibrium）
|
||
|
||
### 2.1 纳什均衡的定义
|
||
|
||
**定义 2.1（纯策略纳什均衡）** 策略组合 $a^* = (a_1^*, \ldots, a_n^*)$ 构成纳什均衡，当且仅当 $\forall i \in N, \forall a_i \in A_i$：
|
||
|
||
$$
|
||
u_i(a_i^*, a_{-i}^*) \geq u_i(a_i, a_{-i}^*)
|
||
$$
|
||
|
||
**等价表述**：$a_i^*$ 是对 $a_{-i}^*$ 的最优响应，即 $a_i^* \in BR_i(a_{-i}^*)$。
|
||
|
||
### 2.2 混合策略纳什均衡
|
||
|
||
**定义 2.2（混合策略）** 玩家 $i$ 的混合策略 $\sigma_i$ 是其纯策略空间 $A_i$ 上的概率分布：
|
||
|
||
$$
|
||
\sigma_i(a_i) \geq 0, \quad \sum_{a_i \in A_i} \sigma_i(a_i) = 1
|
||
$$
|
||
|
||
**定义 2.3（混合策略纳什均衡）** 混合策略组合 $\sigma^* = (\sigma_1^*, \ldots, \sigma_n^*)$ 构成纳什均衡，当且仅当 $\forall i, \forall a_i \in A_i$：
|
||
|
||
$$
|
||
u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(a_i, \sigma_{-i}^*)
|
||
$$
|
||
|
||
其中 $u_i(\sigma_i, \sigma_{-i}) = \sum_{a_i, a_{-i}} \sigma_i(a_i) \sigma_{-i}(a_{-i}) u_i(a_i, a_{-i})$。
|
||
|
||
### 2.3 纳什均衡的存在性证明
|
||
|
||
**定理 2.1（纳什存在定理）** 任意有限玩家、有限策略的正常形博弈至少存在一个混合策略纳什均衡。
|
||
|
||
**证明（Brouwer 不动点定理）**：
|
||
|
||
构造策略组合空间 $\Delta = \Delta_1 \times \cdots \times \Delta_n$，其中 $\Delta_i$ 为玩家 $i$ 的混合策略单纯形。
|
||
|
||
对每个玩家 $i$ 定义响应函数 $f_i: \Delta_{-i} \rightarrow \Delta_i$：
|
||
|
||
$$
|
||
f_i(\sigma_{-i})(a_i) = \frac{\max(0, u_i(a_i, \sigma_{-i}) - u_i(\sigma_i, \sigma_{-i}))}{\sum_{a_i' \in A_i} \max(0, u_i(a_i', \sigma_{-i}) - u_i(\sigma_i, \sigma_{-i}))}
|
||
$$
|
||
|
||
其中 $u_i(\sigma_i, \sigma_{-i})$ 为当前策略下的期望收益。
|
||
|
||
该映射 $F: \Delta \rightarrow \Delta$ 连续（收益函数的线性组合）。由于 $\Delta$ 为紧凸集，Brouwer 不动点定理确保存在 $\sigma^*$ 使得 $F(\sigma^*) = \sigma^*$。
|
||
|
||
验证不动点条件：对任何 $a_i$ 若 $u_i(a_i, \sigma_{-i}^*) > u_i(\sigma_i^*, \sigma_{-i}^*)$，则 $f_i(\sigma_{-i}^*)(a_i) > 0$；若 $u_i(a_i, \sigma_{-i}^*) < u_i(\sigma_i^*, \sigma_{-i}^*)$，则 $f_i(\sigma_{-i}^*)(a_i) = 0$。故不动点即为纳什均衡。$\square$
|
||
|
||
### 2.4 纳什均衡的唯一性与稳定性
|
||
|
||
**定义 2.4（NE 的唯一性）** 博弈可能有多个纳什均衡，需通过稳定性分析筛选。
|
||
|
||
**定义 2.5（渐进稳定）** 考虑最佳响应动态的离散系统：
|
||
|
||
$$
|
||
\sigma_i^{t+1} = BR_i(\sigma_{-i}^t)
|
||
$$
|
||
|
||
若某 NE 周围的雅可比矩阵特征值模小于 1，则该 NE 局部渐进稳定。
|
||
|
||
---
|
||
|
||
## 3. 零和博弈（Zero-Sum Game）
|
||
|
||
### 3.1 基本定义
|
||
|
||
**定义 3.1（零和博弈）** 双人零和博弈满足 $u_1 + u_2 = 0$，可记为收益矩阵 $A$（玩家 1 的收益）：
|
||
|
||
$$
|
||
u_1(p, q) = p^\top A q, \quad u_2(p, q) = -p^\top A q
|
||
$$
|
||
|
||
其中 $p \in \Delta(A_1)$，$q \in \Delta(A_2)$ 为双方的混合策略。
|
||
|
||
### 3.2 鞍点与 Minimax 定理
|
||
|
||
**定义 3.2（鞍点）** 策略对 $(p^*, q^*)$ 为鞍点若满足：
|
||
|
||
$$
|
||
p^{*\top} A q^* \leq p^{*\top} A q, \quad \forall p \in \Delta(A_1), \forall q \in \Delta(A_2)
|
||
$$
|
||
|
||
**定理 3.1（Minimax 定理）** 有限双人零和博弈满足：
|
||
|
||
$$
|
||
\max_{p \in \Delta(A_1)} \min_{q \in \Delta(A_2)} p^\top A q = \min_{q \in \Delta(A_2)} \max_{p \in \Delta(A_1)} p^\top A q = v^*
|
||
$$
|
||
|
||
**证明（线性规划对偶）**：
|
||
|
||
玩家 1 的最小最大化问题：
|
||
|
||
$$
|
||
\max_p \min_q p^\top A q = \max_p v \quad \text{s.t.} \quad [Ap]_j \geq v, \forall j
|
||
$$
|
||
|
||
等价变换（消除常数 $v$）：
|
||
|
||
$$
|
||
\min_{p, v} -v \quad \text{s.t.} \quad Ap \geq v \cdot \mathbf{1}, \quad \sum_i p_i = 1, \quad p \geq 0
|
||
$$
|
||
|
||
其对偶问题为：
|
||
|
||
$$
|
||
\max_{q, \lambda} \lambda \quad \text{s.t.} \quad A^\top q \leq \lambda \cdot \mathbf{1}, \quad \sum_j q_j = 1, \quad q \geq 0
|
||
$$
|
||
|
||
这恰对应玩家 2 的最大化最小化问题 $\min_q \max_p p^\top A q$。由线性规划对偶理论，强对偶性成立。$\square$
|
||
|
||
### 3.3 鞍点不等式推导
|
||
|
||
**引理 3.1（鞍点不等式）** 若 $(p^*, q^*)$ 为鞍点，则：
|
||
|
||
$$
|
||
p^\top A q^* \leq p^{*\top} A q^* \leq p^{*\top} A q, \quad \forall p, \forall q
|
||
$$
|
||
|
||
由鞍点性质可直接导出 minimax 等式：
|
||
|
||
$$
|
||
\max_p p^\top A q^* \leq p^{*\top} A q^* \leq \min_q p^{*\top} A q
|
||
$$
|
||
|
||
由于 $\max_p \min_q p^\top A q \geq \min_q p^\top A q$ 对任意 $p, q$ 成立，故等式两边相等。
|
||
|
||
### 3.4 策略空间的线性规划
|
||
|
||
双人零和博弈的求解可转化为线性规划：
|
||
|
||
**玩家 1 的 LP（最大化最小收益）**：
|
||
|
||
$$
|
||
\max_{p, v} v \quad \text{s.t.} \quad \sum_i p_i a_{ij} \geq v, \quad \forall j, \quad \sum_i p_i = 1, \quad p_i \geq 0
|
||
$$
|
||
|
||
**玩家 2 的 LP（最小化最大收益）**：
|
||
|
||
$$
|
||
\min_{q, u} u \quad \text{s.t.} \quad \sum_j a_{ij} q_j \leq u, \quad \forall i, \quad \sum_j q_j = 1, \quad q_j \geq 0
|
||
$$
|
||
|
||
---
|
||
|
||
## 4. 纳什均衡的计算
|
||
|
||
### 4.1 优势消去（IESDS）
|
||
|
||
**定义 4.1（严格劣势策略）** 策略 $a_i$ 对玩家 $i$ 严格劣于 $a_i'$，若 $\forall a_{-i}$：
|
||
|
||
$$
|
||
u_i(a_i, a_{-i}) < u_i(a_i', a_{-i})
|
||
$$
|
||
|
||
**算法：迭代优势消去（IESDS）**
|
||
|
||
```
|
||
while 存在劣势策略 do
|
||
消去所有严格劣势策略
|
||
end while
|
||
```
|
||
|
||
**性质**：若博弈存在唯一纳什均衡，IESDS 必收敛至该均衡；但若有多个均衡，IESDS 可能消去部分均衡。
|
||
|
||
### 4.2 虚拟对弈（Fictitious Play）
|
||
|
||
**定义 4.2（虚拟对弈）** 经典虚拟对弈中，玩家假设对手以历史平均频率选择策略：
|
||
|
||
$$
|
||
\sigma_{-i}^t = \frac{1}{t} \sum_{\tau=1}^t a_{-i}^{\tau}
|
||
$$
|
||
|
||
玩家 $i$ 以最优响应更新策略：
|
||
|
||
$$
|
||
a_i^{t+1} \in BR_i(\sigma_{-i}^t)
|
||
$$
|
||
|
||
**收敛性**：针对特定博弈类（如零和博弈）可证伪，但一般博弈不一定收敛。
|
||
|
||
### 4.3 Lemke-Howson 算法
|
||
|
||
**算法 4.1（Lemke-Howson）** 适用于双人有限博弈的均衡求解：
|
||
|
||
1. 选择初始失衡玩家 $k$ 和扰动参数 $\lambda$
|
||
2. 构造辅助线性规划问题
|
||
3. 沿着可行方向 pivot 直到满足均衡条件
|
||
|
||
该算法在最坏情况下指数复杂度，但在实践中对结构化博弈效率较高。
|
||
|
||
### 4.4 梯度下降法（Gradient Play）
|
||
|
||
**定义 4.3（梯度Play）** 将纳什均衡视为不动点，用梯度下降求解：
|
||
|
||
$$
|
||
\sigma^{t+1} = \Pi_{\Delta}\left(\sigma^t - \eta \cdot \nabla u(\sigma^t)\right)
|
||
$$
|
||
|
||
其中 $\Pi_{\Delta}$ 为欧几里得投影到策略单纯形。
|
||
|
||
**收敛性**：对于单阶梯度动态，一般博弈无收敛保证；但对零和博弈可证某些条件下收敛。
|
||
|
||
---
|
||
|
||
## 5. 扩展形博弈与子博弈完美均衡
|
||
|
||
### 5.1 扩展形博弈的表示
|
||
|
||
扩展形博弈通过博弈树 $T = (V, E)$ 描述，其中：
|
||
- $V = V_h \cup V_z$（决策节点与终点节点）
|
||
- 每个决策节点 $v \in V_h$ 关联玩家 $P(v) \in N$
|
||
- 边 $(v, v', a)$ 表示行动 $a$
|
||
|
||
### 5.2 信息集与完美回忆
|
||
|
||
**定义 5.1（信息集）** 同一玩家不可区分的节点集合：
|
||
|
||
$$
|
||
I_i = \{h \in H : P(h) = i\}
|
||
$$
|
||
|
||
完美回忆要求：玩家在信息集中各节点的可达历史完全相同。
|
||
|
||
### 5.3 子博弈完美均衡（SP E）
|
||
|
||
**定义 5.2（子博弈）** 从节点 $h$ 开始的子博弈包含所有以 $h$ 为根的可达终止节点。
|
||
|
||
**定义 5.3（子博弈完美均衡）** 策略组合 $\sigma^*$ 在每个子博弈上均构成纳什均衡。
|
||
|
||
**定理 5.1（SPE 存在性）** 任意有限扩展形博弈（完美回忆）存在至少一个子博弈完美均衡。
|
||
|
||
### 5.4 逆向归纳法（Backward Induction）
|
||
|
||
**算法 5.1（逆向归纳）**
|
||
|
||
```
|
||
从终止节点逆向计算：
|
||
for 节点 h 从深到浅 do
|
||
若 h 为终点：计算效用
|
||
若 h 为玩家节点：
|
||
选择使该玩家收益最大的行动
|
||
end for
|
||
```
|
||
|
||
**性质**：有限完美信息博弈中，逆向归纳产生唯一 SPE。
|
||
|
||
---
|
||
|
||
## 6. CFR（Counterfactual Regret Minimization）
|
||
|
||
### 6.1 虚拟对局后悔值
|
||
|
||
**定义 6.1（Counterfactual Regret）** 在时刻 $t$ 玩家 $i$ 选择行动 $a$ 的虚拟后悔值：
|
||
|
||
$$
|
||
R_i^t(a) = \frac{1}{N} \sum_{k=1}^N I(h \in I_i) [u_i(\sigma^k) - u_i(\sigma^k_{-I_i}, a)]
|
||
$$
|
||
|
||
其中：
|
||
- $N$：总采样序列数
|
||
- $I(h \in I_i)$：指示函数，判断历史 $h$ 是否在玩家 $i$ 的信息集 $I_i$ 中
|
||
- $\sigma^k_{-I_i}, a$：在第 $k$ 次序列中，在 $I_i$ 处替换为行动 $a$ 的策略
|
||
|
||
### 6.2 CFR 算法
|
||
|
||
**算法 6.1（CFR 迭代）**
|
||
|
||
对每次迭代 $t$：
|
||
1. 基于当前策略 $\sigma^t$ 生成采样序列
|
||
2. 对每个信息集 $I_i$ 和行动 $a$，计算后悔值 $R_i^t(a)$
|
||
3. 更新策略：
|
||
|
||
$$
|
||
\sigma^{t+1}_i(a) = \frac{\max(0, R_i^{+,t}(a))}{\sum_{a' \in A(I_i)} \max(0, R_i^{+,t}(a'))}
|
||
$$
|
||
|
||
其中 $R_i^{+,t}(a) = \max(R_i^t(a), 0)$ 为正部分。
|
||
|
||
### 6.3 CFR+ 算法
|
||
|
||
CFR+ 通过以下改进提升收敛速度：
|
||
|
||
1. **线性加权平均**：对历史策略加权平均，近期权重更高
|
||
|
||
$$
|
||
\bar{\sigma}^T = \frac{\sum_{t=1}^T (2t-1) \sigma^t}{\sum_{t=1}^T (2t-1)}
|
||
$$
|
||
|
||
2. **替代遗憾值**：$R_i^{T}(a) = \max(R_i^{T-1}(a) + R_i^{t}(a), 0)$
|
||
|
||
### 6.4 外部后悔值与收敛性
|
||
|
||
**定义 6.2（外部后悔值）**：
|
||
|
||
$$
|
||
R_T(\sigma) = \frac{1}{T} \max_{\sigma^*} \sum_{t=1}^T [u(\sigma^*, \sigma_{-i}^t) - u(\sigma^t, \sigma_{-i}^t)]
|
||
$$
|
||
|
||
**定理 6.1（CFR 收敛性）** 若每个玩家的外部后悔值 $R_T \rightarrow 0$，则平均策略序列收倥至纳什均衡。
|
||
|
||
### 6.5 蒙特卡洛 CFR（MCCFR）
|
||
|
||
**算法 6.2（MCCFR）**
|
||
|
||
- ** outcome sampling**：对每条轨迹只采样一个后继
|
||
- ** chance sampling**：对 chance 节点按先验概率采样
|
||
- **外部采样**：只跟踪单方的信息集更新
|
||
|
||
---
|
||
|
||
## 7. 均值场博弈（Mean Field Game）
|
||
|
||
### 7.1 大量智能体的近似
|
||
|
||
均值场博弈处理 $N \rightarrow \infty$ 的多智能体系统，其中单个智能体的影响可忽略。
|
||
|
||
**定义 7.1（均值场近似）** 智能体 $i$ 视其他智能体为统计分布 $\mu \in \mathcal{P}(\Theta)$：
|
||
|
||
$$
|
||
\mu(\theta) = \lim_{N \to \infty} \frac{1}{N-1} \sum_{j \neq i} \delta_{\theta_j}
|
||
$$
|
||
|
||
### 7.2 配对均值场近似
|
||
|
||
智能体间相互作用通过配对势能 $V(x, x')$ 建模：
|
||
|
||
$$
|
||
U_i(x, \mu) = \int V(x, y) d\mu(y)
|
||
$$
|
||
|
||
### 7.3 连续统中的博弈均衡
|
||
|
||
**定义 7.2（Mean Field Equilibrium）** 策略 $\pi^*$ 与分布 $\mu^*$ 满足自洽条件：
|
||
|
||
$$
|
||
\mu^* = \Phi(\pi^*, \mu^*)
|
||
$$
|
||
|
||
其中 $\Phi$ 为策略诱导的分布映射。
|
||
|
||
---
|
||
|
||
## 8. 多人博弈中的深度学习
|
||
|
||
### 8.1 神经网络在博弈论中的应用
|
||
|
||
神经网络用于近似：
|
||
- 价值函数：$V_{\theta}(s, \mu) \approx \mathbb{E}_{a \sim \pi(\cdot|s, \mu)}[Q(s, a)]$
|
||
- 策略函数：$\pi_{\theta}(a|s, \mu)$
|
||
|
||
### 8.2 PSRO（Policy Space Response Oracles）
|
||
|
||
**算法 8.1（PSRO）**
|
||
|
||
1. 初始化策略基 $\Pi = \{\pi_0\}$ 和相应收益矩阵
|
||
2. 迭代：
|
||
- 对每个 $\pi_i \in \Pi$，计算最佳响应 $BR(\pi_{-i})$
|
||
- 扩展策略基 $\Pi \leftarrow \Pi \cup \{BR\}$
|
||
- 重新计算 NE
|
||
|
||
### 8.3 博弈论的深度学习应用
|
||
|
||
**对抗训练**：GAN 中的二人零和博弈，收敛至纳什均衡
|
||
|
||
**多智能体强化学习**：
|
||
- 独立 Q-learning 的不稳定性源于非平稳环境
|
||
- 解决方法：均值场近似、注意力机制、中心化训练去中心化执行
|
||
|
||
---
|
||
|
||
## 参考文献
|
||
|
||
1. Osborne, M.J. and Rubinstein, A., 1994. *A course in game theory*. MIT press.
|
||
2. Nash, J., 1950. Equilibrium points in n-person games. *PNAS*, 36(1), pp.48-49.
|
||
3. Von Neumann, J. and Morgenstern, O., 1944. *Theory of games and economic behavior*.
|
||
4. Zinkevich, M. et al., 2007. Regret minimization in games with incomplete information. *NIPS*.
|
||
5. Lasry, J.M. and Lions, P.L., 2007. Mean field games. *Japanese Journal of Mathematics*.
|
||
6. Lanctot, M. et al., 2017. OpenSpiel: A framework for reinforcement learning in games. *arXiv*. |