多修一条路,所有人更慢:Braess 悖论、4/3 的无政府代价,与组织的「协调陷阱」
【锚点】这一讲钉一个判断:【网络里「多一条边」不是单调改进】。【Braess 悖论】证明给系统加容量可以让每个参与者都更差;而【无政府代价】给出这种劣化的精确上界——线性时延下恰好 4/3。
【显式】经典 Braess 网络(4 节点 S、A、B、T,总流量归一化为 1): - S→A 时延 = f₁(走这条路的人比例) - A→T 时延 = 1(常数) - S→B 时延 = 1(常数) - B→T 时延 = f₂ 没有 A→B 跨边时,两条路对称,均衡 f₁=f₂=0.5,每人耗时 = 0.5+1 = 1.5。
现在加一条几乎零耗时的跨边 A→B。新均衡:所有人挤 S→A→B→T,f₁=f₂=1,每人耗时 = 1+0+1 = 2。比 1.5 更差。而且此时三条路(S-A-T、S-A-B-T、S-B-T)耗时都等于 2,没人有单方面偏离动机——它是真均衡,不是暂时拥堵。
【流程节点链路】:【起点:无跨边均衡 f₁=f₂=0.5,代价 1.5】 → 【中间节点:加入零耗时跨边 A→B,出现新路径 S-A-B-T】 → 【中间节点:个体理性把流量推向新路径,f₁、f₂ 同时升到 1】 → 【终点:新均衡所有人代价 2 > 1.5,社会总代价上升】。
【隐式】这不是构造出来的怪例。Roughgarden & Tardos (2002, JACM《How bad is selfish routing?》) 证明:时延函数为线性(a·x+b)的路网里,自私路由的【无政府代价】恰好 ≤ 4/3,而且紧。上面这个 Braess 例子正好达到 4/3:社会最优 1.5,均衡 2,2/1.5 = 4/3。换句话说,Braess 不是孤立悖论,它是「自私均衡最多比最优差 33%」这条定理的极值见证。
【细微】为什么是 4/3 而不是别的数?线性时延下,个体把「我多走一点」的边际成本算成了平均成本,漏掉了对后来者的外部性;这个漏算的比率在最坏情况下恰好放大到 4/3。若时延函数变成任意非减函数,无政府代价可以无界(Roughgarden 2005 的 Pigou 族:一条常数时延路 + 一条时延=流量的路,比率可随参数任意放大)。
【极难发现】组织理论的含义,反直觉:我们默认「增加协调通道 / 增加可选路径 / 增加冗余」总是改善系统。Braess 说不是——当个体只优化自己的局部路径、且新通道对个体是低成本时,系统会自发收敛到更差的全局点。这不是「坏人捣乱」,是【个体理性 + 网络拓扑】的联合产物。所以任何「加一层协调机制」的组织设计,都必须先问:这条新边对个体是免费的吗?如果是,它可能只是把所有人更快地送进同一个瓶颈。
值得辩论的问题:如果 4/3 是线性世界的天花板,那现实组织里我们观察到的「加流程反而更慢」,究竟是超过了 4/3(说明时延非线性、存在阈值/拥塞崩溃),还是根本没到 4/3(说明我们连自私均衡都没达到,是协调失败而非无政府代价)?你所在的系统,属于哪一种?







0 评论