5D Library › 算法博弈论、布雷斯悖论与流量分配的无秩序代价 · English

第二章 无秩序代价:自私最多让我们损失多少

一个比值

上一章的布雷斯网络中,自私均衡的平均通行时间是 2,最优是 1.5,两者之比为 4/3。这个比值有一个名字。

证据

定义与名称。 库楚皮亚斯与帕帕季米特里乌 1999 年研究了一个很简单的网络:若干自私的用户把任务分配到几条并行的链路上。他们提出用「最坏的纳什均衡与社会最优之比」衡量这种系统的效率,并给出了这一比值的上界与下界 (Koutsoupias and Papadimitriou 1999)。帕帕季米特里乌 2001 年在一篇关于算法、博弈与互联网的文章中把它称为无秩序代价(price of anarchy,PoA)(Papadimitriou 2001)。

推导

PoA=最坏的自私均衡的总成本最优的总成本≥1\mathrm{PoA} = \frac{\text{最坏的自私均衡的总成本}}{\text{最优的总成本}} \ge 1

PoA 等于 1 表示自私选择没有损失;PoA 等于 4/3 表示自私均衡的总成本比最优多三分之一。在非原子的路由博弈中,所有用户均衡的总成本都相同,「最坏」一词可以省去。

庇古网络与 4/3

最简单的例子比布雷斯网络还简单。庇古在 1920 年的《福利经济学》中用两条路的例子说明:任由车辆自行分布,两条路上的「麻烦」会变得相等;但把一些车从容易拥堵的那条路移到另一条路上,可以大大减轻留下的车的麻烦,而只略微增加另一条路的麻烦 (Pigou 1920)。写成现代的形式:一单位流量从 ss 到 tt,上路的延迟恒为 1,下路的延迟等于其流量 xx。

推导

均衡。 下路的延迟 x≤1x \le 1,从不比上路慢,所以全部流量走下路,总成本 1×1=11 \times 1 = 1。

最优。 下路走 xx、上路走 1−x1 – x,总成本 x⋅x+(1−x)⋅1x \cdot x + (1 – x) \cdot 1,在 x=1/2x = 1/2 时最小,等于 3/4。

所以 PoA=1/(3/4)=4/3\mathrm{PoA} = 1/(3/4) = 4/3。如果下路延迟改为 xdx^d,最优的下路流量为 x*=(d+1)−1/dx^* = (d+1)^{-1/d},

PoA(d)=[1−d(d+1)−(d+1)/d]−1\mathrm{PoA}(d) = \left[1 – d\,(d+1)^{-(d+1)/d}\right]^{-1}

证据

4/3 与拓扑无关。 拉夫加登与塔尔多什 2002 年证明:在任意网络中,只要每段路的延迟是非负系数的线性函数 ce(x)=aex+bec_e(x) = a_e x + b_e,非原子自私路由的总成本不超过最优的 4/3;对一般的连续、非减延迟函数,自私均衡的总成本不超过「最优地运送两倍流量」的总成本 (Roughgarden and Tardos 2002)。拉夫加登 2003 年进一步证明,对任何包含常数函数的延迟函数类,最坏情形总是由庇古式的两条路网络达到,与网络拓扑无关;对 dd 次以内、非负系数的多项式延迟,上界就是上面的 PoA(d)\mathrm{PoA}(d),它按 Θ(d/ln⁡d)\Theta(d/\ln d) 增长 (Roughgarden 2003)。

作者框架把 4/3 与 Θ(d/ln⁡d)\Theta(d/\ln d) 两个结论都归于拉夫加登与塔尔多什 2002;核对后,「与拓扑无关」的一般结论与多项式上界出自拉夫加登 2003。

推导

# Price of anarchy in Pigou's two-link network: one unit of traffic, link 1 has constant
# time 1, link 2 has time x^d. Selfish users all take link 2 (its time is never above
# 1), total cost 1. The optimum sends x* = (d + 1)^(-1/d) on link 2. Roughgarden (2003)
# showed that for latency functions that are polynomials of degree <= d with nonnegative
# coefficients, this Pigou network is the worst case in ANY network, so PoA <= [1 - d (d
# + 1)^(-(d + 1)/d)]^(-1).
import math

def pigou(d):
    xs = (d + 1) ** (-1 / d)
    opt = xs * xs ** d + (1 - xs)
    return xs, opt, 1 / opt

def brute(d, n=200000):              # check the optimum by a fine grid search
    return min(x / n * (x / n) ** d + 1 - x / n for x in range(n + 1))

print(" d   share on x^d   optimal cost   PoA (closed form)   PoA (grid)   d/ln d")
for d in (1, 2, 3, 4, 6, 8, 10, 16):
    xs, opt, poa = pigou(d)
    dl = f"{d / math.log(d):6.2f}" if d > 1 else "     -"
    print(f"{d:2d}       {xs:.3f}         {opt:.4f}          {poa:.4f}"
          f"          {1 / brute(d):.4f}     {dl}")
print("ratio PoA / (d / ln d): " + ", ".join(
    f"d={d}: {pigou(d)[2] / (d / math.log(d)):.2f}" for d in (4, 16, 64, 256, 1024)))
# The BPR form t = t0 (1 + 0.15 (x/C)^4) is a degree-4 polynomial, so 2.151 bounds its
# PoA. How close does a BPR road get? Worst Pigou network for c(x) = 1 + 0.15 x^4 at
# demand r (in units of capacity): link 1 has the constant time c(r), so selfish users
# all take link 2.
def bpr_pigou(r, n=20000):
    c = lambda x: 1 + 0.15 * x ** 4
    opt = min(r * k / n * c(r * k / n) + (r - r * k / n) * c(r) for k in range(n + 1))
    return r * c(r) / opt
RS = (0.5, 1, 1.5, 2, 3, 5, 10)
print("BPR road, demand / capacity:  " + "  ".join(f"{r:>5}" for r in RS))
print("worst-case PoA:               " + "  ".join(f"{bpr_pigou(r):5.3f}" for r in RS))
#  d   share on x^d   optimal cost   PoA (closed form)   PoA (grid)   d/ln d
#  1       0.500         0.7500          1.3333          1.3333          -
#  2       0.577         0.6151          1.6258          1.6258       2.89
#  3       0.630         0.5275          1.8956          1.8956       2.73
#  4       0.669         0.4650          2.1505          2.1505       2.89
#  6       0.723         0.3803          2.6297          2.6297       3.35
#  8       0.760         0.3246          3.0808          3.0808       3.85
# 10       0.787         0.2847          3.5121          3.5121       4.34
# 16       0.838         0.2116          4.7268          4.7268       5.77
# ratio PoA / (d / ln d): d=4: 0.75, d=16: 0.82, d=64: 0.84, d=256: 0.86, d=1024: 0.88
# BPR road, demand / capacity:    0.5      1    1.5      2      3      5     10
# worst-case PoA:               1.005  1.075  1.300  1.607  1.977  2.125  2.149

闭式解与细网格搜索给出相同的数值:d=1d = 1 时 4/3,d=2d = 2 时 1.626,d=4d = 4 时 2.151,d=16d = 16 时 4.727。PoA(d)\mathrm{PoA}(d) 与 d/ln⁡dd/\ln d 之比从 d=4d = 4 时的 0.75 缓慢升到 d=1024d = 1024 时的 0.88,这就是「按 Θ(d/ln⁡d)\Theta(d/\ln d) 增长」的含义:增长的速度与 d/ln⁡dd/\ln d 相同,但两者并不相等。

交通规划中最常用的延迟函数是美国公路局 1964 年手册中的形式 t=t0[1+0.15(x/C)4]t = t_0[1 + 0.15\,(x/C)^4],CC 是通行能力 (Bureau of Public Roads 1964)。它是四次多项式,所以 2.151 是它的上界。但程序的最后两行显示,要接近这个上界,需求必须远远超过通行能力:需求等于通行能力时,最坏的庇古网络的 PoA 只有 1.075;需求是通行能力的 2 倍时为 1.607;10 倍时才达到 2.149。原因是 BPR 函数的常数项 t0t_0 在中等负荷下占主导,拥堵项要到严重超载时才压过它。

左:多项式延迟下无秩序代价的上界(蓝线)与 d/\ln d(虚线)。右:BPR 型道路在最坏的庇古网络中的无秩序代价随「需求 / 通行能力」的变化,严重超载时才接近上界 2.151。

随机网络上的检验

上界说的是最坏情形。一个自然的问题是:在「一般的」网络中,PoA 有多大?

推导

程序随机生成有 7 个节点、一对起终点的无环网络,每段路的延迟为 b+axdb + a x^d,aa、bb 在 0 与 1 之间均匀随机,需求从 0.5、1、2、4 中随机选取。对 d=1d = 1 与 d=4d = 4 各生成 150 个网络,计算用户均衡与系统最优,检查 4/3 与 2.151 的上界与「两倍流量」的结论;最后取一个四次延迟的网络,看 PoA 怎样随需求变化。

推导

# Numerical check of the price-of-anarchy bounds on random networks (Roughgarden &
# Tardos 2002; Roughgarden 2003). Random acyclic networks with 7 nodes, one
# origin-destination pair and latencies c(x) = b + a x^d with random a, b >= 0. UE and
# SO by path equilibration.
import random
rng = random.Random(4)

def lat(e, x, m):                    # m = True gives the marginal cost (for the optimum)
    a, b, d = e
    return b + (d + 1 if m else 1) * a * x ** d

def solve(net, paths, demand, m=False, tol=1e-10):
    f = [0.0] * len(paths); f[0] = demand
    load = {k: 0.0 for k in net}
    for k in paths[0]: load[k] += demand
    pc = lambda p, L: sum(lat(net[k], L[k], m) for k in p)
    for _ in range(20000):
        c = [pc(p, load) for p in paths]
        used = [i for i in range(len(paths)) if f[i] > 1e-14]
        hi = max(used, key=lambda i: c[i])
        lo = min(range(len(paths)), key=lambda i: c[i])
        if c[hi] - c[lo] < tol: break
        H, Lo = set(paths[hi]), set(paths[lo])
        def gap(s):
            L = dict(load)
            for k in H - Lo: L[k] -= s
            for k in Lo - H: L[k] += s
            return pc(paths[hi], L) - pc(paths[lo], L)
        s, t = 0.0, f[hi]
        if gap(t) > 0: s = t
        else:
            for _ in range(50):
                mid = (s + t) / 2
                if gap(mid) > 0: s = mid
                else: t = mid
        f[hi] -= s; f[lo] += s
        for k in H - Lo: load[k] -= s
        for k in Lo - H: load[k] += s
    return f, load

def cost(net, load):
    return sum(x * lat(net[k], x, False) for k, x in load.items())

def random_net(d, n=7):
    net = {}
    for i in range(n - 1):
        net[(i, i + 1)] = (rng.random(), rng.random(), d)        # keeps a path s -> t
        for j in range(i + 2, n):
            if rng.random() < 0.35: net[(i, j)] = (rng.random(), rng.random(), d)
    out = {}
    for (i, j) in net: out.setdefault(i, []).append(j)
    paths, stack = [], [(0, [])]
    while stack:
        v, p = stack.pop()
        if v == n - 1: paths.append(tuple(p)); continue
        for w in out.get(v, []): stack.append((w, p + [(v, w)]))
    return net, paths

def poa(net, paths, r):
    _, lu = solve(net, paths, r); _, lo = solve(net, paths, r, True)
    return cost(net, lu) / cost(net, lo), cost(net, lu), lo

for d, bound in ((1, 4 / 3), (4, 2.1505)):
    ratios, aug = [], 0
    for _ in range(150):
        net, paths = random_net(d)
        r = rng.choice((0.5, 1, 2, 4))
        q, cu, _ = poa(net, paths, r); ratios.append(q)
        _, lo2 = solve(net, paths, 2 * r, True)
        aug += cu <= cost(net, lo2) + 1e-9
    ratios.sort()
    print(f"degree {d}: 150 random networks, PoA median {ratios[75]:.3f}, "
          f"90th percentile {ratios[134]:.3f},\n   max {ratios[-1]:.3f} "
          f"(bound {bound:.3f}); above 1.05 in {sum(q > 1.05 for q in ratios)} networks")
    print(f"   UE cost at demand r <= optimal cost at demand 2r in {aug} of 150 networks")
rng.seed(7)
net, paths = random_net(4)
print(f"one random degree-4 network ({len(paths)} paths), PoA as demand grows:")
DEM = (0.1, 0.5, 1, 2, 4, 8, 16, 64)
print("   demand  " + "  ".join(f"{r:>5}" for r in DEM))
print("   PoA     " + "  ".join(f"{poa(net, paths, r)[0]:5.3f}" for r in DEM))
# degree 1: 150 random networks, PoA median 1.013, 90th percentile 1.048,
#    max 1.095 (bound 1.333); above 1.05 in 14 networks
#    UE cost at demand r <= optimal cost at demand 2r in 150 of 150 networks
# degree 4: 150 random networks, PoA median 1.028, 90th percentile 1.231,
#    max 1.595 (bound 2.151); above 1.05 in 59 networks
#    UE cost at demand r <= optimal cost at demand 2r in 150 of 150 networks
# one random degree-4 network (15 paths), PoA as demand grows:
#    demand    0.1    0.5      1      2      4      8     16     64
#    PoA     1.000  1.000  1.062  1.055  1.201  1.008  1.000  1.000

线性延迟的 150 个网络中,PoA 的中位数只有 1.013,90% 分位数 1.048,最大 1.095,远低于 4/3;只有 14 个网络的损失超过 5%。四次延迟时损失大一些:中位数 1.028,90% 分位数 1.231,最大 1.595,仍低于 2.151;150 个网络中有 59 个超过 5%。两种情形下,「自私地运送需求 rr」的总成本都不超过「最优地运送 2r2r」,150 个网络无一例外。最后一个网络显示了 PoA 对需求的依赖:需求很小(0.1、0.5)时没有损失,因为大家都走同一条最快的路而它还没拥堵;需求为 4 时损失最大,约 20%;需求达到 16 与 64 时又回到 1.000,因为所有路线都严重拥堵,自私与最优的分配趋于一致。

证据

PoA 随需求先升后降。 尹、加斯特纳与郑 2008 年在模型网络中发现,PoA 在低流量时为 1,随流量增加急剧上升,达到峰值后在高流量时回落到 1;在真实路网中,PoA 随总流量有多个局部峰值 (Youn et al. 2008)。奥黑尔、康纳斯与沃特林 2016 年系统分析了决定 PoA 随出行需求变化的机制,指出理解这种变化有助于判断在什么时候值得采取提高路网效率的干预 (O’Hare et al. 2016)。

注

上界的适用范围。 第一,4/3 只对非原子用户成立:每个人只占流量的无穷小一份。如果参与者是有限的几个人、各人流量相同,每人选一条不可拆分的路线,线性延迟下纯策略均衡的最坏 PoA 是 5/2(两组作者 2005 年分别证明)(Awerbuch et al. 2005; Christodoulou and Koutsoupias 2005)。第八章的实验每组只有 6 人,这一区别很重要。第二,上界只比较总通行时间,不涉及公平:一个总时间接近最优的分配,可能让少数人承担很长的延迟。第三,模型假设每个人对路况有完全的信息并且完全理性;真实司机的信息与习惯都会改变结果。所以「PoA 不超过 4/3」不能读作「现实中的拥堵损失不超过三分之一」,更不能反过来读作「现实中的损失一定接近三分之一」。

假说 · 尚未验证

中等负荷假说(尚未确立)。作者推测,团队中的自发任务分配(每个人自己选择找谁审批、走哪条流程)的效率损失,在中等工作量时最大,在很闲与极忙时都较小,与路由博弈中 PoA 的形状相似。可以检验的预测是:在记录了每周请求量与平均处理时间的多个团队中,「自发分配」与「集中调度」两种方式的处理时间之差,在请求量的中段最大。如果差异随请求量单调增加或单调减少,这一假说就被推翻。

本章小结

无秩序代价是最坏的自私均衡与最优之比。在线性延迟、非原子用户的网络中,它不超过 4/3,而且最坏情形就是庇古的两条路网络,与拓扑无关;dd 次多项式延迟下上界为 [1−d(d+1)−(d+1)/d]−1[1 – d(d+1)^{-(d+1)/d}]^{-1},d=4d = 4 时为 2.151,按 Θ(d/ln⁡d)\Theta(d/\ln d) 增长。随机网络中的 PoA 通常远低于上界,并随需求先升后降;BPR 型道路只有在严重超载时才接近最坏情形。上界不适用于有限人数的博弈,后者的最坏情形是 5/2。下一章问:能不能用价格消除这部分损失?

参考文献

Awerbuch, Baruch, Yossi Azar, and Amir Epstein. 2005. “The Price of Routing Unsplittable Flow.” Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC ’05) (New York), 57–66. https://doi.org/10.1145/1060590.1060599.
Bureau of Public Roads. 1964. Traffic Assignment Manual. U.S. Department of Commerce, Urban Planning Division.
Christodoulou, George, and Elias Koutsoupias. 2005. “The Price of Anarchy of Finite Congestion Games.” Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC ’05) (New York), 67–73. https://doi.org/10.1145/1060590.1060600.
Koutsoupias, Elias, and Christos Papadimitriou. 1999. “Worst-Case Equilibria.” STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science (Berlin), Lecture notes in computer science, vol. 1563: 404–13.
O’Hare, Steven J., Richard D. Connors, and David P. Watling. 2016. “Mechanisms That Govern How the Price of Anarchy Varies with Travel Demand.” Transportation Research Part B: Methodological 84: 55–80. https://doi.org/10.1016/j.trb.2015.12.005.
Papadimitriou, Christos. 2001. “Algorithms, Games, and the Internet.” Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC ’01) (New York), 749–53. https://doi.org/10.1145/380752.380883.
Pigou, Arthur C. 1920. The Economics of Welfare. Macmillan.
Roughgarden, Tim. 2003. “The Price of Anarchy Is Independent of the Network Topology.” Journal of Computer and System Sciences 67 (2): 341–64. https://doi.org/10.1016/S0022-0000(03)00044-8.
Roughgarden, Tim, and Éva Tardos. 2002. “How Bad Is Selfish Routing?” Journal of the ACM 49 (2): 236–59. https://doi.org/10.1145/506147.506153.
Youn, Hyejin, Michael T. Gastner, and Hawoong Jeong. 2008. “Price of Anarchy in Transportation Networks: Efficiency and Optimality Control.” Physical Review Letters 101 (12): 128701. https://doi.org/10.1103/PhysRevLett.101.128701.

Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: From Wardrop Equilibria and Selfish Routing to Platform Congestion, Read Beside Classical Chinese Hydraulic Engineering [算法博弈论、布雷斯悖论与流量分配的无秩序代价] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).