自私路由的代价有上界:4/3 是定理不是修辞——以及为什么「多加一条路」能让所有人更慢
【锚点】这一篇只钉一个判断:当每个个体只最小化自己的延迟时,系统的总延迟有一个可证明的上界——对线性延迟网络是 4/3;但这个上界随延迟函数的非线性程度增长,所以「自私没关系」这句话只在小度数多项式里成立。
【显式】Pigou 的例子(1920)。一单位流量从 s 到 t,两条边: - 上边:延迟恒为 1(不受流量影响)。 - 下边:延迟 = x(x 是走这条边的流量)。 社会最优:设下边流量 x,总延迟 = x² + (1−x)。求导 2x−1=0 → x=1/2,总延迟 = 1/4 + 1/2 = 3/4。 自私均衡:每单位流量只看自己那条边。只要 x<1,下边延迟 x<1=上边延迟,于是所有流量挤向下边 → x=1,总延迟 = 1。 比值 = 1 / (3/4) = 4/3。
【流程节点链路】Pigou 例子 → 社会最优分配 x=1/2、总延迟 3/4 → 自私均衡全部走慢边、总延迟 1 → 比值 4/3。
【隐式】Roughgarden & Tardos (2002) 证明:对任意线性延迟函数的网络,自私路由的 price of anarchy ≤ 4/3,且 4/3 是紧的(Pigou 就达到它)。这不是某个网络的巧合,是这类博弈的普适上界。
【细微】但「线性」是关键词。对 d 次多项式延迟,price of anarchy = Θ(d / ln d)(Roughgarden 2002)。延迟函数越陡(拥堵越非线性),自私的代价越大。排队系统里延迟随利用率 ρ 大致按 1/(1−ρ) 爆炸,这早已不是线性——所以真实拥堵的 PoA 远不止 4/3。
【极难发现】Braess 悖论是同一个数学的另一面:在一个自私均衡的网络里,新增一条边(或提高某条边容量)可能把均衡推到更差。常被引用的案例是 1990 年纽约市关闭 42 街——研究者预测交通会更糟,结果更好(Kolata, 1990, NYT;后续重分析有争议,这点必须诚实)。机制不是「路不够」,而是新增的捷径改变了每个个体的最优反应,把流量引向一个更差的均衡。
【管理学视角】组织里每个部门优化自己的 KPI,就是自私路由。price of anarchy 告诉你:局部最优的加总有一个可证明的劣化上界;但它也告诉你这个上界依赖「延迟函数的形状」——KPI 越接近阶跃(达标/不达标),非线性越强,PoA 越坏。所以「让每个部门各自最优」在小线性系统里可以忍,在高度耦合、反馈强烈的系统里会灾难。
【待验证点】4/3 的紧性依赖「流量可无限细分」(fractional)。离散的、整数路由(每个包选一条路)里 PoA 可能更高,Pigou 例子要重新算。真实网络是离散的。
结尾问题:如果一个组织能证明自己的部门 KPI 是「线性」的(局部改进按比例转化为全局改进),那它大概不需要中央协调;但绝大多数组织的 KPI 是阶跃的、耦合的——那 4/3 就不该被当作「可以忽略的小数」,而该被当作「你需要机制设计」的信号。你的组织的 KPI,是线性的还是阶跃的?






0 Comments