5D Library › 算法博弈论、布雷斯悖论与流量分配的无秩序代价 · English
第一章 布雷斯悖论:多修一条路,所有人更慢
一个不需要事故的拥堵
通常我们以为,拥堵是因为路不够:多修一条路,至少不会更坏。布雷斯 1968 年的论文给出了一个反例 (Braess 1968)。他考虑的是一个道路网络,每个出发点有已知数量的车辆要去已知的目的地,每段路的通行时间随车流量增加;每位司机都选择对自己最快的路线。在这样的设定下,他证明了「每个人都选对自己最好的路线」与「总通行时间最短」并不是一回事,并给出一个例子:在网络中增加一条路,交通重新分布之后,每个人的通行时间都变长了 (Braess et al. 2005)。
这个结论的关键不在于新路本身,而在于选择的外部性:一个人选了某条路,就给这条路上的所有人增加了一点延迟,而他在做决定时并不计入这部分。本章先把「每个人都选最快的路」写成精确的均衡条件,然后在布雷斯的菱形网络上把悖论完整算出来,最后看同一组方程怎样描述弹簧与电路。
瓦德罗普的两条原则
证据
瓦德罗普原则。 英国道路研究实验室的瓦德罗普在 1952 年的论文中提出了交通分配的两条原则:第一,实际被使用的各条路线的通行时间相等,并且不长于任何一条未被使用的路线;第二,平均通行时间最短 (Wardrop 1952)。前者后来被称为用户均衡(user equilibrium,UE),后者被称为系统最优(system optimum,SO)。贝克曼、麦圭尔与温斯滕 1956 年证明,在每段路的延迟只取决于该段流量的条件下,用户均衡等价于一个凸优化问题的解,从而存在;当延迟随流量严格增加时,各段路的流量是唯一的 (Beckmann et al. 1956)。
推导
设网络中有若干条从起点到终点的路线 ,路线流量为 ,总需求为 。路段 上的流量 ,延迟为 ,路线的通行时间 。
用户均衡: 若 ,则 。也就是说,没有人能通过换路变得更快。这里的「人」是非原子的:每个人只占流量的无穷小一份,他换路不会改变任何一段路的延迟。
系统最优: 使总成本 最小。对 求导可知,最优流量满足同样形式的条件,只是把延迟 换成边际成本 :多一个人走这段路,除了他自己承受的 ,还让已经在路上的 个人每人慢了 。
两种条件的差别就是 这一项。自私的用户只看前一项,社会成本还包括后一项。
本书的程序用「路线均衡法」求解:反复找出被使用的路线中最慢的一条与所有路线中最快的一条,在两者之间转移流量,直到它们的通行时间相等。求系统最优时,用边际成本代替延迟。
菱形网络
推导
四个节点:起点 、终点 与中间的 、。路段 与 的延迟等于流量 (随拥堵增加),路段 与 的延迟恒为 1(宽阔但较远)。两条路线 与 各包含一段延迟为 的路与一段延迟为 1 的路。总需求为 1。然后在 与 之间修一条延迟为 0 的捷径,形成第三条路线 。程序求有无捷径时的用户均衡与系统最优,检查捷径是否占优,并改变需求与网络参数。
推导
# 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}")
# 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没有捷径时,两条路线各走一半,每段 路的延迟是 0.5,通行时间 。修了捷径之后,用户均衡是全部流量走 ,两段 路都满载,通行时间 。每个人都比以前慢了三分之一,而系统最优仍然是不走捷径、各走一半,平均 1.5。
为什么没有人愿意离开捷径?捷径路线的时间是 ,另外两条是 与 。由于每段流量都不超过 1,捷径从不比另外两条慢。程序在 441 种流量组合上检查了这一点:捷径在全部组合中都不更慢,在其中 400 种中严格更快,只在某段 路满载( 或 )时打平。所以走捷径是每个人的弱占优策略,而所有人都走捷径的结果,恰好落在打平的那一点上:三条路线都是 2。
注
两处修正。 作者框架中说「两路各有延迟函数 与 」,准确的说法是每条路线由一段 路与一段常数路交叉组成;如果一条路线全是 、另一条全是 1,那是第二章的庇古网络,加捷径无从谈起。框架中说走捷径是「严格占优策略」,准确地说是弱占优:它从不更差,但在均衡处与其他路线一样。这个「 与 1」的版本是教科书中的简化形式;布雷斯 1968 年原文的数值例子是需求为 6、延迟函数为 、 与新路 ,加路后通行时间从 83 增至 92 (Braess et al. 2005),这也是介绍布雷斯悖论时最常转引的例子 (Nagurney 2010)。程序最后一部分复现了这个例子。
悖论并不是在所有需求下都出现。表中可以看到,需求只有 0.5 时,捷径让所有人从 1.25 降到 1.0;需求为 2/3 时两者打平;需求在 2/3 与 2 之间时,捷径使均衡变坏(需求为 1 时最坏,2.0 对 1.5);需求达到 2 以后,两段 路本身已经比常数路慢,捷径无人使用,悖论消失。较大的例子也一样:加路只在需求介于约 2.58 与 8.89 之间时有害。纳格尼 2010 年专门讨论了「需求增加时布雷斯悖论的消失」,算出这个例子中需求增加到 时新路不再被使用 (Nagurney 2010)。
在真实路网中
证据
真实路网中的模型估计。 尹、加斯特纳与郑 2008 年用波士顿、伦敦与纽约的真实街道网络(217 到 319 条路段)和标准的拥堵函数计算了用户均衡与系统最优。波士顿的无秩序代价(第二章)在每小时 1 万辆车时最高,约为 1.30;伦敦约高 24%,纽约在每小时 1.2 万辆车时约高 28%。他们还找出了一些「布雷斯路段」:在模型中关闭它们会降低均衡通行时间,在波士顿与伦敦的计算中各有 6 条与 7 条,在纽约有 12 条 (Youn et al. 2008)。
这些都是模型中的结论:路网是真实的,但需求与延迟函数是假设的,司机被假设为完全理性、信息充分。「拆掉一条路后交通反而变好」的城市轶事常被引用,作者没有找到系统的前后对照数据,不把它们当作证据。第八章讨论的实验室证据更直接:在受控的路线选择实验中,参与者在加了捷径的网络中确实收敛到较差的均衡 (Rapoport et al. 2009)。
弹簧、绳子与电路
证据
机械与电路中的悖论。 科恩与霍洛维茨 1991 年在《自然》上描述了一个机械版本:一根弹簧挂在支架上,下端用一段短绳连着第二根弹簧,第二根弹簧挂着重物;另有两根较长的「安全绳」,一根从支架连到第二根弹簧的上端,一根从第一根弹簧的下端连到重物,平时松弛。剪断中间的短绳之后,两根弹簧从串联变为各自经一根安全绳的并联,每根只承受一半的重量、伸长减少,重物反而升高。他们给出的数值是支架到重物的距离从约 1.5 米缩短到约 1.25 米。他们还给出电路版本:电阻对应弹簧,齐纳二极管对应不可伸长的绳子,在电路中加一条支路反而使总压降升高;并指出这些物理悖论与布雷斯的交通悖论密切相关 (Cohen and Horowitz 1991)。
| 交通网络 | 弹簧—绳子网络 | 电路 |
|---|---|---|
| 流量 | 张力 | 电流 |
| 延迟 | 长度 = 绳长 + 张力 / 劲度系数 | 压降 = 齐纳电压 + 电流 × 电阻 |
| 随流量增加的路段() | 弹簧 | 电阻 |
| 固定延迟的路段() | 不可伸长的绳子 | 齐纳二极管 |
| 未被使用的路线 | 松弛的绳子 | 未导通的二极管 |
| 共同的通行时间 | 支架到重物的距离 | 两端电压 |
推导
# One equilibrium problem, three physical readings (after Cohen and Horowitz 1991).
# Element "cost" = b + a x: traffic (time = free time + congestion), spring + string
# (length = string length + force / k), resistor + Zener diode (voltage = Zener voltage
# + I R). Flow = traffic, force or current. The equilibrium is found by minimising
# Beckmann's potential (sum over elements of the integral of cost) on a fine grid of
# splits: for springs this is the complementary energy, for circuits the content. A path
# whose cost exceeds the common value carries no flow (an unused road, a slack string, a
# diode that does not conduct).
def braess(flex, fixed, link):
"""Two load-dependent elements (a = flex), two fixed ones (b = fixed), middle link."""
return {"s1": (flex, 0), "f1": (0, fixed), "f2": (0, fixed), "s2": (flex, 0),
"m": (0, link)}
PATHS = [("s1", "f1"), ("f2", "s2"), ("s1", "m", "s2")]
def evaluate(net, f):
x = {k: sum(q for p, q in zip(PATHS, f) if k in p) for k in net}
phi = sum(b * x[k] + a * x[k] ** 2 / 2 for k, (a, b) in net.items())
cost = [sum(net[k][1] + net[k][0] * x[k] for k in p) for p in PATHS]
return phi, cost
def equilibrium(net, load, link=True, n=200):
splits = [(load * i / n, load * j / n, load * (n - i - j) / n)
for i in range(n + 1) for j in range(n + 1 - i) if link or i + j == n]
f = min(splits, key=lambda s: evaluate(net, s)[0])
phi, cost = evaluate(net, f)
return f, max(c for c, q in zip(cost, f) if q > 1e-12), phi
CASES = [("traffic: time x, time 1, shortcut 0, demand 1", 1, 1, 0, 1, "units"),
("springs k=1 N/m, safety strings 1 m, link string 0 m, weight 1 N",
1, 1, 0, 1, "m"),
("Cohen-Horowitz numbers: link string 0.5 m, weight 0.5 N", 1, 1, 0.5, 0.5, "m"),
("circuit: 1 ohm, 1 V Zener diodes, bridging wire, 1 A", 1, 1, 0, 1, "V")]
for lab, a, b, link, load, unit in CASES:
net = braess(a, b, link)
f3, with_link, phi = equilibrium(net, load)
f2, without, _ = equilibrium(net, load, link=False)
print(f"{lab}\n with the middle link {with_link:.2f} {unit} (flows "
+ " ".join(f"{q:.2f}" for q in f3) + f"); without it {without:.2f} {unit}")
net = braess(1, 1, 0)
f, _, phi = equilibrium(net, 1)
total = sum(q * c for q, c in zip(f, evaluate(net, f)[1]))
print(f"at the equilibrium: potential {phi:.4f} (its minimum over 20,301 splits),"
f" total cost {total:.2f};\n the split 0.5/0.5/0 has potential "
f"{evaluate(net, (0.5, 0.5, 0))[0]:.4f} but total cost 1.50")
# traffic: time x, time 1, shortcut 0, demand 1
# with the middle link 2.00 units (flows 0.00 0.00 1.00); without it 1.50 units
# springs k=1 N/m, safety strings 1 m, link string 0 m, weight 1 N
# with the middle link 2.00 m (flows 0.00 0.00 1.00); without it 1.50 m
# Cohen-Horowitz numbers: link string 0.5 m, weight 0.5 N
# with the middle link 1.50 m (flows 0.00 0.00 0.50); without it 1.25 m
# circuit: 1 ohm, 1 V Zener diodes, bridging wire, 1 A
# with the middle link 2.00 V (flows 0.00 0.00 1.00); without it 1.50 V
# at the equilibrium: potential 1.0000 (its minimum over 20,301 splits), total cost 2.00;
# the split 0.5/0.5/0 has potential 1.2500 but total cost 1.50同一个求解器给出了三个系统的结果。单位参数下(重量 1 牛、劲度系数 1 牛/米、安全绳 1 米、中间绳长 0),有中间短绳时距离为 2 米,剪断后为 1.5 米,与交通网络的 2 与 1.5 完全相同;电路中有桥接导线时压降 2 伏,去掉后 1.5 伏。若用科恩与霍洛维茨的数值(中间绳长 0.5 米、重量 0.5 牛),距离从 1.5 米变为 1.25 米,与他们报告的数值一致。
这种同构不是巧合。在交通网络中,用户均衡使贝克曼势函数 最小 (Beckmann et al. 1956);程序正是用「在 20,301 种分配中找势函数最小者」来求均衡的:最小值 1.0000 出现在全走捷径处,此时总成本是 2.00;总成本只有 1.50 的平分方案,势函数却是 1.2500。在弹簧与绳子构成的结构中,给定重量下的平衡使「余能」最小;在由电阻与理想二极管组成的电路中,基尔霍夫定律决定的电流分布使电路的「含量」(content,即各元件压降对电流的积分之和)最小。三者最小化的都是同一个量,而不是总成本:物理系统和自私的司机一样,只服从局部的平衡条件。
注
电网中的布雷斯现象是另一回事。 维特豪特与蒂姆 2012 年在交流电网的振子模型中发现,在负载已经很重的区域增加一条输电线,可能使发电机与负荷失去同步、导致停电;他们称之为振子网络中的布雷斯悖论,原因是新线路给相位关系增加了一个无法同时满足的约束 (Witthaut and Timme 2012)。交流电网中的潮流由相位差决定,机制与本章的同构不同;作者框架把电网与交通网、弹簧网络并列为「同构」,本书只对弹簧与直流电路写同构,对电网写为相关现象。
假说 · 尚未验证
快速通道假说(尚未确立)。作者推测,组织中对所有请求开放的「快速通道」常常具有布雷斯网络的结构:它使原本分别处理两类事务的少数关键人成为所有事务的必经之路。可以检验的预测是:引入这种快速通道之后,全部请求的平均处理时间上升。如果在事先登记的阶梯式引入研究中,平均处理时间没有上升,这一假说就被推翻。第八章核查表第一步给出一个虚构的示例。
本章小结
用户均衡要求被使用的路线一样快,系统最优要求总成本最低,两者相差每个人给别人增加的边际延迟。在布雷斯网络中,对每个人都弱占优的零延迟捷径使通行时间从 1.5 增至 2.0,而最优根本不用它;悖论只在一段需求范围内出现。同一组条件也描述弹簧—绳子网络与直流电路。下一章问:自私最多比最优差多少?
参考文献
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).