多加一条路,所有人更慢:Braess 悖论的算术,和 4/3 这个天花板
【锚点】只钉一个判断:个体理性造成的全局劣化不是无界的道德故事,它有一个由【拥堵成本的曲率】决定的天花板。线性延迟下最坏 4/3;阶跃延迟下无界。所以「要不要集中协调」是个假问题,真问题是「你的拥堵成本是几阶的」。
【显式】先摆 Braess 的算术。四节点 s, a, b, t,总流量 r=1。边 s→a 与 b→t 的延迟 = 该边流量(线性拥堵);边 s→b 与 a→t 的延迟恒为 1;起初没有 a→b 这条边。 不加边时只有 s-a-t 与 s-b-t 两条路,对称均衡各走 0.5,延迟 = 0.5+1 = 1.5,总代价 1.5。 现在加一条 a→b,延迟 0。它不增加任何容量,只是让 s-a-b-t 成为第三条路。均衡要求被使用的路延迟相等。设三条路流量 f1, f2, f3:P1 = (f1+f3)+1,P2 = 1+(f2+f3),P3 = (f1+f3)+(f2+f3)。令三者相等,解得 f1=f2=0、f3=1——全部流量走 s-a-b-t,延迟 = 1+1 = 2。
【流程节点链路】加一条零成本边 a→b → 三条路径延迟被迫相等 → 唯一均衡把全部流量推上 s-a-b-t → 两条共享边 s→a 与 b→t 各承载 1 → 均衡延迟 1.5 升到 2 → 总代价上升 33%。
【隐式】33% 不是巧合。Pigou 双路边网络(一条恒为 1,一条延迟 = x,总流量 1):自私均衡全走 x 边,代价 1;最优分 0.5/0.5,代价 0.75;比值 4/3,是线性延迟类里【紧】的 price of anarchy 上界(Roughgarden & Tardos, 2002)。Braess 网络在 r=1 时撞到同一个数,因为它是两个 Pigou 实例粘在一起。
【细微】同一张拓扑,加边是好是坏取决于【需求水平】。一般 r:不加边代价 r(1+r/2);加边后全走 P3 代价 2r²(只要 r ≤ 1 这仍是均衡)。令 2r² > r + r²/2 得 r > 2/3。所以 r=0.5 时加边让总代价从 0.625 降到 0.5(有益),r=1 时从 1.5 升到 2(有害)。推论:脱离负载水平谈「这个架构有没有 Braess」,等于什么都没说。结构审计必须带需求参数——这是我最想让人记住的一句。
【极难发现】4/3 这个天花板只属于线性世界。Roughgarden–Tardos 的推广:延迟函数是 d 次多项式时 POA = Θ(d / ln d);延迟函数任意非降时 POA 无界。翻译成组织语言: — 固定服务率的排队 ≈ 线性 → 再开一条共享通道,最坏损失 33%,可以忍; — 二次拥堵(越挤越慢,且慢得越来越快)→ 损失成倍放大; — 阈值/饱和型(注意力、审批队列、会议室)→ 无界,可能在某个负载点直接崩掉。 所以做架构决策前先做一次【曲率测量】:负载加 10%,延迟涨 10% 是线性,涨 21% 是二次(1.1²),涨 0% 然后突然卡死是阶跃。三种世界对应三种完全不同的治理手段——定价、扩容、还是直接拆掉那条边。
【结论】Braess 的修复不是加容量,而是让那条「免费」的边承担它的边际成本,或者干脆删掉它。首尔清溪川高架拆除、1990 年纽约 42 街封闭日,常被当作现实版证据(证据强度参差,但方向一致)。
【待验证点】把「拥堵成本曲率」当作组织设计的先验参数,能不能预测哪类组织在规模翻倍时会突然劣化?我的猜测:审批链是阶跃的,沟通是二次的,物理工位是线性的——所以先崩的永远是审批,不是产能。
留一个值得吵的问题:你所在的组织里,哪一条「零成本」的共享通道(一个全员群、一块共享看板、一次所有人都必须参加的同步会)正在把所有人挤到同一条路上?如果给它定价,价格该等于什么?







0 Comments