What does Braess's Paradox and the Price of Anarchy conclude, in numbers, about “The Price of Anarchy: How Much Can Selfishness Cost?”?
Answer: The price of anarchy is the ratio of the worst selfish equilibrium to the optimum. In networks with linear delays and nonatomic users it is at most 4/3, and the worst case is Pigou's two-road network whatever the topology; with polynomial delays of degree \(d\) the bound is \([1 - d(d+1){-(d+1)/d}]{-1}\), which is 2.151 for \(d = 4\) and grows as \(\Theta(d/\ln d)\). In random networks the PoA is usually far below the bound and first rises, then falls, with demand; a BPR-type road approaches the worst case only under severe overload. The bound does not apply to games with finitely many players, whose worst case is 5/2. The next chapter asks whether prices can remove this loss.
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: 2.151
degree 1: 150 random networks, PoA median 1.013, 90th percentile 1.048, max 1.095 (bound 1.333); above 1.05 in 14 networks UE cost at demand r <= optimal cost at demand 2r in 150 of 150 networks degree 4: 150 random networks, PoA median 1.028, 90th percentile 1.231, max 1.595 (bound 2.151); above 1.05 in 59 networks UE cost at demand r <= optimal cost at demand 2r in 150 of 150 networks one random degree-4 network (15 paths), PoA as demand grows: demand 0.1 0.5 1 2 4 8 16 64 PoA 1.000 1.000 1.062 1.055 1.201 1.008 1.000 1.000
Key formula
Show the full program
# Numerical check of the price-of-anarchy bounds on random networks (Roughgarden &
# Tardos 2002; Roughgarden 2003). Random acyclic networks with 7 nodes, one
# origin-destination pair and latencies c(x) = b + a x^d with random a, b >= 0. UE and
# SO by path equilibration.
import random
rng = random.Random(4)
def lat(e, x, m): # m = True gives the marginal cost (for the optimum)
a, b, d = e
return b + (d + 1 if m else 1) * a * x ** d
def solve(net, paths, demand, m=False, tol=1e-10):
f = [0.0] * len(paths); f[0] = demand
load = {k: 0.0 for k in net}
for k in paths[0]: load[k] += demand
pc = lambda p, L: sum(lat(net[k], L[k], m) for k in p)
for _ in range(20000):
c = [pc(p, load) for p in paths]
used = [i for i in range(len(paths)) if f[i] > 1e-14]
hi = max(used, key=lambda i: c[i])
lo = min(range(len(paths)), key=lambda i: c[i])
if c[hi] - c[lo] < tol: break
H, Lo = set(paths[hi]), set(paths[lo])
def gap(s):
L = dict(load)
for k in H - Lo: L[k] -= s
for k in Lo - H: L[k] += s
return pc(paths[hi], L) - pc(paths[lo], L)
s, t = 0.0, f[hi]
if gap(t) > 0: s = t
else:
for _ in range(50):
mid = (s + t) / 2
if gap(mid) > 0: s = mid
else: t = mid
f[hi] -= s; f[lo] += s
for k in H - Lo: load[k] -= s
for k in Lo - H: load[k] += s
return f, load
def cost(net, load):
return sum(x * lat(net[k], x, False) for k, x in load.items())
def random_net(d, n=7):
net = {}
for i in range(n - 1):
net[(i, i + 1)] = (rng.random(), rng.random(), d) # keeps a path s -> t
for j in range(i + 2, n):
if rng.random() < 0.35: net[(i, j)] = (rng.random(), rng.random(), d)
out = {}
for (i, j) in net: out.setdefault(i, []).append(j)
paths, stack = [], [(0, [])]
while stack:
v, p = stack.pop()
if v == n - 1: paths.append(tuple(p)); continue
for w in out.get(v, []): stack.append((w, p + [(v, w)]))
return net, paths
def poa(net, paths, r):
_, lu = solve(net, paths, r); _, lo = solve(net, paths, r, True)
return cost(net, lu) / cost(net, lo), cost(net, lu), lo
for d, bound in ((1, 4 / 3), (4, 2.1505)):
ratios, aug = [], 0
for _ in range(150):
net, paths = random_net(d)
r = rng.choice((0.5, 1, 2, 4))
q, cu, _ = poa(net, paths, r); ratios.append(q)
_, lo2 = solve(net, paths, 2 * r, True)
aug += cu <= cost(net, lo2) + 1e-9
ratios.sort()
print(f"degree {d}: 150 random networks, PoA median {ratios[75]:.3f}, "
f"90th percentile {ratios[134]:.3f},\n max {ratios[-1]:.3f} "
f"(bound {bound:.3f}); above 1.05 in {sum(q > 1.05 for q in ratios)} networks")
print(f" UE cost at demand r <= optimal cost at demand 2r in {aug} of 150 networks")
rng.seed(7)
net, paths = random_net(4)
print(f"one random degree-4 network ({len(paths)} paths), PoA as demand grows:")
DEM = (0.1, 0.5, 1, 2, 4, 8, 16, 64)
print(" demand " + " ".join(f"{r:>5}" for r in DEM))
print(" PoA " + " ".join(f"{poa(net, paths, r)[0]:5.3f}" for r in DEM))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 2: The Price of Anarchy: How Much Can Selfishness Cost?. 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
- Chapter 1 · Braess's Paradox: One More Road, Everyone Slower
- Chapter 3 · Pigouvian Tolls and Potential Games: Pricing the Unseen Delay
- Chapter 4 · Congestion in Attention: Hot Niches, Hotelling and a Digital Braess Paradox
- Chapter 5 · Exploration and Exploitation: Bandits, the Matthew Effect and Traffic Pools in Recommendation
- Chapter 6 · Stable Matching: Deferred Acceptance, Early Contracting and Telling the Truth
- Chapter 8 · Practice and a Pre-Registered Trial