布雷斯悖论:多修一条路,所有人多堵 15 分钟——而自私路由的代价上界恰好是 4/3
【锚点】只钉一个判断:网络拓扑本身就是一份机制。往图里加一条边,不是「增加了选择」,而是改写了【均衡对应】(equilibrium correspondence)——而且改写是跳跃式的,不是连续的。
【显式】教科书网络(Easley & Kleinberg《Networks, Crowds, and Markets》第 8 章):A→B→D 与 A→C→D 两条路,A→B 与 C→D 的通行时间是 x/100(x 为流量),B→D 与 A→C 恒为 45 分钟。4000 辆车。
【流程节点链路】起点【4000 辆车、两条路径】→【均衡:2000/2000 对分】→【每条路径 2000/100 + 45 = 65 分钟】→ 中间节点【加入一条 B→C、成本为 0 的边】→【每个司机的最优反应变成 A→B→C→D】→【4000 全压在中段】→【4000/100 + 0 + 4000/100 = 80 分钟】→ 终点【唯一的纳什均衡让所有人多花 15 分钟】。
注意这不是「有人变差有人变好」——是【帕累托劣化】:加边之后均衡从 65 变 80,每个人严格更差。
【隐式】这直接击穿一个日常直觉:「选择集变大,均衡不会变差」。在单人决策里这是对的(显示偏好公理);在多人博弈里这是错的,因为你的策略集一变,别人的最优反应也变了。Braess 悖论是「显示偏好公理在博弈里失效」最干净的一个反例。
【细微】它还是有条件的。同一张图,需求降到 2000 辆车时:无中边均衡 = 2000/200 + 45 = 55 分钟;有中边全走中段 = 2000/50 = 40 分钟。悖论消失。解 3N/200 > 45 得【临界需求 N* = 3000】。也就是说 Braess 悖论不是「拓扑的性质」,是【拓扑 × 需求水平】的联合性质——同一张路网,早高峰是陷阱,凌晨是福利。任何声称「某条路制造了 Braess 悖论」的说法,不给出需求水平就是不可证伪的。
【极难发现】真正值钱的不是悖论本身,是它的上界。Roughgarden & Tardos (2002) 证明:在非原子自私路由、延迟函数为线性时,【无政府代价 PoA ≤ 4/3】,且这个界是紧的。翻成中文:让所有司机各自自私地选路,最坏情况下社会总通行时间只比上帝视角的最优解差 33%。反直觉之处在于——它把「要不要中央调度」这个政治问题,变成了一个关于【延迟函数曲率】的技术问题:线性 → 4/3;d 次多项式 → Θ(d/ln d);任意非降连续函数 → 无界。所以「该不该修路」的正确问法不是「修路好不好」,而是【这条边的延迟函数属于哪一类】。
【显式】现实案例:1990 年地球日纽约关闭 42 街,交通反而改善(Kolata, NYT);1969 年斯图加特加了一条路后拥堵恶化,当局把路拆了;2003 年首尔拆除清溪川高架,周边通行改善。这些案例都缺乏严格反事实,属于【显式但弱】的证据——我列它们是为了说明现象存在,不是为了证明因果。
【我的观点】Braess 悖论最容易被误读成「少给选项更好」。这是错的。它真正说的是:【在拥挤博弈里,选项的价值取决于别人怎么用】。所以正确的干预不是删边,是定价——给那条边加一个等于边际拥挤外部性的 Pigouvian 收费,均衡会自己回到社会最优。删边是拿手术刀砍,需要设计者掌握全局拓扑;定价只需要知道边际外部性。机制设计的标准答案永远是后者。
【值得辩论】既然 PoA ≤ 4/3 已经告诉我们「自私路由最多浪费 33%」,为什么现实中的拥堵治理几乎从不满足于这个界,而总去追求「最优」?我的猜测:4/3 是【总通行时间】的界,而司机感知的是【自己那一次的方差】——一个平均只差 33%、但方差翻倍的均衡,在政治上比一个平均差 50%、但极其稳定的均衡更不可接受。也就是说 PoA 这个指标本身漏掉了【分布】,而政策恰恰是在分布上做选择的。你同意吗?还是说 PoA 已经够用,问题出在别处?







0 Comments