5D Library › 算法博弈论、布雷斯悖论与流量分配的无秩序代价 · English
第三章 庇古税与势博弈:给看不见的延迟定价
看不见的那一项
第一章的推导表明,自私的用户与社会最优之间只差一项:多一个人走路段 ,他自己承受平均延迟 ,同时让路上已有的 个人每人慢 ,合计给别人增加 的延迟。这部分延迟由别人承担,所以他做决定时不计入。经济学把这种情形称为外部性。庇古在 1920 年的《福利经济学》中正是用两条路的例子说明:私人的边际成本与社会的边际成本不一致时,自由的选择不会达到最好的结果,适当的税可以纠正它 (Pigou 1920)。
证据
奈特的批评与贝克曼等人的形式化。 奈特 1924 年批评庇古的分析,认为如果那条容易拥挤的好路属于私人业主,业主收取的通行费会自然地使交通达到有效分布;问题的根源是道路被当作无主的资源 (Knight 1924)。贝克曼、麦圭尔与温斯滕 1956 年在网络上给出了完整的数学处理:用户均衡等价于最小化势函数 ,系统最优等价于最小化 ,并讨论了使两者一致的定价 (Beckmann et al. 1956)。
边际成本通行费
推导
设 是系统最优的流量。在每段路上征收固定的通行费
用户按「时间 + 通行费」选择路线。收费后的用户均衡条件是:被使用的路线上 最小。在 处,这正是系统最优的条件 最小。由于收费后的势函数 是凸的, 就是收费博弈的均衡。
通行费的数值等于在最优处一个人给别人增加的延迟。它需要事先知道最优流量与延迟函数的斜率。
推导
# 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;布雷斯网络在两段 路上各收 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 年证明,在每种资源的成本只取决于使用人数的拥堵博弈中,存在纯策略纳什均衡:函数 在任何一个人单方面换路时,变化量恰好等于他自己成本的变化量,所以 的最小值点就是一个均衡 (Rosenthal 1973)。蒙德勒与沙普利 1996 年把具有这种性质的博弈称为势博弈,证明有限的势博弈具有「有限改进性质」:任何一串单方面改进的换路必定在有限步后停止,停止之处就是纳什均衡 (Monderer and Shapley 1996)。
推导
6 名玩家各从三条路线中选一条:上路 U()、下路 L()与桥路 Z()。拥堵路段 与 的成本为每人 使用人数,固定路段 与 成本为 70,桥 成本为 0。参数是示意的,结构与第一章相同,规模缩小到第八章实验的一组人数。程序列出所有纯策略均衡,让玩家随机地做单方面改进,检查势函数的下降是否恰好等于改进者的收益;最后让每人对自己使用的每段拥堵路支付「给其他人增加的延迟」: 个拥堵积分。
推导
# 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:离开桥去走上路, 上仍有 6 人(包括自己),成本 ,更差。总成本最低的分配仍是 3 比 3、不用桥,总计 600;均衡是 720,有限人数下的无秩序代价为 1.20。从 1000 个随机起点出发的随机改进过程,全部停在「6 人全走桥」,平均只需 4.6 次换路,最多 9 次;每一次换路,势函数的下降都恰好等于换路者省下的时间。这就是第八章实验要检验的「陷入布雷斯均衡」:不需要任何人犯错。
收取拥堵积分之后,所有人都走桥时,每人给别人增加的延迟是 100 个积分(两段拥堵路各 ),离开桥变得划算,全走桥不再是均衡;新的均衡有四种(3/3/0、3/2/1、2/3/1、2/2/2),平均通行时间都是 100,即最优水平。原因在于,第 个使用者的成本加上他给前 人增加的延迟,逐项相加正好等于 :收费后的势函数就是总成本,总成本最低的分配一定是均衡。但总成本的局部最小点也可能是均衡,一般不能保证所有均衡都最优;本例中恰好都是。
注
收费的限制。 拥堵积分与第 27 本第二章的 VCG 机制是同一个思想:让每个人承担自己的外部性。通行费需要知道延迟函数与最优流量;不同人的时间价值不同时,单一的通行费不能使每个人的选择都最优;还有公平与政治上的可接受性问题。
假说 · 尚未验证
外部性可见假说(尚未确立)。作者推测,即使不扣积分、只显示「你这一轮给其他人增加了多少延迟」,也能使一部分参与者离开布雷斯均衡。可以检验的预测是:在第八章的实验中增加「只显示、不扣分」的第三组,其陷入比例介于两组之间;如果它与对照组没有差别,这一假说就被推翻。
本章小结
在最优处按 收费,自私均衡就与最优重合,但不退还收入时用户的「时间 + 费用」未必下降;斯德哥尔摩的拥堵费显示价格能显著改变出行。有限人数的拥堵博弈是势博弈,6 人布雷斯网络中的改进停在「全走桥、每人 120」;按外部性收取积分后,势函数变成总成本,全走桥不再是均衡。下一章把这一结构搬到注意力市场。
参考文献
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).