Communications of the ACM

Research highlights

Intrinsic Robustness of the Price of Anarchy

By Tim Roughgarden
Communications of the ACM, July 2012, Vol. 55 No. 7, Pages 116-123
10.1145/2209249.2209274
Comments

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.

Back to Top

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 s_i from a set S_i, like a path in a network. The cost C_i(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:

for every i and , 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.¹⁷ and the references therein.

 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 problem⁹ 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 version²² discusses additional generalizations of pure Nash equilibria, including approximate equilibria and outcome sequences generated by best-response dynamics. We formally define the equilibrium concepts of Figure 1—mixed Nash equilibria, correlated equilibria, and coarse correlated equilibria—in Section 3.1, but mention next some of their important properties.

Enlarging the set of equilibria weakens the behavioral and technical assumptions necessary to justify equilibrium analysis. First, while there are games with no pure Nash equilibria—"Matching Pennies" being a simple example—every (finite) game has at least one mixed Nash equilibrium.¹⁶ As a result, the "nonexistence critique" for pure Nash equilibria does not apply to any of the more general concepts in Figure 1. Second, while computing a mixed Nash equilibrium is in general a computationally intractable problem,^{5, 8} computing a correlated equilibrium is not (see, e.g., Chapter 2 of Nisan et al.¹⁷). Thus, the "intractability critique" for pure and mixed Nash equilibria does not apply to the two largest sets of Figure 1. More importantly, these two sets are "easily learnable": when a game is played repeatedly over time, there are natural classes of learning dynamics—processes by which a player chooses its strategy for the next time step, as a function only of its own payoffs and the history of play—that are guaranteed to converge quickly to these sets of equilibria (see Chapter 4 of Nisan et al.¹⁷).

 1.2. Overview

Our contributions can be divided into three parts.

1. We identify a sufficient condition for an upper bound on the POA of pure Nash equilibria of a game, which encodes a canonical proof template for deriving such bounds. We call such proofs "smoothness arguments." Many of the POA upper bounds in the literature can be recast as instantiations of this canonical method.
2. 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 all of the more general equilibrium concepts pictured in Figure 1.
3. We prove that routing games, with cost functions restricted to some arbitrary set, are "tight" in the following sense: smoothness arguments, despite their automatic generality, are guaranteed to produce optimal worst-case upper bounds on the POA, even for the set of pure Nash equilibria. Thus, in these classes of games, the worst-case POA is the same for each of the equilibrium concepts of Figure 1.

Back to Top

2. Smooth Games

 2.1. Definitions

By a cost-minimization game, we mean a game—players, strategies, and cost functions—together with the joint cost objective function . Essentially, a "smooth game" is a cost-minimization game that admits a POA bound of a canonical type (a "smoothness argument"). We give the formal definition and then explain how to interpret it.

DEFINITION 2.1 (SMOOTH GAMES): A cost-minimization game is (λ, μ)-smooth if for every two outcomes s and s*,

Roughly, smoothness controls the cost of a set of "one-dimensional perturbations" of an outcome, as a function of both the initial outcome s and the perturbations s*.

We claim that if a game is (λ, μ)-smooth, with λ > 0 and μ < 1, then each of its pure Nash equilibria s has cost at most λ/(1 − μ) times that of an optimal solution s*. In proof, we derive

where (3) follows from the definition of the objective function; inequality (4) follows from the Nash equilibrium condition (1), applied once to each player i with the hypothetical deviation ; and inequality (5) follows from the defining condition (2) of a smooth game. Rearranging terms yields the claimed bound.

Definition 2.1 is sufficient for the last line of this three-line proof (3)–(5), but it insists on more than what is needed: it demands that the inequality (2) hold for every outcome s, and not only for Nash equilibria. This is the basic reason why smoothness arguments imply worst-case bounds beyond the set of pure Nash equilibria.

We define the robust POA as the best upper bound on the POA that is provable via a smoothness argument.

DEFINITION 2.2 (ROBUST POA): The robust price of anarchy of a cost-minimization game is

with μ always constrained to be less than 1.

REMARK 2.3 (VARIATIONS ON SMOOTHNESS): Examining the three-line proof (3)–(5) reveals that the assumptions can be weakened in two ways. First, the assumption that the objective function satisfies can be replaced by the assumption ; we exploit this in Example 2.5 below. Second, in Definition 2.1, the inequality (2) only needs to hold for all outcomes s and some optimal solution s*, rather than for all pairs s, s* of outcomes. This relaxation is useful in some applications.^4,23

Finally, there is an analogous definition of smooth games for maximization objectives; see Example 2.5.

 2.2. Intuition

Smoothness arguments should be interpreted as a class of upper bound proofs for the POA of pure Nash equilibria that are confined to use the equilibrium hypothesis in a minimal way. To explain, recall the canonical three-line proof (3)–(5). The first inequality (4) uses the Nash equilibrium hypothesis, but only to justify why each player i selects its equilibrium strategy s_i rather than its strategy in the optimal outcome. If we care only about the POA of pure Nash equilibria, then we are free to invoke the Nash equilibrium hypothesis again to prove the second inequality (5) or, more generally, to establish an upper bound using any argument that we please. Using a smoothness argument—that is, proving inequality (5) for all outcomes s—is tantamount to discarding the Nash equilibrium hypothesis after it is used to justify the first inequality (4).

 2.3. Two examples

Concern about the range of applicability of a definition grows as its interesting consequences accumulate. Given that smoothness arguments enable the extension theorem discussed in Section 1.2, how many games can be (λ, μ)-smooth with interesting values of λ, μ? To alleviate such fears and add some concreteness to the discussion, we next single out two well-known POA analyses that can be recast as smoothness arguments. More generally, many but not all of the known price of anarchy bounds follow from smoothness proofs^a; see the full version²² for a detailed discussion.

The first example is a special class of congestion games; Section 4 studies the general case in detail. The second example concerns Vetta's well-studied utility games,²⁵ and also illustrates how smoothness arguments can be defined and used in payoff-maximization games, and also with a "one-sided" variant of sum objective functions (cf., Remark 2.3).

EXAMPLE 2.4 (ATOMIC CONGESTION GAMES): A congestion game is a cost-minimization game defined by a ground set E or resources, a set of k players with strategy sets S₁,...,S_k ⊆ 2^E, and a cost function c_e: for each resource e E.²⁰ In this article, we always assume that cost functions are nonnegative and nondecreasing. A canonical example is routing games, where E is the edge set of a network, and the strategies of a player correspond to paths between its source and sink vertices. Given a strategy profile s = (s₁,..., s_k), with s_i S_i for each i, we say that x_e = |{i: e s_i}| is the load induced on e by s, defined as the number of players that use it in s. The cost to player i is defined as , where x is the vector of loads induced by s. For this example, we assume that every cost function is affine, meaning that c_e(x) = a_ex + b_e with a_e, b_e ≥ 0 for every resource e E.

We claim that every congestion game with affine cost functions is (5/3, 1/3)-smooth. The basic reason for this was identified by Lemma 1 of Christodoulou and Koutsoupias,⁷ who noted that

for all nonnegative integers y, z. Thus, for all a, b ≥ 0 and nonnegative integers y, z,

To establish smoothness, consider a pair s, s* of outcomes of a congestion game with affine cost functions, with induced loads x, x*. Since the number of players using resource e in the outcome (, s_-i) is at most one more than that in s, and this resource contributes to precisely terms of the form C_i(, s_-i), we have

where (7) follows from (6), with and x_e playing the roles of y and z, respectively. The canonical three-line argument (3)–(5) then implies an upper bound of 5/2 on the POA of pure Nash equilibria in every congestion game with affine cost functions. This fact was first proved independently in Awerbuch et al.² and Christodoulou and Koutsoupias,⁷ where matching lower bounds were also supplied. Our extension theorem (Theorem 3.1) implies that the bound of 5/2 extends to the other three sets of outcomes shown in Figure 1. These extensions were originally established in two different papers^3,6 subsequent to the original POA bound.^2,7

EXAMPLE 2.5 (VALID UTILITY GAMES): Our final example concerns a class of games called valid utility games.²⁵ These games are naturally phrased as payoff-maximization games, where each player has a payoff function Π_i(s) that it strives to maximize. We use Π to denote the objective function of a payoff-maximization game. We call such a game (λ, μ)-smooth if

for every pair s, s* of outcomes. A derivation similar to (3)–(5) shows that, in a (λ, μ)-smooth payoff-maximization game, the objective function value of every pure Nash equilibrium is at least a λ/(1 + μ) fraction of the maximum possible. We define the robust POA of a payoff-maximization game as the supremum of λ/(1 + μ) over all legitimate smoothness parameters (λ, μ).

A valid utility game is defined by a ground set E, a nonnegative submodular function V defined on subsets of E, and a strategy set S_i ⊆ 2^E and a payoff function Π_i for each player i = 1, 2,..., k.^b For example, the set E could denote a set of locations where facilities can be built, and a strategy s_i ⊆ E could denote the locations at which player i chooses to build facilities. For an outcome s, let U(s) ⊆ E denote the union of players' strategies in s. The objective function value of an outcome s is defined as Π(s) = V(U(s)). Furthermore, the definition requires that two conditions hold: (i) for each player i, Π_i(s) ≥ V(U(s)) - V(U(Ø, s_-i)) for every outcome s; and (ii) for every outcome s. One concrete example of such a game is competitive facility location with pricetaking markets and profit-maximizing firms.²⁵

We claim that every valid utility game with a nondecreasing objective function V is (1, 1)-smooth. The proof is essentially a few key inequalities from Theorem 3.2 of Vetta²⁵, as follows. Let s, s* denote arbitrary outcomes of a valid utility game with a nondecreasing objective function. Let U_i ⊆ E denote the union of all of the players' strategies in s, together with the strategies employed by players 1, 2,..., i in s*. Applying condition (i), the submodularity of V, and the nondecreasing property of V yields

as desired. This smoothness argument implies a lower bound of 1/2 on the POA of pure Nash equilibria in every valid utility game with a nondecreasing objective function—a result first proved in Vetta,²⁵ along with a matching upper bound. Our extension theorem shows that this lower bound applies more generally to all of the equilibria depicted in Figure 1, a fact first established in Blum et al.³

Back to Top

3. An Extension Theorem

This section states and proves the extension theorem discussed in Section 1.2: every POA bound on pure Nash equilibria derived from a smoothness argument extends automatically to the more general equilibrium concepts in Figure 1 and to the corresponding outcome sequences in games played over time. Several less direct consequences of smoothness arguments are discussed in the full version.²² We work with cost-minimization games, though similar results hold for smooth payoff-maximization games (cf., Example 2.5).

 3.1. Static equilibrium concepts

We begin with implications of Definition 2.1 for randomized equilibrium concepts in one-shot games; the next section treats outcome sequences generated by repeated play.

A set (σ₁,..., σ_k) of independent probability distributions over strategy sets—one per player of a cost-minimization game—is a mixed Nash equilibrium of the game if no player can decrease its expected cost under the product distribution σ = σ₁ x ... x σ_k via a unilateral deviation:

for every i and s_i, s'_i s_i, where σ_-i, is the product distribution of all σ_j's other than σ_i. (By linearity, it suffices to consider only pure-strategy unilateral deviations.) Obviously, every pure Nash equilibrium is a mixed Nash equilibrium and not conversely; indeed, many games have no pure Nash equilibrium, but every finite game has a mixed Nash equilibrium.¹⁶

A correlated equilibrium of a cost-minimization game G is a (joint) probability distribution σ over the outcomes of G with the property that

for every i and s_i, s'_i S_i. A classical interpretation of a correlated equilibrium is in terms of a mediator, who draws an outcome s from the publicly known distribution σ and privately "recommends" strategy s_i to each player i. The equilibrium condition requires that following a recommended strategy always minimizes the expected cost of a player, conditioned on the recommendation. Mixed Nash equilibria are precisely the correlated equilibria that are also product distributions. Correlated equilibria have been widely studied as strategies for a benevolent mediator, and also because of their relative tractability. Because the set of correlated equilibria is explicitly described by a small set of linear inequalities, computing (and even optimizing over) correlated equilibria can be done in time polynomial in the size of the game (see, e.g., Chapter 2 of Nisan et al.¹⁷). They are also relatively "easy to learn," as discussed in the next section.

Finally, a coarse correlated equilibrium of a cost-minimization game is a probability distribution σ over outcomes that satisfies

for every i and s'_i, s_i. While a correlated equilibrium (8) protects against deviations by players aware of their recommended strategy, a coarse correlated equilibrium (9) is only constrained by player deviations that are independent of the sampled outcome. Since every correlated equilibrium is also a coarse correlated equilibrium, coarse correlated equilibria are "even easier" to compute and learn, and are thus a still more plausible prediction for the realized play of a game.

We now give our extension theorem for equilibrium concepts in one-shot games: every POA bound proved via a smoothness argument extends automatically to the set of coarse correlated equilibria. With the "correct" definitions in hand, the proof writes itself.

THEOREM 3.1 (EXTENSION THEOREM—STATIC VERSION) For every cost-minimization game G with robust POA ρ(G), every coarse correlated equilibrium σ of G, and every outcome s* of G,

PROOF: Let G be a (λ, μ)-smooth cost-minimization game, σ a coarse correlated equilibrium, and s* an outcome of G. We can write

where equality (10) follows from the definition of the objective function, equalities (11), (13), and (15) follow from linearity of expectation, inequality (12) follows from the definition (9) of a coarse correlated equilibrium (applied once per player, with the hypothetical deviation ), and inequality (14) follows from the assumption that the game is (λ, μ)-smooth. Rearranging terms completes the proof.

 3.2. Repeated play and no-regret sequences

The extension theorem (Theorem 3.1) applies equally well to certain outcome sequences generated by repeated play, because of a well-known correspondence between such sequences and static equilibrium concepts. To illustrate this point, consider a sequence s¹, s²,..., s^T of outcomes of a (λ, μ)-smooth game and a minimum-cost outcome s* of the game. For each i and t, define

as the hypothetical improvement in player i's cost at time t had it used the strategy in place of s^t_i. When s^t is a Nash equilibrium, δ_i(s^t) cannot be positive; for an arbitrary outcome s^t, δ_i(s^t) can be positive or negative. We can mimic the derivation in (3)–(5) to obtain

for each t.

Suppose that every player i experiences vanishing average (external) regret, meaning that its cost over time is competitive with that of every time-invariant strategy:

Repeating the same pure Nash equilibrium over and over again yields a degenerate example, but in general such sequences can exhibit highly oscillatory behavior over arbitrarily large time horizons (see, e.g., Blum et al.³ and Kleinberg et al.¹³).

Averaging (17) over the T time steps and reversing the order of the resulting double summation yields

Recalling from (16) that δ_i(s^t) is the additional cost incurred by player i at time t due to playing strategy s^t_i instead of the (time-invariant) strategy , the no-regret guarantee (18) implies that is bounded above by a term that goes to 0 with T. Since this holds for every player i, inequality (19) implies that the average cost of outcomes in the sequence is no more than the robust POA times the minimum-possible cost, plus an error term that approaches zero as T → ∞.

THEOREM 3.2 (EXTENSION THEOREM—REPEATED VERSION) For every cost-minimization game G with robust POA ρ(G), every outcome sequence σ¹, ..., σ^T that satisfies (18) for every player, and every outcome s* of G,

as T → ∞.

Blum et al.³ were the first to consider bounds of this type, calling them "the price of total anarchy."

We reiterate that the type of bound in Theorem 3.2 is significantly more compelling, and assumes much less from both the game and its participants, than the one that applies only to Nash equilibria. While Nash equilibria can be intractable or impossible to find, there are several computationally efficient "off-the-shelf" learning algorithms with good convergence rates that are guaranteed, in any game, to generate outcome sequences with vanishing average regret (see, e.g., Chapter 4 of Nisan et al.¹⁷). Of course, the guarantee in Theorem 3.2 makes no reference to which learning algorithms (if any) the players' use to play the game—the bound applies whenever repeated joint play has low regret, whatever the reason.

REMARK 3.3 (THEOREMS 3.1 AND 3.2): Theorems 3.1 and 3.2 are essentially equivalent, in that either one can be derived from the other. The reason is that the set of coarse correlated equilibria of a game is precisely the closure of the empirical distributions of (arbitrarily long) sequences in which every player has nonpositive average regret.

REMARK 3.4 (CORRELATED EQUILIBRIA AND SWAP REGRET) There is a more stringent notion of regret—swap regret—under which there is an analogous correspondence between the correlated equilibria of a game and the outcome sequences in which every player has nonpositive (swap) regret. There are also computationally efficient "off the shelf" learning algorithms that guarantee each player vanishing average swap regret in an arbitrary game.^10,12

Back to Top

4. Congestion Games are Tight

The worst-case POA for a set of allowable outcomes can only increase as the set grows bigger. This section proves that, in congestion games with restricted cost functions, the worst-case POA is exactly the same for each of the equilibrium concepts of Figure 1. We prove this by showing that smoothness arguments, despite their automatic generality, provide a tight bound on the POA, even for pure Nash equilibria.

More precisely, let denote a set of cost-minimization games, and assume that a nonnegative objective function has been defined on the outcomes of these games. Let denote the parameter values (λ, μ) such that every game of is (λ, μ)-smooth. Let denote the games with at least one pure Nash equilibrium, and ρ_pure(G) the POA of pure Nash equilibria in a game The canonical three-line proof (3)–(5) shows that for every (λ, μ) and every G , ρ_pure(G) ≤ λ/(1 − μ). We call a set of games tight if equality holds for suitable choices of (λ, μ) and .

DEFINITION 4.1 (TIGHT CLASS OF GAMES): A set of games is tight if

The right-hand side of (20) is the best worst-case upper bound provable via a smoothness argument, and it applies to all of the sets shown in Figure 1. The left-hand side of (20) is the actual worst-case POA of pure Nash equilibria in —corresponding to the smallest set in Figure 1—among games with at least one pure Nash equilibrium. That the left-hand side is trivially upper bounded by the right-hand side is reminiscent of "weak duality." Tight classes of games are characterized by the min-max condition (20), which can be loosely interpreted as a "strong duality-type" result.^c In a tight class of games, every valid upper bound on the worst-case POA of pure Nash equilibria is superseded by a suitable smoothness argument. Thus, every such bound—whether or not it is proved using a smoothness argument—is "intrinsically robust," in that it applies to all of the sets of outcomes in Figure 1.

Recall from Example 2.4 the definition of and notation for congestion games. Here, we consider arbitrary nonnegative and nondecreasing cost functions c_e. The worst-case POA in congestion games depends on the "degree of nonlinearity" of the allowable cost functions. For example, for polynomial cost functions with nonnegative coefficients and degree at most d, the worst-case POA in congestion games is finite but exponential in d.^1,2,7,18

Example 2.4 shows that, if is the set of congestion games with affine cost functions, then the right-hand side of (20) is at most 5/2. Constructions in Awerbuch et al.² and Christodoulou and Koutsoupias⁷ show that the left-hand side of (20) is at least 5/2 for this class of games. Thus, congestion games with affine cost functions form a tight class. Our final result shows that this fact is no fluke.

THEOREM 4.2: For every non-empty set C of nondecreasing, positive cost functions, the set of congestion games with cost functions in C is tight.

In addition to showing that smoothness arguments always give optimal POA bounds in congestion games, this result and its proof imply the first POA bounds of any sort for congestion games with nonpolynomial cost functions, and the first structural characterization of universal worst-case examples for the POA in congestion games.

The proof of Theorem 4.2 is technical and we provide only a high-level outline; the complete proof can be found in the full version.²² For the following discussion, fix a set of cost functions. The first step is to use the fact that, in a congestion game, the objective function and players' cost functions are additive over the resources E. This reduces the search for parameters (λ, μ) that satisfy condition (2) of Definition 2.1—which imposes one constraint for every congestion game with cost functions in , and every pair s, s* of outcomes in that game—to the search for parameters (λ, μ) that satisfy

for every cost function c , nonnegative integer x, and positive integer x*. This condition is the same as (6) in Example 2.4 for the case where is the set of affine cost functions.

The second step of the proof is to understand the optimization problem of minimizing the objective function λ/(1 − μ) over the "feasible region" , where denotes the set of values (λ, μ) that meet the condition (21) above. This optimization problem is almost the same as the right-hand side of (20), and it has several nice properties. First, there are only two decision variables—λ and μ—so is contained in the plane. Second, while there are an infinite number of constraints (21), each is linear in λ and μ. Thus, is the intersection of halfplanes. Third, the objective function λ/(1 - μ) is decreasing is both decision variables. Thus, ignoring some edge cases that can be handled separately, the choice of (λ, μ) that minimizes the objective function lies on the "southwestern boundary" of , and can be characterized as the unique point of that satisfies with equality a particular pair of constraints of the form (21).

The third and most technical part of the proof is to show a matching lower bound on the left-hand side of (20). The intuition behind the construction is to arrange a congestion game in which each player has two strategies, one that uses a small number of resources, and the other a disjoint strategy that uses a large number of resources. In the optimal outcome, all players use their small strategies and incur low cost. (This outcome is also a pure Nash equilibrium.) In the suboptimal pure Nash equilibrium, all players use their large strategies, thereby "flooding" all resources and incurring a large cost. How can this suboptimal outcome persist as a Nash equilibrium? If one player deviates unilaterally, it enjoys the benefit of fewer resources in its strategy, but each of these new resources now has load one more than that of each of the resources it was using previously. Implemented optimally, this construction produces a congestion game and a pure Nash equilibrium of it with cost a λ/(1 − μ) factor larger than that of the optimal outcome, where (λ, μ) are the optimal smoothness parameters identified in the second step of the proof.

REMARK 4.3 (POA BOUNDS FOR ALL COST FUNCTIONS): Theorem 4.2 gives the first solution to the worst-case POA in congestion games with cost functions in an arbitrary set . Of course, precisely computing the exact value of the worst-case POA is not trivial, even for simple sets . Arguments in Aland et al.¹ and Olver¹⁸ imply a (complex) closed-form expression for the worst-case POA when is a set of polynomials with nonnegative coefficients. Similar computations should be possible for some other simple sets . More broadly, the second and third steps of the proof of Theorem 4.2 indicate how to numerically produce good upper and lower bounds, respectively, on the worst-case POA when there is a particular set of interest.

REMARK 4.4 (WORST-CASE CONGESTION GAMES): The details of the construction in the third step of the proof of Theorem 4.2 show that routing games on a bidirected cycle are universal worst-case examples for the POA, no matter what the allowable set of cost functions. This corollary is an analog of a simpler such sufficient condition for nonatomic congestion games—where there is a continuum of players, each of negligible size—in which, under modest assumptions on , the worst-case POA is always achieved in two-node two-link networks.²¹

Back to Top

5. Further Related Work

The price of anarchy was first studied in Koutsoupias and Papadimitriou¹⁴ for makespan minimization in scheduling games. This is not a sum objective function, and the worstcase POA in this model was immediately recognized to be different for different equilibrium concepts.^3,14 See Chapter 20 of Nisan et al.¹⁷ for a survey of the literature on this model.

The POA with a sum objective was first studied in Roughgarden and Tardos²⁴ for nonatomic selfish routing games. The first general results on the POA of pure Nash equilibria for (atomic) congestion games and their weighted variants are in Awerbuch et al.² and Christodoulou and Koutsoupias,⁷ which gave tight bounds for games with affine cost functions and reasonably close upper and lower bounds for games with polynomial cost functions with nonnegative coefficients; matching upper and lower bounds for the latter class were later given independently in Aland et al.¹ and Olver.¹⁸

Many previous works recognized the possibility of and motivation for more general POA bounds. The underlying bound on the POA of pure Nash equilibria can be formulated as a smoothness argument in almost all of these cases, so our extension theorem immediately implies, and often strengthens, these previously proved robust bounds. Specifically, Aland et al.,¹ Awerbuch et al.,² Christodoulou and Koutsoupias,⁷ and Vetta²⁵ each observe that their upper bounds on the worst-case POA of pure Nash equilibria carry over easily to mixed Nash equilibria. In Christodoulou and Koutsoupias,⁶ the worst-case POA of correlated equilibria is shown to be the same as that for pure Nash equilibria in unweighted and weighted congestion games with affine cost functions. Blum et al.³ rework and generalize several bounds on the worst-case POA of pure Nash equilibria to show that the same bounds hold for the average objective function value of no-regret sequences. Their applications include valid utility games²⁵ and the (suboptimal) bounds of Awerbuch et al.² and Christodoulou and Koutsoupias⁷ for unweighted congestion games with polynomial cost functions, and also a constant-sum location game and a fairness objective, which falls outside of our framework.

Versions of our two-parameter smoothness definition are implicit in a few previous papers, in each case for a specific model and without any general applications to robust POA guarantees: Perakis¹⁹ for a nonatomic routing model with nonseparable cost functions, Christodoulou and Koutsoupias⁶ for congestion games with affine cost functions, and Harks¹¹ for splittable congestion games.

Back to Top

6. Conclusion

Pure-strategy Nash equilibria—where each player deterministically picks a single strategy—are often easier to reason about than their more general cousins like mixed Nash equilibria, correlated equilibria, and coarse correlated equilibria. On the other hand, inefficiency guarantees for more general classes of equilibria are crucial for several reasons: pure Nash equilibria do not always exist; they can be intractable to compute, even when they are guaranteed to exist; and even when efficiently computable by a centralized algorithm, they can elude natural learning dynamics.

This article presented an extension theorem, which automatically extends, in "black-box" fashion, price of anarchy bounds for pure Nash equilibria to the more general equilibrium concepts listed above. Such an extension theorem can only exist under some conditions, and the key idea is to restrict the method of proof used to bound the price of anarchy of pure Nash equilibria. We defined smooth games to formalize a canonical method of proof, in which the Nash equilibrium hypothesis is used in only a minimal way, and proved an extension theorem for smooth games. Many of the games in which the price of anarchy has been studied are smooth games in our sense.^d For the fundamental model of congestion games with arbitrarily restricted cost functions, we proved that this canonical proof method is guaranteed to produce an optimal upper bound on the worst-case POA. In this sense, POA bounds for congestion games are "intrinsically robust."

Back to Top

Acknowledgments

This research was supported in part by NSF CAREER Award CCF-0448664, an ONR Young Investigator Award, an AFOSR MURI grant, and an Alfred P. Sloan Fellowship.

Back to Top

Back to Top

Back to Top

Back to Top

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.

---

No entries found