📑 本页目录（点开跳转）
15 · 拥塞博弈与势函数
⏱ 32 分钟 ｜ ⭐⭐ 一个很短的论证，解释了「为什么有些博弈保证有纯策略均衡」
🎯 一句话
给博弈找一个「势函数」：只要有人为自己省了 5 分钟，这个数就正好也降 5 —— 有限的数不能一直降，所以改进迟早停下，停下的地方就是纯策略纳什均衡。 拥塞博弈（大家抢同一批资源，用的人越多越慢）就是有这种函数的一类。
🚗 一、先手算一个：一万个人选路
第 11 章说过一件让人不安的事：纯策略纳什均衡不保证存在（石头剪刀布就没有）。但下面这个复杂得多的博弈，纯策略均衡不但有，还能手算。
10000 个人从 X 城到 Y 城，三条路，耗时随人数 $z$ 变化：高速路 $t_a(z) = 50 + z/1000$（底子慢但抗堵）、连接路 $t_b(z) = 40 + z/500$、乡道 $t_c(z) = z/100$（空着飞快，一堵就完）。每人的效用 = 负的耗时。
⚠️ 必踩的坑：判断「没人想换路」时，换过去之后你自己也要算进新路的拥堵里。条件是 $$t_x(|N_x| + 1) \ \ge\ t_y(|N_y|) \quad \text{对所有 } x \ne y$$ 忘了那个 +1，算出来的均衡会偏。
先假设三条路都有人走，那耗时必须相等（否则最慢那条上的人会跑），联立：
$$50 + \frac{n_a}{1000} = \frac{n_c}{100}, \qquad 40 + \frac{n_b}{500} = \frac{n_c}{100}, \qquad n_a + n_b + n_c = 10000$$
前两式解出 $n_a = 10n_c - 50000$、$n_b = 5n_c - 20000$，代进第三式：
$$16 n_c - 70000 = 10000 \ \Rightarrow\ n_c = 5000 \ \Rightarrow\ n_a = \mathbf{0},\ n_b = 5000$$
⭐ $n_a = 0$ 落在了边界上——高速路一个人都没有。验一下：$t_b(5000) = 40+10 = 50$，$t_c(5000) = 50$，两条各 5000 人各 50 分钟；想换到空着的高速路，$t_a(0+1) = 50.001 > 50$，不划算。
⭐ 纯策略均衡：$(0,\ 5000,\ 5000)$，每人 50 分钟。 高速路固定耗时 50 太高，空着都跑不赢挤满的另外两条。「某条资源在均衡里根本不被使用」很常见，别看到 0 就以为算错。
🧱 二、拥塞博弈：把上面那个抽象成一类
上面这题只是特例。拥塞博弈的一般模型只有四条：
- 有一堆资源 $R$（路段、机器、频段……）
- 每个玩家挑一个资源子集 $a_i \subseteq R$（上题每人只挑一条路，也可以是一整条路径上的多段）
- ⭐ 资源 $x$ 的成本 $c(x, k)$ 只依赖用它的人数 $k$，不管用它的是谁
- 玩家成本 = 所选资源成本之和：$\text{cost}_i(a) = \sum_{x \in a_i} c\big(x,\ n_x(a)\big)$（$n_x(a)$ 是用 $x$ 的人数），效用 = 负成本
第 3 条是关键：成本对使用者匿名。谁来用都一样贵——这是后面那个论证能成立的全部理由。
| 真实系统 | 资源 | 一个玩家选什么 |
|---|---|---|
| 城市路网 | 每一段路 | 一条从家到公司的路径 |
| 推理集群 | 每台 GPU 机器 | 请求打到哪台（并发越高排队越久） |
| 无线频段 | 每个信道 | 用哪几个信道（同频用户越多干扰越大） |
🔑 三、⭐ 势函数：这一章真正的内容
先说为什么需要它
要证明「纯策略均衡一定存在」，最省事的办法不是去构造它，而是找一个只会下降的量：
若有一个函数 $\Phi$，使得「任何人做一次让自己变好的改动，$\Phi$ 都严格下降」，那么—— $\Phi$ 的取值只有有限个（玩家有限、策略有限），不能一直降； 所以让不满意的人轮流改，有限步之后一定卡住；卡住 = 没人能再改进 = 纯策略纳什均衡。∎
整个证明就这三行。剩下的问题只有一个：$\Phi$ 长什么样。
Rosenthal 势函数
$$\Phi(a) \ =\ \sum_{x \in R}\ \sum_{k=1}^{n_x(a)} c(x, k)$$
⚠️ 它不是总成本。 总成本 $\sum_x n_x \cdot c(x, n_x)$ 是每个人按最终拥堵付钱；$\Phi$ 是每加一个人记一次当时的价，像一张分期账单。一条路、$c(x,k)=k$、3 人在用：总成本 $= 3 \times 3 = \mathbf{9}$，而 $\Phi$ 这一项 $= 1+2+3 = \mathbf{6}$。别把 $\Phi$ 当"系统总耗时"，它就是个记账量。
⭐ 核心论证（很短，值得看完）
玩家 $i$ 把选择从 $a_i$ 换成 $b_i$，其他人不动。记 $m_x$ = 除 $i$ 之外用资源 $x$ 的人数。
他自己的成本变了多少？ 两边共有的资源（$a_i \cap b_i$）人数没变、直接抵消，只剩两头：
$$\Delta_{\text{cost}} \ =\ \sum_{x \in b_i \setminus a_i} c(x,\ m_x + 1)\ -\ \sum_{x \in a_i \setminus b_i} c(x,\ m_x + 1)$$
（新用的资源，他是第 $m_x+1$ 个人；退出的资源，原本他就是第 $m_x+1$ 个。）
$\Phi$ 变了多少？ $\Phi$ 按资源分列求和，只有人数变了的那些列有变化：新用的那列人数 $m_x \to m_x+1$，多加一项 $c(x,m_x+1)$；退出的那列 $m_x+1 \to m_x$，少掉一项 $c(x,m_x+1)$。于是
$$\Delta_\Phi \ =\ \sum_{x \in b_i \setminus a_i} c(x,\ m_x+1)\ -\ \sum_{x \in a_i \setminus b_i} c(x,\ m_x+1)\ =\ \Delta_{\text{cost}}$$
⭐⭐ 两者一模一样，一分不多一分不少。 于是「让自己变好」和「让 $\Phi$ 下降」是同一件事，上面三行直接套上去：每个有限拥塞博弈都有纯策略纳什均衡。
⭐ 它还顺手给了一个算法：随便从一个组合出发，反复让不满意的人换到更好的选择（最佳响应动态），一定会停，停处就是均衡。
为什么一般博弈没有这个待遇
⭐ 纯策略均衡存在与否，取决于「最佳响应能不能绕圈」。 石头剪刀布的最佳响应链是石头→布→剪刀→石头，永远回到起点，没有任何量在单调变化；有势函数就绕不了圈——绕一圈回到原点，$\Phi$ 却严格降过，矛盾。
⭐ 对照 14 章：那里也有一个纯策略均衡的存在性保证（Selten），理由却完全不同——靠的是时间顺序让逆向归纳有得可挑。同一个结论，两条毫无关系的路。
🌉 四、Braess 悖论：加一条路，所有人更慢
势函数保证的是会停下来，不保证停在好地方。下面这个例子是这句话最狠的注脚。
4000 辆车要从 S 到 T。
改造前：两条对称路径，均衡是各走 2000 辆，每人 $2000/100 + 45 = \mathbf{65}$ 分钟。
改造后：多了一条 A→B、耗时 0 的通道，所有 4000 辆都走 S→A→B→T，$40 + 0 + 40 = \mathbf{80}$ 分钟。这确实是均衡——单独一个人改走 S→A→T 是 $40+45=85$，改走 S→B→T 是 $45+40=85$，都更慢。
💀 每个人都慢了 15 分钟（65 → 80，+23%），而且没有任何人愿意单方面改回去。 一条完全免费、纯属白送的路把所有人都害了。 ⭐ 原因：新路让「S→A」和「B→T」这两段会堵的路同时被所有人使用。原来的路网靠那两段 45 分钟的固定耗时，被迫把人流劈成两半；新路把这个约束拆了。
⭐ 均衡的 80 与最优的 65 之比 $\approx 1.23$，这个比值叫无政府状态的代价（Price of Anarchy）：自私均衡比集中调度差多少。
⚠️ 常被引用的现实版是 1990 年纽约第 42 街封街那天交通反而更顺、首尔拆掉清溪川高架路之后市中心通行改善。真实城市同时变化的因素太多，当直觉佐证可以，当证据不行。
⚠️ 五、这个保证什么时候就没了
| 前提 | 破坏之后 |
|---|---|
| 成本只依赖人数，与是谁无关 | 💀 加权拥塞博弈（大车小车占的道不一样）一般不再保证有纯策略均衡 |
| 玩家、策略有限 | 论证的最后一步「有限个取值不能一直降」直接塌掉 |
| 只要求存在，不要求快 | ⚠️ 存在 ≠ 好找。最佳响应动态可能要走指数多步才停（这类问题属于 PLS 完全） |
| 均衡 = 稳定 | ⭐ 均衡不等于好（Braess）。想要好结果，得改规则，不能指望人自觉 |
最后这条就是下一章的入口：既然自发的均衡可能停在 80 分钟，那规则该怎么写，才能让它停在 65？
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 11 · 纳什均衡 | 「纯策略均衡不保证存在」这句话是本章的出发点。先看清它为什么不保证，才知道势函数买到的是什么 |
| 14 · 扩展式博弈 | 那里有另一个纯策略均衡存在性保证（Selten），靠的是时间顺序不是势函数。两条互不相干的路通向同一类结论 |
| 16 · 机制设计在解什么 | Braess 说明「均衡会停在坏地方」。下一章开始问反过来的问题：想要好结果，规则该怎么设计 |
| AI基础设施 20 · 推理服务化 | 那一章的负载均衡与路由，就是一个活的拥塞博弈：每个请求都想去最空的机器，结果大家一起涌过去。要不要中心化调度，本质上是这一章的问题 |
✅ 检查点
- 判断「没人想换路」时，为什么要用 $t_x(n_x + 1)$ 而不是 $t_x(n_x)$？
- 一万人选路那题的均衡是什么？为什么高速路上一个人都没有？
- 拥塞博弈的四条模型里，哪一条是势函数论证成立的关键？
- Rosenthal 势函数长什么样？它和「总成本」是不是一回事？举个数字说明。
- 势函数论证的三步是什么？为什么「有限」这个前提不能省？
- 某人换策略让自己的成本降了 3，$\Phi$ 会变多少？为什么？
- Braess 悖论里改造前后每人分别耗时多少？既然所有人都变慢了，为什么没人改回去？
- 势函数保证了什么、没保证什么？
👀 答案
- 因为你换过去之后，自己也算进新路的拥堵里。条件是 $t_x(|N_x|+1) \ge t_y(|N_y|)$；漏掉 $+1$ 会把均衡算偏。
- $(n_a, n_b, n_c) = (\mathbf{0},\ 5000,\ 5000)$，每人 50 分钟。高速路固定耗时就是 50，空着都跑不赢挤满 5000 人的另外两条（$t_a(1) = 50.001 > 50$）。看到 0 不要以为算错。
- 第 3 条：成本 $c(x,k)$ 只依赖人数、与是谁无关（匿名）。一旦不同玩家在同一资源上成本不同（加权拥塞博弈），保证就没了。
- $\Phi(a) = \sum_{x} \sum_{k=1}^{n_x(a)} c(x,k)$。不是总成本——总成本按最终拥堵给每人计价。一条路 $c(x,k)=k$、3 人使用：总成本 $=3\times3=\mathbf{9}$，$\Phi$ 这一项 $=1+2+3=\mathbf{6}$。
- ① 让自己变好的改动都使 $\Phi$ 严格下降；② $\Phi$ 只有有限个取值，不能一直降；③ 所以有限步后卡住 = 没人能改进 = 纯策略均衡。「有限」不能省：取值无限时可以一直降而永不到底（像 $1/n$），第 ③ 步就不成立。
- 也降 3。共有资源抵消后 $\Delta_\Phi$ 和 $\Delta_{\text{cost}}$ 逐项相同——新用的资源各加一项 $c(x,m_x+1)$，退出的各减一项 $c(x,m_x+1)$。
- 改造前 $2000/100+45=\mathbf{65}$，改造后 $40+0+40=\mathbf{80}$（+23%）。没人改回去是因为单方面改更慢：S→A→T 和 S→B→T 都是 85。这正是"均衡"的意思——没人能靠自己变好，哪怕大家一起换回去所有人都能变好。
- 保证了纯策略均衡一定存在、最佳响应动态一定会停。没保证：① 停在的地方好不好（Braess：均衡 80、最优 65，PoA ≈ 1.23）；② 多久能停（可能指数步，PLS 完全）；③ 加权拥塞博弈里连存在性都没了。
🛑 可以停在这里
⚡ 走神救援
拥塞博弈 = 一堆资源、每人挑一个资源子集、⭐资源成本 $c(x,k)$ 只依赖用它的人数（与是谁无关）、玩家成本 = 所选资源成本之和。手算例题：10000 人三条路，令耗时相等联立得 $n_b=n_c=5000$、⭐$n_a=\mathbf{0}$，每人 50 分钟——高速路固定耗时 50，空着都跑不赢挤满的另外两条。⚠️ 判均衡要用 $t_x(n_x+1) \ge t_y(n_y)$，换过去自己也算进拥堵里，漏掉 +1 就算偏。这一章真正的内容是 Rosenthal 势函数 $\Phi(a)=\sum_x \sum_{k=1}^{n_x} c(x,k)$：⚠️ 它不是总成本——一条路 $c(x,k)=k$、3 人用时总成本 $3\times3=9$，而 $\Phi$ 这一项是 $1+2+3=6$，它是「每加一个人记一次当时的价」的分期账单。⭐⭐ 核心论证：玩家 $i$ 从 $a_i$ 换成 $b_i$，共有资源直接抵消，只剩 $b_i \setminus a_i$（各加一项 $c(x,m_x+1)$）和 $a_i \setminus b_i$（各减一项 $c(x,m_x+1)$）；他自己的成本变化和 $\Phi$ 的变化逐项相同——省多少 $\Phi$ 就降多少，一分不差。于是三行收工：改进 ⟹ $\Phi$ 严格降 ⟹ 有限个取值不能一直降 ⟹ 有限步后卡住 ⟹ 卡住处就是纯策略纳什均衡，而且最佳响应动态一定收敛。⭐ 一般博弈没这待遇是因为最佳响应会绕圈（石头→布→剪刀→石头）；有势函数就绕不了圈。💀 Braess 悖论：4000 辆车两条对称路径，均衡各 2000 辆、每人 65 分钟；加一条 耗时 0 的 A→B 通道后所有人改走 S→A→B→T，$40+0+40=\mathbf{80}$ 分钟，每人慢 15 分钟却没人愿意单方面改回去（改走别的都是 85）。⭐ 80 / 65 ≈ 1.23 就是 Price of Anarchy。所以势函数保证的是会停下来，不是停在好地方——这正是下一章「规则该怎么设计」的入口。⚠️ 边界：加权拥塞博弈连存在性都没了；有限性前提不能省；存在 ≠ 好找（PLS 完全）。
下一节 👉 16-机制设计在解什么.md