Price of Anarchy

Definitions

The price of anarchy (PoA) and price of stability (PoS) quantify the inefficiency of equilibria relative to centralized optimal solutions.

Price of Anarchy

For a game with social cost function C (to minimize) or social welfare W (to maximize):

PoA = max_NE C(NE) / C(OPT) (cost minimization) PoA = W(OPT) / min_NE W(NE) (welfare maximization)

The PoA measures the worst-case ratio over all Nash equilibria, capturing how bad selfish behavior can be.

Price of Stability

PoS = min_NE C(NE) / C(OPT) (cost minimization)

The PoS measures the best equilibrium, capturing whether there exists an equilibrium close to optimal. PoS <= PoA always. When PoS is small, the challenge is coordination (reaching the good equilibrium), not incentive misalignment.

Extensions

PoA for mixed NE, correlated equilibrium, coarse correlated equilibrium: Typically analyzed separately; coarse CE gives the strongest PoA bounds (since it is the largest set)
Bayesian PoA: Ratio over Bayesian Nash equilibria in incomplete information settings
Robust PoA: Bounds that hold for all coarse correlated equilibria simultaneously

Braess's Paradox

The Paradox

Adding a road to a network can increase total travel time at equilibrium.

Classic example: Network with source s, destination t, and 4000 drivers.

Original network: two paths, each with one constant-cost edge (45 min) and one congestion-dependent edge (x/100 min). Equilibrium: 2000 on each path, travel time = 65 min.
Add a zero-cost shortcut connecting the midpoints. New equilibrium: all 4000 use the shortcut path (congestion edges), travel time = 80 min.

General implication: Selfish routing can produce counterintuitive outcomes. Network design must account for strategic behavior. Braess's paradox is not pathological; it occurs in many real road networks.

Braess's Paradox and Mechanism Design

Removing edges (Stackelberg routing), tolls (marginal cost pricing), or information restriction can improve equilibrium outcomes. These are instances of coordination mechanisms.

Congestion Games

Definition

A congestion game is defined by:

Players: N = {1, ..., n}
Resources: E = {e_1, ..., e_m}
Strategy sets: S_i subset of 2^E (each strategy is a subset of resources)
Latency functions: l_e: {1, ..., n} -> R for each resource (depends only on the number of users)
Cost: c_i(s) = sum_{e in s_i} l_e(n_e(s)), where n_e(s) is the number of players using resource e

Rosenthal's Theorem (Potential Games)

Theorem: Every congestion game is a potential game with exact potential:

Phi(s) = sum_{e in E} sum_{j=1}^{n_e(s)} l_e(j)

Proof: When player i switches from strategy s_i to s'_i, the change in Phi equals the change in c_i. Therefore, any sequence of improving moves (unilateral deviations that decrease a player's cost) strictly decreases Phi, guaranteeing convergence to a pure Nash equilibrium in finite steps.

Implications: Pure NE always exist in congestion games. Best-response dynamics converge (but may take exponentially many steps in worst case). Computing a PNE is PLS-complete.

Weighted Congestion Games

Players have weights w_i; resource cost depends on total weight. Weighted congestion games are NOT exact potential games in general; pure NE may not exist. Milchtaich showed PNE existence for singleton strategies (each strategy is a single resource).

Network Congestion Games

Resources are edges of a graph; strategies are paths from source to destination. Special case of congestion games. Symmetric if all players share the same source-destination pair.

Selfish Routing (Wardrop Model)

Nonatomic Model

Infinitesimal players (continuum of users) route flow on a network. Each user is negligible.

Wardrop equilibrium: All used paths between the same source-destination pair have equal (minimum) latency. No user can reduce their latency by switching paths. Equivalent to a convex optimization problem when latency functions are non-decreasing:

minimize sum_e integral_0^{f_e} l_e(x) dx, subject to flow conservation constraints

PoA for Selfish Routing

Pigou's example: Two parallel links from s to t. Link 1: l(x) = 1. Link 2: l(x) = x. Social optimum: f_1 = f_2 = 1/2, total cost = 3/4. Wardrop equilibrium: all flow on link 2, total cost = 1. PoA = 4/3.

Roughgarden-Tardos Theorem: For networks with affine latency functions l_e(x) = a_e * x + b_e:

PoA = 4/3

This bound is tight (achieved by Pigou's example) and holds for all network topologies and demand patterns.

Polynomial latencies: For latency functions of degree d:

PoA = Theta(d / ln d)

The PoA grows with the degree of the polynomial, reflecting that more convex latency functions cause greater inefficiency.

General latencies: Roughgarden (2003) showed that the PoA of selfish routing depends only on the class of allowable latency functions, not on the network topology. The worst case is always a simple two-link (Pigou-like) network.

Tolls and Optimal Routing

Marginal cost pricing: Charging each user a toll equal to the marginal external cost l'_e(f_e) * f_e induces the social optimum as the Wardrop equilibrium. Users internalize the externality they impose.

Stackelberg routing: A central authority controls a fraction alpha of the flow and routes it optimally; remaining (1-alpha) fraction routes selfishly. Can improve PoA significantly.

Load Balancing Games

Setting

n jobs (players) assigned to m machines (resources). Job i has weight w_i. Machine j's load is L_j = sum of weights of jobs assigned to j. Latency = load (identical machines) or l_j(L_j) (related/unrelated machines).

Social cost: Makespan = max_j L_j (minimize the maximum load).

PoA Results

| Setting | PoA (pure NE) | |---|---| | Identical machines | 2 - 2/(m+1) (Theta(2)) | | Uniformly related machines | Theta(log m / log log m) | | Unrelated machines | Theta(log m / log log m) |

For identical machines with weighted jobs: pure NE always exists (potential game with ordinal potential). The PoA of 2 - 2/(m+1) is achieved by the "staircase" construction.

Coordination Mechanisms

Design the latency functions (scheduling policies) on machines to improve PoA:

SPT (Shortest Processing Time): Process jobs in order of increasing weight. PoA = O(log m / log log m) for unrelated machines.
LPT (Longest Processing Time): Better for identical machines; PoA = 4/3.
Coordination ratio: The PoA under the best coordination mechanism.

Smooth Games Framework

Definition (Roughgarden, 2015)

A game is (lambda, mu)-smooth if for every strategy profile s and every strategy profile s*:

sum_i c_i(si, s{-i}) <= lambda * C(s) + mu * C(s)

where c_i is player i's cost and C is the social cost.

PoA Bound

Theorem: If a game is (lambda, mu)-smooth with mu < 1, then:

PoA <= lambda / (1 - mu)

This bound applies simultaneously to:

Pure Nash equilibria
Mixed Nash equilibria
Correlated equilibria
Coarse correlated equilibria
Bayesian Nash equilibria (with independent types)

Power of Smoothness

The smoothness framework provides a unified method for proving PoA bounds across different equilibrium concepts and information structures. Many known PoA results can be recovered (and sometimes strengthened) as corollaries.

Congestion games with polynomial latencies l_e(x) = sum_d a_{e,d} x^d: (lambda, mu)-smooth with:

PoA <= Phi_{d}^{d+1} where Phi_d is approximately (d+1)^{d+1}/d^d for degree-d polynomials.

For affine latencies (d=1): PoA <= 5/2 for atomic (weighted) congestion games.

Tightness

The smoothness framework gives tight bounds for many games (selfish routing with polynomial latencies, valid utility games). However, it can be loose: for some games, the actual PoA is better than the smooth bound. The composition theorem states that smooth bounds compose: if sub-games are smooth, the composed game has PoA bounded by the product of individual smooth parameters.

Network Design Games

n players want to connect their source-destination pairs in a network. Edge e has cost c_e shared equally among users: each player using edge e with k_e total users pays c_e / k_e.

PoA: O(log n) for directed graphs; Theta(n) for general cases
PoS: H_n = O(log n) (achieved by the best pure NE)

The PoS result uses the potential function argument: the potential function of any PNE is at most H_n times the optimal cost.

Buy-at-Bulk Network Design

Players choose paths; edge cost has economies of scale. PoA can be much worse due to the tension between sharing (coordination) and individual optimization.

Applications and Implications

The PoA framework has practical implications for:

Transportation: Quantifies traffic congestion costs; informs toll design
Internet routing: BGP routing as a congestion game; PoA of selfish ISP routing
Cloud computing: Job scheduling on shared infrastructure
Resource allocation: Shared resource management in distributed systems

The central message: simple, decentralized systems (where agents act selfishly) often perform reasonably well compared to centralized optima. The PoA provides a rigorous, worst-case guarantee for this intuition.