0%
✦
Back to blog
• 3 min read • 学习笔记 • 学习路线

博弈论 Notes

从标准型博弈、纳什均衡到合作博弈与组合博弈，系统梳理博弈论的核心概念与经典例子。

学习笔记 算法 博弈论 纳什均衡

博弈论研究理性参与者在相互影响的环境中如何决策。这里的“理性”通常指每个参与者都追求自身收益最大化，并正确预判他人的行为。本文从非合作博弈入手，再简要介绍合作博弈与组合博弈的基本思想。

Definition

一个**标准型博弈（Normal-form Game）**由三元组 G=(N,(Si)i∈N,(ui)i∈N)G = (N, (S_i)_{i \in N}, (u_i)_{i \in N}) 描述：

  • NN：参与者集合；
  • SiS_i：参与者 ii 的策略集；
  • ui:S1×⋯×Sn→Ru_i: S_1 \times \cdots \times S_n \to \mathbb{R}：参与者 ii 的收益函数。

所有参与者的策略组合记为 s=(s1,…,sn)s = (s_1, \dots, s_n)，其中 si∈Sis_i \in S_i。

占优策略与纳什均衡

占优策略

如果无论其他参与者选择什么策略，参与者 ii 选择 si′s_i' 都比 sis_i 更好，即

ui(si′,s−i)>ui(si,s−i)对所有 s−i 成立,u_i(s_i', s_{-i}) > u_i(s_i, s_{-i}) \quad \text{对所有 } s_{-i} \text{ 成立},

则称 si′s_i' 严格占优 sis_i。如果某个策略严格占优于其他所有策略，则称之为严格占优策略。

Note

一个理性参与者不会选择被严格占优的策略。反复剔除严格被占优策略后剩下的策略组合称为迭代剔除均衡（IEDS）。

纳什均衡

纳什均衡是博弈论中最重要的解概念之一。在纳什均衡中，每个参与者的策略都是对其他参与者策略的最优反应。

Definition

策略组合 s∗=(s1∗,…,sn∗)s^* = (s_1^*, \dots, s_n^*) 是一个纳什均衡，如果对所有参与者 ii 和任意 si∈Sis_i \in S_i，都有

ui(si∗,s−i∗)≥ui(si,s−i∗).u_i(s_i^*, s_{-i}^*) \ge u_i(s_i, s_{-i}^*).

即：给定其他人的策略，没有人愿意单方面改变自己的策略。

Theorem

纳什存在性定理（Nash, 1950）：任何有限策略集的标准型博弈都至少存在一个（可能是混合策略的）纳什均衡。

经典例子

囚徒困境

两名嫌疑人被分开审讯。每人可以选择“坦白”或“沉默”。收益矩阵如下（第一个数字为参与者 A 的收益）：

B 沉默B 坦白
A 沉默(−1,−1)(-1, -1)(−3,0)(-3, 0)
A 坦白(0,−3)(0, -3)(−2,−2)(-2, -2)

对 A 而言，无论 B 如何选择，“坦白”都优于“沉默”；B 同理。因此（坦白，坦白）是唯一的纳什均衡，收益为 (−2,−2)(-2, -2)。然而若双方都沉默，收益 (−1,−1)(-1, -1) 对双方更有利。这个例子说明个体理性可能导致集体非最优结果。

协调博弈

假设两个人约定见面，可以选择地点 X 或 Y。若两人选同一地点，各得收益 1；否则收益 0。该博弈有两个纯策略纳什均衡：（X, X）和（Y, Y）。这体现了均衡选择问题：多个均衡同时存在时，参与者需要某种共同信念或约定才能协调。

猜硬币博弈

A 和 B 同时出硬币正面或反面。若相同，A 赢 1 元；若不同，B 赢 1 元。收益矩阵为

B 正面B 反面
A 正面(1,−1)(1, -1)(−1,1)(-1, 1)
A 反面(−1,1)(-1, 1)(1,−1)(1, -1)

此博弈不存在纯策略纳什均衡：无论对方出什么，自己都想改变选择。

零和博弈与混合策略

混合策略

当纯策略纳什均衡不存在时，参与者可以按某种概率分布随机选择策略，称为混合策略。设参与者 ii 的混合策略为 σi∈Δ(Si)\sigma_i \in \Delta(S_i)，即 SiS_i 上的概率分布。

Definition

在混合策略意义下，策略组合 σ∗=(σ1∗,…,σn∗)\sigma^* = (\sigma_1^*, \dots, \sigma_n^*) 是纳什均衡，如果对所有 ii 和任意 σi∈Δ(Si)\sigma_i \in \Delta(S_i)，都有

ui(σi∗,σ−i∗)≥ui(σi,σ−i∗).u_i(\sigma_i^*, \sigma_{-i}^*) \ge u_i(\sigma_i, \sigma_{-i}^*).

零和博弈与 Minimax 定理

若对所有策略组合都有 u1(s)+u2(s)=0u_1(s) + u_2(s) = 0，则称该博弈为零和博弈。零和博弈中，一方的收益等于另一方的损失。

Theorem

Minimax 定理（von Neumann, 1928）：对于有限零和博弈，存在值 vv 和混合策略 σ1∗,σ2∗\sigma_1^*, \sigma_2^*，使得

max⁡σ1min⁡σ2u1(σ1,σ2)=v=min⁡σ2max⁡σ1u1(σ1,σ2),\max_{\sigma_1} \min_{\sigma_2} u_1(\sigma_1, \sigma_2) = v = \min_{\sigma_2} \max_{\sigma_1} u_1(\sigma_1, \sigma_2),

且 (σ1∗,σ2∗)(\sigma_1^*, \sigma_2^*) 构成纳什均衡。

猜硬币的混合策略均衡

回到猜硬币博弈。设 A 以概率 pp 出正面，B 以概率 qq 出正面。为使对方无利可图，需要

p⋅1+(1−p)⋅(−1)=0（B 对正面的期望收益）,p \cdot 1 + (1-p) \cdot (-1) = 0 \quad \text{（B 对正面的期望收益）},

解得 p=1/2p = 1/2。同理 q=1/2q = 1/2。因此双方都随机出正反面，构成唯一的混合策略纳什均衡。

合作博弈简介

在合作博弈中，参与者可以组成联盟并达成有约束力的协议。通常用特征函数（Characteristic Function） v:2N→Rv: 2^N \to \mathbb{R} 描述每个联盟 C⊆NC \subseteq N 能够保证获得的总收益。

核心（Core）

Definition

核心是所有满足以下条件的收益分配 x=(x1,…,xn)x = (x_1, \dots, x_n) 的集合：

  1. 集体理性：∑i∈Nxi=v(N)\sum_{i \in N} x_i = v(N)；
  2. 联盟稳定性：对任意联盟 C⊆NC \subseteq N，∑i∈Cxi≥v(C)\sum_{i \in C} x_i \ge v(C)。

若存在联盟能通过对内再分配使所有成员都更好，则该分配不在核心中。

Shapley 值

Shapley 值是一种公平分配联盟总收益的方法，基于参与者的边际贡献。

Definition

参与者 ii 的 Shapley 值为

ϕi(v)=∑C⊆N∖{i}∣C∣!(∣N∣−∣C∣−1)!∣N∣![v(C∪{i})−v(C)].\phi_i(v) = \sum_{C \subseteq N \setminus \{i\}} \frac{|C|!(|N|-|C|-1)!}{|N|!} \big[v(C \cup \{i\}) - v(C)\big].

它表示在所有可能的加入顺序中，ii 对联盟的平均边际贡献。

Shapley 值满足四条公理：效率性、对称性、 dummy 性和可加性，因此在许多公平分配场景中广泛应用。

组合博弈：Nim 与 SG 函数

**公平组合博弈（Impartial Combinatorial Game）**满足：参与者可用的走法只依赖于当前局面，而与当前轮到谁无关；没有随机性；有限步内必结束；无法行动者输。

Nim 游戏

Nim 游戏中有若干堆石子，两位玩家轮流从一堆中取走任意正整数个石子，无法行动者输。

Theorem

Bouton 定理：Nim 局面的先手必胜当且仅当所有堆的石子数异或和不为零，即

a1⊕a2⊕⋯⊕an≠0.a_1 \oplus a_2 \oplus \cdots \oplus a_n \neq 0.

Sprague-Grundy 函数

对于更一般的公平组合博弈，每个局面 xx 可以定义一个 Grundy 数（SG 值）：

g(x)=mex⁡{g(y)∣y 是 x 的后继局面},g(x) = \operatorname{mex}\{ g(y) \mid y \text{ 是 } x \text{ 的后继局面} \},

其中 mex⁡\operatorname{mex} 表示不在后继 SG 值集合中的最小非负整数。

Theorem

Sprague-Grundy 定理：多个独立公平组合博弈的组合局面的 SG 值，等于各子博弈 SG 值的异或和。总局面为必胜态当且仅当该异或和非零。

这一结论是算法竞赛中解决博弈问题的核心工具。

总结

博弈论提供了刻画多主体决策的数学框架：

  • 非合作博弈强调个体理性与策略互动，纳什均衡是核心解概念；
  • 零和博弈中 Minimax 定理揭示了随机化策略的价值；
  • 合作博弈关注联盟形成与收益分配，核心和 Shapley 值是两类基本工具；
  • 组合博弈则用 SG 函数系统分析无偏博弈的胜负态。

理解这些概念不仅有助于分析经济和社会现象，也为算法设计、多智能体系统和机制设计提供了理论基础。

Comments