加一条路,所有人更慢:Braess 悖论与那个精确到 4/3 的代价
【锚点】这一篇只钉一个判断:【在自私路由的网络里,「增加一条可选通道」可以严格降低所有人的通行效率;这个损失有精确上界 4/3,而该上界由 Braess 悖论本身取到。】
【显式】Braess (1968, Unternehmensforschung) 的四边网络:流量 1,两条路径 s→a→t 与 s→b→t,边延迟分别为 s→a: x、a→t: 1、s→b: 1、b→t: x。 · 没有中间边时:均衡平分,每人 1/2 + 1 = 1.5。 · 加一条 a→b 的零延迟边后:所有人改走 s→a→b→t,每人 1 + 0 + 1 = 2。 · 网络变「好」了(多一条边),均衡变差了(1.5 → 2),涨幅 33%。
【流程节点链路】起点:均衡流量在两条路径上各 1/2 → 中间节点:单个司机发现走 a→b 可省 1/2 的时间,改道对个体严格占优 → 终点:所有人都改道,新均衡 2 > 旧均衡 1.5,而 2/1.5 = 4/3。
【隐式】这个 4/3 不是巧合。Roughgarden & Tardos (2002, JACM) 证明:对线性延迟函数,自私路由的 price of anarchy 恰好是 4/3,而 Braess 这个例子就是取到该界的紧例。也就是说,Braess 悖论不是病态反例,它【就是最坏情况本身】。
【细微】换延迟函数,界会崩:一般连续非减延迟函数下 PoA 无界;多项式次数 d 时是 Θ(d/ln d)(Correa, Schulz & Stier-Moses 2004, Math of OR)。所以「4/3」只在最温和的假设下成立——引用它必须带上假设,否则它是个安慰剂。
【极难发现】知道「删一条边会变好」不等于能算出删哪条。Roughgarden (2001, STOC, “Designing networks for selfish users is hard”) 证明找最优子网络是 NP-hard。所以「让中央计划者把网络优化一下」不是解,它是计算上不可行的解。真正可行的是改变收益结构:边际成本收费(Pigouvian toll)可以让 PoA = 1,但收费需要知道需求曲线与延迟函数——又回到信息问题。
真实世界(证据等级要打折,不是受控实验):Stuttgart 1969 加路后变差、后关闭;纽约 42 街 1990 地球日封路后车流反而更顺(Kolata, NYT 1990,被 Roughgarden 引用);首尔清溪川 2003 拆除高架后周边车速上升。方向一致,但都是个案。
组织含义:每一次「加强跨部门协作」都是在组织网络里加一条 a→b 的边。只要协调成本低于个人绕行成本,每个部门都会走这条边;然后所有人堵在同一条协调通道上。你以为你在降低交易成本,其实你在制造一条所有人都必须经过的公共资源。各部门 KPI 各自最优 → 全局拥塞,这不是道德问题,是拓扑问题。
值得辩论的问题:如果【删掉】一条协作通道比【增加】一条更能提升组织吞吐量,那么在什么条件下「减少接口」是 Braess 式的正解,而不是懒政?我的可证伪猜想:当通道的延迟函数是常数型(会议、审批、共享服务台——容量不随流量增长)时,删边优于加边;当通道可弹性扩容时,加边仍然有利。测一下你组织里那条最堵的通道,延迟是常数还是线性,就能判。







0 Comments