博弈与策略

本章目标：掌握经典博弈论智力题的必胜策略分析方法，入门 Sprague-Grundy 理论。

题型特点

博弈题在量化金融和算法面试中频繁出现。这类题的共同结构：两个玩家轮流操作，每步有有限选择，游戏必然终止，问"先手必胜还是后手必胜"。

解题核心方法：终局倒推 → 寻找模式 → 证明必胜策略。数学工具包括 SG 函数、Nim 和、P-position/N-position 分类。

为什么面试官爱考

考察逆向思维：从终局倒推是分析博弈的标准方法。
考察数学抽象：能否把具体游戏归约为数学模型。
考察算法能力：SG 函数与递归、动态规划紧密相关。
考察信息论与概率：不完全信息博弈需要混合策略。

博弈论基础

关键概念

概念	含义
完全信息博弈	双方知道所有信息（如国际象棋）
不完全信息博弈	有隐藏信息（如扑克）
impartial game	双方可执行的操作相同（如 Nim）
partizan game	双方操作不同（如象棋）
P-position	Previous-position，先手必败（后手必胜）
N-position	Next-position，先手必胜
零和博弈	一方收益等于另一方损失
纳什均衡	任何单方改变策略都不会更好的状态

博弈分类

博弈
├── 合作 vs 非合作
├── 零和 vs 非零和
├── 完全信息 vs 不完全信息
└── 静态（同时） vs 动态（顺序）

求解流程

判断博弈类型：impartial 还是 partizan？完全信息还是不完全？
从小情况分析：n=1, 2, 3 时谁赢？
找 P/N-position：递推标记每个状态。
寻找通项公式：P-position 有什么共同特征？
证明必胜策略：归纳法。

题目 1：Nim 游戏

题面

桌上有 n 堆石子，每堆数量不同。两名玩家轮流操作，每次从某一堆中取走任意正数个石子（至少 1，可以取完整堆）。取走最后一个石子的人获胜。问：先手必胜的条件是什么？

拆解与思考

分析简单情况：

1 堆：先手直接全部取走，必胜。
2 堆（各 a 个）：
- 两堆相等：先手取多少，后手在对称堆取同样多，后手必胜。
- 两堆不等：先手取到相等，此后维持对称，先手必胜。

一般情况——Nim 和：

定义"Nim 和"为所有堆数量的按位异或（XOR）：

$\text{Nim-sum} = \text{pile}_1 \oplus \text{pile}_2 \oplus \cdots \oplus \text{pile}_n$

Bouton 定理：先手必胜当且仅当 Nim-sum ≠ 0。

证明

两个关键性质：

从 Nim-sum = 0 的状态，任何操作都会使 Nim-sum ≠ 0。
- 至少改变一堆的数量，假设从 x 变为 x' < x。新的 Nim-sum = (原 Nim-sum) ⊕ x ⊕ x' = 0 ⊕ x ⊕ x' = x ⊕ x' ≠ 0（因为 x ≠ x'）。
从 Nim-sum ≠ 0 的状态，存在操作使 Nim-sum 变为 0。
- 设 Nim-sum = s ≠ 0，其最高位为第 k 位。
- 必存在一堆 pile_i 第 k 位为 1（否则 s 第 k 位怎么来）。
- 取该堆，把数量从 pile_i 改为 pile_i ⊕ s。
- 因为 pile_i 第 k 位为 1，s 第 k 位为 1，pile_i ⊕ s < pile_i（更高位相同，第 k 位由 1 变 0）。所以这是合法操作（数量减少）。
- 新 Nim-sum = s ⊕ pile_i ⊕ (pile_i ⊕ s) = 0 ✓

终局分析：全 0 状态的 Nim-sum = 0。先手若能始终把对手推到 Nim-sum = 0 的状态，最终对手面对全 0 状态，必败。

答案

先手必胜 ⟺ Nim-sum ≠ 0。策略：每步操作使所有堆的异或和为 0。

代码实现

python

def nim_winner(piles):
    """True 表示先手必胜"""
    xor_sum = 0
    for p in piles:
        xor_sum ^= p
    return xor_sum != 0

def nim_move(piles):
    """返回必胜策略下的下一步：(堆索引, 取走数量)"""
    xor_sum = 0
    for p in piles:
        xor_sum ^= p
    if xor_sum == 0:
        return None  # 先手必败
    # 找最高位
    k = xor_sum.bit_length() - 1
    for i, p in enumerate(piles):
        if (p >> k) & 1:  # 该堆第 k 位为 1
            target = p ^ xor_sum
            return (i, p - target)

延伸

Nim 游戏是组合博弈论的基石——任何公平的 impartial game 都可以转化为 Nim 游戏（Sprague-Grundy 定理）。

工程意义：

区块链 PoW：哈希难题本质是 Nim 类型的"赌注游戏"。
拍卖理论：竞标策略与博弈论紧密相关。
网络协议：随机化退避算法避免冲突。

题目 2：Bash Game（取石子限制版）

题面

一堆石子共 n 个。两人轮流取，每次取 1 到 m 个。取走最后一个的获胜。问先手必胜的条件？

拆解与思考

从小情况分析：

n = 1 到 m：先手一次取完，必胜。
n = m+1：无论先手取 1 到 m，后手都能取完剩余，后手必胜。
n = m+2 到 2m+1：先手取到剩余 m+1，后手进入必败态，先手必胜。
n = 2(m+1)：先手取任何数量，后手取到剩余 m+1 的倍数，后手必胜。

规律：n 是 (m+1) 的倍数时，后手必胜（P-position）；否则先手必胜（N-position）。

必胜策略

先手取 n mod (m+1) 个，之后每轮补齐到 m+1。

例：n=10, m=3。

先手取 10 mod 4 = 2 个，剩 8。
对手取 x 个，先手取 4-x 个。
对手取 1，先手取 3 → 剩 4。
对手取 2，先手取 2 → 剩 0，先手胜。

答案

先手必胜 ⟺ n mod (m+1) ≠ 0。策略：先手取 n mod (m+1) 个，之后每次取 (m+1 - 对手上轮取的数) 个。

变体：取最后一个的人输

分析类似但翻转：

n=1 时先手必败（被迫取最后 1 个）。
n=m+2 时先手必胜（取 m+1，留 1 个给对手）。
一般：n mod (m+1) = 1 时后手必胜。

延伸

类似规则题：每次取 1-k 个连续项；每次取平方数个；每次取斐波那契数个。这些都可用 SG 函数分析。

题目 3：Wythoff Game（威佐夫博弈）

题面

两堆石子，分别有 a 个和 b 个。两人轮流操作，每次可以：

从一堆中取任意正数个；或
从两堆中同时取相同的正数个。

取走最后一个石子者获胜。问必胜策略？

拆解与思考

找出所有 P-position（先手必败态）：

(0, 0)：终态，必败。
(1, 2)：先手怎么操作都无法让对手进入必败态。
(3, 5)：同理。
(4, 7), (6, 10), (8, 13), (9, 15), (11, 18)...

观察规律（假设 a ≤ b）：

a 序列：0, 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, ...
b - a：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

b - a 从 0 开始递增，每个差值恰好出现一次。

Wythoff 公式

第 k 个 P-position：

$a_k = \lfloor k \cdot \phi \rfloor, \quad b_k = \lfloor k \cdot \phi^2 \rfloor = a_k + k$

其中 φ = (1+√5)/2 ≈ 1.618 是黄金比例。

验证：

k	a_k = ⌊kφ⌋	b_k = ⌊kφ²⌋ = a_k + k
0	0	0
1	1	2
2	3	5
3	4	7
4	6	10
5	8	13
6	9	15
7	11	18

答案

P-position（先手必败）为 (⌊kφ⌋, ⌊kφ²⌋)（k=0,1,2,...）。如果当前局面不是 P-position，先手必胜，策略是移动到最近的 P-position。

判断算法

python

import math
PHI = (1 + math.sqrt(5)) / 2

def is_wythoff_p(a, b):
    """判断 (a, b) 是否为 P-position"""
    if a > b: a, b = b, a
    k = b - a
    return a == int(k * PHI)

延伸

为什么是黄金比例？

Wythoff Game 中黄金比例的出现堪称数学之美。这源于 Beatty 序列定理：

若 α 和 β 是正无理数且满足 1/α + 1/β = 1，则 ⌊nα⌋ 和 ⌊nβ⌋（n=1,2,3,...）恰好覆盖所有正整数各一次。

取 α = φ，则 β = φ² = φ + 1，满足 1/φ + 1/φ² = 1。

博弈论与几何学的意外交叉——这是数学之美的典范。

题目 4：汉诺塔最小步数

题面

3 根柱子，n 个大小不同的圆盘套在第一根柱子上，从下到上由大到小排列。目标：把所有圆盘移到第三根柱子。规则：每次只能移动一个圆盘，且大盘不能放在小盘上面。求最少步数。

拆解与思考

设 T(n) 为 n 个盘的最少步数。

要把最大的盘从柱 A 移到柱 C，必须先把上面 n-1 个盘全部移到柱 B（否则最大盘被压住）。

把 n-1 个盘从 A 移到 B：T(n-1) 步
把最大盘从 A 移到 C：1 步
把 n-1 个盘从 B 移到 C：T(n-1) 步

递推：T(n) = 2·T(n-1) + 1，T(1) = 1。

求解：

$T(n) = 2^n - 1$

验证：T(1)=1, T(2)=3, T(3)=7, T(4)=15 ✓

答案

n 个盘的最少步数为 2^n - 1。

n	步数
1	1
3	7
5	31
10	1023
20	~100 万
64	~1.8×10¹⁹

梵天塔传说：64 个金盘从一根柱移到另一根，需要 2⁶⁴ - 1 ≈ 1.8 × 10¹⁹ 步。按每秒 1 步算，需要约 5845 亿年——远超宇宙年龄。

代码

python

def hanoi(n, src='A', mid='B', dst='C'):
    if n == 1:
        return [(n, src, dst)]
    moves = []
    moves.extend(hanoi(n-1, src, dst, mid))
    moves.append((n, src, dst))
    moves.extend(hanoi(n-1, mid, src, dst))
    return moves

# 实际移动
moves = hanoi(3)
for disk, src, dst in moves:
    print(f"圆盘 {disk}: {src} → {dst}")

延伸

4 柱汉诺塔（Frame-Stewart 算法）：

策略：把 n 个盘分成上下两部分，上 k 个先用 4 柱移到辅助柱，下 n-k 个用 3 柱移到目标，再把上 k 个用 4 柱移到目标。

递推：F(n) = min_k [2·F(k) + T(n-k)] = min_k [2·F(k) + 2^{n-k} - 1]

最优 k 的选择是未解问题，4 柱汉诺塔的最少步数至今没有完全证明最优。

题目 5：抢 30 游戏

题面

两人轮流报数，每次报 1 或 2 个连续自然数（从 1 开始顺序报）。报到 30 的人获胜。先手必胜还是后手必胜？策略是什么？

拆解与思考

反向思考：

谁能报到 30 就赢。要确保报到 30，需要确保上一轮到 27——因为从 27 出发，对手报 1 个你报 2 个到 30，对手报 2 个你报 1 个到 30。

递推：30, 27, 24, 21, ..., 3, 0。间隔为 3。

关键：先手第一步只能加 1 或 2，到不了 3。所以后手必胜。

答案

后手必胜。策略：先手加 x，后手加 (3-x)，保证每轮总数增加 3。后手会依次到达 3, 6, 9, ..., 30。

推广：每次报 1 到 k 个数，报到 n 获胜

若 n mod (k+1) = 0：后手必胜。
否则先手必胜（先手报到 n mod (k+1)）。

变体：报到 30 输

类似的反向分析：避开 30。要避开 30 就要控制 29，控制 29 就要控制 26，...

递推：29, 26, 23, ..., 2。先手能到 2，先手必胜。

题目 6：Sprague-Grundy 理论

题面

什么是 SG 函数？如何用它判断任意公平组合博弈的胜负？

拆解与思考

impartial game：双方可执行的操作相同（如 Nim）。Sprague-Grundy 理论是分析这类游戏的通用工具。

SG 函数定义：

SG(x) = \text{mex}\{SG(y) : y \text{ 是 } x \text{ 的后继}\}

mex（minimum excludant）= 不在集合中的最小非负整数。

例：集合 {0, 1, 2, 4} 的 mex = 3。集合 {1, 2, 3} 的 mex = 0。集合 ∅ 的 mex = 0。

关键定理

定理	内容
SG=0 的位置是 P-position	先手必败
SG≠0 的位置是 N-position	先手必胜
多个独立子游戏的 SG	各子游戏 SG 值的异或和

这就是为什么 Nim 游戏的胜负判断用异或——因为 Nim 游戏中每堆石子的 SG 值恰好等于石子数（n 个石子的堆可以转移到 0 到 n-1 个石子的堆，mex{0,1,...,n-1} = n）。多个堆的组合 SG 就是异或和。

示例

一个游戏中有 3 堆石子分别有 3、4、5 个，但规则是每次只能取 1-3 个（不是 Nim 的任意取）。

计算每堆的 SG 值：

SG(0) = 0（终态）
SG(1) = mex{SG(0)} = mex{0} = 1
SG(2) = mex{SG(1), SG(0)} = mex{1, 0} = 2
SG(3) = mex{SG(2), SG(1), SG(0)} = mex{2, 1, 0} = 3
SG(4) = mex{SG(3), SG(2), SG(1)} = mex{3, 2, 1} = 0
SG(5) = mex{SG(4), SG(3), SG(2)} = mex{0, 3, 2} = 1

三堆组合 SG：SG(3) ⊕ SG(4) ⊕ SG(5) = 3 ⊕ 0 ⊕ 1 = 2 ≠ 0，先手必胜。

答案

SG 函数将任意 impartial game 归约为 Nim 游戏。计算每个子游戏的 SG 值，取异或和，非零则先手必胜。

代码

python

def sg_value(state, transitions, memo=None):
    """计算 state 的 SG 值
    transitions: 函数，返回 state 的所有后继状态
    """
    if memo is None: memo = {}
    if state in memo: return memo[state]
    successors = transitions(state)
    sg_set = {sg_value(s, transitions, memo) for s in successors}
    # mex
    mex = 0
    while mex in sg_set: mex += 1
    memo[state] = mex
    return mex

延伸

应用场景：

Nim：SG = 石子数。
Bash Game：SG = n mod (m+1)。
Wythoff：SG 复杂，但 P-position 仍可由公式确定。
图游戏（如 chomp、knight's tour）：递归计算 SG。

SG 理论由 Sprague（1935）和 Grundy（1939）独立发现，是组合博弈论的基石。

题目 7：囚徒困境

题面

两个嫌疑人被分别审讯。每人有两个选择：合作（Cooperate，沉默）或背叛（Defect，揭发）。

双方都合作：各 1 年（轻判）。
双方都背叛：各 5 年（重判）。
一方合作一方背叛：合作者 10 年，背叛者 0 年。

每人独立选择，不能交流。理性人会怎么选？

拆解与思考

收益矩阵（用刑期表示，越小越好）：

	B 合作	B 背叛
A 合作	(1, 1)	(10, 0)
A 背叛	(0, 10)	(5, 5)

分析 A 的视角：

如果 B 合作：A 合作判 1 年，A 背叛判 0 年。背叛更好。
如果 B 背叛：A 合作判 10 年，A 背叛判 5 年。背叛更好。

无论 B 怎么选，A 都应该背叛（严格优势策略）。同理 B。

结果：双方都背叛，各判 5 年。比双方都合作（各 1 年）更差。

答案

理性个体各自选择会导致集体次优——双方都背叛，各判 5 年。但合作（各 1 年）是更好的集体结果。

纳什均衡 vs 帕累托最优

纳什均衡（双方背叛）：任何单方改变策略都不会更好。
帕累托最优（双方合作）：没有任何一方可以变好而不让另一方变差。

两者不一致——这就是困境。

重复博弈与一报还一报

重复囚徒困境：游戏进行多轮，可以基于历史决策。

Axelrod 锦标赛（1984）：让各种策略相互对战，**"一报还一报"（Tit for Tat）**胜出：

第一轮合作。
之后模仿对手上一轮的行为。

为什么有效：

友善：从合作开始，不会主动背叛。
可激怒：对手背叛立即报复。
宽恕：对手回到合作，立即原谅。
不嫉妒：不试图获得比对手更多。

延伸

现实应用：

国际军备竞赛（双方都扩军 vs 双方都裁军）。
公地悲剧（人人都过度放牧）。
价格战（双方都降价 vs 都维持）。
区块链与信任机制。

工程意义：信誉系统、peer-to-peer 网络、反垃圾邮件协议都基于重复博弈。

题目 8：最后一位报数（每次报 1-3 个）

题面

n 个连续自然数 1 到 n。两人轮流报，每次报 1-3 个连续数（必须按顺序）。报到 n 的人赢。先手必胜还是后手必胜？

拆解与思考

这是 Bash Game 的变种，目标 30 → n，每次报 1-3。

n mod 4 = 0：后手必胜。
否则先手必胜。

策略：先手报到 n mod 4，之后每轮总和为 4（对手报 x，先手报 4-x）。

答案

若 n mod 4 = 0：后手必胜。否则：先手必胜（先手报到 n mod 4）。

题目 9：海盗分金（详细版）

题面

5 个海盗（A, B, C, D, E）抢到 100 枚金币。按等级 A > B > C > D > E。从 A 开始提议分配方案，所有人投票（包括提议者）。若 ≥ 半数同意则通过，否则提议者被扔下海，下一人继续。海盗都理性、自私、嗜血（同等收益时倾向扔人下海）。A 如何分配？

拆解与思考（逆向归纳）

只剩 E：E 全拿 100。但实际不会到这一步（D 会先分）。

剩 D 和 E：D 提议 D=100, E=0。投票：D 同意（1/2 ≥ 50%），通过。

剩 C, D, E：C 知道自己死后 D 全拿，所以 C 给 E 1 金币（E 比被 D 分得 0 好，必同意）。C 提议：C=99, D=0, E=1。投票：C 同意 + E 同意 = 2/3，通过。

剩 B, C, D, E：B 知道自己死后 C 分配是 (99, 0, 1)。B 给 D 1 金币（D 比 0 好，必同意）。B 提议：B=99, C=0, D=1, E=0。投票：B + D = 2/4 = 50%，通过。

剩 A, B, C, D, E（全部）：A 知道自己死后 B 分配是 (99, 0, 1, 0)。A 给 C 和 E 各 1 金币（他们都比被 B 分得 0 好，必同意）。A 提议：A=98, B=0, C=1, D=0, E=1。投票：A + C + E = 3/5 = 60%，通过。

答案

A 提议 (98, 0, 1, 0, 1)——A 拿 98 枚，C 和 E 各 1 枚。

推广：N 海盗

奇偶规律：N 个海盗时，提议者总能联合最少数量的"被排挤者"获得半数支持。

N	提议者收益	拿到 1 金币的人
2	100	无
3	99	最低 1
4	99	倒数第二
5	98	倒数第一和第三
6	98	倒数第二和第四
...

N ≥ 200 后规律更复杂——金币不够买支持，开始有人被扔下海。

工程意义

博弈论中的逆向归纳。这种"从终点倒推"的思路在 chess endgame、定价策略、谈判中都有应用。

题目 10：信息不对称博弈

题面

什么是信息不对称博弈？与完全信息博弈有什么区别？

拆解与思考

完全信息博弈：双方知道所有信息——棋类（国际象棋、围棋）、Nim 等。双方看到相同的棋盘，没有隐藏信息。

不完全信息博弈：有些信息只有一方知道——扑克、军棋、拍卖。

不完全信息博弈的核心工具：

贝叶斯纳什均衡：在不知道对手类型的情况下，基于概率选择最优策略。
混合策略：以一定概率随机选择行动，使对手无法预测。

经典例子——扑克中的诈唬

你手牌差但你下大注。对手不知道你是真的好牌还是诈唬，必须基于概率决策。

如果你从不诈唬，对手看到大注就弃牌。
如果你总诈唬，对手每次都跟。
最优策略：以一定频率诈唬，使对手跟注和弃牌的期望收益相等。

答案

信息不对称博弈需要用概率混合策略，核心是让对手无法通过你的行为推断你的私有信息。

延伸

John Nash 的纳什均衡理论（他因此获得诺贝尔经济学奖）是分析所有博弈类型的基础工具。

AI 在德州扑克中击败人类（CMU 的 Libratus）用的就是 Counterfactual Regret Minimization 算法——通过自我对弈学习"什么时候该诈唬"。

工程意义：网络安全中的入侵检测、广告竞价中的出价策略、推荐系统中的探索-利用平衡都基于不完全信息博弈。

题目 11：选票博弈（投票悖论）

题面

3 个选民投票选 3 个候选人 A, B, C。选民偏好：

选民 1：A > B > C
选民 2：B > C > A
选民 3：C > A > B

两两比较：

A vs B：A 有选民 1, 3 支持，B 只有选民 2 → A 胜。
B vs C：B 有选民 1, 2 支持，C 只有选民 3 → B 胜。
C vs A：C 有选民 2, 3 支持，A 只有选民 1 → C 胜。

结果：A > B > C > A，循环！

拆解与思考

Condorcet 悖论（1785）：个人偏好是理性的（可传递的），但集体偏好可能不可传递，导致循环。

Arrow 不可能性定理（1951，诺贝尔奖）：

在 ≥ 3 个候选人的选举中，没有任何投票系统能同时满足以下合理条件：
普遍性：任何个人偏好都允许。
单调性：选民提高某候选人排名不会让他落选。
独立性：A vs B 的结果不取决于 C 的存在。
非独裁：没有一个人的偏好决定结果。
传递性：集体偏好可传递。

答案

不存在完美的投票制度。任何投票系统都有"悖论"——这是数学定理，不是工程问题。

现实影响

2000 年美国大选：Nader 分走了 Gore 的选票，导致 Bush 当选（独立性违反）。
法国选举：Jospin 在第一轮被淘汰，但若与 Chirac 单挑会胜（多数制缺陷）。
区块链共识机制：PBFT、Tendermint 等需要解决拜占庭将军问题（投票的极端情况）。

延伸

机制设计（反向博弈论）：设计博弈规则使参与者即使自私也达成社会最优。如拍卖、匹配市场（医学院学生实习分配）。

题目 12：拍卖理论

题面

四种主要拍卖形式：

英式拍卖：从低价起，逐步加价，最后剩余者得标。
荷式拍卖：从高价起，逐步降价，第一个接受者得标。
第一价格密封拍卖：每人暗中报价，最高者得标，付自己的报价。
第二价格密封拍卖（Vickrey）：每人暗中报价，最高者得标，付第二高报价。

哪种对卖家最有利？买家该如何策略？

拆解与思考

收益等价定理（Myerson, 1981）：在独立私人价值假设下，四种拍卖形式给卖家的期望收益相同。

但策略不同：

英式拍卖：买家最优策略是报自己的真实估值（不会多付）。
荷式拍卖：买家需猜测他人估值，复杂。
第一价格密封：买家应低于真实估值报价（"阴影报价"），否则多付。
第二价格密封（Vickrey）：买家应报真实估值——这是"激励兼容"的。

Vickrey 拍卖的巧妙

为什么报真实估值是最优的？

设你估值 V，报价 B，第二高报价 S。

若 B > S：你赢，付 S。收益 V - S > 0。
若 B < S：你输，收益 0。
若 B = S：平局。

关键：你付的是 S，不是 B（只要 B > S）。所以：

若 V > S：报 B = V 必赢（B = V > S），收益 V - S > 0。
若 V < S：报 B = V 必输（B = V < S），收益 0。
报其他 B' ≠ V：
- 若 B' > V 但 B' > S 而本应 V < S：你赢但 V - S < 0，亏。
- 若 B' < V 但 B' < S 而本应 V > S：你输，少赚。

任何偏离都不优于报真实估值。

答案

四种拍卖期望收益相同，但Vickrey 拍卖具有"激励兼容"性——买家报真实估值是最优策略。这是机制设计的经典范例。

现实应用

Google AdWords：本质是 Vickrey 拍卖的推广（GSP 拍卖）。
国债拍卖：美国财政部用混合形式。
碳配额拍卖：环境政策工具。
eBay：英式拍卖的电子版。

题目 13：稳定婚姻问题

题面

n 男 n 女相亲。每人心里对所有异性有一个偏好排序。如何匹配使匹配稳定——不存在一对男女：他们都更喜欢对方胜过自己的配偶？

拆解与思考

Gale-Shapley 算法（1962，2012 诺贝尔经济学奖）：

每个男人向最喜欢的女人求婚。
每个女人暂时接受求婚中最喜欢的（拒绝其他）。
被拒的男人转向下一个喜欢的女人求婚。
重复直到所有人订婚。

性质：

算法必然终止。
结果是稳定的（不存在私奔对）。
算法对求婚方有利——每个男人得到的是他能得到的最好伴侣。
算法对被求婚方不利——每个女人得到的是她能得到的最差"稳定"伴侣。

代码

python

def gale_shapley(men_pref, women_pref):
    """men_pref[m] = [w1, w2, ...] m 对女人的偏好排序
       women_pref[w] = [m1, m2, ...] w 对男人的偏好排序
    """
    n = len(men_pref)
    free_men = list(men_pref.keys())
    proposals = {m: 0 for m in men_pref}  # 每个男人下次求婚的女人索引
    wife = {}  # woman -> man
    husband = {}  # man -> woman

    while free_men:
        m = free_men.pop()
        idx = proposals[m]
        w = men_pref[m][idx]
        proposals[m] += 1

        if w not in wife:
            # w 单身，接受
            wife[w] = m
            husband[m] = w
        else:
            # w 已订婚，比较现任和新求婚者
            m_current = wife[w]
            w_rank = women_pref[w]
            if w_rank.index(m) < w_rank.index(m_current):
                # w 更喜欢新求婚者
                wife[w] = m
                husband[m] = w
                free_men.append(m_current)  # 现任恢复自由
            else:
                free_men.append(m)  # 被拒，继续
    return husband

答案

Gale-Shapley 算法保证找到稳定匹配。算法复杂度 O(n²)。

现实应用

医学院学生实习分配（NRMP）：每年匹配数万医学生到医院。
学校选择：波士顿、纽约中小学分配。
肾脏移植匹配：捐献者与患者的多对多匹配（Alvin Roth 2012 诺奖）。
生产者-消费者匹配：劳动力市场、相亲平台。

延伸

稳定匹配不唯一——可能有多个稳定匹配。Gale-Shapley 找到的是"男性最优"或"女性最优"中的一个。

题目 14：Chomp 游戏（吃毒巧克力）

题面

一块 m×n 的巧克力（网格）。左上角那块（(1,1)）有毒。两人轮流吃：

选一块 (i, j)，吃掉它和右下角的所有块（即所有 (i', j') 满足 i' ≥ i, j' ≥ j）。
吃到 (1,1) 的输。

问：先手必胜还是后手必胜？策略是什么？

拆解与思考

Strategy Stealing Argument：

假设后手有必胜策略 S。

先手第一步只吃右下角那一块 (m, n)（最小操作）。
之后假装自己是后手，使用 S。
如果 S 让先手走到已被吃掉的位置——不可能，因为右下角是最大位置，其他位置都还在。

所以先手能"偷"用后手的必胜策略 S，矛盾。

故先手必胜。

答案

先手必胜（除 1×1 巧克力外）。但具体策略未知——一般情况下的显式策略是数学未解问题。

已知小情况

大小	先手第一步
1×n	吃 (1, n-1)，留 (1, n)（其实先手吃 (1, n) 之后留 1×（n-1）的链）
2×2	吃 (2, 2)
2×3	吃 (2, 2)（留 L 形）
3×3	吃 (2, 3)（或对称）
大	未知显式策略

延伸

为什么 strategy stealing 不给出策略？

它只证明存在必胜策略，但不构造。这是数学中"存在性证明"与"构造性证明"的区别。

工程意义：很多问题（如 Nash 均衡的存在）可以证明存在但难以构造——这是数学之美也是数学之痛。

题目 15：Nim 变体（Misère Nim）

题面

标准 Nim 游戏规则，但取走最后一个石子的人输（不是赢）。胜负如何判断？

拆解与思考

Misère Nim 的 Bouton 定理变体：

若所有堆都只有 1 个石子：先手必胜 ⟺ 堆数为偶数。
否则：先手必胜 ⟺ Nim-sum ≠ 0（与标准 Nim 相同）。

证明直觉

标准版：终态（全 0）对应 Nim-sum = 0，先手把对手推到 Nim-sum = 0 即胜。
Misère 版：终态前一步是"只剩 1 堆 1 个石子"，对应 Nim-sum = 1。先手要把对手推到这个状态，所以最后阶段策略反转。

答案

Misère Nim：

若所有堆 ≤ 1：先手必胜 ⟺ 堆数为偶数。
否则：先手必胜 ⟺ Nim-sum ≠ 0。

延伸

Misère Nim 比 Standard Nim 难分析得多。对一般 impartial game，Misère 版本的 SG 理论极其复杂——Misère Nim 是少数有完整解答的。

题目 16：两人轮流取数（区间博弈）

题面

数组 [4, 5, 1, 8, 2, 9]。两人轮流从两端之一取一个数（左端或右端）。取完后总和大的赢。两人都最优操作，先手必胜的分数？

拆解与思考

动态规划：dp[i][j] = 在子数组 [i..j] 中，当前玩家比对手多拿多少分。

递推：

dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])

解释：当前玩家选左端 nums[i]，对手在 [i+1..j] 中比他多拿 dp[i+1][j]，所以当前玩家净赚 nums[i] - dp[i+1][j]。同理选右端。

边界：dp[i][i] = nums[i]（只剩一个数）。

代码

python

def predict_winner(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = nums[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
    return dp[0][n-1]

答案

对 [4, 5, 1, 8, 2, 9]：

最终 dp[0][5] = 5，即先手比后手多拿 5 分。

总和 = 4+5+1+8+2+9 = 29。先手得分 = (29+5)/2 = 17，后手 12。

延伸

LeetCode 486：Predict the Winner。

变体：石头游戏（偶数堆时先手必胜）。

解题模板（总结）

通用流程

判断博弈类型：impartial（双方操作相同）还是 partizan？完全信息还是不完全信息？
从小情况开始：n=1, 2, 3 时谁能赢？
找 P-position 和 N-position：递推标记每个状态。
寻找通项公式：P-position 有什么共同特征？
对于组合博弈：计算 SG 值，用异或和判断。
证明：归纳法——证明 P-position 的下一步都是 N-position，N-position 至少有一个后继是 P-position。
信息不对称：考虑混合策略和贝叶斯更新。

信号清单

题面信号	推理工具
"n 堆石子，任取一堆中若干"	Nim 和（异或）
"一堆石子，每次取 1-m"	Bash Game：模 (m+1)
"两堆石子，可同减"	Wythoff：黄金比例公式
"棋盘/塔的移动"	汉诺塔：2^n - 1
"每次报 k 个数，目标 n"	Bash 变体：模 (k+1)
"n 个开关 / 灯泡"	数论（完全平方数）
"对称棋盘 / 圆桌"	对称策略
"两人报价 / 投票"	博弈论 / 机制设计
"信息不对称 / 隐藏信息"	混合策略 / 贝叶斯
"吃最后的人输"	Misère 变体

常见陷阱

错判博弈类型：partizan 游戏不能用 SG 函数。
忽略终态：终态决定一切，要明确"输赢"。
不证必胜策略：找到规律后需归纳证明。
滥用对称：只有真正的对称（无禁手）才能用对称策略。
混淆混合与纯策略：不完全信息博弈往往需要随机化。
忽视逆向归纳：博弈分析应从终局倒推。

工具速查

工具	适用场景
Nim 和	多堆取石子
SG 函数	任意 impartial game
逆向归纳	有限博弈（如海盗分金）
贝叶斯更新	不完全信息
纳什均衡	一般博弈
Strategy stealing	对称博弈先手必胜
Gale-Shapley	双边匹配
Vickrey 拍卖	激励兼容机制

博弈与策略 ​

题型特点 ​

为什么面试官爱考 ​

博弈论基础 ​

关键概念 ​

博弈分类 ​

求解流程 ​

题目 1：Nim 游戏 ​

题面 ​

拆解与思考 ​

证明 ​

答案 ​

代码实现 ​

延伸 ​

题目 2：Bash Game（取石子限制版） ​

题面 ​

拆解与思考 ​

必胜策略 ​

答案 ​

变体：取最后一个的人输 ​

延伸 ​

题目 3：Wythoff Game（威佐夫博弈） ​

题面 ​

拆解与思考 ​

Wythoff 公式 ​

答案 ​

判断算法 ​

延伸 ​

题目 4：汉诺塔最小步数 ​

题面 ​

拆解与思考 ​

答案 ​

代码 ​

延伸 ​

题目 5：抢 30 游戏 ​

题面 ​

拆解与思考 ​

答案 ​

推广：每次报 1 到 k 个数，报到 n 获胜 ​

变体：报到 30 输 ​

题目 6：Sprague-Grundy 理论 ​

题面 ​

拆解与思考 ​

关键定理 ​

示例 ​

答案 ​

代码 ​

延伸 ​

题目 7：囚徒困境 ​

题面 ​

拆解与思考 ​

答案 ​

纳什均衡 vs 帕累托最优 ​

重复博弈与一报还一报 ​

延伸 ​

题目 8：最后一位报数（每次报 1-3 个） ​

题面 ​

拆解与思考 ​

答案 ​

题目 9：海盗分金（详细版） ​

题面 ​

拆解与思考（逆向归纳） ​

答案 ​

推广：N 海盗 ​

工程意义 ​

题目 10：信息不对称博弈 ​

题面 ​

拆解与思考 ​

经典例子——扑克中的诈唬 ​

答案 ​

延伸 ​

题目 11：选票博弈（投票悖论） ​

题面 ​

拆解与思考 ​

答案 ​

现实影响 ​

延伸 ​

题目 12：拍卖理论 ​

题面 ​

拆解与思考 ​

博弈与策略

题型特点

为什么面试官爱考

博弈论基础

关键概念

博弈分类

求解流程

题目 1：Nim 游戏

题面

拆解与思考

证明

答案

代码实现

延伸

题目 2：Bash Game（取石子限制版）

题面

拆解与思考

必胜策略

答案

变体：取最后一个的人输

延伸

题目 3：Wythoff Game（威佐夫博弈）

题面

拆解与思考

Wythoff 公式

答案

判断算法

延伸

题目 4：汉诺塔最小步数

题面

拆解与思考

答案

代码

延伸

题目 5：抢 30 游戏

题面

拆解与思考

答案

推广：每次报 1 到 k 个数，报到 n 获胜

变体：报到 30 输

题目 6：Sprague-Grundy 理论

题面

拆解与思考

关键定理

示例

答案

代码

延伸

题目 7：囚徒困境

题面

拆解与思考

答案

纳什均衡 vs 帕累托最优

重复博弈与一报还一报

延伸

题目 8：最后一位报数（每次报 1-3 个）

题面

拆解与思考

答案

题目 9：海盗分金（详细版）

题面

拆解与思考（逆向归纳）

答案

推广：N 海盗

工程意义

题目 10：信息不对称博弈

题面

拆解与思考

经典例子——扑克中的诈唬

答案

延伸

题目 11：选票博弈（投票悖论）

题面

拆解与思考

答案

现实影响

延伸

题目 12：拍卖理论

题面

拆解与思考