关于「无秩序代价:自私最多让我们损失多少」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?
结论:无秩序代价是最坏的自私均衡与最优之比。在线性延迟、非原子用户的网络中,它不超过 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 段程序,全部核对)、原典与作者的假说。
对照数据表
下表数字由本章 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}
}