---
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*.