📑 本页目录（点开跳转）
14 · 扩展式博弈
⏱ 34 分钟 ｜ ⭐⭐ 前面五章都假设「同时出手」，这一章把时间加回来
🎯 一句话
把博弈画成一棵树，从叶子往根倒着算一遍，那些「说了不会真做」的威胁会自己掉出来。 纳什均衡在这里不够用：它允许均衡里藏着一个没人会真执行的动作，而只要没人去试，这个动作就永远不会被拆穿。
🌳 一、同时出手，和有先有后
前面五章（09 到 13）里的博弈都长成一张表，两个人同时把手伸出来。但真实世界里大量的事情是有先后的：先出价再还价、先进入市场再看对手反应、下棋你一步我一步——而且后手看得见先手做了什么。
拿第 12 章那个猜硬币来试：同时出手时没有纯策略均衡，混合均衡各 50%，谁也占不到便宜。现在只改一件事：让玩家 1 先亮，玩家 2 看完再亮。
玩家 2 只要盯着玩家 1 出的东西反着来，就能保证赢。同一组收益，只因为多了个先后顺序，胜负就定了。
⭐ 正常形博弈丢掉的信息是顺序和看得见什么。这两样一旦重要，就必须换一种表示法。
🧩 二、博弈树的零件清单
一棵博弈树上只有四种东西：
| 树上的东西 | 是什么 | 上图里的例子 |
|---|---|---|
| 中间节点 | 一个待决的局面，写着轮到谁 | v₁ 轮到玩家 1，v₂ / v₃ 轮到玩家 2 |
| 边 | 那个局面下可做的一个动作 | 正面 / 反面 |
| 终局节点（叶子） | 游戏结束了 | 四个方框 |
| 收益 | 只在叶子上有，每人一个数 | (1, -1) 即玩家 1 得 1、玩家 2 得 -1 |
形式化是个八元组 $(N, A, H, Z, \chi, \rho, \sigma, (u_i)_{i \in N})$，看着吓人，其实就是这四行的拆分：玩家、全部动作、中间节点、终局节点、每个节点可选哪些动作、轮到谁、走完到哪、终局收益。
⚠️ 本章只讲完美信息的树：轮到自己时完整知道当前在哪个节点。扑克那种「不知道对手手牌」要再加「信息集」，不展开。
🎒 三、⭐ 策略在树上是什么（这里最容易错）
初学者的直觉是：玩家 2 的策略就是「出正面」或「出反面」，两个。错。
⭐⭐ 树上的策略 = 给你的每一个决策点都指定一个动作。 $S_i = \prod_{h \in H:\, \rho(h)=i} \chi(h)$ —— 所有决策点上选择的笛卡尔积。
玩家 2 有 v₂、v₃ 两个决策点，所以他的一个策略是（在 v₂ 出什么，在 v₃ 出什么），共 2 × 2 = 4 个：(正,正)、(正,反)、(反,正)、(反,反)。
⚠️ 走不到的决策点也必须指定动作。 玩家 1 出了正面，v₃ 这辈子都到不了，为什么还要写它？
- 别人正是靠它判断要不要走过去。 玩家 1 出正面还是反面，取决于「如果我出反面，他在 v₃ 会怎么做」。你不写，他没法算。
- 不写就没法验证纳什均衡。 判断均衡要看「有人偏离会怎样」，而偏离恰恰把游戏带到那些原本走不到的节点上。
🔑 策略不是「我打算怎么走」，是「把我交给一个机器人，它需要的全部指令」。 机器人要能应付任何局面，哪怕按计划不会发生。
$|S_i| = \prod_{h:\,\rho(h)=i} |\chi(h)|$ 长得非常快：第六节那个否决游戏的第三个人有 12 个决策点，4096 个策略。⭐ 这就是「树更紧凑」——上图 7 个节点画完，转成正常形却是 2 × 4 的表。
转成正常形
策略定清楚之后转换就是机械的：每个策略组合走到某个叶子，把收益抄进表格（下表是 $u_1, u_2$）。
| (正,正) | (正,反) | (反,正) | (反,反) | |
|---|---|---|---|---|
| 正面 | 1, -1 | 1, -1 | -1, 1 | -1, 1 |
| 反面 | -1, 1 | 1, -1 | -1, 1 | 1, -1 |
看列 (反,正)：玩家 1 怎么出都得 -1。所以均衡是（正面/反面,（反,正）），玩家 2 稳赢 —— 和从树上直接看出来的一致。
👻 四、子博弈完美：把空威胁筛掉
上面那个例子太干净，看不出纳什均衡有什么毛病。换一个。
进入博弈。 新公司要不要进入某个市场；如果进了，在位的老公司可以打价格战，或者容忍。
转成正常形（挑战者两个策略，在位者两个策略）：
| 打价格战 | 容忍 | |
|---|---|---|
| 进入 | -2, 1 | 2, 2 ⭐ |
| 不进入 | 0, 5 ⚠️ | 0, 5 |
这张表有两个纯策略纳什均衡：
- （进入, 容忍）= (2, 2)：挑战者不进只有 0，在位者打价格战只有 1，谁都不想动。✅
- （不进入, 打价格战）= (0, 5)：挑战者面对「打价格战」只得 -2，不进更好；在位者反正没人来，打不打都是 5，「打价格战」也算最优反应。✅ 形式上完全合法。
⚠️ 可第二个均衡里「打价格战」永远不会被执行——挑战者被吓住了压根不来。万一真来了呢？在位者眼前是 1（打）和 2（容忍），他会容忍。那句威胁是假的，这就叫 空威胁（non-credible threat）。
💀 这个 bug 特别阴：空威胁在均衡路径上不会被验证。整局玩下来那个假动作一次都不发生，从结果上根本看不出「均衡里有个谎」。纳什均衡只要求「没人想单方面偏离」，而不偏离恰恰意味着谎话不会被戳穿。
子博弈与 SPNE
子博弈 = 树上任取一个节点、以它为根的整棵子树（上图有 2 个）。子博弈完美纳什均衡（SPNE） = 在每一个子博弈上都是纳什均衡的策略组合。
量一下：「进入之后」那个子博弈里在位者面对 1 和 2，选 1 不是最优反应，（不进入, 打价格战）不是 SPNE，筛掉。剩下唯一的 SPNE 是（进入, 容忍）。
⭐ Selten 1965：每个有限的完美信息扩展式博弈，都存在纯策略 SPNE。 对比：正常形连纯策略纳什均衡都不保证有（石头剪刀布就没有）。把时间加回来反而买到了一个存在性保证 —— 逆向归纳每步只是在有限个数里挑最大值，永远挑得出来。
⚠️ 空威胁不是「永远假的」，而是在你没有承诺手段时是假的。在位者若提前签了「全网最低价保证」、或故意建了过剩产能，打价格战的成本真降下来，威胁就变真了。⭐ 这种「自缚双手」的承诺装置本章之后不再展开；第 16 章起换的是另一个角度：与其等局中人自己造承诺，不如由规则制定者直接改掉收益 —— 那一章「给背叛加一条赔偿 2，合作就变成占优策略」就是同一件事的外部版本。
🔁 五、逆向归纳：手算套路
找 SPNE 不用枚举策略组合，有一套完全机械的做法。
逆向归纳（backward induction） ① 找一个所有子节点都已标好收益向量的节点（第一轮就是子节点全是叶子的那些） ② 看这个节点轮到谁 ③ 挑他自己那一维最大的那条边，标成"选中" ④ ⭐ 把选中那条边的整个收益向量搬到这个节点上 ⑤ 回到 ①，直到根节点
⚠️ 第 ④ 步是唯一会错的地方：搬整个向量，不是只搬那个人的数字——再往上一层轮到别人，他看的是自己那一维，你把别人的数字丢了就算不下去。
练一棵：
四轮：v₄（玩家 2）g 给 1、h 给 3 → 选 h，搬上 (4,3)；v₃（玩家 2）e 给 4、f 给 0 → 选 e，搬上 (2,4)；v₂（玩家 1）c 给 3、d 给 4 → 选 d；v₁（玩家 1）a 给 4、b 给 2 → 选 a。SPNE：玩家 1 用 (a,d)、玩家 2 用 (e,h)，走到 (4,3)。⭐「我最想去的叶子」和「我能到的叶子」是两回事。
✍️ 六、完整手算：三个人否决投票
Alice（1）、Bob（2）、Charlie（3）一起出去玩，候选城市 A、B、C、D。规则：按 Alice → Bob → Charlie 的顺序每人否决一个，剩下的最后一个就是目的地。 偏好（收益越大越喜欢）：
| A | B | C | D | |
|---|---|---|---|---|
| Alice $u_1$ | 3 | 1 | 2 | 0 |
| Bob $u_2$ | 1 | 3 | 0 | 2 |
| Charlie $u_3$ | 3 | 1 | 0 | 2 |
树有 4 × 3 × 2 = 24 个叶子，画出来太挤，直接用表做逆向归纳。
第 1 层（Charlie）：面对两个城市留下自己更喜欢的。他的顺序是 A ≻ D ≻ B ≻ C：
| 剩下 | 结果 | 收益 |
|---|---|---|
| {A,B} / {A,C} / {A,D} | A | (3, 1, 3) |
| {B,C} | B | (1, 3, 1) |
| {B,D} / | D | (0, 2, 2) |
⭐ 只要 A 还在，Charlie 一定留 A。Charlie 是 A 的守门人——这条决定整局。
第 2 层（Bob）：面对三个城市，看自己那一维（$u_2$）：
| Alice 否了 | Bob 面对 | 三个选项各导向哪（括号里 $u_2$） | Bob 的结果 |
|---|---|---|---|
| A | {B,C,D} | 否B→D(2)｜否C→D(2)｜否D→B(3) | B：(1,3,1) |
| B | {A,C,D} | 否A→D(2)｜否C→A(1)｜否D→A(1) | D：(0,2,2) |
| C | {A,B,D} | 否A→D(2)｜否B→A(1)｜否D→A(1) | D：(0,2,2) |
| D | {A,B,C} | 否A→B(3)｜否B→A(1)｜否C→A(1) | B：(1,3,1) |
⭐ 看第 2、3 行：只要 A 在场 Bob 就把 A 否掉——Charlie 会替 A 保驾，留着 A 等于把结果送给只值 1 分的 A。
第 3 层（Alice）：看 $u_1$——否 A→B 得 1，否 B→D 得 0，否 C→D 得 0，否 D→B 得 1。她最好也只有 1。
💀 SPNE 结果是 Brisbane，收益 (1, 3, 1)。Alice 第一个出手，拿到的却是四个选项里的第三名（最爱的 A 值 3 分，到手的 B 只有 1 分），最后出手的 Charlie 也只有 1，赢家是中间那个 Bob（满分 3）。 ⭐ 先手不等于优势——谁占便宜取决于树的形状和后面人的偏好。
顺手看一个空威胁
反过来问：有没有一个纳什均衡，结果是 Alice 最爱的 Adelaide？ 有——Alice 否 D，Bob 面对 {A,B,C} 否 B，Charlie 面对 {A,C} 否 C，⚠️ 而且 Charlie 宣称「面对 {B,C} 我否 B（留 C）」。
最后这句是谎（C 是 Charlie 的 0 分城市），但它让 Bob 不敢否 A：否了会落到 {B,C}、按宣称变成 C、Bob 得 0，不如老实否 B 拿 A 的 1 分。于是谁都不想偏离，这是合法的纳什均衡，结果 Adelaide、(3,1,3)，显然不是 SPNE。第四节那件事在真实大小的例子上重演了一遍。
🌌 七、树太大的时候（一句话带过）
逆向归纳的代价 ≈ 叶子的数量，所以它只对小树可行。
Zermelo 1913：每个零和扩展式博弈都有唯一确定的值——国际象棋理论上早就"解出来"了，三句必有一句成立（先手必胜 / 后手必胜 / 双方保和），我们只是不知道是哪一句。井字棋不到 26 万节点跑得完，国际象棋局面数在 $10^{44}$ 量级跑不完：「有解」和「算得出」之间差着天文数字。于是工程上只能剪枝 + 估值函数，再到 AlphaZero 用自对弈学估值函数替代"算到底"——那是强化学习的活。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 11 · 纳什均衡 | SPNE 是纳什均衡的加强版，先把原版的定义和毛病弄清楚，才知道这里打的是哪条补丁 |
| 13 · 零和与极大极小 | Zermelo 定理是极大极小定理在树上的版本；「零和博弈为什么有唯一的值」在那一章 |
| 15 · 拥塞博弈与势函数 | 本章拿到一个「纯策略均衡一定存在」的保证（Selten），下一章拿到另一个，理由完全不同：靠势函数 |
| 16 · 机制设计在解什么 | 本章说「威胁要可信得先把退路堵死」，那正是机制设计干的事：改规则来改行为，而不是劝人 |
| 不靠数据的 AI 12 · 评估函数与棋类 AI | ⭐ 树太大、逆向归纳算不到底时怎么办：Shannon 1950 的两条路（固定深度全宽度 vs 只挑有希望的几步），以及「评估函数 = 一串特征的加权和」和它带来的地平线效应 |
| 强化学习基础 01 | ⚠️ 分工不同，别指望它讲树：那边根本不建博弈树，靠一次次试错学出「这个局面值多少」。同一个问题（局面怎么估分）的另一条路线 |
✅ 检查点
- 同一组收益，从「同时出手」改成「有先有后」，猜硬币的结论怎么变？为什么？
- 玩家 2 在顺序猜硬币里有几个策略？为什么不是 2 个？走不到的点为什么也要写？
- 逆向归纳第 ④ 步往上搬的是什么？搬错了会怎样？
- 进入博弈的两个纯策略纳什均衡分别是什么？哪一个不是 SPNE，为什么？空威胁为什么在均衡路径上永远不会被拆穿？
- Selten 定理说了什么？它和「正常形博弈的纯策略均衡不保证存在」怎么对得上？
- 否决投票那个例子里 SPNE 的结果是哪个城市？Alice 先出手却拿到第几名？为什么？
- 那个「结果是 Adelaide 的纳什均衡」靠的是谁的哪一句空话？
- Zermelo 定理说国际象棋「已经解出来了」，为什么我们还在下棋？
👀 答案
- 从「五五开的混合均衡」变成后手必胜：玩家 2 看得见玩家 1 出了什么，反着来就赢。正常形表示丢掉了顺序和可见性。
- 4 个——策略要在每一个决策点指定动作，玩家 2 有 v₂、v₃ 两个点，$2\times2=4$，均衡里他用 (反,正)。走不到的点也要写：① 别人靠它做决定；② 不写没法验证均衡，验证靠的就是偏离，而偏离恰好把游戏带到那些点上。
- 搬整个收益向量。上一层轮到别人，他要看自己那一维；丢了就算不下去。
- （进入, 容忍）=(2,2) 和（不进入, 打价格战）=(0,5)。后者不是 SPNE：那个子博弈里在位者打得 1、容忍得 2，选 1 不是最优反应。拆不穿是因为威胁生效了——挑战者被吓住不来，那个动作一次都不执行，而纳什均衡只要求「没人想单方面偏离」。
- 每个有限完美信息扩展式博弈都存在纯策略 SPNE；正常形连纯 NE 都不保证有。因为逆向归纳每步只是在有限个数里挑最大值。
- Brisbane，(1,3,1)，Alice 拿到第三名（最爱的 A 值 3 分，到手的 B 只有 1 分）。因为 Charlie 是 A 的守门人，只要 A 在场 Bob 就先把 A 否掉。赢家是中间的 Bob。
- Charlie 的「面对 {B,C} 我否 B（留 C）」。C 是他 0 分的最差城市，真到了只会留 B。这句话让 Bob 不敢否 A，结果停在 Adelaide、(3,1,3)。
- 「有唯一的值」和「算得出」差着天文数字：代价 ≈ 叶子数，井字棋不到 26 万节点跑得完，国际象棋的 $10^{44}$ 量级跑不完。所以工程上走剪枝 + 估值函数，直到 AlphaZero 用自对弈学估值函数替代"算到底"。
🛑 可以停在这里
⚡ 走神救援
这一章把时间加回来：博弈从一张表变成一棵树，中间节点写着轮到谁，边是动作，只有叶子上有收益。⭐ 同一组收益，猜硬币从「五五开」变成「后手必胜」——正常形丢掉的正是顺序和看得见什么。⭐⭐ 最容易错的一条：树上的策略 = 给你的每一个决策点都指定一个动作，所以玩家 2 有 2×2 = 4 个策略不是 2 个；⚠️ 走不到的点也要写——别人正是靠「如果我走过去你会怎么做」做决定，而且验证均衡靠的就是偏离，偏离恰恰会走到那些点。把策略想成交给机器人的完整指令就不会错。进入博弈是空威胁的标准例子：收益 (0,5)、(-2,1)、(2,2)，两个纯策略纳什均衡，其中（不进入, 打价格战）靠一句永不执行的威胁——真到了那个节点打得 1、容忍得 2，他会容忍。💀 阴的地方：威胁一旦生效就永不被验证。SPNE = 在每个子博弈上都是纳什均衡，那个假均衡于是被筛掉；⭐ Selten 1965 保证纯策略 SPNE 一定存在，而正常形连纯 NE 都不保证有。逆向归纳：找子节点已标好的节点 → 看轮到谁 → 挑他那一维最大 → ⭐把整个收益向量搬上去（只搬自己那个数字是唯一会犯的错）→ 重复到根。完整手算是三人否决投票：Charlie 是 A 的守门人，于是只要 A 在场 Bob 就先把 A 否掉，SPNE 结果 Brisbane、(1,3,1)：⭐ Alice 第一个出手却只拿到第三名，赢家是中间的 Bob——先手不等于优势。同一题还能造一个结果是 Adelaide 的纳什均衡，靠 Charlie 那句「{B,C} 我留 C」的空话吓得 Bob 不敢否 A。最后：Zermelo 1913 说国际象棋理论上早有唯一的值，但局面数在 $10^{44}$ 量级、逆向归纳的代价 ≈ 叶子数，所以工程上只能剪枝 + 估值，直到 AlphaZero 用自对弈学估值函数替代「算到底」。
下一节 👉 15-拥塞博弈与势函数.md