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

\[\mathrm{PoA} = \frac{\text{最坏的自私均衡的总成本}}{\text{最优的总成本}} \ge 1\]
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