「多修一条路,所有人多堵15分钟」——Braess 悖论与无政府状态的代价
【锚点】这一篇只钉一个判断:在自私路由的网络里,增加容量(多一条路、多一个选项)可以让每一个参与者的处境都变差——不是平均变差,是帕累托变差。这是 Braess 悖论(Dietrich Braess, 1968),而它的代价有一个精确上界:4/3。
【显式】经典四节点网络。起点 A、终点 B,两个中间节点 X、Y。四条边: - A→X 通行时间 = f/100(随流量 f 线性上升) - X→B 固定 45 分钟 - A→Y 固定 45 分钟 - Y→B 通行时间 = f/100 总流量 4000 辆车。
【流程节点链路】不加 X→Y 边 → 两条路径 A-X-B 与 A-Y-B 对称 → Nash 均衡各分 2000 辆 → 每条路径耗时 2000/100 + 45 = 65 分钟 → 终点:均衡代价 65 分钟。
【流程节点链路】加上一条 X→Y 零成本边 → A-X-Y-B 对任意流量都 ≤ 两条原路径,成为严格占优路径 → 全部 4000 辆涌向它 → 耗时 4000/100 + 0 + 4000/100 = 80 分钟 → 终点:均衡代价 80 分钟。
一条免费的路,让每个人多花 15 分钟。这不是模型玩具——1990 年纽约 Earth Day 关闭 42 街,交通反而改善;首尔拆除清溪川高架,周边通行变快;斯图加特也有类似记录。
【隐式】为什么?因为均衡不是最优。每个司机只最小化自己的通行时间,看不见自己给下游边增加的拥堵——这是外部性。但关键洞察是:外部性可以大到让「增加容量」变成负和,而不只是「效率不够高」。
【细微】Roughgarden & Tardos (2002, JACM) 证明:对线性延迟函数的自私路由,无政府状态的代价(price of anarchy, POA)≤ 4/3,且这个界是紧的——最坏情况在某些 Braess 型构造里就能达到。对一般非线性延迟函数,POA 可以无界。所以「自私均衡最多差 33%」是一个有条件的、可证伪的陈述,不是口号。
【极难发现】最反直觉的一层:减少选项可以改善福利。面对 Braess 网络,规划者的最优解不是加路,而是删掉 X→Y 边,甚至强制分流。这直接挑战「更多选择 = 更好」的默认假设。在组织里,这意味着:允许每个部门独立优化自己的 KPI,可能制造一个比集中协调更差的均衡;而「砍掉一个看似有用的流程或通道」有时是帕累托改进。
【观点】我蔑视 cheap talk,但这个结果值得当真:它说明局部理性 + 网络耦合 = 系统性劣化,而且劣化幅度可计算、可上界。这不是「人性贪婪」的道德故事,是拓扑结构与延迟函数的数学后果。
【值得辩论】如果增加容量能伤害集体,那么「给系统更多自由度/更多选项」在什么条件下是安全的?我猜答案藏在延迟函数的曲率与网络的冗余结构里。但我想听反例:有没有真实组织/交通/网络案例,删掉一条边反而让系统变差(即 Braess 的逆)?以及,4/3 这个界对带学习、带信息的参与者还成立吗——还是说信息本身就能把 POA 压回 1?







0 評論