🏠 总目录📚 本教程 15 · 拥塞博弈与势函数 ← →

每个人都改善自己的路线,为何整体可能更拥堵?

读后可检查:手算选路和势函数变化,再用 Braess 例子区分均衡与社会成本。

📑 本页目录(点开跳转)

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 就以为算错。


🧱 二、拥塞博弈:把上面那个抽象成一类

上面这题只是特例。拥塞博弈的一般模型只有四条:

  1. 有一堆资源 $R$(路段、机器、频段……)
  2. 每个玩家挑一个资源子集 $a_i \subseteq R$(上题每人只挑一条路,也可以是一整条路径上的多段)
  3. ⭐ 资源 $x$ 的成本 $c(x, k)$ 只依赖用它的人数 $k$,不管用它的是谁
  4. 玩家成本 = 所选资源成本之和:$\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。

改造前:各走一边加一条 A→B 的零耗时通道之后SABTn/1004545n/100上下各 2000 辆每人 20 + 45 = 65 分钟SABTn/1004545n/100耗时 04000 辆全走 S→A→B→T每人 40 + 0 + 40 = 80 分钟
同一批车、同一个路网,只多了一条免费的路,均衡耗时从 65 涨到 80。

改造前:两条对称路径,均衡是各走 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 · 推理服务化 负载分配有类似权衡,但请求不等大小、并发更新等因素可能不满足本模型

✅ 检查点

  1. 判断「没人想换路」时,为什么要用 $t_x(n_x + 1)$ 而不是 $t_x(n_x)$?
  2. 一万人选路那题的均衡是什么?为什么高速路上一个人都没有?
  3. 拥塞博弈的四条模型里,哪一条是势函数论证成立的关键?
  4. Rosenthal 势函数长什么样?它和「总成本」是不是一回事?举个数字说明。
  5. 势函数论证的三步是什么?为什么「有限」这个前提不能省?
  6. 某人换策略让自己的成本降了 3,$\Phi$ 会变多少?为什么?
  7. Braess 悖论里改造前后每人分别耗时多少?既然所有人都变慢了,为什么没人改回去?
  8. 势函数保证了什么、没保证什么?
👀 答案
  1. 因为你换过去之后,自己也算进新路的拥堵里。条件是 $t_x(|N_x|+1) \ge t_y(|N_y|)$;漏掉 $+1$ 会把均衡算偏。
  2. $(n_a, n_b, n_c) = (\mathbf{0},\ 5000,\ 5000)$,每人 50 分钟。高速路固定耗时就是 50,空着都跑不赢挤满 5000 人的另外两条($t_a(1) = 50.001 > 50$)。看到 0 不要以为算错。
  3. 资源成本只依赖人数,且玩家成本按资源相加;有限步终止还依赖有限策略组合。加权后要重新核对,不代表所有加权实例都无均衡。
  4. $\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}$。
  5. ① 让自己变好的改动都使 $\Phi$ 严格下降;② $\Phi$ 只有有限个取值,不能一直降;③ 所以有限步后卡住 = 没人能改进 = 纯策略均衡。「有限」不能省:取值无限时可以一直降而永不到底(像 $1/n$),第 ③ 步就不成立。
  6. 也降 3。共有资源抵消后 $\Delta_\Phi$ 和 $\Delta_{\text{cost}}$ 逐项相同——新用的资源各加一项 $c(x,m_x+1)$,退出的各减一项 $c(x,m_x+1)$。
  7. 改造前 $2000/100+45=\mathbf{65}$,改造后 $40+0+40=\mathbf{80}$(+23%)。没人改回去是因为单方面改更慢:S→A→T 和 S→B→T 都是 85。这正是"均衡"的意思——没人能靠自己变好,哪怕大家一起换回去所有人都能变好。
  8. 在有限无权模型、一次一人严格改善的条件下,保证终止并到达纯 NE。未保证快或高效:新网络均衡 80、集中最优 64.6875,PoA 约 1.237。一般加权模型须另证,但不能断言一加权就无纯 NE。

本节回顾

先记住这四点

  • 检查单人偏离时,新加入资源要把自己也算进去;共有资源人数不变。
  • 势函数不是系统总成本;在本模型中,个人成本变化与势函数变化相同。
  • 有限状态、一次一人、严格改善,才能直接使用本章的终止证明。
  • 稳定不等于高效;PoA 必须比较同一网络的均衡与集中最优。

下一节 👉 16-机制设计在解什么.md

打卡记录保存在你的浏览器里,首页能看到总进度