博弈论基础

文档概述

博弈论是研究决策主体行为相互作用及策略选择的数学理论。本指南系统介绍标准形式博弈与扩展形式博弈、Nash均衡的存在性证明、演化博弈论、合作博弈论（Shapley值）以及机制设计（Vickrey拍卖）等核心内容。

关键词

序号	关键词	英文	核心概念
1	标准形式博弈	Normal Form Game	$(N,A,u)$ 三元组
2	扩展形式博弈	Extensive Form Game	序贯决策的博弈树
3	Nash均衡	Nash Equilibrium	无玩家可单方偏离获利
4	混合策略	Mixed Strategy	策略的概率分布
5	演化稳定策略	ESS	演化博弈的稳定状态
6	Shapley值	Shapley Value	贡献公平分配的解概念
7	机制设计	Mechanism Design	反向设计激励相容的规则
8	Vickrey拍卖	Vickrey Auction	次价密封投标拍卖
9	纳什证明	Nash Existence Proof	角谷不动点定理
10	囚徒困境	Prisoner’s Dilemma	个体理性与集体理性的冲突
11	激励相容	Incentive Compatibility	说真话是占优策略
12	占优策略	Dominant Strategy	无论他人行动均最优

---

一、标准形式博弈

1.1 博弈论的基本框架

标准形式博弈（Normal Form Game）由三元组 $(N,A,u)$ 定义：

• 玩家集合：$N=\{1,2,\dots ,n\}$
• 行动空间：$A=A_1\times A_2\times \cdots \times A_n$，其中 $A_i$ 是玩家 $i$ 的可行行动集合
• 效用函数：$u=(u_1,u_2,\dots ,u_n)$，其中 $u_i:A\to \mathbb{R}$ 表示玩家 $i$ 的收益

双人博弈的收益矩阵：用表格展示每个策略组合下各玩家的收益。

性别之战（Battle of the Sexes）

	足球	芭蕾
足球	(2, 1)	(0, 0)
芭蕾	(0, 0)	(1, 2)

第一个数字是行玩家（妻子）的收益，第二个是列玩家（丈夫）的收益。夫妻偏好一致但优先级不同：都更喜欢在一起（2,1）或(1,2)而非分开(0,0)。

1.2 策略类型

纯策略：确定性选择，$s_i\in A_i$。

混合策略：玩家以概率分布 ${\sigma }_i$ 随机选择纯策略。混合策略集合为：

${\Sigma }_i=\left\{{\sigma }_i\in \Delta (A_i):{\sum }_{a_i\in A_i}{\sigma }_i(a_i)=1,{\sigma }_i(a_i)\ge 0\right\}$

其中 $\Delta (A_i)$ 是 $A_i$ 上的概率单纯形。

混合扩展：引入混合策略后，博弈变为：

$u_i(\sigma )={\sum }_{a\in A}{u}_i(a){\prod }_{j\in N}{\sigma }_j(a_j)$

1.3 占优策略与重复删除

严格占优：策略 $s_i$ 严格优于 $s_i^{\prime }$，若对所有 $s_{-i}$：

$u_i(s_i,s_{-i})>u_i(s_i^{\prime },s_{-i})$

理性玩家绝不会选择被严格占优的策略。

弱占优：$u_i(s_i,s_{-i})\ge u_i(s_i^{\prime },s_{-i})$，且至少一处严格不等。

迭代删除严格劣势策略（Iterated Elimination of Strictly Dominated Strategies, IESDS）：

1. 识别并删除被严格占优的策略
2. 在简化的博弈中重复步骤1
3. 最终留下的策略集是理性共识

IESDS的局限性

IESDS可能删除所有策略（如Rock-Paper-Scissors），或产生多个可能结果。弱占优的删除则可能产生路径依赖（不同删除顺序导致不同结果）。

---

二、扩展形式博弈

2.1 博弈树与信息集

扩展形式博弈（Extensive Form Game）用博弈树描述序贯决策：

• 节点：表示博弈的某个状态
• 分支：表示玩家的行动选择
• 叶节点：博弈结束时的收益

信息集（Information Set）：同一玩家在博弈中无法区分的节点集合。玩家知道自己在信息集内，但不知道具体在哪个节点。

完美回忆：玩家记得自己的所有历史行动。在完美回忆博弈中，同一玩家的不同信息集互不相交。

序贯博弈：蜈蚣博弈

两个玩家交替决定是否终止博弈。若在第 $n$ 轮终止，支付为 $(n-1,n-2)$；若继续到第 $m$ 轮后终止，支付为 $(m-2,m-1)$。理性玩家会持续合作的悖论是博弈论经典难题之一。

2.2 子博弈完美均衡

子博弈（Subgame）：从非终止节点开始、包含该节点所有后继的博弈。

子博弈完美均衡（Subgame Perfect Equilibrium, SPE）：

1. 是原博弈的纳什均衡
2. 在每个子博弈上产生的行动都是纳什均衡

SPE通过逆向归纳法（Backward Induction）求解：

1. 从最后一个决策点开始，确定最优行动
2. 逐步向前，每步考虑前序玩家的最优反应

SPE vs 纳什均衡

SPE是对纳什均衡的精炼——它剔除了”不可信威胁”。即使某策略组合是纳什均衡，如果其中包含不可信的威胁（如在后续节点不会真正执行），它就不是SPE。

2.3 逆向归纳法的应用

Stackelberg竞争（领导者-追随者模型）：

1. 领导者先选择产量 $q_1$
2. 追随者观测到 $q_1$ 后选择 $q_2$
3. 市场价格 $P=a-(q_1+q_2)$，成本为零

逆向归纳：

• 追随者利润：${\pi }_2=q_2(a-q_1-q_2)$
• 最优反应：$q_2^{\ast }=\frac{a-q_1}{2}$
• 领导者预测追随者反应，选择 $q_1$ 最大化 ${\pi }_1=q_1(a-q_1-\frac{a-q_1}{2})=q_1(\frac{a}{2}-\frac{q_1}{2})$
• 领导者最优：$q_1^{\ast }=\frac{a}{2}$，追随者反应：$q_2^{\ast }=\frac{a}{4}$

---

三、Nash均衡存在性证明

3.1 Nash均衡的定义

纳什均衡：策略组合 $(s_1^{\ast },\dots ,s_n^{\ast })$ 是纳什均衡，当且仅当对每个玩家 $i$：

$u_i(s_i^{\ast },s_{-i}^{\ast })\ge u_i(s_i,s_{-i}^{\ast }),\forall s_i\in S_i$

即没有任何玩家可以通过单方面改变策略来提高自己的收益。

混合策略纳什均衡：上述定义中的 $s_i$ 可以是混合策略。

3.2 存在性定理

纳什定理（Nash, 1950）：每一个有限博弈（有限玩家、有限行动）至少存在一个纳什均衡（可能包含混合策略）。

证明思路（使用角谷不动点定理）：

1. 构造最佳反应对应 $B{R}_i({\sigma }_{-i})$：给定其他玩家的混合策略 ${\sigma }_{-i}$，返回玩家 $i$ 的最优混合策略集合。

2. 构造纳什对应 $N(\sigma )={\prod }_{i}B{R}_i({\sigma }_{-i})$：策略组合的笛卡尔积，每个分量是相应玩家的最佳反应集合。

3. 验证角谷不动点定理条件：

   • 每个 ${\Sigma }_i$ 是 ${\mathbb{R}}^{|A_i|}$ 中的紧凸集（概率单纯形）
   • 最佳反应对应 $B{R}_i({\sigma }_{-i})$ 是非空凸值的上半连续对应
   • 因此 $N(\sigma )$ 是非空凸值的上半连续对应

4. 角谷不动点：存在 ${\sigma }^{\ast }$ 使得 ${\sigma }^{\ast }\in N({\sigma }^{\ast })$，即 ${\sigma }^{\ast }$ 是自身的最佳反应组合。

5. 验证为纳什均衡：若 ${\sigma }^{\ast }\in N({\sigma }^{\ast })$，则对每个 $i$，${\sigma }_i^{\ast }\in B{R}_i({\sigma }_{-i}^{\ast })$，即 ${\sigma }^{\ast }$ 是纳什均衡。

证明的直观理解

可以将纳什均衡视为策略空间上的”稳定点”：如果其他人都按均衡策略行动，每个人都没有动机偏离自己的均衡策略。角谷不动点定理保证了这种稳定点的存在——本质上是因为策略空间的”凸性”和”连续性”。

3.3 纳什均衡的精炼

颤抖手完美均衡（Trembling Hand Perfect Equilibrium, THPE）：

• 剔除了因”颤抖”（失误）而无法达到的均衡
• 要求均衡对微小的策略扰动稳健

序贯均衡（Sequential Equilibrium）：

• 结合了SPE的序贯理性要求和THPE的稳健性

---

四、演化博弈论

4.1 演化博弈的基本框架

演化博弈论从生物学角度研究策略的动态演化，核心概念是演化稳定策略（Evolutionarily Stable Strategy, ESS）。

ESS定义：策略 $s^{\ast }$ 是演化稳定的，如果对每个替代策略 $s\ne s^{\ast }$，存在阈值 $\overline{ϵ}\in (0,1)$ 使得：

$u(s^{\ast },(1-ϵ)s^{\ast }+ϵs)>u(s,(1-ϵ)s^{\ast }+ϵs),\forall ϵ\in (0,\overline{ϵ})$

ESS的直观理解

如果整个种群都采用ESS $s^{\ast }$，那么入侵的突变策略 $s$ 无法获得更高的适应度（收益）。这解释了为何某些策略在自然界中稳定存在（如鸽-鹰博弈中的混合策略）。

4.2 复制者动态

复制者动态（Replicator Dynamics）描述策略频率的时间演化：

${\dot{x}}_i=x_i[u(s_i,x)-\bar{u}(x)]$

其中 $x_i$ 是采用策略 $i$ 的种群比例，$\bar{u}(x)$ 是平均适应度。

直觉：表现优于平均的策略比例增加，表现劣于平均的策略比例减少。

ESS与复制者动态的关系：

• ESS是复制者动态的稳定不动点
• 但稳定不动点不一定是ESS

4.3 博弈动态的其他模型

动态模型	特点
复制者动态	生物学动机，适应度驱动
Best Response动态	每次一个玩家调整到最优反应
虚幻学习	考虑有限理性的学习过程
fictitious play	基于历史平均频率的最佳反应

---

五、合作博弈论与Shapley值

5.1 合作博弈的形式

联盟博弈（Coalitional Game）由 $(N,v)$ 定义：

• $N=\{1,\dots ,n\}$ 是玩家集合
• $v:2^N\to \mathbb{R}$ 是联盟值函数，满足 $v(\varnothing )=0$

联盟的价值：$v(S)$ 表示联盟 $S$ 可以获得的收益（或创造的额外价值）。

合作收益分配

三位农夫合作灌溉：单独耕作各得1单位，联合后总产出5单位。如何公平分配这5单位？ Shapley值给出了一种基于”边际贡献”的公平分配方案。

5.2 Shapley值

Shapley值 ${\varphi }_i(v)$ 是玩家 $i$ 在联盟博弈 $(N,v)$ 中的”公平”收益分配：

${\varphi }_i(v)={\sum }_{S\subseteq N\setminus \{i\}}\frac{|S|!(n-|S|-1)!}{n!}[v(S\cup \{i\})-v(S)]$

其中 $|S|!$ 是联盟 $S$ 中玩家的排列数，$(n-|S|-1)!$ 是 $i$ 之后玩家的排列数。

直觉解释：Shapley值是玩家加入联盟时边际贡献的期望值，按所有可能的联盟形成顺序平均。

5.3 Shapley值的公理化特征

Shapley值是满足以下公理的唯一分配方案：

1. 效率性：${\sum }_{i\in N}{\varphi }_i(v)=v(N)$
2. 对称性：若玩家 $i$ 和 $j$ 对所有联盟 $S$ 有相同边际贡献，则 ${\varphi }_i(v)={\varphi }_j(v)$
3. 虚拟玩家：若 $v(S)=0$ 对所有包含 $i$ 的 $S$ 成立，则 ${\varphi }_i(v)=0$
4. 可加性：对任意两个博弈 $v$ 和 $w$，$\varphi (v+w)=\varphi (v)+\varphi (w)$

---

六、机制设计（Vickrey拍卖）

6.1 机制设计的基本框架

机制设计是从目标出发反向设计博弈规则，使理性个体在追求私利时自然实现设计者目标。

社会选择函数 $f:\Theta \to O$ 将环境参数（如类型）映射到社会结果（如物品分配）。

直接机制：要求每个参与者真实报告类型（说真话）。

激励相容（Incentive Compatibility, IC）：说实话是占优策略。

$u_i({\theta }_i,{\theta }_{-i})\ge u_i({\hat{\theta }}_i,{\theta }_{-i}),\forall {\theta }_i,{\hat{\theta }}_i,{\theta }_{-i}$

6.2 Vickrey-Clarke-Groves机制

VCG机制是对一般社会选择函数的激励相容机制。

对于资源分配问题，VCG支付为：

$p_i(\theta )=\left({\max }_{a\in A}{\sum }_{j\ne i}{v}_j({\theta }_j,a)\right)-{\sum }_{j\ne i}{v}_j({\theta }_j,a^{\ast }(\theta ))$

其中 $a^{\ast }(\theta )$ 是机制选择的结果。

VCG的性质：

• 强激励相容（dominant strategy truth-telling）
• 帕累托有效（给定报告）
• 支付是非负的（至少不需付钱）

6.3 Vickrey拍卖

Vickrey拍卖（次价密封投标拍卖）是VCG在单物品拍卖中的特例：

1. 投标者密封提交投标
2. 最高投标者获胜
3. 获胜者支付第二高投标额（而非自己的投标额）

激励相容性证明：

设投标者 $i$ 的真实价值为 $v_i$，其他人的最高投标为 $b_{-i}^{\max }$。

• 若 $v_i>b_{-i}^{\max }$：说真话赢得物品，支付 $b_{-i}^{\max }$，获得净效用 $v_i-b_{-i}^{\max }>0$
• 若 $v_i<b_{-i}^{\max }$：无论投标多少都输，效用为0

若投标者说假话投标 $b_i<v_i$：

• 若 $b_i<b_{-i}^{\max }$：仍然输，无差异
• 若 $b_i>b_{-i}^{\max }$：仍然赢，但支付 $b_{-i}^{\max }$，效用不变

因此，说实话是占优策略。

Vickrey拍卖的意义

Vickrey证明了”说真话”是占优策略，这与直觉（人们会过度或过低投标）相反。这一发现深刻影响了拍卖理论和机制设计领域。

6.4 拍卖理论在人工智能中的应用

广告拍卖：Google、Facebook等平台的广告位通过广义第二价格拍卖（GSP）分配。

联邦学习中的激励机制：如何公平分配参与者的贡献？

多智能体系统：设计协议使自私的智能体能够协作完成任务。

---

参考文献

1. Nash, J. (1950). Equilibrium Points in N-Person Games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
2. Osborne, M. J., & Rubinstein, A. (1994). A Course in Game Theory. MIT Press.
3. Myerson, R. B. (1991). Game Theory: Analysis of Conflict. Harvard University Press.
4. Shapley, L. S. (1953). A Value for n-Person Games. Contributions to the Theory of Games, 2(28), 307-317.
5. Vickrey, W. (1961). Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16(1), 8-37.

---

相关文档

• 统计学深度指南 - 贝叶斯博弈中的类型空间
• 凸优化深度指南 - 机制设计的优化视角
• 图论深度指南 - 网络博弈与图结构