📑 本页目录（点开跳转）
13 · 零和与极大极小
⏱ 44 分钟 ｜ ⭐⭐ 整套理论里唯一被真正解决掉的设定
🎯 一句话
当两个人的利益完全相反时，博弈存在一个确定的数 v：玩家 1 能保证至少拿到 v，玩家 2 能保证最多输掉 v —— 第 11 章列的「多重 / 低效 / 难算」三个毛病，在这里同时消失。
这是整门课里唯一一处「博弈被彻底解掉」的地方。也正因为如此， 自我对弈那一整套方法（围棋、国际象棋）只在这个角落里成立。
🛡 一、先不谈均衡：我最差能拿多少
纳什均衡有个隐含前提：对手是理性的，而且大家能协调到同一个均衡上。 可现实里你经常不敢这么假设 —— 对手可能是个新手、可能在赌气、可能是段有 bug 的程序。
那就换一个问题问：
⭐ 不管别人怎么打，我能保证拿到的最低收益是多少？
这个数叫玩家 i 的安全水平（security level），取到它的策略叫 maximin 策略：
$$\underline{v}_i = \max_{s_i}\ \min_{s_{-i}}\ u_i(s_i, s_{-i}),\qquad \text{maximin 策略} = \arg\max_{s_i}\ \min_{s_{-i}}\ u_i(s_i, s_{-i})$$
⭐⭐ maximin 完全不假设对手理性 —— 这是它和 NE 最根本的分野。 它把「所有其他人」当成一个专门挑最坏情况给你的自然界。
⭐ 还有一条省事的引理：
$$\max_{s_i}\min_{s_{-i}} u_i(s_i,s_{-i}) \;=\; \max_{s_i}\min_{a_{-i}} u_i(s_i,a_{-i})$$
对手的最坏情况一定能在纯动作里取到 —— 混合是纯动作的加权平均，平均值不会低于其中最小的那个。 所以内层的 min 只要扫对手那有限几个纯动作就行，不用管他怎么混。
手算套路：行最小值里挑最大
- 只看你自己的收益（行玩家就是每格第一个数）
- 每行取最小值 —— 打这一行最坏能拿多少
- 在这些最小值里取最大 —— 这就是纯策略下的安全水平，对应的行就是纯 maximin 策略
- 列玩家同理：每列取最小值（用他的收益），再在这些最小值里取最大
走一个 3×3（格里写「行收益, 列收益」）：
| 行 ＼ 列 | x | y | z | 行最小（行玩家） |
|---|---|---|---|---|
| a | 4, 0 | 1, 3 | 3, 1 | 1 |
| b | 2, 2 | 2, 1 | 2, 4 | 2 ← 最大 |
| c | 5, 1 | 0, 2 | 1, 5 | 0 |
行玩家：行最小值 1 / 2 / 0，最大是 2 → maximin 策略 = b，安全水平 = 2。
列玩家：按列取他自己收益的最小值 —— x 列 $\min(0,2,1)=0$，y 列 $\min(3,1,2)=1$，z 列 $\min(1,4,5)=1$， 最大是 1，y 和 z 并列都是 maximin 策略，安全水平 = 1。
⚠️ c 行有全表最大的 5，却第一个被淘汰 —— 因为同一行里还有个 0。 maximin 只看每行最差的那一格，不看最好的，这就是「保守」的字面含义。
⭐ 顺便：这个博弈一个纯策略 NE 都没有（用圈法验一下），maximin 却照样算得出来 —— 它不需要任何存在性定理撑腰。
混合能把安全水平抬高
上一章那个性别之争：
| 行 ＼ 列 | 拳击 | 芭蕾 |
|---|---|---|
| 拳击 | 2, 1 | 0, 0 |
| 芭蕾 | 0, 0 | 1, 2 |
纯策略下行最小值是 $\min(2,0)=0$ 和 $\min(0,1)=0$，安全水平 = 0，惨不忍睹。
但允许混合就不一样了。设行玩家打 $(p\ \text{拳击},\ 1-p\ \text{芭蕾})$， 按上面的引理只需要对着列玩家的两个纯动作算：
$$u_1(\cdot,\text{拳击}) = 2p, \qquad u_1(\cdot,\text{芭蕾}) = 1-p$$
保底值是 $\min(2p,\ 1-p)$。一条随 p 上升、一条随 p 下降，最高点必然在交点：
$$2p = 1-p \Rightarrow \boxed{p = 1/3},\qquad \underline{v}_1 = 2/3$$
⭐ 混合把安全水平从 0 抬到了 2/3。 这也是 2×2 求 maximin 的标准手法：两条直线求交。
⚠️⚠️ 但在一般博弈里，maximin 不是均衡
同一个性别之争，把两个数摆一起看：
| 行玩家打拳击的概率 | |
|---|---|
| maximin 策略 | 1/3 |
| 混合 NE 里的策略（第 12 章算过） | 2/3 |
同一个博弈、同一个玩家，两个完全不同的答案。 而且 maximin 会被看穿：列玩家一旦知道 行玩家在打 maximin（拳击 1/3、芭蕾 2/3），就直接 100% 打芭蕾，拿到 $0\times\tfrac13 + 2\times\tfrac23 = \tfrac43$ —— 比他在混合 NE 里的 2/3 整整高一倍。 行玩家倒是拿满了自己的 2/3 保底，但对手白赚。
⚠️ 在一般博弈里，maximin 是「保底」，不是「均衡」。 它保守、可被利用。
那问题来了：什么时候「对手白赚」这件事不可能发生？ —— 当对手赚的正好是你亏的时候。
⚖️ 二、零和博弈
定义：二人正常形博弈，对所有动作组合 $a$ 都有 $u_1(a) + u_2(a) = 0$。
两个人的利益完全相反：玩家 1 的所得就是玩家 2 的所失。
⭐ 因为 $u_2(a) = -u_1(a)$，只写一个矩阵就够了 —— 惯例写行玩家（玩家 1）的收益， 列玩家的读成相反数。上一章两个主例写成单矩阵是这样（左：罚球；右：石头剪刀布）：
| 罚球者 ＼ 守门员 | 扑左 | 扑右 |
|---|---|---|
| 踢左 | −1 | 1 |
| 踢右 | 1 | −1 |
| 行 ＼ 列 | 石头 | 剪刀 | 布 |
|---|---|---|---|
| 石头 | 0 | 1 | −1 |
| 剪刀 | −1 | 0 | 1 |
| 布 | 1 | −1 | 0 |
⚠️ 绝大多数博弈不是零和的：囚徒困境不是（(合作,合作) 总和 4，(叛变,叛变) 总和 2）， 性别之争也不是（3 和 0）。常数和博弈（$u_1+u_2=c$）则本质相同，每人减去 $c/2$ 就化归了。
⭐ 零和是一个很强的假设，所以它能换来很强的结论。 下一节那个定理就是这笔交易的全部内容。
⭐⭐ 三、极大极小定理
在零和博弈里，两个人的安全水平分别是
$$v_1 = \max_{s_1}\min_{s_2} u_1(s_1,s_2), \qquad v_2 = \max_{s_2}\min_{s_1} u_2(s_1,s_2) = \max_{s_2}\min_{s_1}\big(-u_1(s_1,s_2)\big)$$
⭐⭐ 定理（von Neumann, 1928）：在每个有限二人零和博弈里都有 $$v_1 = -v_2$$
翻译成人话：玩家 1 能保证至少拿到 $v_1$，玩家 2 能保证最多输掉 $v_1$。 两个「保证」严丝合缝扣在一起，中间一点缝隙都没有。 这个共同的数就叫博弈的值 $v = v_1$ —— 零和博弈是完全确定的（fully determined）， v 是它唯一理性的结果。
名字是怎么来的：max min = min max
把 $v_2$ 里的负号翻出来（$\min(-x) = -\max x$），得 $v_2 = -\min_{s_2}\max_{s_1} u_1$， 于是 $v_1 = -v_2$ 就等价于那个更好记的形式：
$$\max_{s_1}\min_{s_2} u_1 \;=\; \min_{s_2}\max_{s_1} u_1 \;=\; v$$
⭐ 直觉：先亮牌不吃亏
- 左边 $\max_{s_1}\min_{s_2}$：玩家 1 先承诺一个策略，玩家 2 看到之后最优应对。
- 右边 $\min_{s_2}\max_{s_1}$：玩家 2 先承诺，玩家 1 应对。
直觉上后动的人占便宜，所以 $\max\min \le \min\max$ 这个方向对任何博弈都成立（弱的那一半）。 定理说的是：在零和博弈里，这个便宜正好等于 0。
⚠️ 但请把前提咬住：先亮的是「混合策略」，不是「具体动作」。 罚球里你先告诉对方「我踢左」，你必输；你告诉对方「我 50/50」，他知道了也没用。 ⭐⭐ 随机化正是那个抹掉先后差异的东西 —— 第 12 章那套掷骰子，在这里兑现了它的价值。
手算例子：缝隙怎么合上
还是罚球，把两个方向都算一遍：
| 罚球者 ＼ 守门员 | 扑左 | 扑右 | 行最小 |
|---|---|---|---|
| 踢左 | −1 | 1 | −1 |
| 踢右 | 1 | −1 | −1 |
| 列最大 | 1 | 1 |
只用纯策略：$\max\min = -1$，$\min\max = 1$ —— 中间有 2 的缝隙，定理不成立。
允许混合：罚球者打 $(p, 1-p)$，对着守门员两个纯动作的收益是 $1-2p$ 和 $2p-1$， 交点 $p=1/2$、$v_1 = 0$；守门员同理 $v_2 = 0$。于是 $v_1 = -v_2$，缝隙合上，博弈的值 $v = 0$。
⭐ 这个 (1/2, 1/2) 和第 12 章解出来的混合 NE 一模一样，不是巧合 —— 见下一节。 石头剪刀布同理：纯策略下 $-1 < 1$，混合之后两边都收敛到 $(\tfrac13,\tfrac13,\tfrac13)$，$v = 0$。
🔍 一个手算捷径：先看有没有鞍点
$\max\min$ 和 $\min\max$ 在纯策略层面就相等的话，那个格子叫鞍点，你根本不用混合：
| 行 ＼ 列 | x | y | z | 行最小 |
|---|---|---|---|---|
| a | 3 | 1 | 4 | 1 |
| b | 2 | 2 | 5 | 2 ← 最大 |
| c | 0 | 1 | 6 | 0 |
| 列最大 | 3 | 2 ← 最小 | 6 |
行最小的最大 = 2，列最大的最小 = 2，相等 → 鞍点在 (b, y)，博弈的值 v = 2，两人都打纯策略就行。 （验一下：列 y 固定时行玩家拿 1/2/1，b 最好；行 b 固定时列玩家要把 $u_1$ 压小，2/2/5 里 y 已是最小 —— 互为最佳响应。）
⭐ 拿到一个零和矩阵，第一件事就是算这两个数。相等 → 鞍点，纯策略解完；不相等 → 老老实实混合。
🎁 四、推论：为什么说零和博弈「被解决了」
极大极小定理带来四条推论，每一条都在拆第 11 章列的毛病：
| 推论 | 拆掉了什么 |
|---|---|
| ⭐ maximin 策略的任意组合都是 NE | 两人各自闷头算自己的保底策略，凑一起自动就是均衡 —— 不需要协调，也不需要猜对手瞄的是哪个均衡 |
| NE 集合是凸的 | 两个 NE 的任意加权平均还是 NE。⚠️ 一般博弈里完全不成立：性别之争两个纯 NE 平均一下（各 1/2）行玩家立刻想偏离 |
| ⭐⭐ 所有 NE 给出同一个值 v | 「多重均衡」这个毛病直接失效 —— 均衡可能不止一个，但你完全不用操心挑哪个，值都一样 |
| ⭐ NE 可以高效计算 | 求零和博弈的值是一个线性规划，多项式时间。对比一般博弈的 PPAD-完全 |
再加上一条：零和博弈里每一个结果都是帕累托最优的 —— 一方多拿必然另一方少拿， 所以「均衡低效」（囚徒困境那种）这个毛病在这里根本无从谈起。
⭐⭐ 讲义原话的分量：「对零和博弈，纳什均衡满足所有的期望。」 第 11 章列的三个毛病 —— 多重、低效、难算 —— 在这里一次性全部消失。 这在整门课里只发生这一次。
🤖 五、这一条为什么撑得起 AlphaZero 那一类方法
⭐⭐ 提炼成一句：零和博弈是「可解的」，一般博弈不是。
- 一般博弈里，「最优策略」这个词其实没有定义 —— 最优取决于对手打什么； 有多个均衡时你连该瞄准哪一个都不知道（性别之争就是活例子）。
- 零和博弈里它有定义：值 $v$ 唯一，「最优策略」= 保证拿到 $v$ 的策略，且与对手打什么无关。
⭐ 所以自我对弈（self-play）才讲得通：两边都在逼近同一个确定的东西。 围棋、国际象棋、将棋都是二人零和博弈 —— AlphaZero 那条路线之所以有明确的收敛目标， 底下垫的就是这个 1928 年的定理。（它们还带先后顺序，属于扩展式博弈， 零和结论在那里换成极小化极大搜索 + 剪枝 —— 下一章讲博弈树和逆向归纳，而搜索算法本身在 《不靠数据的 AI》10–12 章。）
⚠️ 别往外推：一换成非零和（谈判、多方拍卖、大部分真实多智能体系统）， 「自我对弈会收敛到什么」重新变成一个没有答案的问题。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 12-混合策略.html | 本章「两条直线求交」和求 v 那一步，用的全是那一章的期望收益算法；罚球与石头剪刀布的混合 NE 也在那里解过，一比就知道零和里两者为什么重合 |
| 11-纳什均衡.html | 「多重 / 低效 / 难算」三个毛病的原始清单在那里。本章是全书唯一一处三个同时消失的设定 |
| 14-扩展式博弈.html | 本章的 minimax 换到博弈树上就成了逆向归纳 |
| ⭐⭐ 《不靠数据的 AI》10 · 博弈树与 Minimax | 本章是定理，那一章是算法。 极大极小定理（1928）说「值存在且唯一」，Minimax 搜索说「怎么把它算出来」—— 一个是存在性结论，一个是能跑的代码 |
| ⭐ 《不靠数据的 AI》11 · α-β 剪枝 | 上面那句「换成极小化极大搜索 + 剪枝」里的剪枝就在那一章：同样的答案，少看一半的树（最优序下 $O(b^m) \to O(b^{m/2})$，等于同样时间能多看一倍深度） |
| ../强化学习基础/02-MDP.html | 单 agent 的 MDP 里「最优策略」是良定义的、也能算。⭐ 零和博弈是多 agent 世界里唯一保住这个性质的角落 |
✅ 检查点
- 安全水平和 maximin 策略分别是什么？maximin 和纳什均衡在假设上最大的分别在哪？为什么内层的 min 只需扫对手的纯动作？
- 手算第一节那个 3×3，行玩家和列玩家的 maximin 策略与安全水平各是多少？为什么有个 5 的 c 行第一个出局？
- 性别之争里行玩家的 maximin 策略是什么、保底多少？和第 12 章算出的混合 NE 策略比差在哪？
- 零和博弈的定义是什么？为什么只用写一个矩阵？囚徒困境是零和的吗？
- 极大极小定理说了什么？把 $v_1 = -v_2$ 改写成 max min 与 min max 的形式，并说清「先亮牌不吃亏」这个直觉的前提。
- 罚球博弈里纯策略下的 $\max\min$ 和 $\min\max$ 各是多少？混合之后呢？什么叫鞍点？
- 极大极小定理的四条推论是什么？它们分别拆掉了第 11 章的哪个毛病？
- 为什么说「零和博弈是可解的，一般博弈不是」？这跟自我对弈有什么关系？
👀 答案
- 安全水平 $\underline{v}_i = \max_{s_i}\min_{s_{-i}} u_i$，即不管别人怎么打都能保证拿到的最低收益；取到它的策略就是 maximin 策略。⭐ 最大分别：maximin 完全不假设对手理性，把其他人当成专挑最坏情况的自然；NE 则假设人人理性、且协调到同一个均衡上。内层 min 只扫纯动作，是因为混合是纯动作的加权平均、不会低于其中最小的那个 —— 所以 maximin 扫一遍矩阵就有答案。
- 行玩家：行最小值 1 / 2 / 0，最大是 2 → maximin b，安全水平 2。列玩家：按列取自己收益的最小值 0 / 1 / 1，最大是 1 → y 和 z 并列，安全水平 1。⚠️ c 行有全表最大的 5，但同一行还有个 0 —— maximin 只看每行最差那一格。
- 纯策略保底是 $\min(2,0)$ 和 $\min(0,1)$，都是 0；允许混合后 $2p = 1-p \Rightarrow p = 1/3$，保底抬到 2/3。⚠️ 而第 12 章的混合 NE 是 p = 2/3，完全不同。maximin 还会被看穿：列玩家若知道你在打它，就 100% 打芭蕾拿 $\tfrac43$，比他在混合 NE 里的 $\tfrac23$ 高一倍。⭐ 一般博弈里 maximin 是保底，不是均衡。
- 二人博弈且对所有 $a$ 有 $u_1(a)+u_2(a)=0$。因为 $u_2 = -u_1$，列玩家的收益读成相反数就行。⚠️ 囚徒困境不是：(合作,合作) 总和 4、(叛变,叛变) 总和 2。
- （von Neumann, 1928）每个有限二人零和博弈都有 $v_1 = -v_2$：玩家 1 保证至少拿 $v_1$，玩家 2 保证最多输 $v_1$，中间没有缝隙，这个共同的数叫博弈的值 v。改写：$\max_{s_1}\min_{s_2} u_1 = \min_{s_2}\max_{s_1} u_1 = v$。⚠️ 前提是先亮的是混合策略不是具体动作 —— 说「我踢左」必输，说「我 50/50」对方知道也没用。
- 纯策略：$\max\min = \mathbf{-1}$、$\min\max = \mathbf{1}$，中间 2 的缝隙；混合后两人都是 $(\tfrac12,\tfrac12)$，缝隙合上，v = 0（与第 12 章的混合 NE 重合）。鞍点＝$\max\min$ 与 $\min\max$ 在纯策略层面就相等的那一格，此时不用混合；正文 3×3 的鞍点是 (b, y)，v = 2。
- ① maximin 组合都是 NE → 不需要协调；② NE 集合是凸的 → 一般博弈不成立（性别之争两个纯 NE 各取 1/2 就不是 NE）；③ ⭐⭐ 所有 NE 给同一个值 v → 拆掉「多重均衡」；④ 可高效计算（线性规划） → 拆掉「难算」，对比一般博弈的 PPAD-完全。另加：零和里每个结果都帕累托最优，「均衡低效」无从谈起。
- 一般博弈里「最优策略」没有定义 —— 取决于对手打什么，多均衡时连瞄哪个都不知道；零和里有 —— 值 $v$ 唯一，最优策略＝保证拿到 $v$ 的策略，与对手无关。⭐ 所以自我对弈才讲得通：两边逼近的是同一个确定的东西。⚠️ 一换成非零和（谈判、多方拍卖），「会收敛到什么」重新变成没有答案的问题。
🛑 可以停在这里
⚡ 走神救援
⭐安全水平 $\underline{v}_i = \max_{s_i}\min_{s_{-i}} u_i$ ＝「不管别人怎么打我至少拿多少」，取到它的策略叫 maximin；⭐⭐它和 NE 最根本的分别是不假设对手理性。⭐内层 min 只需扫对手的纯动作（混合是纯动作的平均，不会低于最小值），手算就是每行取最小 → 在这些最小值里取最大：正文 3×3 行最小 1/2/0 → maximin 是 b、安全水平 2，列玩家 0/1/1 → y 与 z 并列、安全水平 1。⚠️c 行有全表最大的 5 却第一个出局 —— maximin 只看每行最差那一格。⭐混合能抬高保底：性别之争纯策略保底 0，混合后 $2p=1-p \Rightarrow p=1/3$、保底 2/3（2×2 通法：两条直线求交，取下包络最高点）。⚠️但一般博弈里 maximin 不是均衡：同一博弈的混合 NE 是 p = 2/3，列玩家看穿后 100% 打芭蕾拿 4/3，是他在 NE 里 2/3 的两倍。零和＝二人且 $u_1+u_2=0$，所以只写一个矩阵（囚徒困境不是：总和 4 和 2）。⭐⭐极大极小定理（von Neumann, 1928）：$v_1=-v_2$，即 $\max\min u_1 = \min\max u_1 = v$ —— 玩家 1 保证至少拿 v、玩家 2 保证最多输 v，中间没有缝隙，v 叫博弈的值。直觉「先亮牌不吃亏」，⚠️前提是亮的是混合策略不是具体动作（说「我踢左」必输，说「我 50/50」对方知道也没用）——随机化正是抹掉先后差异的东西。罚球纯策略下 $\max\min=-1 < 1=\min\max$（缝隙 2），混合后两边都 $(\tfrac12,\tfrac12)$、v = 0，与第 12 章的混合 NE 重合。⭐捷径：算「行最小的最大」和「列最大的最小」，相等就是鞍点、纯策略解完（正文 3×3 是 (b,y)、v = 2）。⭐⭐四条推论：maximin 组合都是 NE（不用协调）、NE 集合凸、所有 NE 值相同（拆掉多重均衡）、线性规划可高效算（对比 PPAD-完全）；加上零和里每个结果都帕累托最优，「低效」也无从谈起 —— 第 11 章三个毛病一次全消，全书只此一次。⭐意义：零和「可解」，一般博弈不可解（一般博弈里「最优策略」没有定义，零和里有：v 唯一、与对手无关），所以自我对弈才有明确的收敛目标；⚠️一出零和就作废。
下一节 👉 14-扩展式博弈.md
去那里的理由：前面六章都假设两人同时出手。真实世界大量事情是有先后的， 而且后手看得见先手做了什么 —— 本章那个「先亮牌不吃亏」的结论， 到了博弈树上会变成逆向归纳，同时会冒出一个新问题：均衡里可以藏着没人会真执行的威胁。