关于「无秩序代价:自私最多让我们损失多少」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?

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

数据口径:书中关于流量池与推荐算法的模型都是示意,不描述任何真实平台;本书不是投资、经营或营销建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序,全部核对)、原典与作者的假说。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 2.151

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

核心公式

\[\mathrm{PoA} = \frac{\text{最坏的自私均衡的总成本}}{\text{最优的总成本}} \ge 1\]
查看完整验算程序
# 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))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第 2 章「无秩序代价:自私最多让我们损失多少」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094

DOI: 10.5281/zenodo.23782094 · 阅读本章所在专著 · 5DL-B-032 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026032,
  author    = {Fan, Yafu},
  title     = {Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  doi       = {10.5281/zenodo.23782094},
  url       = {https://doi.org/10.5281/zenodo.23782094}
}

本书其他章节结论