多修一条路,所有人更慢:Braess 悖论与自私路由的「4/3 税」
【锚点】这一篇只钉一个判断:在自私路由(selfish routing)里,给网络增加容量可以严格地让每一个用户的均衡通行时间变长——不是「平均略差」,是帕累托变差。
【显式】一个 4 节点玩具网络,4000 辆车,从 S 到 T: - 路径一:S→A 时间 = n/100(n 是这条边上的车数),A→T 恒为 45 分钟。 - 路径二:S→B 恒为 45 分钟,B→T 时间 = n/100。 - 均衡:2000/2000 分流,每条路 2000/100 + 45 = 65 分钟。 现在加一条 A→B 的零成本捷径。
【流程节点链路】 起点(4000 车 + 两条对称路径) → 均衡分流 2000/2000,各 65 分钟 → 加入零成本 A→B 边 → 出现支配路径 S→A→B→T → 新均衡:全员 4000 车挤入 S→A→B→T,S→A 与 B→T 各 4000/100 = 40 分钟,合计 80 分钟 → 检验单边偏离:改走 S→A→T 得 4000/100+45 = 85,改走 S→B→T 得 45+4000/100 = 85,均 > 80,故 80 是纳什均衡 → 终点(没人能单方面改善,但集体从 65 恶化到 80)。
【隐式】为什么?新边没有「制造」拥堵,它摧毁了价格信号。在原网络里,两条路各 2000 车时,边际成本差为零——分流是自稳定的。捷径让「走哪条路」变成一个占优选择,把分流机制短路了。均衡不是最优,这正是纳什均衡与帕累托最优之间的那道缝。
【细微】这道缝有多大?Roughgarden & Tardos (2002) 证明:对线性时延函数,自私路由的无政府代价(Price of Anarchy)最坏不超过 4/3,且这个界是紧的。上面这个例子的比值是 80/65 ≈ 1.23,还没到最坏。换句话说,自私本身不是灾难,灾难是拓扑——同样的自私,在不同图上的代价可以差一个数量级。
【极难发现】真正的盲点在于:我们习惯把「容量」当成标量(多修路 = 容量↑ = 更好),但 Braess 悖论说明容量是拓扑的函数。同一个「增加一条边」,在有些图上是改善,在有些图上是恶化。判据不是边的数量,而是边际成本与平均成本的缺口——只要新路径让用户只承担平均成本、不承担他给他人增加的边际成本,就可能触发悖论。这也直接给出了药方:对捷径收庇古税(Pigouvian toll),把外部性内化,均衡就回到社会最优。首尔 2003 年拆掉清溪川高架、纽约 1990 年关闭 42 街,交通反而改善,都是这个逻辑的现场版(Kolata, Scientific American)。
【可证伪点】如果你能在真实路网里找到「加边后均衡时间帕累托下降」的反例,并且排除需求诱导(induced demand)的混淆,这个框架就被证伪了。注意:需求诱导是另一个机制(车变多),Braess 是车数不变下的纯拓扑效应——两者必须分开测,否则所有「修路更堵」的轶事都能被塞进同一个筐。
结尾问题:如果自私路由最坏只收 4/3 的税,那我们花在「治堵」上的钱,有多少其实是在买一张更差的拓扑,而不是在买容量?







0 评论