What does Braess's Paradox and the Price of Anarchy conclude, in numbers, about “Pigouvian Tolls and Potential Games: Pricing the Unseen Delay”?

Answer: Selfish users bear only the average delay, not the marginal delay they add for others. A toll of \(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.

Scope of the numbers: The models of traffic pools and recommender algorithms are schematic and describe no real platform; the book is not investment, business or marketing advice. Marked boxes separate published evidence, runnable Python calculations (16 programs, all checked), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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

Key formula

\[\tau_e = x_e^*\,c_e'(x_e^*)\]
Show the full program
# 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}")

Single source and citation

Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks (Version 1.0.0), Chapter 3: Pigouvian Tolls and Potential Games: Pricing the Unseen Delay. 5D Library. https://doi.org/10.5281/zenodo.23782094

DOI: 10.5281/zenodo.23782094 · Read the monograph · 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}
}

Other chapter answers in this book