关于「布雷斯悖论:多修一条路,所有人更慢」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?

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

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

English version

对照数据表

下表数字由本章 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_sv1 or x_wt = 1)
demand no shortcut shortcut (UE) shortcut (SO)
0.5001.250 1.000 1.000
0.6671.333 1.333 1.250
1.0001.500 2.000 1.500
1.5001.750 2.000 1.750
2.0002.000 2.000 2.000
2.5002.250 2.250 2.250
classic example, demand 683.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}
}

本书其他章节结论