关于「庇古税与势博弈:给看不见的延迟定价」,《布雷斯悖论与无秩序代价》给出的定量结论是什么?

结论:在最优处按 \(x*c'(x*)\) 收费,自私均衡就与最优重合,但不退还收入时用户的「时间 + 费用」未必下降;斯德哥尔摩的拥堵费显示价格能显著改变出行。有限人数的拥堵博弈是势博弈,6 人布雷斯网络中的改进停在「全走桥、每人 120」;按外部性收取积分后,势函数变成总成本,全走桥不再是均衡。下一章把这一结构搬到注意力市场。

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

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 120

Nash equilibria: routes UL: U3 L3 Z0 (each pays 100); routes ULZ: U0 L0 Z6 (each pays 120)
with the bridge, lowest total time: U3 L3 Z0 = 600 (Nash: 720); atomic PoA = 1.20
1000 runs of random improvement: every switch lowered Phi by the mover's gain: True;
   end points {'U0 L0 Z6': 1000}; switches per run: mean 4.6, max 9
charging each user her externality (congestion points; 100 each when all
   six are on the bridge): Nash equilibria U3 L3 Z0; U3 L2 Z1; U2 L3 Z1; U2 L2 Z2
   their average times 100, 100, 100, 100; all-on-bridge still an equilibrium: False

核心公式

\[\tau_e = x_e^*\,c_e'(x_e^*)\]
查看完整验算程序
# Atomic (finite-player) Braess game as in the lab: 6 players each pick one route.
# Links s->v and w->t cost 10 per user, v->t and s->w cost 70, the bridge v->w costs 0.
# Rosenthal's potential Phi = sum_e sum_{k=1..n_e} c_e(k) falls by exactly the mover's
# gain at every unilateral switch, so improvement dynamics must stop at a Nash
# equilibrium (Rosenthal 1973; Monderer & Shapley 1996). Illustrative parameters.
import random, itertools
rng = random.Random(6)
N = 6
COST = {"sv": lambda n: 10 * n, "vt": lambda n: 70, "sw": lambda n: 70,
        "wt": lambda n: 10 * n, "vw": lambda n: 0}
ROUTES = {"U": ("sv", "vt"), "L": ("sw", "wt"), "Z": ("sv", "vw", "wt")}
loads = lambda p: {e: sum(e in ROUTES[r] for r in p) for e in COST}
# externality of one user on link e with n users: (n - 1)(c(n) - c(n - 1))
toll = lambda e, n: (n - 1) * (COST[e](n) - COST[e](n - 1)) if n > 0 else 0

def pcost(prof, i, tolls=False, route=None):
    p = list(prof); p[i] = route or p[i]; n = loads(p)
    return sum(COST[e](n[e]) + (toll(e, n[e]) if tolls else 0) for e in ROUTES[p[i]])

potential = lambda prof: sum(COST[e](k) for e, m in loads(prof).items()
                             for k in range(1, m + 1))

def nash(routes, tolls=False):
    return [c for c in itertools.combinations_with_replacement(routes, N)
            if all(pcost(c, i, tolls) <= min(pcost(c, i, tolls, r) for r in routes)
                   for i in range(N))]

show = lambda c: "U%d L%d Z%d" % tuple(c.count(r) for r in "ULZ")
total = lambda c: sum(pcost(c, i) for i in range(N))
print("Nash equilibria: " + "; ".join(f"routes {r}: " + ", ".join(
    f"{show(c)} (each pays {pcost(c, 0)})" for c in nash(r)) for r in ("UL", "ULZ")))
best = min(itertools.combinations_with_replacement("ULZ", N), key=total)
ne = nash("ULZ")[0]
print(f"with the bridge, lowest total time: {show(best)} = {total(best)} "
      f"(Nash: {total(ne)}); atomic PoA = {total(ne) / total(best):.2f}")
ends, exact, steps = {}, True, []
for _ in range(1000):
    prof, k = [rng.choice("ULZ") for _ in range(N)], 0
    while True:
        movers = [(i, r) for i in range(N) for r in "ULZ"
                  if pcost(prof, i, route=r) < pcost(prof, i)]
        if not movers: break
        i, r = rng.choice(movers)
        gain, before = pcost(prof, i) - pcost(prof, i, route=r), potential(prof)
        prof[i] = r; k += 1
        exact &= abs((before - potential(prof)) - gain) < 1e-9
    ends[show(prof)] = ends.get(show(prof), 0) + 1; steps.append(k)
print(f"1000 runs of random improvement: every switch lowered Phi by the mover's gain:"
      f" {exact};\n   end points {ends}; switches per run: mean {sum(steps) / 1000:.1f},"
      f" max {max(steps)}")
eq, z6 = nash("ULZ", tolls=True), sum(toll(e, 6) for e in ROUTES["Z"])
print(f"charging each user her externality (congestion points; {z6} each when all")
print("   six are on the bridge): Nash equilibria " + "; ".join(show(c) for c in eq))
print("   their average times " + ", ".join(f"{total(c) / N:.0f}" for c in eq)
      + f"; all-on-bridge still an equilibrium: {('Z',) * 6 in eq}")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《算法博弈论、布雷斯悖论与流量分配的无秩序代价》第 3 章「庇古税与势博弈:给看不见的延迟定价」(版本 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}
}

本书其他章节结论