一、4000 个人,两条路
一座城市里,4000 位上班族每天早上都要从 S 去 T。有两条路线:
- 上路:先走 S→A,再走 A→T。S→A 是一条窄路,耗时 = 这条路上的车数 ÷ 100(分钟);A→T 是一条宽路,固定 45 分钟。
- 下路:先走 S→B,再走 B→T。S→B 是宽路,固定 45 分钟;B→T 是窄路,耗时 = 车数 ÷ 100。
窄路上车越多越堵:1000 辆车是 10 分钟,4000 辆车是 40 分钟。宽路不管多少车,都是 45 分钟。
每个人都想早点到,每个人都只挑自己此刻最快的那条路,没人会让给别人。
先别往下读。请你想一想:两条路上最后各走多少人?每个人花多少分钟?
两条路一模一样,所以各走 2000 人。窄路耗时 2000 ÷ 100 = 20 分钟,加上宽路的 45 分钟:每个人 65 分钟。这是均衡:如果你现在换到另一条路,那条路上多了你一辆车,窄路变成 2001 ÷ 100 ≈ 20.01 分钟,你反而慢了一点点,所以没人想换。
现在,市政府想做件好事:在 A 和 B 之间修一条免费的捷径,从 A 直接开到 B,耗时 0 分钟。这样就多了一条新路线:S→A→B→T,先走窄路 S→A,再走捷径,再走窄路 B→T。
再请你想一想:捷径修好以后,每个人的通勤时间,会变短、不变,还是变长?
大多数人的第一反应是:变短,至少不会变长。多了一个选择,不想用的人可以不用。
可是答案是:变成 80 分钟。 人人都更慢了。
这一讲要讲的就是这个现象,和它背后的更一般的问题:当每个人都只算自己的账,合起来的结果,比大家商量着来差多少?
二、一个更简单的例子:Pigou 的两条路
我们先把 Braess 放一放,看一个更简单的、能把道理看透的例子。
假设有一群司机,人数记作 1(也可以把它看成"全部司机的 100%")。这些司机从同一个地方去同一个地方,有两条路:
- 路 1:宽路,不管多少人走,耗时都是 1 小时。
- 路 2:窄路,耗时 = 走这条路的人所占的比例 x(小时)。比如一半的人走它,耗时 0.5 小时;所有人都走它,耗时 1 小时。
均衡会是什么? 不管别人怎么走,路 2 的耗时最多是 1 小时(所有人都走它的时候),也就是不会比路 1 慢。所以走路 2 永远不吃亏。均衡是:所有人都走路 2,每个人 1 小时,平均 1 小时。路 1 空着,因为没人想去:就算你一个人换到路 1,也还是 1 小时,不比留在路 2 好。
可是请你想一想:这是最好的安排吗?
假设有一位"交通指挥员",可以直接给每个人指派路线,目标是让大家的平均耗时最短。指挥员让一半的人(x = 1/2)走路 2,一半走路 1:
- 路 2 上的人:耗时 0.5 小时。
- 路 1 上的人:耗时 1 小时。
- 平均:0.5 × 1 + 0.5 × 0.5 = 0.75 小时。
比均衡的 1 小时少了四分之一。换一种说法:均衡的平均耗时,是最优的 1 ÷ 0.75 = 4/3 倍,也就是多花了三分之一。
(0.75 确实是最优:如果有比例 x 的人走路 2,平均耗时 = (1 − x) × 1 + x × x = x² − x + 1,是一条开口朝上的抛物线,最低点在 x = 1/2,值 3/4。)
这就是无政府的代价(price of anarchy):每个人各自选最好的路(“无政府”,没人指挥),合起来的结果,比有人统一安排的最优结果差多少。 这里差的比例是 4/3。
为什么会这样:你只付自己那一份
为什么均衡会差?关键是这一点:你走路 2 的时候,你只感受到"我自己多花了多少时间",没感受到"我让别人多花了多少时间"。
路 2 上已经有 x 比例的人了。你再走上去,你自己的耗时是 x,可是你同时让路 2 上每一个人都慢了一点。路 2 上人的总耗时是 x × x(人数 × 每人耗时),你再多加一个人,总耗时增加的量是 2x,而你自己只承担了其中的 x,另外的 x 是别人替你付的。
这和一个熟悉的场景一模一样:AA 制的饭局。 你们一桌十个人,说好最后平摊。你点一道很贵的菜,你自己只付十分之一,另外十分之九由别人摊。于是人人都多点了几道,账单比大家各付各的时高得多。道路拥堵也是这样:你多占一点路,代价由所有人平摊。 每个人都在算自己那一份,没人算别人那一份。
经济学把这种"我做的事让别人付了代价"叫外部性(externality)。拥堵是外部性最典型的例子。
那在 Pigou 的例子里,这个"别人替你付的"有多大?在最优安排 x = 1/2 的时候,你再多走一个人到路 2,自己多花 x = 0.5,别人多花 x = 0.5,一共多花 1,比走路 1 的 1 小时刚好打平。也就是说,如果每个人都要为自己给别人添的堵付账,大家刚好愿意停在 x = 1/2。这就引出了本讲最后的主题:收费。
三、Braess 悖论:多一条路,人人更慢
现在回到开头的城市。
为什么捷径把人人都拖慢了
捷径修好以前,两条路各 2000 人,每人 65 分钟。捷径刚开通的那一刻,大家还在 2000 / 2000 的位置,请你算一算,第一个想试试捷径的司机会怎样:这位司机走 S→A→B→T,S→A 上有 2000 人(再加上这位司机自己),大约 20 分钟,捷径 0 分钟,B→T 上有 2000 人,大约 20 分钟,一共大约 40 分钟。比 65 分钟快得多!
所以第一个人会换到捷径。第二个人也会。第三个……每个人都发现,换到捷径对自己更好。
一直到所有 4000 人都走了捷径:S→A 上有 4000 人,40 分钟;捷径 0 分钟;B→T 上有 4000 人,40 分钟。每个人 80 分钟。
这时候没人想换回去吗?看另外两条路线:
- S→A→T:S→A 上有 4000 人,40 分钟,加上宽路 A→T 的 45 分钟,一共 85 分钟。
- S→B→T:宽路 S→B 45 分钟,加上 B→T 上有 4000 人,40 分钟,一共 85 分钟。
都比 80 分钟慢。所以没人想换,80 分钟就是新的均衡。
对比一下:
| 没有捷径 | 有了捷径 | |
|---|---|---|
| 每个人的耗时 | 65 分钟 | 80 分钟 |
| 4000 人总耗时 | 260,000 分钟 | 320,000 分钟 |
多修了一条路,每个人每天多花 15 分钟,一共多花了 60,000 分钟(1000 小时)。
⚠️ 难点:为什么"更多选择"会让大家更糟
这里第一次读,往往觉得是个骗局:多一个选择,怎么可能更糟?不想用的人,不用不就行了吗?
关键在于:你不用的时候,你的"不用"并不是一个选项。 每个人看到的是:“如果别人都不用,我用一下,我快得多(40 分钟对 65 分钟)。“所以每个人都想用。 而当每个人都用,窄路 S→A 和 B→T 同时被挤满,捷径带来的那点"一路畅通"的好处,被挤出来的堵吃光了。
用一句话说:每一步,对每一个个人,都是划算的;合起来,对所有人,都是亏的。 这和囚徒困境是同一种味道:每个人做对自己最好的事,合起来比原来更糟。不同的是,Braess 里没有人"背叛”,没有人做坏事,每个人只是选了自己此刻最快的路。
再看一个关键点:这是个均衡,而且只有"人人都走捷径"这一个均衡。 没人能靠自己一个人的努力走出来。你一个人换回旧路线,是 85 分钟,比 80 分钟更慢。要走出来,得大家一起不用它。
不是"修路总是有害”
请不要把这个例子记成"修路没用"。同一座城市,人数不同,结论就变了。
设一共有 n 个人,其他都不变(窄路耗时 = 车数 ÷ 100,宽路 45 分钟):
- 没有捷径:各 n/2 人,每人 n/200 + 45 分钟。
- 有了捷径:人人走捷径(只要这是均衡),每人 n/100 + n/100 = n/50 分钟。
| n | 没有捷径 | 有了捷径 | 捷径带来的变化 |
|---|---|---|---|
| 2000 | 55 分钟 | 40 分钟 | 好事,快了 15 分钟 |
| 3000 | 60 分钟 | 60 分钟 | 刚好打平 |
| 3500 | 62.5 分钟 | 70 分钟 | 坏事 |
| 4000 | 65 分钟 | 80 分钟 | 坏事 |
分界点是 n/50 = n/200 + 45,解出 n = 3000。人少的时候,捷径是好事:窄路不挤,大家都快;人多了,窄路挤满,捷径就成了拖累。(n = 3500 时,人人走捷径仍然是均衡:另外两条路各要 3500 ÷ 100 + 45 = 80 分钟,比 70 分钟慢。)
所以 Braess 悖论讲的是:在某些网络、某些流量下,多一条路会让均衡变差,而不是"路越多越差"。更要紧的是:从外面看,你很难知道自己的城市在哪一边。
慢一点的捷径更糟,更慢的反而好了
再看一个更奇怪的事。假设捷径不是 0 分钟,而是 c 分钟。4000 人的城市,均衡时每个人的耗时是(5 到 25 之间的算法,下面会讲):
| 捷径耗时 c | 0 | 5 | 10 | 15 | 20 | 25 | 30 |
|---|---|---|---|---|---|---|---|
| 均衡耗时 | 80 | 85 | 80 | 75 | 70 | 65 | 65 |
图 2 画的就是这条曲线。三个读法:
- c ≥ 25:捷径太慢,没人走它,均衡就是原来的 65 分钟。
- c = 5:最糟,每个人 85 分钟。捷径要 5 分钟,但人人还是都走它。
- 5 < c < 25:只有一部分人走捷径,其余人走原来的两条路。三条路线耗时要相等:设两条窄路上各有 m 辆车,则 m ÷ 100 + 45 = 2m ÷ 100 + c,解得 m ÷ 100 = 45 − c,每人耗时 90 − c 分钟。c 越大,捷径越慢,反而每个人越快。
最后一条值得多想一想:在 5 到 25 之间,把捷径修得更慢,大家反而更快。 这是不是说,要故意修烂一条路?不是。这说的是:路的"快"要看有多少人在用它,如果它快到会把所有人都吸过来,它就会把窄路挤满。
怎么走出来
两种办法都能让这座城市回到 65 分钟:
- 关掉捷径(或者让它慢到 25 分钟以上)。
- 收费:给走捷径的人加一个代价,让它对个人来说不再划算。
听起来很奇怪:关掉一条路,让大家更快。可这不是说"路越少越好",而是说:在这个网络里,那条路只是把"每个人只算自己的账"这件事放大了。
四、无政府的代价:到底有多糟
两个例子给了两个数字:
- Pigou 的例子:均衡比最优多花 4/3 倍。
- Braess 的例子:有了捷径的均衡是 80 分钟。如果由指挥员统一安排,最好能做到平均约 64.7 分钟(1750 人走上路,1750 人走下路,500 人走捷径;把所有分配方式算一遍可以核对)。比值 80 ÷ 64.7 ≈ 1.24 倍,比 Pigou 的 4/3 小一点。
那最坏能坏到多少呢?
线性耗时的道路网络里,最多 4/3。 如果每条路的耗时都是车数的"一次函数"(形如 a × 车数 + b,比如我们这一讲的所有例子),那么不管路网多复杂、有多少起点终点,每个人各自选最快路的均衡,总耗时最多是最优安排的 4/3 倍,而且 Pigou 的例子说明这个 4/3 是能达到的,不能再小。这是 Roughgarden 和 Tardos 在 2002 年证明的(论文题目是《自私的路由有多糟》,发表在计算机科学的权威期刊《ACM 会刊》上)。
所以:在线性耗时的世界里,“无政府"的代价至多是三分之一。 这个数字不大不小:人人各自为战,没有那么灾难,但也远不是可以忽略的。
另外一个事实:4/3 这个上界只对线性耗时成立。 如果路上车数一多,耗时就急剧上升(比方 Pigou 的路 2 耗时是 x⁴,而不是 x),均衡与最优的差距可以更大:这个例子里,最优让大约 67% 的人走路 2,平均耗时约 0.465 小时,均衡是 1 小时,比值约 2.15。
“无政府的代价"这个名字来自计算机科学家 Koutsoupias 和 Papadimitriou 在 1999 年的论文(论文当时称它"协调比”,price of anarchy 这个名字是后来才通行的)。这两项工作后来一起获得了 2012 年的哥德尔奖(理论计算机科学的重要奖项)。
五、怎么办:让每个人为自己添的堵付账
既然问题出在"你只付自己那一份”,办法就很自然:让你也为别人替你付的那一份付账。 这就是拥堵收费(congestion pricing)。
回到 Pigou 的例子。在最优的安排(一半对一半)下,路 2 上的每一位司机,给别人添的堵相当于 x = 0.5 小时。对路 2 收 0.5 小时的"过路费"(用小时来折算钱):
- 路 2 的人,花费 = 耗时 + 过路费 = x + 0.5。
- 路 1 的人,花费 = 1。
两边一样的时候:x + 0.5 = 1,x = 0.5。刚好是最优的那个安排。 司机们仍然只算自己的账,没有人指挥,但是因为账里多了一项,大家自己走到了最优。
这个收费有一条原则:过路费 = 你给别人添的那一份堵(经济学叫边际外部成本)。Pigou 在 1920 年的《福利经济学》里就用这类例子讲过这个道理(据通行的说法);Vickrey 1969 年的《拥堵理论与交通投资》则把它发展成按时段收费的思路。
再看那个"更陡"的变种。路 2 的耗时变成 2x(而不是 x),路 1 仍然是 1:
- 均衡:2x = 1,x = 0.5,平均耗时 1。
- 最优:平均耗时 = (1 − x) + x × 2x = 1 − x + 2x²,最低点 x = 1/4,平均 0.875。
- 无政府的代价:1 ÷ 0.875 = 8/7,约 1.14 倍。
- 收费:在最优的 x = 1/4,你给别人添的堵相当于 2x = 0.5。收 0.5:路 2 花费 = 2 × 0.25 + 0.5 = 1,等于路 1,大家自己停在 x = 1/4。
⚠️ 难点:司机自己,真的更好了吗?
这里有一个容易漏掉的地方。Pigou 的例子里,收费以后:
- 路 2 的人:耗时 0.5 小时,加上过路费 0.5,花费 1。
- 路 1 的人:耗时 1 小时,花费 1。
每个司机的"总花费"(时间加钱)是 1,和不收费时一模一样。 好处在哪里?在总的时间省了:平均耗时从 1 降到 0.75,而每个路 2 的司机交了 0.5,一半人走路 2,人均收到 0.25 小时的过路费。这笔钱去哪了?
- 如果这笔钱还给大家(比如减税、补贴公交),每个人平均净赚 0.25 小时。
- 如果这笔钱没还给司机,司机们没有一个人变好,只是政府多了一笔钱。
所以:收费让"总的账"变好了,但谁拿到这份好处,要看收来的钱怎么用。 这不是计算能回答的问题。
六、证据:理论与现实
按照惯例,把"理论预测"“证据"“局限"“分歧"分开讲。
理论预测:
- 均衡一般比最优差(无政府的代价)。
- 在特定网络里,加一条路可能让均衡更差(Braess)。
- 线性耗时下,差距最多 4/3;收费等于外部成本,可以把均衡推回最优。
证据:
- **Braess(1968)**的原始论文是德语的《关于交通规划中的一个悖论》,发表在《运筹学》(Unternehmensforschung)第 12 卷 258–268 页,2005 年才有英译(《运输科学》39 卷 446–450 页)。它是一个数学例子,不是对现实的测量。
- **Youn、Gastner 和 Jeong(2008)**在《物理评论快报》101 卷 128701,用波士顿、纽约、伦敦的道路网络做了分析,讨论均衡和最优之间的差距,以及调整路网能不能改善。我只核对到题目和摘要,没核对具体数字,请不要把它读成"这三座城市的真实数据证明了 Braess”:这是模型分析。
- 新闻报道:纽约时报 1990 年 12 月 25 日有一篇 Kolata 的报道,讲的是纽约 42 街(据报道)短暂关闭,交通并没有预想的那么糟。这是新闻,不是对照实验,我也没核对全文。网上流传的德国斯图加特类似故事,我只见到二手的说法,没核对原始资料,不引用。
- 实验室实验:Rapoport、Kugler、Dugar 和 Gisches(2009)在《博弈与经济行为》65 卷第 2 期(538–571 页)让真人参与者在网络里选路。据摘要,参与者很快收敛到均衡的路线,即使在加了一条路的网络里,收入也大幅下降。这说明 Braess 的现象不只出现在黑板上。
- 收费:伦敦从 2003 年起对进入市中心的车辆收费,Leape(2006,《经济展望杂志》20 卷第 4 期 157–176 页)讨论过这个政策。我没有读全文,所以这里不引用任何具体的效果数字。
局限:
- 现实的司机不是一个同质的整体:每个人的"时间值多少钱"不一样,有人愿意付钱换时间,有人不愿意。
- 现实的路是动态的:堵车在一天里有高峰有低谷;出发时间本身也是选择。
- 现实的司机不一定清楚所有路线:多数人靠习惯、靠导航,而不是在每个路口比较。
- Braess 悖论是特定网络、特定流量下的结果(n = 2000 的例子里,捷径反而有益),在真实的城市里,判断某条路属于哪一种,需要实际的流量数据与模型。
分歧(事实问题与价值问题要分开):
- 事实问题:收费能让道路变得多快?谁真的承担了成本?这些要靠数据,各城市的结果不同。
- 价值问题:道路是应当"谁出得起钱谁用”,还是"谁需要谁用”? 收费在效率上说得通,可是付得起的人继续开,付不起的人被挤到别处,这算不算公平?收来的钱应当用在哪里?这些没有计算能回答的正确答案,取决于你更看重什么。博弈论能告诉你每种做法"会发生什么",不能替你决定"该不该"。
七、常见的误用
- 把 Braess 读成"多修路没用"。 不对。n = 2000 的例子里,捷径让每个人快了 15 分钟。悖论说的是"可能",不是"一定"。
- 把"无政府的代价"读成"必须有政府管"。 无政府的代价只量了比最优差多少,没说"管"的成本。管理要花钱,管错了还可能更糟。线性耗时下最多差 4/3,这个数字本身就是一个提醒:有时候不管,代价也有限。
- 以为收费就是为了"赚钱"。 在这里,收费的作用是让价格反映你给别人添的堵,目的是把均衡推向最优。钱是副产品。
- 以为每个人"聪明"就不会堵。 在 Braess 里,每个人都足够聪明,都选了自己此刻最快的路。堵车不是因为谁笨,而是每个人的最优反应汇在一起,不是大家的最优。
- 把 4/3 当成通用的上界。 它只对线性耗时成立。路一旦"陡"起来(x⁴ 的例子),比值可以更大。
八、小结
- 均衡:每个人各选自己最快的路,被用到的路耗时一样,没被用到的路不比它快。
- Pigou 的例子:路 1 固定 1 小时,路 2 耗时 x。均衡是所有人走路 2,平均 1;最优是一半一半,平均 0.75;无政府的代价 4/3。
- 外部性:你多占一点路,别人替你付了代价。像 AA 制饭局:你点一道贵菜,只付十分之一。
- Braess 悖论:4000 人,窄路 = 车数 ÷ 100、宽路 45 分钟。没有捷径 65 分钟;修了免费捷径,人人走它,80 分钟;总耗时从 260,000 增到 320,000(分钟·人)。
- 不是"修路有害":n = 2000 时捷径有益(55 → 40),n = 3000 持平,n > 3000 有害。捷径耗时 c = 5 时最糟(85),5 到 25 之间是 90 − c,c ≥ 25 时没人走它。
- 无政府的代价:Braess 例子约 1.24 倍;线性耗时下,最多 4/3(Roughgarden–Tardos 2002);更陡的耗时可以更大(x⁴ 约 2.15)。
- 拥堵收费:收费 = 你给别人添的那一份堵。Pigou 例子收 0.5,大家自己走到一半对一半;变种 2x 收 0.5,走到 x = 1/4。
- 谁得益:司机自己的总花费没变,好处在收来的钱怎么用。
- 证据:Braess 1968 是数学例子;Youn 等 2008 是模型分析;Rapoport 等 2009 的实验支持 Braess 现象;关于 42 街和伦敦的说法,我只核对了出处,没核对细节。
回到开头的城市。下次你堵在路上,请想一想:此刻你选的这条路,是你一个人的最优,还是大家的最优?如果有人让你为自己添的堵付一点钱,你会换一条路吗?这笔钱,你希望用在哪里?
思考题
- 把开头城市的人数改成 2000,其他不变。没有捷径时每人耗时多少?修了免费捷径后,人人走捷径,每人耗时多少?捷径是好事还是坏事?再说明为什么此时人人走捷径仍然是均衡。
- 人数是 n,窄路耗时 = 车数 ÷ 100,宽路 45 分钟。用 n 表示"没有捷径"和"人人走免费捷径"的每人耗时,并求出分界点 n。
- Pigou 的例子,但路 2 的耗时是 3x(路 1 仍是 1)。求均衡、最优、无政府的代价,以及能使司机自己走到最优的过路费。
- 开头城市,4000 人,捷径耗时 10 分钟。均衡时每个人耗时 80 分钟,请求出三条路线各有多少人走。(提示:先猜两条窄路的车数相同。)
- Pigou 的例子(路 2 耗时 x),如果过路费定成 0.3(而不是 0.5),均衡时走路 2 的比例是多少?平均耗时是多少?和最优比,差多少?
- 你所在的城市(或学校、小区)有没有"每个人只算自己那一份"的地方:拥堵的路、电梯、食堂排队、共享单车乱停?如果要设计一种"让人为自己添的堵付账"的办法,你会怎么设计?这个办法的好处和代价各是什么,哪些部分是事实问题,哪些是价值问题?
思考题提示
- 没有捷径:各 1000 人,每人 1000 ÷ 100 + 45 = 55 分钟。有了捷径,人人走:S→A 2000 人 20 分钟,捷径 0,B→T 2000 人 20 分钟,每人 40 分钟。捷径是好事(快 15 分钟)。仍是均衡:另外两条路各要 20 + 45 = 65 分钟,比 40 分钟慢,没人想换。
- 没有捷径:n/200 + 45。人人走捷径:n/100 + n/100 = n/50。令 n/50 = n/200 + 45,4n/200 − n/200 = 45,3n/200 = 45,n = 3000。n 小于 3000 时捷径更快(好事),大于 3000 时更慢(坏事)。
- 均衡:路 2 的耗时 3x 涨到 1 时,两条路一样快,没人再想换,所以 3x = 1,x = 1/3。平均耗时 1。最优:平均 = (1 − x) + 3x² ,对 x 求最低点:−1 + 6x = 0,x = 1/6,平均 = 5/6 + 3/36 = 5/6 + 1/12 = 11/12 ≈ 0.917。无政府的代价 = 1 ÷ (11/12) = 12/11。过路费 = 你给别人添的那份 = 3x(最优时 x = 1/6)= 0.5,验证:路 2 花费 = 3 × 1/6 + 0.5 = 1,等于路 1。
- 设 S→A→T、S→B→T 各 y 人,捷径路线 z 人,对称所以两条窄路车数相同,都是 y + z。窄路耗时 (y + z)/100。路线耗时相等:S→A→T = (y + z)/100 + 45;捷径 = (y + z)/100 + 10 + (y + z)/100。令相等:(y + z)/100 = 35,y + z = 3500。又 2y + z = 4000,解得 y = 500,z = 3000。三条路线:S→A→T 500 人,S→B→T 500 人,捷径 3000 人;每人 35 + 45 = 80 分钟。
- 路 2 花费 = x + 0.3,路 1 花费 = 1,相等得 x = 0.7。平均耗时 = 0.3 × 1 + 0.7 × 0.7 = 0.79 小时。最优 0.75,差 0.04 小时。(比不收费的 1 小时好,但没有到最优;过路费刚好等于外部成本时才到最优。)
- 开放题。思路:电梯里"每个人只想着自己快",高峰时人人都挤,反而慢;食堂可以用"错峰优惠"让一部分人晚一点来。事实问题:错峰优惠能让多少人改变时间?价值问题:愿意付钱的人先吃,是否公平?钱用在哪里?