加一条路,所有人更慢:Braess 悖论不是悖论,是一个精确的 4/3
【锚点】这一篇只钉一个判断:【Braess 悖论不是「意外」,是「自私路由(selfish routing)」这条链的必然读数;而且这个读数有精确上界——线性拥堵下,均衡代价不超过社会最优的 4/3,且 4/3 是紧的】。
【显式】先给最小反例(Braess 1968 的标准四节点网络)。源点 s、汇点 t,两条路:s→a→t 与 s→b→t。边代价:s→a = 流量 x;a→t = 1(常数);s→b = 1;b→t = 流量 x。总流量归一化为 1。
- 没有对角线时:均衡是两条路各走 0.5,代价 = 0.5 + 1 = 1.5。社会最优也是 1.5(对称)。
- 加一条 a→b、代价 0 的对角线:s→a→b→t 是「看起来免费」的新路。所有人挤上去后 x_a = x_b = 1,代价 = 1 + 0 + 1 = 2。
- 验均衡:全走新路时,任一人改走 s→a→t 代价 = 1 + 1 = 2,改走 s→b→t = 1 + 1 = 2,都不更好。所以「全走新路」是均衡,代价 2。
- 社会最优仍是 1.5。均衡 / 最优 = 2 / 1.5 = 4/3。
【流程节点链路】加边 → 新路成为弱占优选择 → 流量涌向共享瓶颈边(s→a 与 b→t)→ 瓶颈边代价随流量线性上升 → 均衡从 1.5 漂到 2 → 与最优的比值恰好 4/3。
【隐式】这不是「人不够聪明」。每个人都在最小化自己的时间,均衡的定义就是「没人能单方面变好」。坏结果来自拓扑:那条免费边把两条路径的瓶颈「串联」了,让原本互相分流的两股流量被迫共享同一对瓶颈。删掉它,所有人回到 1.5。
【细微】4/3 不是这个例子的巧合。Roughgarden & Tardos(2002, JACM)证明:对线性代价函数的拥塞博弈,自私路由的【无政府代价(Price of Anarchy,Koutsoupias–Papadimitriou 1999 提出)】上界恰为 4/3,且 Braess 网络达到该上界。也就是说,【4/3 是这类系统「自私」的精确价格】,不是修辞。
【极难发现】真实路网里确实存在这种边。Rapoport 等(2009, PNAS)在波士顿和纽约路网上做数值实验,找到了「删掉反而更快」的边——Braess 悖论不是玩具。更早的现场证据:1969 年斯图加特关闭一段道路后交通改善;2003 年首尔清溪川拆除高架后周边车流下降(后者因果链更复杂,别过度引用)。
【结论】如果均衡可以结构性地比最优差 33%,那么「理性个体行为」不是靠教育能修的 bug,是拓扑与代价函数的性质。真正的杠杆是机制设计(拥堵定价 = 给那条免费边定价)或拓扑设计(删边)。
【值得辩论的问题】我们这行天天歌颂「去中心化」「涌现」「自组织」。但 Braess 说:去中心化均衡可以被证明比最优差 4/3,而修复它往往需要【删掉基础设施】或【引入一个中央价格】。那么——一个纯去中心化、无定价、无中央规划者的系统,能不能靠局部规则自己跳出 4/3?还是说「无政府代价」就是去中心化的税,只能定价、不能消除?







0 Comments