of the Price of Anarchy
The price of anarchy, defined as the ratio of the worst-case
objective function value of a Nash equilibrium of a game
and that of an optimal outcome, quantifies the inefficiency
of selfish behavior. Remarkably good bounds on this measure are known for a wide range of application domains.
However, such bounds are meaningful only if a game’s
participants successfully reach a Nash equilibrium. This
drawback motivates inefficiency bounds that apply more
generally to weaker notions of equilibria, such as mixed
Nash equilibria and correlated equilibria, or to sequences of
outcomes generated by natural experimentation strategies,
such as simultaneous regret-minimization.
We prove a general and fundamental connection between
the price of anarchy and its seemingly more general relatives. First, we identify a “canonical sufficient condition” for
an upper bound on the price of anarchy of pure Nash equilibria, which we call a smoothness argument. Second, we prove
an “extension theorem”: every bound on the price of anarchy that is derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to
mixed Nash equilibria, correlated equilibria, and the average objective function value of every no-regret sequence of
joint repeated play. Third, we prove that in routing games,
smoothness arguments are “complete” in a proof-theoretic
sense: despite their automatic generality, they are guaranteed to produce an optimal worst-case upper bound on the
price of anarchy.
a network. The cost Ci(s) incurred by a player i in a game is a
function of the entire vector s of players’ chosen strategies,
which is called a strategy profile or an outcome. By definition,
a strategy profile s of a game is a pure Nash equilibrium if no
player can decrease its cost via a unilateral deviation:
Ci(s) ≤ Ci (s′i, s−i )
for every i and si′ ∈ Si, where s−i denotes the strategies chosen by the players other than i in s. These concepts can be
defined equally well via payoff-maximization rather than
cost-minimization; see also Example 2. 5.
The price of anarchy (POA) measures the suboptimality
caused by self-interested behavior. Given a game, a notion
of an “equilibrium” (such as pure Nash equilibria), and an
objective function (such as the sum of players’ costs), the
POA of the game is defined as the ratio between the largest
cost of an equilibrium and the cost of an optimal outcome.
An upper bound on the POA has an attractive worst-case flavor: it applies to every possible equilibrium and obviates the
need to predict a single outcome of selfish behavior. Many
researchers have proved remarkably good bounds on the
POA in a wide range of models; see Chapters 17–21 of Nisan
17 and the references therein.
Every student of game theory learns early and often that
equilibria are inefficient—self-interested behavior by autonomous decision makers generally leads to an outcome
inferior to the one that a hypothetical benevolent dictator
would choose. Such inefficiency is ubiquitous in real-world
situations and arises for many different reasons: congestion
externalities, network effects, mis-coordination, and so on.
It can also be costly or infeasible to eliminate in many situations, with large networks being one obvious example. The
past ten years have provided an encouraging counterpoint
to this widespread equilibrium inefficiency: in a number of
interesting application domains, decentralized optimization by competing individuals provably approximates the
A rigorous guarantee of this type requires a formal behavioral model, in order to define “the outcome of self-interested behavior.” The majority of previous research studies
pure-strategy Nash equilibria, which are defined as follows.
Each player i selects a strategy si from a set Si, like a path in
1. 1. the need for more robust bounds
A good bound on the price of anarchy of a game is not
enough to conclude that self-interested behavior is relatively benign. Such a bound is meaningful only if a game’s
participants successfully reach an equilibrium. For pure
Nash equilibria, however, there are a number of reasons
why this might not occur: perhaps the players fail to coordinate on one of multiple equilibria, or they are playing
a game in which computing a pure Nash equilibrium is a
computationally intractable problem9 or, even more fundamentally, a game in which pure Nash equilibria do not
exist. These critiques motivate worst-case performance
bounds that apply to as wide a range of outcomes as possible, and under minimal assumptions about how players
play and coordinate in a game.
This article presents a general theory of “robust” bounds
on the price of anarchy. We focus on the hierarchy of
fundamental equilibrium concepts shown in Figure 1; the
full version22 discusses additional generalizations of pure
Nash equilibria, including approximate equilibria and
The original version of this article was published in the
Proceedings of the 41st Annual ACM Symposium on Theory
of Computing, May 2009.