博弈论基础

本笔记面向深度学习与强化学习科研人员，系统阐述博弈论的核心概念、数学基础与算法。更新日期：2026-05-14

1. 博弈论基础概念

1.1 基本元素

定义 1.1（博弈） 一个博弈由三元组构成：

：玩家集合
：策略空间，其中为玩家的可行策略集
：收益函数，其中为玩家的效用函数

定义 1.2（正常形博弈） 当博弈描述为玩家同时选择策略时，称为正常形博弈（Normal Form Game），其收益矩阵为：

1.2 扩展形博弈

定义 1.3（扩展形博弈） 扩展形博弈（Extensive Form Game）通过博弈树描述时序决策：

其中：

：非终止节点集合（决策节点）
：终止节点集合（终点）
：所有可行行动集合
：玩家函数，将每个节点分配给某玩家或 chance（随机事件）
：信息分割，其中为玩家的信息集
：玩家在终点的收益

完美回忆（Perfect Recall） 若玩家在博弈过程中始终记得其历史决策，则称该博弈满足完美回忆条件：

历 史 完 全 一 致

1.3 最优响应与效用

定义 1.4（最优响应） 给定其他玩家的策略，玩家的最优响应为：

定义 1.5（严格优势） 策略严格优于策略，若对：

2. 纳什均衡（Nash Equilibrium）

2.1 纳什均衡的定义

定义 2.1（纯策略纳什均衡） 策略组合构成纳什均衡，当且仅当：

等价表述：是对的最优响应，即。

2.2 混合策略纳什均衡

定义 2.2（混合策略） 玩家的混合策略是其纯策略空间上的概率分布：

定义 2.3（混合策略纳什均衡） 混合策略组合构成纳什均衡，当且仅当：

其中。

2.3 纳什均衡的存在性证明

定理 2.1（纳什存在定理） 任意有限玩家、有限策略的正常形博弈至少存在一个混合策略纳什均衡。

证明（Brouwer 不动点定理）：

构造策略组合空间，其中为玩家的混合策略单纯形。

对每个玩家定义响应函数：

其中为当前策略下的期望收益。

该映射连续（收益函数的线性组合）。由于为紧凸集，Brouwer 不动点定理确保存在使得。

验证不动点条件：对任何若，则；若，则。故不动点即为纳什均衡。

2.4 纳什均衡的唯一性与稳定性

定义 2.4（NE 的唯一性） 博弈可能有多个纳什均衡，需通过稳定性分析筛选。

定义 2.5（渐进稳定） 考虑最佳响应动态的离散系统：

若某 NE 周围的雅可比矩阵特征值模小于 1，则该 NE 局部渐进稳定。

3. 零和博弈（Zero-Sum Game）

3.1 基本定义

定义 3.1（零和博弈） 双人零和博弈满足，可记为收益矩阵（玩家 1 的收益）：

其中，为双方的混合策略。

3.2 鞍点与 Minimax 定理

定义 3.2（鞍点） 策略对为鞍点若满足：

定理 3.1（Minimax 定理） 有限双人零和博弈满足：

证明（线性规划对偶）：

玩家 1 的最小最大化问题：

等价变换（消除常数）：

其对偶问题为：

这恰对应玩家 2 的最大化最小化问题。由线性规划对偶理论，强对偶性成立。

3.3 鞍点不等式推导

引理 3.1（鞍点不等式） 若为鞍点，则：

由鞍点性质可直接导出 minimax 等式：

由于对任意成立，故等式两边相等。

3.4 策略空间的线性规划

双人零和博弈的求解可转化为线性规划：

玩家 1 的 LP（最大化最小收益）：

玩家 2 的 LP（最小化最大收益）：

4. 纳什均衡的计算

4.1 优势消去（IESDS）

定义 4.1（严格劣势策略） 策略对玩家严格劣于，若：

算法：迭代优势消去（IESDS）

while 存在劣势策略 do
    消去所有严格劣势策略
end while

性质：若博弈存在唯一纳什均衡，IESDS 必收敛至该均衡；但若有多个均衡，IESDS 可能消去部分均衡。

4.2 虚拟对弈（Fictitious Play）

定义 4.2（虚拟对弈） 经典虚拟对弈中，玩家假设对手以历史平均频率选择策略：

玩家以最优响应更新策略：

收敛性：针对特定博弈类（如零和博弈）可证伪，但一般博弈不一定收敛。

4.3 Lemke-Howson 算法

算法 4.1（Lemke-Howson） 适用于双人有限博弈的均衡求解：

选择初始失衡玩家和扰动参数
构造辅助线性规划问题
沿着可行方向 pivot 直到满足均衡条件

该算法在最坏情况下指数复杂度，但在实践中对结构化博弈效率较高。

4.4 梯度下降法（Gradient Play）

定义 4.3（梯度Play） 将纳什均衡视为不动点，用梯度下降求解：

其中为欧几里得投影到策略单纯形。

收敛性：对于单阶梯度动态，一般博弈无收敛保证；但对零和博弈可证某些条件下收敛。

5. 扩展形博弈与子博弈完美均衡

5.1 扩展形博弈的表示

扩展形博弈通过博弈树描述，其中：

（决策节点与终点节点）
每个决策节点关联玩家
边表示行动

5.2 信息集与完美回忆

定义 5.1（信息集） 同一玩家不可区分的节点集合：

完美回忆要求：玩家在信息集中各节点的可达历史完全相同。

5.3 子博弈完美均衡（SP E）

定义 5.2（子博弈） 从节点开始的子博弈包含所有以为根的可达终止节点。

定义 5.3（子博弈完美均衡） 策略组合在每个子博弈上均构成纳什均衡。

定理 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） 在时刻玩家选择行动的虚拟后悔值：

其中：

：总采样序列数
：指示函数，判断历史是否在玩家的信息集中
：在第次序列中，在处替换为行动的策略

6.2 CFR 算法

算法 6.1（CFR 迭代）

对每次迭代：

基于当前策略生成采样序列
对每个信息集和行动，计算后悔值
更新策略：

其中为正部分。

6.3 CFR+ 算法

CFR+ 通过以下改进提升收敛速度：

线性加权平均：对历史策略加权平均，近期权重更高

替代遗憾值：

6.4 外部后悔值与收敛性

定义 6.2（外部后悔值）：

定理 6.1（CFR 收敛性） 若每个玩家的外部后悔值，则平均策略序列收倥至纳什均衡。

6.5 蒙特卡洛 CFR（MCCFR）

算法 6.2（MCCFR）

** outcome sampling**：对每条轨迹只采样一个后继
** chance sampling**：对 chance 节点按先验概率采样
外部采样：只跟踪单方的信息集更新

7. 均值场博弈（Mean Field Game）

7.1 大量智能体的近似

均值场博弈处理的多智能体系统，其中单个智能体的影响可忽略。

定义 7.1（均值场近似） 智能体视其他智能体为统计分布：

7.2 配对均值场近似

智能体间相互作用通过配对势能建模：

7.3 连续统中的博弈均衡

定义 7.2（Mean Field Equilibrium） 策略与分布满足自洽条件：

其中为策略诱导的分布映射。

8. 多人博弈中的深度学习

8.1 神经网络在博弈论中的应用

神经网络用于近似：

价值函数：
策略函数：

8.2 PSRO（Policy Space Response Oracles）

算法 8.1（PSRO）

初始化策略基和相应收益矩阵
迭代：
- 对每个，计算最佳响应
- 扩展策略基
- 重新计算 NE

8.3 博弈论的深度学习应用

对抗训练：GAN 中的二人零和博弈，收敛至纳什均衡

多智能体强化学习：

独立 Q-learning 的不稳定性源于非平稳环境
解决方法：均值场近似、注意力机制、中心化训练去中心化执行

参考文献

Osborne, M.J. and Rubinstein, A., 1994. A course in game theory. MIT press.
Nash, J., 1950. Equilibrium points in n-person games. PNAS, 36(1), pp.48-49.
Von Neumann, J. and Morgenstern, O., 1944. Theory of games and economic behavior.
Zinkevich, M. et al., 2007. Regret minimization in games with incomplete information. NIPS.
Lasry, J.M. and Lions, P.L., 2007. Mean field games. Japanese Journal of Mathematics.
Lanctot, M. et al., 2017. OpenSpiel: A framework for reinforcement learning in games. arXiv.

Huajishe Notes

Explorer

1-博弈论基础