多修一条路,所有人更慢:Braess 悖论与 4/3 的代价
【锚点】这一篇只钉一个判断:在共享稀缺容量的系统里,「增加一个选项」不是帕累托改进的同义词。Braess 悖论不是交通工程的轶事,它是任何由自利单元分散决策的系统的结构性风险——而且这个风险的代价有精确上界。
【显式】先看数字。4000 个司机,从 S 到 T。 - S→A:耗时 = 流量/100 分钟 - A→T:固定 45 分钟 - S→B:固定 45 分钟 - B→T:耗时 = 流量/100 分钟
没有捷径时,均衡是 2000/2000 分流,每人 20+45 = 65 分钟,总时耗 260,000 车·分钟。现在加一条 A→B 的零成本路。
【流程节点链路】起点:无捷径网络,2000/2000 分流,人均 65 分钟 → 中间节点 1:加入零成本边 A→B,任一司机单独改走 S→A→B→T,成本 2x/100(x 为走新路的人数),x<2000 时远小于 65 → 中间节点 2:个体逐一流入,直到 x=4000,人均 2×4000/100 = 80 分钟 → 中间节点 3:此时改回 S→A→T 要 40+45 = 85 分钟,无人愿意退出,纳什均衡成立 → 终点:人均 80 分钟,总时耗 320,000 车·分钟,比加路之前多 60,000,即 +23%;而社会最优(路在、但没人用)仍是 260,000。
【隐式】机制只有一句话:每个司机只支付自己的通行时间,不支付自己给别人增加的拥挤成本。当延迟函数对流量递增,个体最优与社会最优之间就有一个缺口;Braess 边不是制造这个缺口,而是让均衡主动跳进缺口里——它之所以被选中,恰恰因为它在低流量时极其便宜。
【细微】这个缺口的代价有上界。Roughgarden 与 Tardos(2002, How Bad Is Selfish Routing?)证明:非原子拥堵博弈在线性延迟函数下,无政府代价(price of anarchy)恰好是 4/3,且该界是紧的——存在一列网络让均衡总时耗逼近最优的 4/3。但请注意条件:d 次多项式延迟函数下界退化到 Θ(d/ln d),任意非减函数下无界。所以「去中心化最多损失 33%」是一句有前提的承诺,不是普适定律。
【极难发现】组织里的 Braess 边不是路,是「新流程」「新通道」「新汇报线」。它的诊断信号很反直觉:加了一条新路径之后,端到端周期变长,但没有任何一个单元愿意退回旧路径。这不是「大家不配合」,这是均衡。此时加协调、加会议、加看板都无效——你在给一条已经被均衡选中的边做装饰。有效动作只有两个:删边,或定价。边际成本定价原则上能把均衡推回社会最优,但对零成本边来说,让它在低流量时失去吸引力所需的费用高得离谱(本例中低流量下它几乎免费),所以现实处方多半是删边。
【显式·现实证据】首尔清溪川 2003 年拆除 5.6 公里高架路(日均约 16 万车次),周边通行速度不降反升;斯图加特 1969 年关闭一条主干道后区域交通改善。这类案例的共同点:被删掉的边在低流量时太便宜,在高流量时把所有人拖进同一条路径。
【值得辩论的问题】如果 4/3 只在线性成本下成立,那我们在组织里说「分散决策必然低效」时,究竟是在描述一个结构事实,还是在用一条不满足前提的定理给自己背书?你所在的系统,延迟函数真的是线性的吗?







0 Comments