Intrinsic Robustness
of the Price of Anarchy

abstract

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 )

( 1)

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 et al. 17 and the references therein.

1. intRoDuCtion

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 optimal outcome.

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.