Routing Games

Motivation: routing without a central authority

Most of the literature on the inefficiency of equilibria concerns routing. The practical question is how to route traffic in a large network, like the Internet, with no one in charge. Routing games model two settings:

source routing: each end user picks a full route;
distributed, congestion-sensitive shortest-path routing. If each edge’s length is set to its current congestion cost $c(x)$ , shortest-path routing sends traffic exactly as selfish routing would (Bertsekas–Tsitsiklis).

IntuitionThe central question

When every unit of traffic takes its own cheapest route, how much worse is the total delay than the best possible routing — and what, besides the cost functions, does that loss depend on?

The chapter studies two models:

	Nonatomic	Atomic
players	a continuum; each controls negligible traffic	$k$ players; player $i$ routes $r_i$ on one path
generalizes	Pigou’s example (inefficiency-of-equilibria)	finite games from Chapter 1
equilibria exist?	always	not always (weighted); yes if unweighted or affine
unique?	essentially (all have equal cost)	no
affine PoA	$4/3$	$5/2$ unweighted; $(3+\sqrt5)/2$ weighted
main PoA technique	variational inequality + Pigou bound	per-player deviation + Cauchy–Schwarz

The models look alike on the surface, but different techniques are needed to analyze them.

Nonatomic selfish routing

DefinitionNonatomic instance $(G, r, c)$

A directed graph $G = (V,E)$ , parallel edges allowed, with commodities $(s_1,t_1),\dots,(s_k,t_k)$ .
$\mathcal{P}_i$ is the set of $s_i$ – $t_i$ paths, assumed nonempty, and $\mathcal{P} = \bigcup_i \mathcal{P}_i$ .
A flow $f \ge 0$ is indexed by paths; $f_P$ is the traffic of commodity $i$ on $P \in \mathcal{P}_i$ .
Traffic is inelastic: $f$ is feasible if $\sum_{P\in\mathcal{P}_i} f_P = r_i$ for each $i$ . There are no edge capacities.
Each edge has a cost function $c_e : \mathbb{R}_+ \to \mathbb{R}_+$ that is nonnegative, continuous, nondecreasing. Delay is the canonical example.

Edge and path costs. The load on an edge is $f_e = \sum_{P \ni e} f_P$ , and a path costs $c_P(f) = \sum_{e\in P} c_e(f_e)$ .

DefinitionDefinition 18.1 — equilibrium (Wardrop) flow

A feasible $f$ is an equilibrium flow if for every commodity $i$ and all $P, \tilde P \in \mathcal{P}_i$ with $f_P > 0$ : $c_P(f) \le c_{\tilde P}(f).$ All used paths are cheapest, so all used paths of a commodity have equal cost.

IntuitionNegligible players

One infinitesimal driver switching paths doesn’t change any edge’s congestion. So “no one wants to switch” reduces to “everyone is already on a currently cheapest path.”

ExamplePigou, checked against the definition

All traffic on the lower edge ( $c(x) = x$ ): this is an equilibrium. The only alternative also costs 1.
A 50/50 split is not an equilibrium. The upper edge is used at cost 1, but the lower edge now costs only $1/2$ .

RemarkRemark 18.2 — congestion games

No player set or payoff functions are written down. A player’s cost depends only on its path and the loads on that path, not on who else is there. Games with this property are congestion games, and working with flows directly is simpler.

FormulaSocial cost of a flow

C(f) = \sum_{P\in\mathcal{P}} c_P(f)\, f_P \;=\; \sum_{e\in E} c_e(f_e)\, f_e. \tag{18.1–18.2}

The second form follows by expanding $c_P$ and swapping sums. A feasible flow minimizing $C$ is optimal. The objective is utilitarian, and PoA = equilibrium cost / optimal cost. Any equilibrium can be used, since all have equal cost (Existence and essential uniqueness).

Two warning examples

ExampleExample 18.3 — nonlinear Pigou

Pigou’s example with the lower edge changed to $c(x) = x^p$ .

Equilibrium: everything on the lower edge, cost 1.
Optimum: $\epsilon = 1 - (p+1)^{-1/p}$ on the upper edge, with cost $\epsilon + (1-\epsilon)^{p+1} \to 0$ as $p\to\infty$ .

So PoA $\to\infty$ , growing roughly like $p/\ln p$ (Exercise 18.1).

graph LR
  S["s"] -->|"c = 1"| T["t"]
  S -->|"c = x to the power p"| T

IntuitionWhy nonlinearity hurts

With a steep cost, the lower edge is nearly free until it is almost full, and then its cost shoots up. Selfish drivers fill it right up to the expensive point. The optimum diverts a sliver of traffic to keep the rest on the nearly-free part.

ExampleExample 18.4 — Braess’s Paradox

One unit of traffic from $s$ to $t$ .

(a) Original network. Routes $s\to v\to t$ and $s\to w\to t$ , each with one edge of cost $x$ and one of cost $1$ . Equilibrium: half on each route, everyone pays $1/2 + 1 = 3/2$ .

(b) Add a zero-cost edge $v \to w$ . The route $s\to v\to w\to t$ uses both cost- $x$ edges and never costs more than the old routes, and strictly less while any traffic avoids it. So everyone takes it, and everyone pays $1 + 0 + 1 = 2$ .

Adding a free road made everyone worse off.

graph LR
  S["s"] -->|"x"| V["v"]
  V -->|"1"| T["t"]
  S -->|"1"| W["w"]
  W -->|"x"| T
  V -.->|"0, added edge"| W

WarningMore capacity is not always better

Braess shows the naive intuition fails even with affine costs. In network (b) the optimum is the old equilibrium (cost $3/2$ ), so PoA $= 4/3$ , the same as Pigou. That is no coincidence; see Remark 18.22 below.

RemarkPhysical analogue (Cohen–Horowitz)

Two springs in series, joined by a short taut string, with slack strings providing parallel paths. Cutting the taut string makes the hanging weight rise. Force plays the role of traffic, and extension the role of cost. The rise equals the equilibrium improvement from deleting the zero-cost edge.

Atomic selfish routing

DefinitionAtomic instance $(G, r, c)$

Same ingredients, but it is a finite game. Player $i$ routes all $r_i$ units on one path $P \in \mathcal{P}_i$ . A flow $f_P^{(i)}$ is indexed by player and path, and it is feasible if each player puts $r_i$ on exactly one path. Different players may share a source–sink pair. $c_P$ and $C$ are defined as before.

DefinitionDefinition 18.5 — atomic equilibrium flow

A feasible $f$ is an equilibrium if for every player $i$ and all $P, \tilde P \in \mathcal{P}_i$ with $f_P^{(i)} > 0$ : $c_P(f) \le c_{\tilde P}(\tilde f),$ where $\tilde f$ moves player $i$ ‘s $r_i$ from $P$ to $\tilde P$ . These are pure Nash equilibria.

WarningThe deviator’s own traffic counts

The comparison is against $c_{\tilde P}(\tilde f)$ , with $i$ ‘s traffic added to the new path. A nonnegligible player sees its own congestion, which is exactly what the nonatomic definition ignores.

Unweighted instances are those where all $r_i$ are equal.

ExampleExample 18.6 — the AAE example (Awerbuch–Azar–Epstein)

A bidirected triangle on $u, v, w$ . Edges $v\to u$ and $w \to u$ cost $0$ ; the other four edges cost $x$ . Four unit-traffic players:

Player	Route	One-hop path	Two-hop path
1	$u \to v$	$u\to v$	$u\to w\to v$
2	$u \to w$	$u\to w$	$u\to v\to w$
3	$v \to w$	$v\to w$	$v\to u\to w$
4	$w \to v$	$w\to v$	$w\to u\to v$

All one-hop: each costly edge has load 1, for total cost 4. This is optimal and an equilibrium.
All two-hop: loads are $u\to w$ : 2, $u\to v$ : 2, $w\to v$ : 1, $v\to w$ : 1. Players 1 and 2 pay $2+1 = 3$ ; players 3 and 4 pay $0+2 = 2$ . Total 10. It is an equilibrium: each one-hop alternative now costs exactly as much as the current route (3 for players 1–2, 2 for 3–4).

PoA $= 10/4 = 5/2$ , with affine costs, where nonatomic instances never exceed $4/3$ .

graph LR
  U["u: sources of players 1, 2"] -->|"x"| V["v"]
  U -->|"x"| W["w"]
  V -->|"0"| U
  W -->|"0"| U
  V -->|"x"| W
  W -->|"x"| V

ExampleExample 18.7 — no equilibrium in a weighted instance

A four-vertex network with polynomial edge costs and two players from $s$ to $t$ , with $r_1 = 1$ and $r_2 = 2$ . The paths are $P_1: s\to t$ , $P_2: s\to v\to t$ , $P_3: s\to w\to t$ , $P_4: s\to v\to w\to t$ . The unique best responses cycle:

player 2 on $P_1$ or $P_2$ ⇒ player 1 best-responds with $P_4$ ;
player 2 on $P_3$ or $P_4$ ⇒ player 1 best-responds with $P_1$ ;
player 1 on $P_4$ ⇒ player 2 best-responds with $P_3$ ;
player 1 on $P_1$ ⇒ player 2 best-responds with $P_2$ .

Following these around gives no fixed point, so there is no pure equilibrium.

NoteVerification left to the reader

The chapter leaves checking (1)–(4) as an exercise. The example is due to Goemans et al. (2005).

Existence and essential uniqueness

Optimal flows are equilibria for marginal costs

Assume each $x\,c_e(x)$ is convex and continuously differentiable. This is edge $e$ ‘s contribution to $C$ .

DefinitionMarginal cost function

c_e^*(x) = \big(x\,c_e(x)\big)' = c_e(x) + x\,c_e'(x),\qquad c_P^*(f) = \sum_{e\in P} c_e^*(f_e).

Example: $c(x) = ax^p$ gives $c^*(x) = (p+1)ax^p$ .

IntuitionTwo terms, two audiences

$c_e(x)$ is what the marginal user pays itself. The term $x\,c_e'(x)$ is the extra delay it imposes on the $x$ units already there. A selfish user sees only the first term.

PropositionProposition 18.9 — characterization of optimal flows

$f^*$ is optimal iff for every $i$ and all $P, \tilde P \in \mathcal{P}_i$ with $f^*_P > 0$ : $c_P^*(f^*) \le c_{\tilde P}^*(f^*)$ .

NoteProof omitted

These are the first-order (KKT) conditions for a convex program with nonnegativity constraints (Bertsekas 1999, ch. 2).

CorollaryCorollary 18.10 — optimal = equilibrium for marginal costs

$f^*$ is optimal for $(G,r,c)$ iff it is an equilibrium flow for $(G, r, c^*)$ .

Instance	Marginal costs	Optimal flow from “equilibrium for $c^*$ “
Pigou	$1$ and $2x$	equalize at 1: split $1/2, 1/2$
nonlinear Pigou	$1$ and $(p+1)x^p$	$(p+1)^{-1/p}$ on the lower edge
Braess (b)	$2x$ on the cost- $x$ edges	half on each outer route; all three paths have marginal cost 2

The Beckmann potential

Invert Corollary 18.10. We want a function whose minimizers are equilibria. Replace $x\,c_e(x)$ by some $h_e$ with $h_e' = c_e$ , i.e. $h_e(x) = \int_0^x c_e(y)\,dy$ . This is convex and $C^1$ automatically, since $c_e$ is continuous and nondecreasing.

FormulaNonatomic potential function

$\Phi(f) = \sum_{e\in E}\int_0^{f_e} c_e(x)\,dx. \tag{18.3}$

Component	Detail
Signature	$\Phi : \{\text{feasible flows}\} \to \mathbb{R}_{\ge0}$
Domain	a routing of all traffic
Codomain	the “area under each edge’s cost curve up to its load”
Compare	cost $C$ charges every unit on $e$ the final cost $c_e(f_e)$ ; $\Phi$ charges the $x$ -th unit the cost $c_e(x)$ it saw on arrival

PropositionProposition 18.11 — equilibria minimize $\Phi$

A feasible flow is an equilibrium iff it is a global minimum of $\Phi$ .

ProofProposition 18.9 applied to

h_e

Apply Proposition 18.9 with $x\,c_e(x)$ replaced by $h_e(x) = \int_0^x c_e$ , which is convex and $C^1$ . Its “marginal cost” is $h_e' = c_e$ , so the optimality condition for $\Phi$ reads “used paths minimize $c_P$ ,” which is exactly Definition 18.1.

∎

TheoremTheorem 18.8 — existence and essential uniqueness

For every nonatomic instance:

(a) an equilibrium flow exists;
(b) if $f, \tilde f$ are equilibria, then $c_e(f_e) = c_e(\tilde f_e)$ for every edge.

Hence all equilibria have equal cost, and PoA = PoS.

ProofWeierstrass for existence; convexity for uniqueness

Step 1: Existence. Feasible flows form a compact subset of $\mathbb{R}^{|\mathcal{P}|}$ , and $\Phi$ is continuous. By Weierstrass, $\Phi$ attains its minimum, which is an equilibrium by Proposition 18.11.

Step 2: $\Phi$ is convex. Each summand $\int_0^{f_e} c_e$ is convex because $c_e$ is nondecreasing.

Step 3: The chord between two minimizers is flat. For equilibria $f, \tilde f$ , every $\lambda f + (1-\lambda)\tilde f$ is feasible, and

\Phi(\lambda f + (1-\lambda)\tilde f) \le \lambda\Phi(f) + (1-\lambda)\Phi(\tilde f). \tag{18.4}

Both endpoints are global minima, so equality must hold for all $\lambda$ .

The key step: a sum of convex functions is linear along a segment only if each summand is. So each $\int_0^x c_e$ is linear between $f_e$ and $\tilde f_e$ , which forces $c_e$ to be constant there. So $c_e(f_e) = c_e(\tilde f_e)$ .

∎

WarningUniqueness is of costs, not flows

Two equilibria can route traffic differently. What is unique is every edge’s cost, and hence every path cost and the total cost.

Atomic existence: the Rosenthal potential

The AAE example rules out uniqueness, and Example 18.7 rules out existence in general. There are two escapes: restrict the instances (here), or relax the equilibrium concept (Remark 18.26).

TheoremTheorem 18.12 — unweighted atomic instances have equilibria

If every $r_i$ equals a common $R > 0$ , an equilibrium flow exists.

FormulaRosenthal’s potential (take $R = 1$ )

$\Phi_a(f) = \sum_{e\in E}\sum_{i=1}^{f_e} c_e(i). \tag{18.5}$ This is the discrete version of (18.3): the integral becomes a sum over the “arrival order” of units on each edge.

ProofThe potential exactly tracks a deviator’s cost change

Step 1: A minimizer exists. Finitely many players with finitely many paths give finitely many flows. Let $f$ minimize $\Phi_a$ .

Step 2: Suppose a profitable deviation. Player $i$ moves from $P$ to $\tilde P$ , producing $\tilde f$ with

0 > c_{\tilde P}(\tilde f) - c_P(f) = \sum_{e\in\tilde P\setminus P} c_e(f_e + 1) - \sum_{e\in P\setminus\tilde P} c_e(f_e). \tag{18.6}

Shared edges $P \cap \tilde P$ cancel.

Step 3: Compute $\Phi_a(\tilde f) - \Phi_a(f)$ . Edges in $\tilde P\setminus P$ gain the term $c_e(f_e+1)$ , edges in $P\setminus\tilde P$ lose the term $c_e(f_e)$ , and shared edges are unchanged. That is exactly the right side of (18.6).

The key step: so $\Phi_a(\tilde f) < \Phi_a(f)$ , contradicting minimality.

∎

RemarkRemark 18.13 — an exact potential

For every flow, player and deviation, the change in the deviator’s cost equals the change in $\Phi_a$ . So best-response dynamics strictly lower $\Phi_a$ and must terminate at an equilibrium. This is the defining property of potential games (Monderer–Shapley); more in Chapter 19.

RemarkRemark 18.14 — monotonicity not used

The proof never uses nondecreasing costs. This matters for network design games (Chapter 19), which are atomic routing games with decreasing per-user costs.

TheoremTheorem 18.15 — affine atomic instances have equilibria

With affine costs $c_e(x) = a_e x + b_e$ ( $a_e, b_e \ge 0$ ), equilibria exist even when weighted.

NoteExercise 18.4

Same outline as Theorem 18.12, with a variant potential. Proved for weighted affine instances by Fotakis et al. (2005).

The price of anarchy: nonatomic

Headline: the PoA depends on the nonlinearity of the cost functions and nothing else: not network size, not topology, not the number of commodities. For any class of costs, the worst network is one that best imitates Pigou.

A first bound from the potential

TheoremTheorem 18.16 — potential function upper bound

If $x\,c_e(x) \le \gamma \int_0^x c_e(y)\,dy$ for all $e$ and $x \ge 0$ , then PoA $\le \gamma$ .

ProofSandwich cost between potential and

\gamma\times

potential

Let $f$ be an equilibrium and $f^*$ optimal.

C(f) \overset{(a)}{\le} \gamma\,\Phi(f) \overset{(b)}{\le} \gamma\,\Phi(f^*) \overset{(c)}{\le} \gamma\,C(f^*).

(a) The hypothesis, edge by edge.
(b) $f$ minimizes $\Phi$ (Proposition 18.11).
(c) $\int_0^x c_e \le x\,c_e(x)$ because $c_e$ is nondecreasing.

∎

IntuitionApproximately optimizing the right thing

Equilibria exactly optimize $\Phi$ . If $\Phi$ is within $\gamma$ of the true cost $C$ , equilibria are within $\gamma$ of optimal.

CorollaryCorollary 18.17 — polynomials

For polynomial costs with nonnegative coefficients and degree $\le p$ , $x\,c(x) \le (p+1)\int_0^x c$ , so PoA $\le p+1$ .

WarningNot tight

Example 18.3 gives only about $p/\ln p$ , so the bound is off by a $\ln p$ factor. Closing the gap needs a different technique.

The Pigou bound

DefinitionDefinition 18.18 — Pigou bound

For a nonempty class $\mathcal{C}$ of cost functions,

\alpha(\mathcal{C}) = \sup_{c\in\mathcal{C}}\ \sup_{x,r\ge0} \frac{r\cdot c(r)}{x\cdot c(x) + (r-x)\,c(r)}, \tag{18.7}

with $0/0 = 1$ .

IntuitionReading (18.7) as a two-link network

Rate $r$ travels over a link with cost $c$ , next to a parallel link with constant cost $c(r)$ . The numerator is the equilibrium, where everyone uses $c$ and pays $c(r)$ . The denominator is the alternative that puts only $x$ on $c$ and the other $r-x$ on the constant link. $\alpha$ is the worst Pigou-like ratio.

PropositionProposition 18.19 — the Pigou bound is a lower bound

If $\mathcal{C}$ contains all constant functions, nonatomic instances with costs in $\mathcal{C}$ have PoA arbitrarily close to $\alpha(\mathcal{C})$ .

ProofBuild the two-link network

Fix $c\in\mathcal{C}$ and $x, r$ . If $x \ge r$ , the ratio is $\le 1$ (since $c$ is nondecreasing), so assume $x < r$ . Take two parallel $s$ – $t$ edges with costs $c(y)$ and the constant $c(r)$ , and traffic $r$ .

All traffic on the $c$ -edge is an equilibrium, with cost $r\,c(r)$ : the alternative costs the same $c(r)$ .
Putting $x$ on the $c$ -edge and $r - x$ on the constant edge costs $x\,c(x) + (r-x)c(r)$ .

So PoA is at least the ratio. Take the supremum.

∎

NoteWeaker hypothesis suffices

The conclusion holds whenever $\mathcal{C}$ is inhomogeneous, meaning $c(0) > 0$ for some $c$ (Exercise 18.5).

The variational inequality

PropositionProposition 18.20 — variational inequality

A feasible $f$ is an equilibrium iff for every feasible $f^*$ : $\sum_{e\in E} c_e(f_e)\,f_e \le \sum_{e\in E} c_e(f_e)\,f_e^*.$

ProofFreeze the edge costs at their equilibrium values

Step 1: Define a linear cost. $H_f(f^*) = \sum_i\sum_{P\in\mathcal{P}_i} c_P(f)\,f_P^* = \sum_e c_e(f_e)\,f^*_e$ . This is the cost of $f^*$ when each edge’s cost is frozen at the constant $c_e(f_e)$ .

Step 2: Restate the claim. By the second form, the proposition says: $f$ is an equilibrium iff $f$ minimizes $H_f$ .

Step 3: Minimizers of a linear cost. With constant costs, $f^*$ minimizes $H_f$ iff each commodity’s traffic uses only paths minimizing $c_P(f)$ . Applied to $f^*=f$ , that is exactly Definition 18.1.

∎

IntuitionWhat the inequality says

An equilibrium is optimal for the frozen costs it creates. Once congestion is fixed at equilibrium levels, no rerouting can beat it.

Tightness

TheoremTheorem 18.21 — the Pigou bound is tight

Every nonatomic instance with costs in $\mathcal{C}$ has PoA $\le \alpha(\mathcal{C})$ .

ProofPer-edge Pigou bound, then the variational inequality

Let $f^*$ be optimal and $f$ an equilibrium.

Step 1: Apply (18.7) edge by edge with $x = f^*_e$ and $r = f_e$ :

c_e(f^*_e)\,f^*_e \ge \frac{c_e(f_e)f_e}{\alpha(\mathcal{C})} + (f^*_e - f_e)\,c_e(f_e).

Step 2: Sum over edges.

C(f^*) \overset{(a)}{\ge} \frac{1}{\alpha(\mathcal{C})}\sum_e c_e(f_e)f_e + \sum_e (f^*_e - f_e)\,c_e(f_e) \overset{(b)}{\ge} \frac{C(f)}{\alpha(\mathcal{C})}.

(a) Step 1 summed.
(b) The variational inequality (Proposition 18.20): the second sum is $\ge 0$ .

The key step: the variational inequality lets the per-edge Pigou inequalities, each of which only knows about one edge, be summed into a network-wide bound.

∎

ImportantPigou-like examples are the worst case

Propositions 18.19 and 18.21 together: for essentially every class of costs, the worst PoA over all multicommodity networks is achieved by a two-link Pigou-like network.

Cost class $\mathcal{C}$	$\alpha(\mathcal{C})$	Extremal example
affine $ax + b$	$4/3$	Pigou (Ex. 17.1)
polynomials, degree $\le p$ , nonnegative coefficients	$\big[1 - p\,(p+1)^{-(p+1)/p}\big]^{-1} \approx p/\ln p$	nonlinear Pigou (Ex. 18.3)

NoteComputing $\alpha$ is left as exercises

The affine value $4/3$ is Exercise 18.6. The chapter states the polynomial formula without derivation.

CorollaryRemark 18.22 — how bad can Braess get?

After adding edges, the old equilibrium is a feasible flow in the new network. So new-equilibrium / old-equilibrium $\le$ PoA of the new network. With affine costs this is $\le 4/3$ : adding edges can raise equilibrium cost by at most a factor $4/3$ , and Example 18.4 is the worst case. The same holds for the physical analogues.

The price of anarchy: atomic

WarningThe potential function method fails here

Theorem 18.16’s argument is about one equilibrium, the minimizer of the potential. When equilibria are non-unique (AAE), that bounds the price of stability, not the price of anarchy.

The substitute is a per-player version of the variational inequality: each player’s equilibrium path is no worse than its optimal path, counting its own added traffic. The analysis is done for affine costs.

TheoremTheorem 18.23 — affine atomic PoA

Atomic instances with affine costs have PoA $\le (3+\sqrt5)/2 \approx 2.618$ .

NoteTightness (exercises)

A weighted AAE variant shows $(3+\sqrt5)/2$ is tight (Exercise 18.2(a)).
For unweighted instances, a variant of the proof gives $5/2$ , matching AAE (Exercise 18.7).

LemmaLemma 18.24 — equilibrium condition

With $c_e(x) = a_e x + b_e$ , equilibrium $f$ (player $i$ on $P_i$ ) and optimal $f^*$ (player $i$ on $P_i^*$ ):

\sum_{e\in P_i}[a_e f_e + b_e] \le \sum_{e\in P_i^*}[a_e(f_e + r_i) + b_e]. \tag{18.8}

IntuitionWhy " $+r_i$ "

If $i$ switched to $P^*_i$ , its own $r_i$ would be added to edges it doesn’t already use. On shared edges the load stays $f_e$ , which is $\le f_e + r_i$ , so the bound still holds.

LemmaLemma 18.25 — equilibrium inequality

$C(f) \le C(f^*) + \sum_{e\in E} a_e\, f_e\, f^*_e. \tag{18.9}$

ProofWeight by traffic, sum, swap order

C(f) \overset{(a)}{\le} \sum_{i} r_i \sum_{e\in P_i^*}[a_e(f_e+r_i)+b_e] \overset{(b)}{\le} \sum_i r_i\sum_{e\in P_i^*}[a_e(f_e + f^*_e) + b_e] \overset{(c)}{=} \sum_{e} f^*_e\,[a_e(f_e + f^*_e) + b_e].

(a) Multiply (18.8) by $r_i$ and sum; the left side becomes $\sum_i r_i c_{P_i}(f) = C(f)$ .
(b) $r_i \le f^*_e$ for $e \in P^*_i$ , since $i$ ‘s own traffic is part of $f^*_e$ .
(c) Swap sums: $\sum_{i: e\in P^*_i} r_i = f^*_e$ .

The last expression is $\sum_e a_e f_e f^*_e + C(f^*)$ .

∎

ProofTheorem 18.23 — Cauchy–Schwarz on the error term

Step 1: Bound the cross term. Apply Cauchy–Schwarz to the vectors $(\sqrt{a_e}f_e)_e$ and $(\sqrt{a_e}f^*_e)_e$ :

\sum_e a_e f_e f^*_e \le \sqrt{\textstyle\sum_e a_e f_e^2}\, \sqrt{\textstyle\sum_e a_e (f^*_e)^2} \le \sqrt{C(f)}\,\sqrt{C(f^*)},

using $b_e \ge 0$ , so $a_e x^2 \le c_e(x)\,x$ .

Step 2: Combine with (18.9) and divide by $C(f^*)$ . Writing $\rho = C(f)/C(f^*)$ : $\rho - 1 \le \sqrt{\rho}.$

Step 3: Solve. For $\rho \ge 1$ , squaring gives $\rho^2 - 3\rho + 1 \le 0$ , so $\rho \le (3+\sqrt5)/2$ .

∎

WarningAtomic PoA explodes with degree

For degree- $p$ polynomial costs, the atomic PoA grows roughly like $p^p$ , exponential rather than about $p/\ln p$ . Nearly matching lower bounds exist, so this is not an artifact of the proof (Awerbuch et al.; Olver).

RemarkRemark 18.26 — when equilibria may not exist

For polynomial costs, the $p^{O(p)}$ bound extends three ways:

to all pure equilibria when they exist;
to mixed Nash equilibria, which always exist by Nash’s theorem, in expected cost;
to sink equilibria, which always exist in finite games and are motivated by best-response dynamics (Goemans et al.).

NoteAtomic splittable model (open)

If players may split their $r_i$ fractionally, each internalizes its own congestion but not others’. A single player controlling everything routes optimally. Equilibria can be counterintuitive (Exercise 18.9). Early claims that nonatomic bounds carry over were refuted in multicommodity networks (Cominetti et al.). Tight bounds are open.

Reducing the price of anarchy

With highly nonlinear costs the PoA is large. Can modest intervention, short of imposing the optimum, fix this? (This is the design question from inefficiency-of-equilibria.)

Marginal cost pricing

Add a nonnegative tax $\tau_e$ on each edge. Users minimize cost plus tax, so an equilibrium of $(G, r, c+\tau)$ is an equilibrium of $(G,r,c^\tau)$ with $c_e^\tau(x) = c_e(x) + \tau_e$ .

DefinitionMarginal cost (Pigouvian) tax

For a flow $f$ and differentiable costs, set $\tau_e = f_e\,c_e'(f_e)$ .

$c_e'(f_e)$ is the extra delay one more user causes each user of $e$ ;
$f_e$ is how many users suffer it.

This is exactly the term $x\,c_e'(x)$ that selfish users omit from the marginal cost $c_e^*$ .

TheoremTheorem 18.27 — marginal cost taxes induce the optimum

If each $x\,c_e(x)$ is convex and $C^1$ , $f^*$ is optimal, and $\tau_e = f^*_e\,c_e'(f^*_e)$ , then $f^*$ is an equilibrium of $(G, r, c+\tau)$ . So PoA becomes 1.

ProofImmediate from Corollary 18.10

At $f^*$ , $c_e(f^*_e) + \tau_e = c_e^*(f^*_e)$ . By Corollary 18.10, $f^*$ is an equilibrium for the costs $c^*$ . With taxed costs, path costs at $f^*$ coincide with marginal path costs, so the same equilibrium conditions hold at $f^*$ .

∎

NoteWeaker hypotheses

The theorem holds without the convexity assumption. More on pricing in Chapter 22.

RemarkExternality pricing again

Charging each user the harm it imposes on others is the same principle as the Clarke pivot in VCG (mechanism-design), here applied to delay.

Capacity augmentation

The PoA is unbounded for general costs (Example 18.3). A different kind of bound still holds for arbitrary costs.

ExampleExample 18.28 — nonlinear Pigou at double traffic

With $r > 1$ , the optimum sends the extra $r - 1$ over the constant edge, at a cost tending to $r - 1$ . At $r = 2$ , the optimum costs at least 1 for every $p$ , which is the equilibrium cost at $r = 1$ .

TheoremTheorem 18.29 — equilibrium beats optimum at double traffic

If $f$ is an equilibrium for $(G, r, c)$ and $f^*$ is feasible for $(G, 2r, c)$ , then $C(f) \le C(f^*)$ .

ProofInflate costs to at least their equilibrium values

Let $d_i$ be the cheapest $s_i$ – $t_i$ path cost under $f$ . By Definition 18.1, $C(f) = \sum_i r_i d_i$ .

Step 1: Modified costs. Set $\bar c_e(x) = \max\{c_e(f_e), c_e(x)\}$ and write $\bar C$ for cost under $\bar c$ . Then $\bar C(f) = C(f)$ and $\bar C(f^*) \ge C(f^*)$ .

Step 2: The inflation is cheap. $\bar c_e(x) - c_e(x)$ is 0 for $x \ge f_e$ and at most $c_e(f_e)$ for $x < f_e$ . So $x(\bar c_e(x) - c_e(x)) \le c_e(f_e) f_e$ for all $x$ , and

\bar C(f^*) - C(f^*) = \sum_e f^*_e(\bar c_e(f^*_e) - c_e(f^*_e)) \le \sum_e c_e(f_e)f_e = C(f). \tag{18.10}

Step 3: Under $\bar c$ , every path costs at least $d_i$ . Since $\bar c_e \ge c_e(f_e)$ , we get $\bar c_P(\cdot) \ge c_P(f) \ge d_i$ for $P\in\mathcal{P}_i$ . So

\bar C(f^*) = \sum_P \bar c_P(f^*)f^*_P \ge \sum_i d_i\sum_{P\in \mathcal{P}_i} f^*_P = \sum_i 2r_i d_i = 2C(f). \tag{18.11}

The key step: combining, $2C(f) \le \bar C(f^*) \le C(f^*) + C(f)$ , so $C(f) \le C(f^*)$ .

∎

CorollaryCorollary 18.30 — faster links beat central control

Let $\tilde c_e(x) = c_e(x/2)/2$ . The equilibrium cost for $(G, r, \tilde c)$ is at most the optimal cost for $(G, r, c)$ . This is equivalent to Theorem 18.29 (Exercise 18.8(a)).

ExampleM/M/1 delays: just double capacity

For $c_e(x) = 1/(u_e - x)$ (infinite for $x \ge u_e$ ), $\tilde c_e(x) = \frac{1}{2(u_e - x/2)} = \frac{1}{2u_e - x}.$ This is the M/M/1 function with capacity $2u_e$ . Design principle: to outperform optimal routing, double every edge’s capacity.

NoteScope

A counterexample to Theorem 18.29 in atomic instances is in Roughgarden (2005a). Refinements for restricted cost classes are in Chakrabarty (2004) and Correa et al. (2005).

Quick reference

Object	Statement	Note
Nonatomic instance	$(G, r, c)$ ; flows on paths; $\sum_{\mathcal{P}_i} f_P = r_i$	costs nonnegative, continuous, nondecreasing
Equilibrium (Def 18.1)	used paths are cheapest	Wardrop equilibrium
Cost (18.1–18.2)	$\sum_P c_P f_P = \sum_e c_e(f_e)f_e$	utilitarian
Nonlinear Pigou (Ex. 18.3)	PoA $\to\infty$ , about $p/\ln p$	Exercise 18.1
Braess (Ex. 18.4)	free edge: $3/2 \to 2$ for everyone	PoA $4/3$ in new network
Atomic equilibrium (Def 18.5)	no player gains by moving its $r_i$	pure Nash
AAE (Ex. 18.6)	equilibria of cost 4 and 10	affine PoA $\ge 5/2$
Ex. 18.7	weighted atomic, no pure equilibrium	best responses cycle
Marginal cost	$c^*_e = c_e + x c_e'$	$ax^p \mapsto (p+1)ax^p$
Prop 18.9 / Cor 18.10	optimal for $c$ ⟺ equilibrium for $c^*$	KKT
Beckmann potential (18.3)	$\Phi = \sum_e\int_0^{f_e}c_e$	equilibria = global minima (Prop 18.11)
Thm 18.8	existence; $c_e(f_e)$ equal across equilibria	PoA = PoS
Rosenthal potential (18.5)	$\Phi_a = \sum_e\sum_{i=1}^{f_e} c_e(i)$	exact potential; unweighted existence (Thm 18.12)
Thm 18.15	affine atomic, even weighted, has equilibria	Exercise 18.4
Thm 18.16	$x c(x) \le \gamma\int_0^x c$ ⇒ PoA $\le\gamma$	polynomials: $\le p+1$ (Cor 18.17)
Pigou bound (18.7)	$\sup \frac{r c(r)}{x c(x) + (r-x)c(r)}$	lower bound (Prop 18.19)
Variational inequality (Prop 18.20)	$\sum c_e(f_e)f_e \le \sum c_e(f_e)f^*_e$	equilibrium optimal for frozen costs
Thm 18.21	nonatomic PoA $\le \alpha(\mathcal{C})$ , tight	independent of topology
$\alpha$ values	affine $4/3$ ; degree $p$ : $[1-p(p+1)^{-(p+1)/p}]^{-1}$	Pigou / nonlinear Pigou extremal
Remark 18.22	affine Braess increase $\le 4/3$	Ex. 18.4 is worst
Lemma 18.24	$c_{P_i}(f) \le \sum_{P^*_i}[a(f+r_i)+b]$	per-player deviation
Lemma 18.25	$C(f) \le C(f^) + \sum a_e f_e f^_e$
Thm 18.23	affine atomic PoA $\le (3+\sqrt5)/2$	tight weighted; $5/2$ unweighted
Atomic polynomial PoA	about $p^p$	exponential; tight up to lower-order terms
Remark 18.26	extends to mixed and sink equilibria
Pigouvian tax (Thm 18.27)	$\tau_e = f^_e c_e'(f^_e)$ induces $f^*$	PoA $\to 1$
Thm 18.29	eq. cost at $r$ $\le$ opt. cost at $2r$	any costs, nonatomic only
Cor 18.30	$\tilde c(x) = c(x/2)/2$ equilibrium $\le$ optimum	M/M/1: double capacity

Facts to keep to hand

Equilibrium and optimum are the same object for different costs. Equilibria are optimal for $c$ with the externality term removed, and optimal flows are equilibria for $c^* = c + x c'$ . Pigouvian taxes add back exactly the missing term, and the potential $\int c$ is what you get by integrating $c$ instead of differentiating $x\,c$ .
Every nonatomic PoA bound follows one recipe: the variational inequality (equilibrium is optimal for frozen costs) plus a per-edge inequality ((18.7) or the potential sandwich). The network enters only through the variational inequality, which is why topology never matters.
Every atomic PoA bound follows another: a per-player deviation inequality with " $+r_i$ ", weighted by $r_i$ and summed (Lemma 18.25), then Cauchy–Schwarz to control the cross term $\sum a_e f_e f^*_e$ .
Potential functions give existence and PoS, not PoA. In nonatomic games they coincide because the potential is convex and equilibria are essentially unique. In atomic games they don’t.
Atomicity costs a lot. Affine: $4/3 \to 5/2$ or $2.618$ . Degree $p$ : about $p/\ln p \to p^p$ . Existence can fail, uniqueness always can, and capacity augmentation fails.
The worst case is always small. Nonatomic: two parallel links (Pigou). Atomic affine: a triangle (AAE). Braess’s Paradox is bounded by the same $4/3$ as Pigou.
Two cheap fixes, both nonatomic. Tax the externality, which gives the exact optimum. Or double the capacity (twice the traffic, or $c(x/2)/2$ ), which beats optimal routing for any cost functions.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 18 (Roughgarden)

Related

Motivation: routing without a central authority

Nonatomic selfish routing

Two warning examples

Atomic selfish routing

Existence and essential uniqueness

Optimal flows are equilibria for marginal costs

The Beckmann potential

Atomic existence: the Rosenthal potential

The price of anarchy: nonatomic

A first bound from the potential

The Pigou bound

The variational inequality

Tightness

The price of anarchy: atomic

Reducing the price of anarchy

Marginal cost pricing

Capacity augmentation

Quick reference

References

Mentioned in