Smoothed Analysis of Price of Anarchy

A framework showing that worst-case PoA bounds can be overly pessimistic — typical-case bounds are often dramatically better.

Ask the Game theory assistant1 min read · Updated September 9, 2026

Definition

In smoothed analysis, inputs are perturbed by small random noise; the smoothed PoA is the expected (or high-probability) ratio under $\sigma$ -perturbations. Roughgarden (2009) showed that strict Nash equilibria have near-optimal welfare under general conditions.

Smoothly-perturbed congestion games often have PoA close to 1, even when worst-case PoA is unbounded.

Intuition

Worst-case PoA bounds rely on fragile constructions — tiny perturbations often eliminate the worst equilibria.

Smoothed analysis bridges the gap between worst-case theory and observed performance in practice.

Worked example

In atomic selfish routing, worst-case PoA can be $\Theta(n)$ for certain latencies, but smoothed PoA is $O(1)$ .

In congestion games, adding small random noise to latencies makes nearly all Nash equilibria approximately efficient.

The math

Roughgarden (2009) proved that for every $\epsilon>0$ , the PoA of $\epsilon$ -Nash equilibria in continuous nonatomic congestion games satisfies smoothed PoA $\le 1+\epsilon$ .

The framework applies to any set of strategy profiles defined by equilibrium-like conditions that are robust to perturbation.

Where it is used

Theoretical justification for why practical routing, auctions, and markets perform better than worst-case bounds suggest.

Bridges algorithmic game theory and real-world traffic engineering.

More in Game theory

Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.