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

Chapter 2 The Price of Anarchy: How Much Can Selfishness Cost?

A ratio

In Braess’s network of the last chapter, the average travel time is 2 in the selfish equilibrium and 1.5 at the optimum, a ratio of 4/3. This ratio has a name.

Evidence

Definition and name. In 1999 Koutsoupias and Papadimitriou studied a very simple network: selfish users assigning tasks to several parallel links. They proposed measuring the efficiency of such a system by “the ratio between the worst possible Nash equilibrium and the social optimum”, and gave upper and lower bounds on this ratio (Koutsoupias and Papadimitriou 1999). In a 2001 paper on algorithms, games and the Internet, Papadimitriou called it the price of anarchy (PoA) (Papadimitriou 2001).

Calculation

PoA=total cost of the worst selfish equilibriumtotal cost of the optimum≥1\mathrm{PoA} = \frac{\text{total cost of the worst selfish equilibrium}}{\text{total cost of the optimum}} \ge 1

A PoA of 1 means selfish choice loses nothing; a PoA of 4/3 means the selfish equilibrium costs a third more than the optimum. In nonatomic routing games all user equilibria have the same total cost, so the word “worst” can be dropped.

Pigou’s network and 4/3

The simplest example is simpler than Braess’s network. In The Economics of Welfare (1920), Pigou used an example of two roads to argue that, left to itself, traffic distributes so that the “trouble” on the two roads becomes equal, but that shifting some carts from the road prone to congestion to the other could greatly reduce the trouble for those left behind while only slightly increasing it on the other road (Pigou 1920). In modern form: one unit of traffic goes from ss to tt; the upper road has constant delay 1 and the lower road delay equal to its flow xx.

Calculation

Equilibrium. The lower road’s delay x≤1x \le 1 is never more than the upper road’s, so all traffic takes the lower road, at total cost 1×1=11 \times 1 = 1.

Optimum. With xx on the lower road and 1−x1 – x on the upper, total cost is x⋅x+(1−x)⋅1x \cdot x + (1 – x) \cdot 1, minimised at x=1/2x = 1/2 with value 3/4.

Hence PoA=1/(3/4)=4/3\mathrm{PoA} = 1/(3/4) = 4/3. If the lower road’s delay is xdx^d, the optimal flow on it is x*=(d+1)−1/dx^* = (d+1)^{-1/d}, and

PoA(d)=[1−d(d+1)−(d+1)/d]−1\mathrm{PoA}(d) = \left[1 – d\,(d+1)^{-(d+1)/d}\right]^{-1}

Evidence

4/3 is independent of topology. In 2002 Roughgarden and Tardos proved that in any network in which every road’s delay is a linear function with non-negative coefficients, ce(x)=aex+bec_e(x) = a_e x + b_e, the total cost of nonatomic selfish routing is at most 4/3 of the optimum; for general continuous, non-decreasing delays, the selfish equilibrium costs no more than an optimal routing of twice the traffic (Roughgarden and Tardos 2002). In 2003 Roughgarden went further: for any class of delay functions that contains the constants, the worst case is always attained by a Pigou-like network of two roads, whatever the topology; for polynomial delays of degree at most dd with non-negative coefficients the bound is exactly the PoA(d)\mathrm{PoA}(d) above, which grows as Θ(d/ln⁡d)\Theta(d/\ln d) (Roughgarden 2003).

The author’s framework credits both the 4/3 and the Θ(d/ln⁡d)\Theta(d/\ln d) results to Roughgarden and Tardos 2002; on checking, the general topology-independence result and the polynomial bound are from Roughgarden 2003.

Calculation

# Price of anarchy in Pigou's two-link network: one unit of traffic, link 1 has constant
# time 1, link 2 has time x^d. Selfish users all take link 2 (its time is never above
# 1), total cost 1. The optimum sends x* = (d + 1)^(-1/d) on link 2. Roughgarden (2003)
# showed that for latency functions that are polynomials of degree <= d with nonnegative
# coefficients, this Pigou network is the worst case in ANY network, so PoA <= [1 - d (d
# + 1)^(-(d + 1)/d)]^(-1).
import math

def pigou(d):
    xs = (d + 1) ** (-1 / d)
    opt = xs * xs ** d + (1 - xs)
    return xs, opt, 1 / opt

def brute(d, n=200000):              # check the optimum by a fine grid search
    return min(x / n * (x / n) ** d + 1 - x / n for x in range(n + 1))

print(" d   share on x^d   optimal cost   PoA (closed form)   PoA (grid)   d/ln d")
for d in (1, 2, 3, 4, 6, 8, 10, 16):
    xs, opt, poa = pigou(d)
    dl = f"{d / math.log(d):6.2f}" if d > 1 else "     -"
    print(f"{d:2d}       {xs:.3f}         {opt:.4f}          {poa:.4f}"
          f"          {1 / brute(d):.4f}     {dl}")
print("ratio PoA / (d / ln d): " + ", ".join(
    f"d={d}: {pigou(d)[2] / (d / math.log(d)):.2f}" for d in (4, 16, 64, 256, 1024)))
# The BPR form t = t0 (1 + 0.15 (x/C)^4) is a degree-4 polynomial, so 2.151 bounds its
# PoA. How close does a BPR road get? Worst Pigou network for c(x) = 1 + 0.15 x^4 at
# demand r (in units of capacity): link 1 has the constant time c(r), so selfish users
# all take link 2.
def bpr_pigou(r, n=20000):
    c = lambda x: 1 + 0.15 * x ** 4
    opt = min(r * k / n * c(r * k / n) + (r - r * k / n) * c(r) for k in range(n + 1))
    return r * c(r) / opt
RS = (0.5, 1, 1.5, 2, 3, 5, 10)
print("BPR road, demand / capacity:  " + "  ".join(f"{r:>5}" for r in RS))
print("worst-case PoA:               " + "  ".join(f"{bpr_pigou(r):5.3f}" for r in RS))
#  d   share on x^d   optimal cost   PoA (closed form)   PoA (grid)   d/ln d
#  1       0.500         0.7500          1.3333          1.3333          -
#  2       0.577         0.6151          1.6258          1.6258       2.89
#  3       0.630         0.5275          1.8956          1.8956       2.73
#  4       0.669         0.4650          2.1505          2.1505       2.89
#  6       0.723         0.3803          2.6297          2.6297       3.35
#  8       0.760         0.3246          3.0808          3.0808       3.85
# 10       0.787         0.2847          3.5121          3.5121       4.34
# 16       0.838         0.2116          4.7268          4.7268       5.77
# ratio PoA / (d / ln d): d=4: 0.75, d=16: 0.82, d=64: 0.84, d=256: 0.86, d=1024: 0.88
# BPR road, demand / capacity:    0.5      1    1.5      2      3      5     10
# worst-case PoA:               1.005  1.075  1.300  1.607  1.977  2.125  2.149

The closed form and a fine grid search give the same values: 4/3 for d=1d = 1, 1.626 for d=2d = 2, 2.151 for d=4d = 4 and 4.727 for d=16d = 16. The ratio of PoA(d)\mathrm{PoA}(d) to d/ln⁡dd/\ln d creeps from 0.75 at d=4d = 4 to 0.88 at d=1024d = 1024. This is what “grows as Θ(d/ln⁡d)\Theta(d/\ln d)” means: the growth rate is that of d/ln⁡dd/\ln d, but the two are not equal.

The delay function most used in transport planning is the form in the US Bureau of Public Roads manual of 1964, t=t0[1+0.15(x/C)4]t = t_0[1 + 0.15\,(x/C)^4], where CC is the capacity (Bureau of Public Roads 1964). It is a polynomial of degree four, so 2.151 bounds it. But the last two lines of the program show that approaching that bound requires demand far above capacity: when demand equals capacity, the worst Pigou network has a PoA of only 1.075; at twice the capacity, 1.607; only at ten times does it reach 2.149. The reason is that the BPR function’s constant term t0t_0 dominates at moderate loads, and the congestion term overtakes it only under severe overload.

Left: the upper bound on the price of anarchy for polynomial delays (blue) and d/\ln d (dashed). Right: the price of anarchy of a BPR-type road in the worst Pigou network as “demand / capacity” varies; it approaches the bound of 2.151 only under severe overload.

Checks on random networks

The bounds describe the worst case. A natural question is how large the PoA is in “ordinary” networks.

Calculation

The program generates random acyclic networks with 7 nodes and one origin–destination pair; each road’s delay is b+axdb + a x^d with aa and bb uniform between 0 and 1, and demand is drawn from 0.5, 1, 2 and 4. For d=1d = 1 and d=4d = 4 it generates 150 networks each, computes the user equilibrium and the system optimum, and checks the 4/3 and 2.151 bounds and the “twice the traffic” result; finally it takes one network with degree-4 delays and shows how its PoA varies with demand.

Calculation

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

Across the 150 networks with linear delays, the median PoA is only 1.013, the 90th percentile 1.048 and the maximum 1.095, far below 4/3; only 14 networks lose more than 5 %. With degree-4 delays the losses are larger: median 1.028, 90th percentile 1.231, maximum 1.595, still below 2.151; 59 of the 150 networks exceed 5 %. In both cases the total cost of “routing demand rr selfishly” never exceeds that of “routing 2r2r optimally”, in all 150 networks without exception. The last network shows how the PoA depends on demand: at very small demand (0.1 and 0.5) there is no loss, because everyone uses the same fastest route and it is not yet congested; the loss peaks at about 20 % at demand 4; at demand 16 and 64 it is back to 1.000, because every route is badly congested and the selfish and optimal assignments converge.

Evidence

The PoA rises and then falls with demand. Youn, Gastner and Jeong found in 2008 that in model networks the PoA is 1 at low flow, rises steeply as flow grows, peaks, and falls back towards 1 at high flow; in real road networks it shows several local peaks as total flow varies (Youn et al. 2008). In 2016 O’Hare, Connors and Watling analysed systematically the mechanisms that govern how the PoA varies with travel demand, arguing that understanding this variation helps decide when interventions to improve a network’s efficiency are worth their cost (O’Hare et al. 2016).

Note

Where the bounds apply. First, 4/3 holds only for nonatomic users, each an infinitesimal share of traffic. With finitely many players of equal weight, each choosing one unsplittable route, the worst-case PoA of pure equilibria with linear delays is 5/2 (proved independently by two groups in 2005) (Awerbuch et al. 2005; Christodoulou and Koutsoupias 2005). The Chapter 8 experiment has only six people per group, so the distinction matters. Second, the bounds compare total travel time only and say nothing about fairness: an assignment whose total time is close to optimal can still impose long delays on a few people. Third, the model assumes that everyone has full information about traffic and is fully rational; real drivers’ information and habits change the outcome. So “the PoA is at most 4/3” cannot be read as “real congestion losses are at most a third”, still less, conversely, as “real losses must be close to a third”.

Hypothesis · not established

The moderate-load hypothesis (not yet established). The author conjectures that the efficiency loss from spontaneous task allocation in teams (each person choosing whom to ask for approval and which procedure to follow) is greatest at moderate workloads and smaller both when a team is idle and when it is swamped, in the same shape as the PoA of routing games. The testable prediction is that across several teams that record weekly request volumes and average handling times, the difference in handling time between “spontaneous allocation” and “central scheduling” is largest in the middle range of request volume. If the difference rises or falls monotonically with volume, the hypothesis is refuted.

Summary

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 dd the bound is [1−d(d+1)−(d+1)/d]−1[1 – d(d+1)^{-(d+1)/d}]^{-1}, which is 2.151 for d=4d = 4 and grows as Θ(d/ln⁡d)\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.

References

Awerbuch, Baruch, Yossi Azar, and Amir Epstein. 2005. “The Price of Routing Unsplittable Flow.” Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC ’05) (New York), 57–66. https://doi.org/10.1145/1060590.1060599.
Bureau of Public Roads. 1964. Traffic Assignment Manual. U.S. Department of Commerce, Urban Planning Division.
Christodoulou, George, and Elias Koutsoupias. 2005. “The Price of Anarchy of Finite Congestion Games.” Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC ’05) (New York), 67–73. https://doi.org/10.1145/1060590.1060600.
Koutsoupias, Elias, and Christos Papadimitriou. 1999. “Worst-Case Equilibria.” STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science (Berlin), Lecture notes in computer science, vol. 1563: 404–13.
O’Hare, Steven J., Richard D. Connors, and David P. Watling. 2016. “Mechanisms That Govern How the Price of Anarchy Varies with Travel Demand.” Transportation Research Part B: Methodological 84: 55–80. https://doi.org/10.1016/j.trb.2015.12.005.
Papadimitriou, Christos. 2001. “Algorithms, Games, and the Internet.” Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC ’01) (New York), 749–53. https://doi.org/10.1145/380752.380883.
Pigou, Arthur C. 1920. The Economics of Welfare. Macmillan.
Roughgarden, Tim. 2003. “The Price of Anarchy Is Independent of the Network Topology.” Journal of Computer and System Sciences 67 (2): 341–64. https://doi.org/10.1016/S0022-0000(03)00044-8.
Roughgarden, Tim, and Éva Tardos. 2002. “How Bad Is Selfish Routing?” Journal of the ACM 49 (2): 236–59. https://doi.org/10.1145/506147.506153.
Youn, Hyejin, Michael T. Gastner, and Hawoong Jeong. 2008. “Price of Anarchy in Transportation Networks: Efficiency and Optimality Control.” Physical Review Letters 101 (12): 128701. https://doi.org/10.1103/PhysRevLett.101.128701.

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