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

第一章 布雷斯悖论:多修一条路,所有人更慢

一个不需要事故的拥堵

通常我们以为,拥堵是因为路不够:多修一条路,至少不会更坏。布雷斯 1968 年的论文给出了一个反例 (Braess 1968)。他考虑的是一个道路网络,每个出发点有已知数量的车辆要去已知的目的地,每段路的通行时间随车流量增加;每位司机都选择对自己最快的路线。在这样的设定下,他证明了「每个人都选对自己最好的路线」与「总通行时间最短」并不是一回事,并给出一个例子:在网络中增加一条路,交通重新分布之后,每个人的通行时间都变长了 (Braess et al. 2005)。

这个结论的关键不在于新路本身,而在于选择的外部性:一个人选了某条路,就给这条路上的所有人增加了一点延迟,而他在做决定时并不计入这部分。本章先把「每个人都选最快的路」写成精确的均衡条件,然后在布雷斯的菱形网络上把悖论完整算出来,最后看同一组方程怎样描述弹簧与电路。

瓦德罗普的两条原则

证据

瓦德罗普原则。 英国道路研究实验室的瓦德罗普在 1952 年的论文中提出了交通分配的两条原则:第一,实际被使用的各条路线的通行时间相等,并且不长于任何一条未被使用的路线;第二,平均通行时间最短 (Wardrop 1952)。前者后来被称为用户均衡(user equilibrium,UE),后者被称为系统最优(system optimum,SO)。贝克曼、麦圭尔与温斯滕 1956 年证明,在每段路的延迟只取决于该段流量的条件下,用户均衡等价于一个凸优化问题的解,从而存在;当延迟随流量严格增加时,各段路的流量是唯一的 (Beckmann et al. 1956)。

推导

设网络中有若干条从起点到终点的路线 pp,路线流量为 fpf_p,总需求为 d=∑pfpd = \sum_p f_p。路段 ee 上的流量 xe=∑p∋efpx_e = \sum_{p \ni e} f_p,延迟为 ce(xe)c_e(x_e),路线的通行时间 Cp=∑e∈pce(xe)C_p = \sum_{e \in p} c_e(x_e)。

用户均衡: 若 fp>0f_p > 0,则 Cp=min⁡qCqC_p = \min_q C_q。也就是说,没有人能通过换路变得更快。这里的「人」是非原子的:每个人只占流量的无穷小一份,他换路不会改变任何一段路的延迟。

系统最优: 使总成本 ∑exece(xe)\sum_e x_e c_e(x_e) 最小。对 xex_e 求导可知,最优流量满足同样形式的条件,只是把延迟 ce(x)c_e(x) 换成边际成本 ce(x)+xce′(x)c_e(x) + x\,c_e'(x):多一个人走这段路,除了他自己承受的 cec_e,还让已经在路上的 xx 个人每人慢了 ce′(x)c_e'(x)。

两种条件的差别就是 xce′(x)x\,c_e'(x) 这一项。自私的用户只看前一项,社会成本还包括后一项。

本书的程序用「路线均衡法」求解:反复找出被使用的路线中最慢的一条与所有路线中最快的一条,在两者之间转移流量,直到它们的通行时间相等。求系统最优时,用边际成本代替延迟。

菱形网络

推导

四个节点:起点 ss、终点 tt 与中间的 vv、ww。路段 s→vs \to v 与 w→tw \to t 的延迟等于流量 xx(随拥堵增加),路段 v→tv \to t 与 s→ws \to w 的延迟恒为 1(宽阔但较远)。两条路线 s→v→ts \to v \to t 与 s→w→ts \to w \to t 各包含一段延迟为 xx 的路与一段延迟为 1 的路。总需求为 1。然后在 vv 与 ww 之间修一条延迟为 0 的捷径,形成第三条路线 s→v→w→ts \to v \to w \to t。程序求有无捷径时的用户均衡与系统最优,检查捷径是否占优,并改变需求与网络参数。

推导

# 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

没有捷径时,两条路线各走一半,每段 xx 路的延迟是 0.5,通行时间 0.5+1=1.50.5 + 1 = 1.5。修了捷径之后,用户均衡是全部流量走 s→v→w→ts \to v \to w \to t,两段 xx 路都满载,通行时间 1+0+1=21 + 0 + 1 = 2。每个人都比以前慢了三分之一,而系统最优仍然是不走捷径、各走一半,平均 1.5。

为什么没有人愿意离开捷径?捷径路线的时间是 xsv+xwtx_{sv} + x_{wt},另外两条是 xsv+1x_{sv} + 1 与 1+xwt1 + x_{wt}。由于每段流量都不超过 1,捷径从不比另外两条慢。程序在 441 种流量组合上检查了这一点:捷径在全部组合中都不更慢,在其中 400 种中严格更快,只在某段 xx 路满载(xsv=1x_{sv} = 1 或 xwt=1x_{wt} = 1)时打平。所以走捷径是每个人的弱占优策略,而所有人都走捷径的结果,恰好落在打平的那一点上:三条路线都是 2。

注

两处修正。 作者框架中说「两路各有延迟函数 tA(x)=xt_A(x) = x 与 tB(x)=1t_B(x) = 1」,准确的说法是每条路线由一段 xx 路与一段常数路交叉组成;如果一条路线全是 xx、另一条全是 1,那是第二章的庇古网络,加捷径无从谈起。框架中说走捷径是「严格占优策略」,准确地说是弱占优:它从不更差,但在均衡处与其他路线一样。这个「xx 与 1」的版本是教科书中的简化形式;布雷斯 1968 年原文的数值例子是需求为 6、延迟函数为 10x10x、x+50x + 50 与新路 x+10x + 10,加路后通行时间从 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 以后,两段 xx 路本身已经比常数路慢,捷径无人使用,悖论消失。较大的例子也一样:加路只在需求介于约 2.58 与 8.89 之间时有害。纳格尼 2010 年专门讨论了「需求增加时布雷斯悖论的消失」,算出这个例子中需求增加到 8898\frac{8}{9} 时新路不再被使用 (Nagurney 2010)。

左:布雷斯网络,虚线为延迟为 0 的捷径。右:平均通行时间随需求的变化。需求在 2/3 与 2 之间时(灰色区域),有捷径时的自私均衡(紫线)比没有捷径时(绿线)更慢;系统最优(金色虚线)从不比没有捷径时更差。

在真实路网中

证据

真实路网中的模型估计。 尹、加斯特纳与郑 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)。

交通网络 弹簧—绳子网络 电路
流量 张力 电流
延迟 ce=be+aexc_e = b_e + a_e x 长度 = 绳长 + 张力 / 劲度系数 压降 = 齐纳电压 + 电流 × 电阻
随流量增加的路段(ae>0a_e > 0) 弹簧 电阻
固定延迟的路段(beb_e) 不可伸长的绳子 齐纳二极管
未被使用的路线 松弛的绳子 未导通的二极管
共同的通行时间 支架到重物的距离 两端电压

推导

# 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 米,与他们报告的数值一致。

这种同构不是巧合。在交通网络中,用户均衡使贝克曼势函数 ∑e∫0xece(u)du\sum_e \int_0^{x_e} c_e(u)\,\mathrm{d}u 最小 (Beckmann et al. 1956);程序正是用「在 20,301 种分配中找势函数最小者」来求均衡的:最小值 1.0000 出现在全走捷径处,此时总成本是 2.00;总成本只有 1.50 的平分方案,势函数却是 1.2500。在弹簧与绳子构成的结构中,给定重量下的平衡使「余能」最小;在由电阻与理想二极管组成的电路中,基尔霍夫定律决定的电流分布使电路的「含量」(content,即各元件压降对电流的积分之和)最小。三者最小化的都是同一个量,而不是总成本:物理系统和自私的司机一样,只服从局部的平衡条件。

注

电网中的布雷斯现象是另一回事。 维特豪特与蒂姆 2012 年在交流电网的振子模型中发现,在负载已经很重的区域增加一条输电线,可能使发电机与负荷失去同步、导致停电;他们称之为振子网络中的布雷斯悖论,原因是新线路给相位关系增加了一个无法同时满足的约束 (Witthaut and Timme 2012)。交流电网中的潮流由相位差决定,机制与本章的同构不同;作者框架把电网与交通网、弹簧网络并列为「同构」,本书只对弹簧与直流电路写同构,对电网写为相关现象。

假说 · 尚未验证

快速通道假说(尚未确立)。作者推测,组织中对所有请求开放的「快速通道」常常具有布雷斯网络的结构:它使原本分别处理两类事务的少数关键人成为所有事务的必经之路。可以检验的预测是:引入这种快速通道之后,全部请求的平均处理时间上升。如果在事先登记的阶梯式引入研究中,平均处理时间没有上升,这一假说就被推翻。第八章核查表第一步给出一个虚构的示例。

本章小结

用户均衡要求被使用的路线一样快,系统最优要求总成本最低,两者相差每个人给别人增加的边际延迟。在布雷斯网络中,对每个人都弱占优的零延迟捷径使通行时间从 1.5 增至 2.0,而最优根本不用它;悖论只在一段需求范围内出现。同一组条件也描述弹簧—绳子网络与直流电路。下一章问:自私最多比最优差多少?

参考文献

Beckmann, Martin J., C. B. McGuire, and Christopher B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press.
Braess, Dietrich. 1968. “Über Ein Paradoxon Aus Der Verkehrsplanung.” Unternehmensforschung 12: 258–68. https://doi.org/10.1007/BF01918335.
Braess, Dietrich, Anna Nagurney, and Tina Wakolbinger. 2005. “On a Paradox of Traffic Planning.” Transportation Science 39 (4): 446–50. https://doi.org/10.1287/trsc.1050.0127.
Cohen, Joel E., and Paul Horowitz. 1991. “Paradoxical Behaviour of Mechanical and Electrical Networks.” Nature 352: 699–701. https://doi.org/10.1038/352699a0.
Nagurney, Anna. 2010. “The Negation of the Braess Paradox as Demand Increases: The Wisdom of Crowds in Transportation Networks.” EPL (Europhysics Letters) 91 (4): 48002. https://doi.org/10.1209/0295-5075/91/48002.
Rapoport, Amnon, Tamar Kugler, Subhasish Dugar, and Eyran J. Gisches. 2009. “Choice of Routes in Congested Traffic Networks: Experimental Tests of the Braess Paradox.” Games and Economic Behavior 65 (2): 538–71. https://doi.org/10.1016/j.geb.2008.02.007.
Wardrop, John Glen. 1952. “Some Theoretical Aspects of Road Traffic Research.” Proceedings of the Institution of Civil Engineers 1 (3): 325–62. https://doi.org/10.1680/ipeds.1952.11259.
Witthaut, Dirk, and Marc Timme. 2012. “Braess’s Paradox in Oscillator Networks, Desynchronization and Power Outage.” New Journal of Physics 14: 083036. https://doi.org/10.1088/1367-2630/14/8/083036.
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).