【博弈论】自私路由的代价有上界吗?Pigou 的 4/3 与 Braess 的「修路反而更堵」
【锚点】这一篇只钉一件事:去中心化自利决策的代价(Price of Anarchy, PoA)不是玄学,它由【拥堵函数的曲率】决定——线性拥堵下最坏只损失 4/3,凸性越强可以无界。
【显式】先给一个能算到小数点后两位的例子。Pigou(1920)的双路网络:上路固定成本 1(宽高速,加车不减速);下路成本 = x(窄路,x 是走这条路的人占总流量的比例)。总共 1 单位流量从 s 到 t。
【流程节点链路】自利均衡 → 每个人都走「当前更便宜」的路 → 下路成本 x 追上上路成本 1 → 均衡时 x=1,全部走窄路 → 总成本 = 1。社会最优 → 让两条路的【边际成本】相等而不是平均成本 → 下路边际成本是 2x(多一个人既自己慢,也让所有前人慢一点)→ 2x=1 → x=½ → 总成本 = ½·½ + ½·1 = ¾。PoA = 1/(¾) = 【4/3 ≈ 1.333】。
【隐式】关键不是「自私很坏」,而是自私者只算自己的【平均成本】,不算他给别人造成的【边际外部性】。下路每多一人,让所有已在下路的人各慢一点点——这个外部性在均衡里被完全忽略。拥堵定价(Pigouvian tax)收的就是「边际成本 − 平均成本」这个差额。
【细微】Roughgarden & Tardos(2002, JACM《How Bad is Selfish Routing?》)证明:对任意网络、任意【线性】拥堵函数,PoA ≤ 4/3,且 Pigou 例子取到等号。4/3 不是这个例子的巧合,是所有线性拥堵网络的最坏上界——而最坏上界恰好被最简单的两路例子达到,这是网络博弈里少见的干净结果。
【极难发现】4/3 只在【线性】时成立。把下路成本换成 x^p:p 越大 PoA 越大,p→∞ 时 PoA→∞(无界,Roughgarden 2003 对任意非减连续成本函数给出无界)。所以「去中心化最多贵 33%」是一个特权结论,只在成本函数线性时成立。
【细微】Braess 悖论(1968)是同一个病的另一张脸,方向相反:不是「自私太贵」,而是【加一条路让所有人更慢】。标准 4 节点网络:s→A 成本 x,A→t 成本 1,s→B 成本 1,B→t 成本 x。没有 A→B 捷径时,均衡 50/50,每人均成本 0.5+1 = 1.5。加一条 A→B 成本 0 的捷径后,50/50 不再均衡(有人绕 s→A→B→t 成本 0.5+0+0.5 = 1 < 1.5),所有人涌向新路,新均衡 s→A→B→t 成本 1+0+1 = 2。结果:多修一条路,每人从 1.5 涨到 2——总容量增加,社会福利下降。
【隐式】Braess 和 PoA 是同一枚硬币:自利均衡对网络拓扑【不单调】。删一条边可能让所有人变好,加一条边可能让所有人变坏。对组织设计的含义很硬:你不能假设「增加一个部门/一条沟通渠道/一个中间人」一定改善协调——它可能改变博弈的均衡,把所有人卡在一个更差的纳什点上。
【极难发现】为什么这两个现象在组织里经常被误诊?因为管理者看的是【平均指标】(平均通勤时间、平均响应延迟),而均衡是由【边际激励】决定的。你在平均指标上看到的「改善」(新增捷径、新增部门)在边际上可能正好给了每个人一个「搭便车绕路」的激励,把系统推到一个更差的均衡。平均指标的改善 ≠ 均衡的改善——这是 PoA 给组织理论最锋利的一刀。
【可辩论的问题】如果 PoA 的上界由成本函数的曲率决定,那么组织设计的第一性问题就不是「要不要中心化」,而是【这个系统的协调成本函数是线性的还是凸的】。线性协调成本下,去中心化最多贵 33%,可以忍;凸协调成本下(Brooks 定律:n 个人有 n(n−1)/2 条沟通边,是二次的),去中心化可以任意糟,这时中心化定价/协调才划算。你所在的系统,成本函数到底是哪一种?大多数人凭直觉回答「线性」,但 Brooks 定律说它是凸的——这或许正是大组织最终都走向某种中心化的深层原因。







0 Comments