5D Library › Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks · 中文

Chapter 3 Pigouvian Tolls and Potential Games: Pricing the Unseen Delay

The missing term

The derivation of Chapter 1 showed that selfish users and the social optimum differ by a single term: one more user on road ee bears the average delay ce(x)c_e(x) himself and slows each of the xx users already there by ce′(x)c_e'(x), adding xce′(x)x\,c_e'(x) of delay for others in total. Others bear this delay, so he leaves it out of his decision. Economists call this an externality. In The Economics of Welfare (1920) Pigou used exactly an example of two roads to argue that when private and social marginal costs diverge, free choice does not reach the best outcome, and that a suitable tax can correct it (Pigou 1920).

Evidence

Knight’s criticism and Beckmann’s formalisation. In 1924 Knight criticised Pigou’s analysis, arguing that if the good but congestible road belonged to a private owner, the toll the owner charged would naturally bring about an efficient distribution of traffic, and that the root of the problem was treating roads as unowned resources (Knight 1924). In 1956 Beckmann, McGuire and Winsten gave a complete mathematical treatment on networks: the user equilibrium is equivalent to minimising the potential ∑e∫0xece(u)du\sum_e \int_0^{x_e} c_e(u)\,\mathrm{d}u, the system optimum to minimising ∑exece(xe)\sum_e x_e c_e(x_e), and they discussed the pricing that makes the two coincide (Beckmann et al. 1956).

Marginal-cost tolls

Calculation

Let x*x^* be the system-optimal flow. On each road levy the fixed toll

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

and let users choose routes by “time + toll”. The tolled user-equilibrium condition is that used routes minimise ∑e∈p[ce(xe)+τe]\sum_{e \in p}[c_e(x_e) + \tau_e]. At x=x*x = x^* this is exactly the system-optimum condition that ∑e∈p[ce(xe*)+xe*ce′(xe*)]\sum_{e\in p}[c_e(x_e^*) + x_e^* c_e'(x_e^*)] is minimal. Since the tolled potential ∑e[∫0xece+τexe]\sum_e[\int_0^{x_e} c_e + \tau_e x_e] is convex, x*x^* is the equilibrium of the tolled game.

The toll equals the delay one person adds for others at the optimum. It requires knowing the optimal flows and the slopes of the delay functions in advance.

Calculation

# 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

The program finds, on a fine grid of route splits, the flows that minimise the potential (the equilibrium) and those that minimise total time (the optimum). In all three networks the tolled equilibrium flows coincide exactly with the optimal flows. Pigou’s network needs a toll of 0.5 on the lower road only; Braess’s network needs 0.5 on each congestible road and nothing on the shortcut, after which no one takes the shortcut; the example with demand 6 from Chapter 1 needs tolls of 30, 3, 3 and 30 on its four roads.

The last columns of the table deserve a closer look. In Pigou’s network the toll lowers the average travel time from 1.00 to 0.75, but users pay an average toll of 0.25, so “time + toll” is still 1.00, exactly as without the toll. Braess’s network is the same: time falls from 2.0 to 1.5, the toll is 0.5, and the total is still 2.0. In the example with demand 6, time falls from 92 to 83, but the average toll is 33, so “time + toll” rises to 116, and users as payers are worse off. The social gain from tolling sits in the toll revenue: only if that revenue is returned to users in a way unrelated to their route choices (or spent on public goods they value) does each person’s net cost fall to the tolled travel time. This is not a coincidence of these examples: after tolling, each user’s “time + toll” equals the marginal cost of a route at the optimum, which exceeds the average delay, so marginal-cost pricing by itself does not guarantee that payers gain. The author’s framework is right that “the selfish equilibrium then coincides with the social optimum”, but what coincides is the flows and the total travel time, not users’ own burden.

Evidence

The Stockholm congestion charge. Stockholm ran a trial of time-of-day congestion charges from January to July 2006. Car traffic across the charging cordon during charged hours fell by about 22 % compared with the previous year; the reduction in congestion exceeded expectations, and the effect reached well beyond the immediate vicinity of the cordon. The improvement in travel times was noticeable to the public, which helped shift opinion towards a positive outcome in the subsequent referendum on making the charges permanent (Eliasson et al. 2009).

These numbers show that prices can change travel choices substantially. They do not show that the Stockholm charges equalled the theoretical marginal external cost, nor that every traveller became better off.

Games with finitely many players: potentials

The results above concern nonatomic users. If there are only a few players, each choosing a whole route, the problem becomes a congestion game.

Evidence

Potential games. In 1973 Rosenthal proved that congestion games in which the cost of each resource depends only on the number of its users have pure-strategy Nash equilibria: the function Φ=∑e∑k=1nece(k)\Phi = \sum_e \sum_{k=1}^{n_e} c_e(k) changes, whenever one player switches unilaterally, by exactly the change in that player’s own cost, so a minimum of Φ\Phi is an equilibrium (Rosenthal 1973). In 1996 Monderer and Shapley called games with this property potential games and proved that finite potential games have the “finite improvement property”: every sequence of unilateral improving switches must stop after finitely many steps, and it stops at a Nash equilibrium (Monderer and Shapley 1996).

Calculation

Six players each choose one of three routes: upper U (s→v→ts \to v \to t), lower L (s→w→ts \to w \to t) and bridge Z (s→v→w→ts \to v \to w \to t). The congestible roads s→vs \to v and w→tw \to t cost each user 10×10 \times the number of users, the fixed roads v→tv \to t and s→ws \to w cost 70, and the bridge v→wv \to w costs 0. The parameters are illustrative; the structure is that of Chapter 1, scaled down to the size of one group in the Chapter 8 experiment. The program lists all pure-strategy equilibria, lets players make random unilateral improvements and checks whether the drop in the potential always equals the mover’s gain, and finally makes each user pay, on every congestible road she uses, “the delay she adds for others”: (ne−1)×10(n_e – 1) \times 10 congestion points.

Calculation

# 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

Without the bridge the only equilibrium is three players on the upper and three on the lower route, at 100 each. With the bridge the only equilibrium becomes all six on the bridge, at 120 each: a player who leaves the bridge for the upper route still shares s→vs \to v with six users (herself included) and pays 60+70=13060 + 70 = 130, which is worse. The lowest-total assignment is still three and three without the bridge, at 600 in total; the equilibrium costs 720, a finite-player price of anarchy of 1.20. From 1,000 random starting points, random improvement dynamics always stopped at “all six on the bridge”, after a mean of only 4.6 switches and at most 9; at every switch the potential fell by exactly the time the switcher saved. This is the “trapped in the Braess equilibrium” outcome that the Chapter 8 experiment tests: no one needs to make a mistake.

Charging congestion points changes everything. When everyone is on the bridge, each user adds 100 points of delay for others (5×105 \times 10 on each of two congestible roads), so leaving the bridge pays and all-on-the-bridge is no longer an equilibrium; there are four new equilibria (3/3/0, 3/2/1, 2/3/1 and 2/2/2), all with an average travel time of 100, the optimal level. The reason is that the cost of the kk-th user plus the delay she adds for the first k−1k – 1, summed term by term, equals exactly nc(n)n\,c(n): the tolled potential is the total cost, so the lowest-cost assignment must be an equilibrium. Local minima of total cost can also be equilibria, so in general not every tolled equilibrium is optimal; here they all happen to be.

Note

The limits of tolls. Congestion points are the same idea as the VCG mechanism of Chapter 2 of Volume 27: each person bears her own externality. Tolls need the delay functions and the optimal flows; when people value time differently, a single toll cannot make every individual’s choice optimal; and there are problems of fairness and political acceptability.

Hypothesis · not established

The visible-externality hypothesis (not yet established). The author conjectures that merely showing “how much delay you added for others this round”, without deducting points, would lead some participants out of the Braess equilibrium. The testable prediction is that a third arm, “shown but not charged”, added to the Chapter 8 experiment would have a share of trapped groups between those of the other two arms; if it does not differ from the control arm, the hypothesis is refuted. The main trial has only two arms; this is left for later work.

Summary

Selfish users bear only the average delay, not the marginal delay they add for others. A toll of x*c′(x*)x^*c'(x^*) on each road at the optimum makes the selfish equilibrium coincide with the optimum; but unless the revenue is returned, users’ own “time + toll” need not fall and can even rise. The Stockholm congestion charge shows that prices can change travel substantially. Congestion games with finitely many players are potential games: unilateral improvement must stop at an equilibrium, and in the six-player Braess network it stops at “everyone on the bridge, 120 each”; charging points equal to each player’s externality turns the potential into the total cost, and everyone-on-the-bridge is no longer an equilibrium. The next chapter carries the same structure over to attention markets.

References

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