关于「布雷斯悖论:多修一条路,所有人更慢」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?
结论:用户均衡要求被使用的路线一样快,系统最优要求总成本最低,两者相差每个人给别人增加的边际延迟。在布雷斯网络中,对每个人都弱占优的零延迟捷径使通行时间从 1.5 增至 2.0,而最优根本不用它;悖论只在一段需求范围内出现。同一组条件也描述弹簧—绳子网络与直流电路。下一章问:自私最多比最优差多少?
数据口径:书中关于流量池与推荐算法的模型都是示意,不描述任何真实平台;本书不是投资、经营或营销建议。 书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序,全部核对)、原典与作者的假说。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。
| no shortcut, UE path flows 0.500 0.500 average time 1.500 | |
| shortcut, UE path flows 0.000 0.000 1.000 average time 2.000 | |
| shortcut, SO path flows 0.500 0.500 0.000 average time 1.500 | |
| shortcut never worse in 441 of 441 load pairs; strictly better in 400 | |
| (ties only when x_sv | 1 or x_wt = 1) |
| demand no shortcut shortcut (UE) shortcut (SO) | |
| 0.500 | 1.250 1.000 1.000 |
| 0.667 | 1.333 1.333 1.250 |
| 1.000 | 1.500 2.000 1.500 |
| 1.500 | 1.750 2.000 1.750 |
| 2.000 | 2.000 2.000 2.000 |
| 2.500 | 2.250 2.250 2.250 |
| classic example, demand 6 | 83.0 -> 92.0 |
| the added link hurts for demand between 2.58 and 8.89 |
查看完整验算程序
# Wardrop user equilibrium (UE) versus system optimum (SO) on Braess networks.
# Path-based equilibration: repeatedly shift flow from the costliest used path to the
# cheapest path until their costs are equal. Edge latency c(x) = b + a x^d; for SO the
# "cost" is the marginal cost c(x) + x c'(x) = b + (d + 1) a x^d. Nonatomic users: each
# is an infinitesimal share of flow.
def lat(e, x, marginal=False):
a, b, d = e
return b + (d + 1 if marginal else 1) * a * x ** d
def path_costs(net, paths, f, marginal=False):
load = {k: 0.0 for k in net}
for p, q in zip(paths, f):
for k in p: load[k] += q
return [sum(lat(net[k], load[k], marginal) for k in p) for p in paths], load
def solve(net, paths, demand, marginal=False, iters=4000):
f = [demand / len(paths)] * len(paths)
for _ in range(iters):
c, _ = path_costs(net, paths, f, marginal)
used = [i for i in range(len(paths)) if f[i] > 1e-13]
hi, lo = max(used, key=lambda i: c[i]), min(range(len(paths)), key=lambda i: c[i])
if c[hi] - c[lo] < 1e-11: break
s, t = 0.0, f[hi] # bisection on the amount shifted
for _ in range(60):
m = (s + t) / 2; g = f[:]; g[hi] -= m; g[lo] += m
cc, _ = path_costs(net, paths, g, marginal)
if cc[hi] > cc[lo]: s = m
else: t = m
f[hi] -= s; f[lo] += s
return f
def total(net, paths, f):
c, _ = path_costs(net, paths, f)
return sum(q * x for q, x in zip(f, c))
# Simplified Braess network: s->v (x), v->t (1), s->w (1), w->t (x); shortcut v->w (0).
NET = {"sv": (1, 0, 1), "vt": (0, 1, 1), "sw": (0, 1, 1), "wt": (1, 0, 1),
"vw": (0, 0, 1)}
TWO = [("sv", "vt"), ("sw", "wt")]
THREE = TWO + [("sv", "vw", "wt")]
def avg_cost(net, paths, d, marginal=False):
return total(net, paths, solve(net, paths, d, marginal)) / d
if __name__ == "__main__":
for lab, ps, m in (("no shortcut, UE", TWO, False), ("shortcut, UE", THREE, False),
("shortcut, SO", THREE, True)):
f = solve(NET, ps, 1.0, m)
print(f"{lab:16s} path flows " + " ".join(f"{q:.3f}" for q in f)
+ f" average time {total(NET, ps, f):.3f}")
grid = [(u / 20, w / 20) for u in range(21) for w in range(21)] # loads x_sv, x_wt
adv = [min(1 + w, 1 + u) - (u + w) for u, w in grid] # best other route - shortcut
print(f"shortcut never worse in {sum(a >= 0 for a in adv)} of {len(adv)} load pairs; "
f"strictly better in {sum(a > 0 for a in adv)}"
"\n (ties only when x_sv = 1 or x_wt = 1)")
print("demand no shortcut shortcut (UE) shortcut (SO)")
for d in (0.5, 2 / 3, 1.0, 1.5, 2.0, 2.5):
a, b, c = (avg_cost(NET, TWO, d), avg_cost(NET, THREE, d),
avg_cost(NET, THREE, d, True))
print(f" {d:5.3f} {a:6.3f} {b:6.3f} {c:6.3f}")
# Braess's own 1968 example (10x, x + 50, new link x + 10): demand 6, time 83 -> 92.
BIG = {"a": (10, 0, 1), "b": (1, 50, 1), "c": (1, 50, 1), "d": (10, 0, 1),
"e": (1, 10, 1)}
P2, P3 = [("a", "c"), ("b", "d")], [("a", "c"), ("b", "d"), ("a", "e", "d")]
print(f"classic example, demand 6: {avg_cost(BIG, P2, 6):.1f} -> "
f"{avg_cost(BIG, P3, 6):.1f}")
hurt = lambda d: avg_cost(BIG, P3, d) - avg_cost(BIG, P2, d) > 1e-7
def edge(lo, hi): # bisection for where "hurt" switches
for _ in range(30):
m = (lo + hi) / 2
if hurt(m) == hurt(lo): lo = m
else: hi = m
return (lo + hi) / 2
print(f" the added link hurts for demand between {edge(1, 6):.2f} and "
f"{edge(6, 12):.2f}")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第 1 章「布雷斯悖论:多修一条路,所有人更慢」(版本 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}
}