The Inefficiency Of Equilibria

Motivation: how bad is selfishness, exactly?

Parts I and II showed many times that self-interested behaviour can be worse than a centrally designed outcome. This part of the book asks: by how much?

Start with the Prisoner’s Dilemma. In the unique Nash equilibrium each player pays 4; by coordinating, each could pay 2. There are two ways to say this is inefficient:

Perspective	Statement	When it fits
qualitative	the equilibrium is strictly Pareto inefficient: another outcome is better for everyone	costs only encode preferences; no meaningful units
quantitative	fix an objective function on outcomes and compare values	costs are concrete: money, network delay

Two standard objective functions:

• utilitarian: minimize the sum of players’ costs (or maximize the sum of payoffs);
• egalitarian: minimize the maximum player cost.

The Prisoner’s Dilemma equilibrium optimizes neither.

---

Measuring inefficiency: five modeling choices

Every measure of “the inefficiency of a game’s equilibria” is roughly a ratio: the objective value at equilibrium over the objective value at optimum. To make that precise you must answer five questions:

#	Question	Default answer in this part
1	How are payoffs/costs expressed?	concrete payoffs to maximize (money) or costs to minimize (delay)
2	Which objective compares outcomes?	mostly utilitarian; egalitarian in scheduling (below)
3	What does “approximately optimal” mean?	the ratio of objective values
4	What counts as an equilibrium?	Nash equilibria and their analogues for infinitely many players or strategies
5	Which equilibrium, if several?	the worst (price of anarchy) or the best (price of stability)

An outcome is optimal if it optimizes the chosen objective. In the Prisoner’s Dilemma, mutual cooperation is optimal for both objectives.

---

Price of anarchy and price of stability

The problem. A game can have several equilibria with different objective values, as in coordination games. Which one should be compared to the optimum?

Two reasons to study the weaker PoS anyway:

1. Sometimes it is the only nontrivial bound. Shapley network design has PoA $\approx k$ but PoS $\le H_k$; see Shapley network design: why PoS matters.
2. It has a natural design reading. In networking, agents usually interact with a protocol that proposes a collective solution, which each can accept or defect from. The designer would propose the best equilibrium. So PoS measures what stability costs a well-meaning designer.

---

Selfish routing: Pigou’s example

Setup. A large population of drivers each picks an $s$–$t$ route. Each edge’s cost (travel time) depends on how much traffic uses it.

graph LR
  S["s"] -->|"upper: cost 1, constant"| T["t"]
  S -->|"lower: cost x, congestible"| T

Equilibrium. The lower edge is a dominant strategy: its cost is at most 1 whatever others do. So everyone takes it, and everyone pays 1. Average cost is 1.

Optimum. Minimize average cost over the split.

DerivationOptimal split in Pigou’s example

Step 1: Write the average cost. Put $x$ on the lower edge and $1-x$ on the upper edge: $$C(x) = x \cdot x + (1-x)\cdot 1 = x^2 - x + 1.$$

Step 2: Minimize. $C'(x) = 2x - 1 = 0$ gives $x = 1/2$, and $C(1/2) = 3/4$.

Reading: half the drivers take the slow road so the other half enjoy an uncongested fast road at cost $1/2$.

General selfish routing allows an arbitrary directed graph, different source–destination pairs, and edge costs that are nonnegative, continuous and nondecreasing.

---

Shapley network design: why PoS matters

graph LR
  S["s: k players"] -->|"cost k"| T["t"]
  S -->|"cost 1 + eps"| T

graph BT
  S1["s1"] -->|"1"| T["t"]
  S2["s2"] -->|"1/2"| T
  SK["sk"] -->|"1/k"| T
  S1 -->|"0"| V["v"]
  S2 -->|"0"| V
  SK -->|"0"| V
  V -->|"1 + eps"| T

ProofThe direct-path profile is the unique Nash equilibrium

Step 1: The optimum is unstable. With all $k$ players through $v$, player $k$ pays $(1+\epsilon)/k$. Its direct edge costs $1/k$, which is cheaper.

Step 2: The direct path is dominant for player $k$. Whatever others do, the route via $v$ costs player $k$ at least $(1+\epsilon)/k$, since at most $k$ players share $(v,t)$. That exceeds $1/k$.

Step 3: Backward induction. Suppose players $k, k-1, \dots, j+1$ all go direct. Then at most $j$ players can share $(v,t)$, so the route via $v$ costs player $j$ at least $(1+\epsilon)/j > 1/j$. Going direct is strictly better for player $j$ as well.

Step 4: Cost of the equilibrium. Everyone direct costs $\sum_i 1/i = H_k$. Since it is the only equilibrium, $\mathrm{PoS} = H_k/(1+\epsilon) \to H_k$.

∎

---

Scheduling: equilibrium concept and objective both matter

Setup. There are $m$ identical jobs (players) and $m$ identical machines (strategies). Each job wants to minimize the number of jobs on its machine, counting itself.

• Pure Nash equilibria: exactly the $m!$ outcomes with one job per machine.
• Egalitarian objective, makespan: minimize the load of the most crowded machine. The optima coincide with the pure equilibria, all with makespan 1.

So with pure equilibria, $\mathrm{PoA} = 1$. Mixed equilibria change the picture.

ProofUniform randomization is an equilibrium

Step 1: Player 1’s cost on machine $j$. Let $X_{ij}$ indicate that player $i$ picks machine $j$. Choosing $j$ costs $1 + \sum_{i>1} X_{ij}$.

Step 2: Take expectations. By linearity of expectation, $$1 + \sum_{i>1}\mathbb{E}[X_{ij}] = 1 + \frac{m-1}{m} = 2 - \frac1m.$$

The key step: this is the same for every machine. So every pure strategy is a best response, and hence so is every mixture, including uniform. By symmetry the same holds for every player.

∎

So in the same game, with makespan as the objective, the two equilibrium concepts give very different answers:

Equilibrium concept	PoA (makespan)
pure Nash	$1$
mixed Nash	$\Theta(\log m / \log\log m)$

The objective matters too. Three objectives agree on pure profiles but not on mixed ones:

Objective	Optimum	Uniform mixed NE	PoA
expected makespan $\mathbb{E}[\max_j \text{load}_j]$	1	$\Theta(\log m/\log\log m)$	$\Theta(\log m/\log\log m)$
utilitarian: expected sum of costs	$m$	$m(2 - 1/m) = 2m-1$	$2 - 1/m$
maximum expected cost of a player	1	$2 - 1/m$	$2 - 1/m$

---

Resource allocation: proportional sharing

Setup. One divisible resource, such as the bandwidth $C > 0$ of a link, is shared by $n > 1$ players. Player $i$ has a concave, strictly increasing, continuously differentiable utility $U_i$. An outcome is an allocation $x \ge 0$ with $\sum_i x_i = C$. The objective is utilitarian: maximize $\sum_i U_i(x_i)$.

Component	Detail
Signature	$Q_i : \mathbb{R}^n_{\ge 0} \to \mathbb{R}$
Domain	the full bid vector; $i$ controls only $b_i$
Codomain	$i$’s utility for its share, minus its bid
Not an input	anyone’s utility function; the mechanism never sees $U_i$

DerivationSolving for the equilibrium allocation

Let $B = \sum_j b_j$. At least two bids are positive (Exercise 17.5).

Step 1: First-order condition for player 1. $Q_1 = 2b_1/B - b_1$, so $$\frac{\partial Q_1}{\partial b_1} = \frac{2(B - b_1)}{B^2} - 1 = 0.$$ Strict concavity makes this the maximizer.

Step 2: First-order condition for each $i \ge 2$. $(B - b_i)/B^2 = 1$.

Step 3: Subtract. $2(B - b_1) = B - b_i$, so $2b_1 - b_i = B$ for every $i = 2,\dots,n$.

Step 4: Sum the $n-1$ equations. $2(n-1)b_1 - (B - b_1) = (n-1)B$, which gives $$b_1 = \frac{n}{2n-1}\,B.$$

Step 5: Evaluate. Player 1 gets fraction $\frac{n}{2n-1}$, and the others share $\frac{n-1}{2n-1}$. The welfare is

$$2\cdot\frac{n}{2n-1} + \frac{n-1}{2n-1} = \frac{3n-1}{2n-1} \;\to\; \frac32,$$

which is a $\frac{3n-1}{2(2n-1)} \to \frac34$ fraction of the optimum 2.

---

Inefficiency as a design metric

So far each game was given, and we measured its equilibria. The same framework asks a design question: how should we build or modify a game to minimize the inefficiency of its equilibria? This matters most when equilibria are bad but imposing the optimum directly is impractical.

Typical questions:

• Within a class of mechanisms, which one has the best PoA, and what is that PoA?
• Given limited levers on an existing game, which one improves PoA most, and by how much?

These are the goals of algorithmic mechanism design (mechanism-design), but the work differs technically in three ways:

Part II (AMD)	Inefficiency-as-design
strategyproof mechanisms; truth is dominant	equilibria of non-strategyproof mechanisms (e.g. bids $\ne$ utility functions; no dominant strategy)
private preferences are the obstacle	sometimes no private information; the obstacle is lack of control (e.g. pricing edges in selfish routing)
design from scratch	leverage limited power to improve a given game

Proportional sharing is optimal among simple mechanisms

Can we beat 3/4? It depends on which mechanisms are allowed.

Mechanism	PoA	Communication to the mechanism	Communication back
VCG variant	$1$	an entire utility function per player	different effective prices for different players
proportional sharing	$\ge 3/4$	one bid per player	one price $p = B/C$; each gets $x_i = b_i/p$

Other design results

Model	Lever	Result
selfish routing	edge pricing; routing a small fraction of traffic centrally	minimize PoA with limited design power (Roughgarden 2005)
network design	choice of cost-sharing method	among network-oblivious methods, Shapley sharing minimizes worst-case PoS; topology-aware methods can beat it (Chen et al.)
scheduling	machine scheduling policies that prioritize jobs	PoA falls from logarithmic in $m$ to a small constant (Christodoulou et al.; Immorlica et al.)

---

Quick reference

Object	Statement	Note
Pareto inefficiency	another outcome is better for all	qualitative
Utilitarian / egalitarian	sum / max of costs	the two main objectives
Inefficiency ratio	equilibrium value / optimal value	$c/0 = 1$ or $\infty$
Five modeling choices	costs; objective; ratio; equilibrium concept; which equilibrium
PoA	worst equilibrium / optimum	depends on objective and concept
PoS	best equilibrium / optimum	$1 \le \mathrm{PoS} \le \mathrm{PoA}$ (minimization)
Prisoner’s Dilemma	utilitarian ratio $8/4 = 2$	unbounded if scaled
Pigou (Ex. 17.1)	equilibrium cost 1, optimum $3/4$	PoA $=$ PoS $= 4/3$
Selfish routing (Ch. 18)	essential uniqueness; affine PoA $\le 4/3$	arbitrary costs: unbounded (Ex. 17.1)
Shapley network design	equal split of each edge among its users	pure NE always exist (Ch. 19)
Ex. 17.2	parallel edges $k$ and $1+\epsilon$	PoA $\approx k$, PoS $= 1$
Ex. 17.3	direct edges $1/i$ vs shared $1+\epsilon$	PoS $\to H_k \approx \ln k$; tight (Ch. 19)
Load balancing	$m$ jobs, $m$ machines	pure NE = $m!$ permutations
Mixed NE value	expectation of objective under the product distribution
Ex. 17.4	uniform random is NE; expected cost $2 - 1/m$ each
Balls into bins	$\mathbb{E}[\max \text{load}] = \Theta(\log m/\log\log m)$	makespan PoA with mixed NE
Utilitarian PoA (Ex. 17.4)	$(2m-1)/m = 2 - 1/m$	worst equilibrium: Ex. 17.3
Max expected cost PoA	$2 - 1/m$	hides the collisions
Proportional sharing (17.1)	$x_i = b_i C / \sum_j b_j$, pay $b_i$	Kelly
Ex. 17.6	$b_1 = nB/(2n-1)$; welfare $\to 3/2$ vs 2	ratio $\to 3/4$
Proportional sharing PoA	$\ge 3/4$; optimal among single-price, single-bid mechanisms	Ch. 21
VCG	PoA 1, but full utility functions and player-specific prices

Facts to keep to hand

• “The PoA” is meaningless until all five choices are fixed. Example 17.4 alone gives 1, $2 - 1/m$, or $\Theta(\log m/\log\log m)$ depending on the equilibrium concept and objective.
• PoA vs PoS separates two failure modes. Bad equilibria can come from externalities, where everyone’s own best move hurts others (Pigou, one equilibrium). They can also come from coordination failure, where good equilibria exist but aren’t reached (Ex. 17.2, where PoS fixes it). Example 17.3 is both: the only equilibrium is bad.
• Potential functions do three jobs: existence of pure equilibria (network design), essential uniqueness (routing, resource allocation), and bounds on inefficiency (PoS $\le H_k$, affine PoA $\le 4/3$).
• Every inefficiency here is an ignored externality. Pigou: congestion imposed on others. Shapley design: cost shares that make pioneering unattractive. Balls into bins: uncoordinated collisions. Proportional sharing: a large bidder moving its own price.
• Price-taking restores efficiency. Proportional sharing is fully efficient without market power, and loses exactly a quarter in the worst case with it.
• Design trades simplicity against efficiency. VCG reaches PoA 1 with rich communication. Proportional sharing’s single bid and single price cap it at $3/4$, and nothing equally simple does better. Shapley cost sharing plays the same role among network-oblivious cost-sharing rules.
• PoA is the approximation ratio with “insufficient computation” replaced by “insufficient coordination.”

References

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