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

第三章 庇古税与势博弈:给看不见的延迟定价

看不见的那一项

第一章的推导表明,自私的用户与社会最优之间只差一项:多一个人走路段 ee,他自己承受平均延迟 ce(x)c_e(x),同时让路上已有的 xx 个人每人慢 ce′(x)c_e'(x),合计给别人增加 xce′(x)x\,c_e'(x) 的延迟。这部分延迟由别人承担,所以他做决定时不计入。经济学把这种情形称为外部性。庇古在 1920 年的《福利经济学》中正是用两条路的例子说明:私人的边际成本与社会的边际成本不一致时,自由的选择不会达到最好的结果,适当的税可以纠正它 (Pigou 1920)。

证据

奈特的批评与贝克曼等人的形式化。 奈特 1924 年批评庇古的分析,认为如果那条容易拥挤的好路属于私人业主,业主收取的通行费会自然地使交通达到有效分布;问题的根源是道路被当作无主的资源 (Knight 1924)。贝克曼、麦圭尔与温斯滕 1956 年在网络上给出了完整的数学处理:用户均衡等价于最小化势函数 ∑e∫0xece(u)du\sum_e \int_0^{x_e} c_e(u)\,\mathrm{d}u,系统最优等价于最小化 ∑exece(xe)\sum_e x_e c_e(x_e),并讨论了使两者一致的定价 (Beckmann et al. 1956)。

边际成本通行费

推导

设 x*x^* 是系统最优的流量。在每段路上征收固定的通行费

τe=xe*ce′(xe*)\tau_e = x_e^*\,c_e'(x_e^*)

用户按「时间 + 通行费」选择路线。收费后的用户均衡条件是:被使用的路线上 ∑e∈p[ce(xe)+τe]\sum_{e \in p}[c_e(x_e) + \tau_e] 最小。在 x=x*x = x^* 处,这正是系统最优的条件 ∑e∈p[ce(xe*)+xe*ce′(xe*)]\sum_{e\in p}[c_e(x_e^*) + x_e^* c_e'(x_e^*)] 最小。由于收费后的势函数 ∑e[∫0xece+τexe]\sum_e[\int_0^{x_e} c_e + \tau_e x_e] 是凸的,x*x^* 就是收费博弈的均衡。

通行费的数值等于在最优处一个人给别人增加的延迟。它需要事先知道最优流量与延迟函数的斜率。

推导

# Marginal-cost (Pigouvian) tolls. At the optimum x*, charge each link tau_e = x*_e
# c_e'(x*_e), the delay one more user imposes on everyone already on it. Selfish users
# who minimise time + toll then choose exactly the optimal flows (Beckmann, McGuire &
# Winsten 1956). Links have c(x) = b + a x. Each flow pattern is found on a grid of path
# splits: the user equilibrium minimises the potential sum(b x + a x^2 / 2 + toll x),
# the optimum minimises total time sum(x c(x)).
NETS = {
    "Pigou": ({"top": (0, 1), "bottom": (1, 0)}, [("top",), ("bottom",)], 1.0),
    "Braess": ({"sv": (1, 0), "vt": (0, 1), "sw": (0, 1), "wt": (1, 0), "vw": (0, 0)},
               [("sv", "vt"), ("sw", "wt"), ("sv", "vw", "wt")], 1.0),
    "classic (demand 6)": ({"a": (10, 0), "b": (1, 50), "c": (1, 50), "d": (10, 0),
                            "e": (1, 10)},
                           [("a", "c"), ("b", "d"), ("a", "e", "d")], 6.0)}

def loads(net, paths, f):
    return {k: sum(q for p, q in zip(paths, f) if k in p) for k in net}

def best(net, paths, D, score, n=240):
    if len(paths) == 2:
        splits = [(D * i / n, D * (n - i) / n) for i in range(n + 1)]
    else:
        splits = [(D * i / n, D * j / n, D * (n - i - j) / n)
                  for i in range(n + 1) for j in range(n + 1 - i)]
    return loads(net, paths, min(splits, key=lambda f: score(loads(net, paths, f))))

print("network             tolls                  tolled = optimal  "
      "average time   toll time")
print("                                           flows?            "
      "untolled tolled paid + toll")
for name, (net, paths, D) in NETS.items():
    time = lambda x: sum(v * (net[k][1] + net[k][0] * v) for k, v in x.items())
    ue = best(net, paths, D, lambda x: sum(net[k][1] * v + net[k][0] * v * v / 2
                                           for k, v in x.items()))
    so = best(net, paths, D, time)
    tau = {k: so[k] * net[k][0] for k in net}                  # x* c'(x*)
    tolled = best(net, paths, D, lambda x: sum(net[k][1] * v + net[k][0] * v * v / 2
                                               + tau[k] * v for k, v in x.items()))
    paid = sum(tolled[k] * tau[k] for k in net) / D
    same = max(abs(tolled[k] - so[k]) for k in net) < 1e-9
    tl = ", ".join(f"{k} {v:g}" for k, v in tau.items() if v > 1e-9)
    t0, t1 = time(ue) / D, time(tolled) / D
    print(f"{name:19s} {tl:22s} {str(same):15s} {t0:7.2f} {t1:6.2f} {paid:6.2f}"
          f" {t1 + paid:6.2f}")
print("revenue returned as a lump sum: each user's net cost is the tolled time")
# network             tolls                  tolled = optimal  average time   toll time
#                                            flows?            untolled tolled paid + toll
# Pigou               bottom 0.5             True               1.00   0.75   0.25   1.00
# Braess              sv 0.5, wt 0.5         True               2.00   1.50   0.50   2.00
# classic (demand 6)  a 30, b 3, c 3, d 30   True              92.00  83.00  33.00 116.00
# revenue returned as a lump sum: each user's net cost is the tolled time

程序在路线分配的细网格上分别求势函数最小(均衡)与总时间最小(最优)的流量。三个网络中,收费后的均衡流量都与最优流量完全一致。庇古网络只需在下路收 0.5;布雷斯网络在两段 xx 路上各收 0.5,捷径不收费,结果没有人再走捷径;第一章那个需求为 6 的例子中,四段路分别收 30、3、3、30。

但表的最后几列值得细看。庇古网络中,收费使平均通行时间从 1.00 降到 0.75,而用户平均交了 0.25 的费,「时间 + 费用」仍然是 1.00,与不收费时完全相同。布雷斯网络也一样:时间从 2.0 降到 1.5,费用 0.5,合计仍是 2.0。在需求为 6 的例子中,时间从 92 降到 83,但人均交费 33,「时间 + 费用」升到 116,用户作为付费者反而更差。收费的社会收益落在收费收入上:只有当这笔收入以与路线选择无关的方式退还给用户(或用于他们看重的公共支出)时,每个人的净成本才降到收费后的通行时间。这不是这几个例子的巧合:收费后每人付出的「时间 + 费用」等于最优处路线的边际成本,它高于平均延迟,所以边际成本定价本身不保证付费者得益;作者框架中「自私均衡就与社会最优重合」的说法是对的,但「重合」说的是流量与总通行时间,不是用户自己的负担。

证据

斯德哥尔摩拥堵费。 斯德哥尔摩在 2006 年 1 月至 7 月试行按时段收费的拥堵费,跨越收费线的车流在收费时段比前一年减少了约 22%,拥堵的减少超过了事先的预期,而且影响遍及很大的范围而不只在收费线附近;出行时间的改善是公众可以感觉到的,这帮助改变了舆论,使随后的公投支持永久实施 (Eliasson et al. 2009)。

这些数字说明,价格可以显著改变出行选择;它们不说明斯德哥尔摩的收费等于理论上的边际外部成本,也不说明每位出行者都变得更好。

有限人数的博弈:势函数

前面的结论针对非原子的用户。如果参与者只有几个人,每人选一条完整的路线,问题就成了拥堵博弈。

证据

势博弈。 罗森塔尔 1973 年证明,在每种资源的成本只取决于使用人数的拥堵博弈中,存在纯策略纳什均衡:函数 Φ=∑e∑k=1nece(k)\Phi = \sum_e \sum_{k=1}^{n_e} c_e(k) 在任何一个人单方面换路时,变化量恰好等于他自己成本的变化量,所以 Φ\Phi 的最小值点就是一个均衡 (Rosenthal 1973)。蒙德勒与沙普利 1996 年把具有这种性质的博弈称为势博弈,证明有限的势博弈具有「有限改进性质」:任何一串单方面改进的换路必定在有限步后停止,停止之处就是纳什均衡 (Monderer and Shapley 1996)。

推导

6 名玩家各从三条路线中选一条:上路 U(s→v→ts \to v \to t)、下路 L(s→w→ts \to w \to t)与桥路 Z(s→v→w→ts \to v \to w \to t)。拥堵路段 s→vs \to v 与 w→tw \to t 的成本为每人 10×10 \times 使用人数,固定路段 v→tv \to t 与 s→ws \to w 成本为 70,桥 v→wv \to w 成本为 0。参数是示意的,结构与第一章相同,规模缩小到第八章实验的一组人数。程序列出所有纯策略均衡,让玩家随机地做单方面改进,检查势函数的下降是否恰好等于改进者的收益;最后让每人对自己使用的每段拥堵路支付「给其他人增加的延迟」:(ne−1)×10(n_e – 1) \times 10 个拥堵积分。

推导

# 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}")
# 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

没有桥时,唯一的均衡是 3 人走上路、3 人走下路,每人 100。有了桥,唯一的均衡变成 6 人全走桥,每人 120:离开桥去走上路,s→vs \to v 上仍有 6 人(包括自己),成本 60+70=13060 + 70 = 130,更差。总成本最低的分配仍是 3 比 3、不用桥,总计 600;均衡是 720,有限人数下的无秩序代价为 1.20。从 1000 个随机起点出发的随机改进过程,全部停在「6 人全走桥」,平均只需 4.6 次换路,最多 9 次;每一次换路,势函数的下降都恰好等于换路者省下的时间。这就是第八章实验要检验的「陷入布雷斯均衡」:不需要任何人犯错。

收取拥堵积分之后,所有人都走桥时,每人给别人增加的延迟是 100 个积分(两段拥堵路各 5×105 \times 10),离开桥变得划算,全走桥不再是均衡;新的均衡有四种(3/3/0、3/2/1、2/3/1、2/2/2),平均通行时间都是 100,即最优水平。原因在于,第 kk 个使用者的成本加上他给前 k−1k – 1 人增加的延迟,逐项相加正好等于 nc(n)n\,c(n):收费后的势函数就是总成本,总成本最低的分配一定是均衡。但总成本的局部最小点也可能是均衡,一般不能保证所有均衡都最优;本例中恰好都是。

注

收费的限制。 拥堵积分与第 27 本第二章的 VCG 机制是同一个思想:让每个人承担自己的外部性。通行费需要知道延迟函数与最优流量;不同人的时间价值不同时,单一的通行费不能使每个人的选择都最优;还有公平与政治上的可接受性问题。

假说 · 尚未验证

外部性可见假说(尚未确立)。作者推测,即使不扣积分、只显示「你这一轮给其他人增加了多少延迟」,也能使一部分参与者离开布雷斯均衡。可以检验的预测是:在第八章的实验中增加「只显示、不扣分」的第三组,其陷入比例介于两组之间;如果它与对照组没有差别,这一假说就被推翻。

本章小结

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

参考文献

Beckmann, Martin J., C. B. McGuire, and Christopher B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press.
Eliasson, Jonas, Lars Hultkrantz, Lena Nerhagen, and Lena Smidfelt Rosqvist. 2009. “The Stockholm Congestion-Charging Trial 2006: Overview of Effects.” Transportation Research Part A: Policy and Practice 43 (3): 240–50.
Knight, Frank H. 1924. “Some Fallacies in the Interpretation of Social Cost.” Quarterly Journal of Economics 38 (4): 582–606. https://doi.org/10.2307/1884592.
Monderer, Dov, and Lloyd S. Shapley. 1996. “Potential Games.” Games and Economic Behavior 14 (1): 124–43. https://doi.org/10.1006/game.1996.0044.
Pigou, Arthur C. 1920. The Economics of Welfare. Macmillan.
Rosenthal, Robert W. 1973. “A Class of Games Possessing Pure-Strategy Nash Equilibria.” International Journal of Game Theory 2 (1): 65–67. https://doi.org/10.1007/BF01737559.

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).