15 · 拥塞博弈与势函数
⏱ 32 分钟 | ⭐ 一个很短的论证,解释了「为什么有些博弈保证有纯策略均衡」
🎯 一句话
在本章的有限、无权拥塞博弈中,一次只有一人严格改善自己的成本,势函数会等量下降。
策略组合只有有限个,所以这样的改进不能一直继续。没有人能再单独改善时,就到达纯策略纳什均衡。
关键是“只有有限个取值”,不是“数值有下界就一定能停”;例如 1、1/2、1/3 可以无限下降。
🚗 一、先手算一个:一万个人选路
第 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)$$
对每条有人使用的旧路 y($n_y>0$)和另一条路 x($x\ne y$)都要检查。$n_x,n_y$ 是移动前的人数。 忘了那个 +1,算出来的均衡会偏。
先借助可分流量近似找一个候选。 在忽略单个使用者对拥堵的影响时,使用中的路线耗时相等;先尝试三路等成本的方程。
对于本章一人一辆车的离散模型,均衡路线的当前耗时不必严格相同;最终必须用含 +1 的偏离条件验算。
$$50+\frac{n_a}{1000}=\frac{n_c}{100}$$
$$40+\frac{n_b}{500}=\frac{n_c}{100}$$
$$n_a+n_b+n_c=10000$$
前两式解出 $n_a = 10n_c - 50000$、$n_b = 5n_c - 20000$,代进第三式:
$$16n_c-70000=10000\quad\Rightarrow\quad n_c=5000$$
于是 $n_a=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$)人数没变、直接抵消,只剩两头:
$$\begin{aligned} \Delta_{\text{cost}}&=\sum_{x\in b_i\setminus a_i}c(x,m_x+1)\\ &\quad-\sum_{x\in a_i\setminus b_i}c(x,m_x+1) \end{aligned}$$
(新用的资源,他是第 $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)$。于是
$$\begin{aligned} \Delta_\Phi&=\sum_{x\in b_i\setminus a_i}c(x,m_x+1)\\ &\quad-\sum_{x\in a_i\setminus b_i}c(x,m_x+1) \end{aligned}$$
所以 $\Delta_\Phi=\Delta_{\text{cost}}$。这里两者都按“新值减旧值”定义,严格改善时都为负。
⭐ 两者一模一样,一分不多一分不少。 于是「让自己变好」和「让 $\Phi$ 下降」是同一件事,上面三行直接套上去:每个有限拥塞博弈都有纯策略纳什均衡。
算法可以从任意策略组合开始,一次只让一个人严格降低成本。选择任意更好方案叫改善响应;选择当前成本最低的方案叫最佳响应。
两者在此都可用,但无改善时要停。同成本也不断换,或让多人同时换,不能直接套用上述严格下降证明。
为什么一般博弈没有这个待遇
严格改善动态有循环,就不能存在沿每一步都严格下降的势函数。 但“发现一个循环”不等于“整个博弈没有纯 NE”:别的状态仍可能是均衡。
石头剪刀布确实没有纯 NE,因为任何一对纯行动中都有人能通过改招获益;这要检查双方行动组成的完整状态,不能只把三个行动名称连成一圈当证明。
本章势函数排除严格改善循环:若回到同一完整状态,势函数应回到原值,却又曾严格下降,矛盾。
对照 14 章:有限、完全信息的扩展式博弈可用逆向归纳得到纯策略子博弈精炼均衡。不能仅凭“行动有先后”就把该结论推广到不完全信息集的一般扩展式博弈。
🌉 四、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 分钟的固定耗时,被迫把人流劈成两半;新路把这个约束拆了。
PoA 的分母也必须来自新网络
$80/65\approx1.231$ 比较的是改造前后两个网络的均衡耗时,不是新网络的 PoA。
PoA 比较同一个网络的最坏均衡总成本与集中最优总成本。车数固定时,也可以用平均耗时相除。
令上、下、新通道三条路线的车数为 u、l、z,且总数是 4,000。新网络总耗时为:
$$C=\frac{(u+z)^2+(l+z)^2}{100}+45(u+l)$$
固定 z 后,上下对称分流使平方和最小;代入 u=l=(4,000−z)/2:
$$C(z)=\frac{(4000+z)^2}{200}+45(4000-z)$$
这是开口向上的二次函数,最小点 z=500。因此集中调度应让上、下各走 1,750,新通道走 500。
| 新网络中的状态 | 总耗时 | 平均耗时 |
|---|---|---|
| 均衡:全走新通道 | 320,000 | 80 |
| 集中最优:(1,750,1,750,500) | 258,750 | 64.6875 |
本例每条外侧 45 分钟的路,都可被负载至多 4,000、耗时至多 40 的可变路段替代;因此新通道路线严格优于另外两条,均衡是全走新通道。
$$\operatorname{PoA}=\frac{80}{64.6875}=\frac{256}{207}\approx1.237$$
看清两个对照: 65→80 说明扩路后均衡反而变慢;80 对 64.6875 才衡量新网络内部的均衡效率损失。项目复算见第 27 章挑战 A。
⚠️ 常被引用的现实版是 1990 年纽约第 42 街封街那天交通反而更顺、首尔拆掉清溪川高架路之后市中心通行改善。真实城市同时变化的因素太多,当直觉佐证可以,当证据不行。
⚠️ 五、这个保证什么时候就没了
| 前提 | 破坏之后 |
|---|---|
| 成本只依赖人数,与是谁无关 | 一般加权模型不能直接沿用本证明;不等于每个加权实例都没有纯 NE |
| 玩家、策略有限 | 论证的最后一步「有限个取值不能一直降」直接塌掉 |
| 只要求存在,不要求快 | 一般拥塞博弈的纯 NE 搜索可为 PLS 完全,改善路径也可能很长;不是说每个简单路网都难算 |
| 均衡 = 稳定 | ⭐ 均衡不等于好(Braess)。想要好结果,得改规则,不能指望人自觉 |
加权还要看成本函数与模型。 标准仿射成本的加权拥塞博弈仍有势函数与纯 NE 保证,不能把原证明失效写成“一加权就绕圈”。加权模型的原论文摘要
下一章开始问:既然均衡可能停在 80 分钟,怎样调整规则,让它接近同一网络中的集中最优?限制通道、收费等手段需要各自建模,不能只承诺停在某个预设数字。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 11 · 纳什均衡 | 「纯策略均衡不保证存在」这句话是本章的出发点。先看清它为什么不保证,才知道势函数买到的是什么 |
| 14 · 扩展式博弈 | 有限完全信息博弈可用逆向归纳;其前提与势函数论证不同 |
| 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 不要以为算错。
- 资源成本只依赖人数,且玩家成本按资源相加;有限步终止还依赖有限策略组合。加权后要重新核对,不代表所有加权实例都无均衡。
- $\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。这正是"均衡"的意思——没人能靠自己变好,哪怕大家一起换回去所有人都能变好。
- 在有限无权模型、一次一人严格改善的条件下,保证终止并到达纯 NE。未保证快或高效:新网络均衡 80、集中最优 64.6875,PoA 约 1.237。一般加权模型须另证,但不能断言一加权就无纯 NE。
本节回顾
先记住这四点
- 检查单人偏离时,新加入资源要把自己也算进去;共有资源人数不变。
- 势函数不是系统总成本;在本模型中,个人成本变化与势函数变化相同。
- 有限状态、一次一人、严格改善,才能直接使用本章的终止证明。
- 稳定不等于高效;PoA 必须比较同一网络的均衡与集中最优。
下一节 👉 16-机制设计在解什么.md