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

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).

Definition 2. 2 (Robust POA): The robust price of anarchy of a cost-minimization game is with m 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 si rather than its strategy s i 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).

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 S1, . . . , Sk ⊆ 2E, and a cost function ce: Z+ → R for each resource e  E. 20 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 = (s1, .. . , sk), with si ∈ Si for each i, we say that xe = |{i : e ∈ si}| 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 ce(x) = aex + be with ae, be ≥ 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, 7
who noted that
for all nonnegative integers y, z. Thus, for all a, b ≥ 0 and
nonnegative integers y, z,
( 6)

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 , s–i ) is at most one more than that in s, and this resource contributes to precisely x e terms of the form Ci (s*i , s−i ), we have

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 (λ, m)- smooth with interesting values of λ, m 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 proofsa; see the full version22 for a detailed discussion.

The first example is a special class of congestion games;
Section 4 studies the general case in detail. The second exam-
ple concerns Vetta’s well-studied utility games, 25 and also
( 7)

a The most common reason that a price of anarchy bound fails to qualify as a smoothness proof is that the Nash equilibrium hypothesis is invoked for a hypothetical deviation s*i that is a function of the other players’ equilibrium actions s– i. In most of these cases, it is also known that the worst-case POA of mixed Nash equilibria is strictly worse than that of pure Nash equilibria, and hence no lossless extension theorem exists.

where ( 7) follows from ( 6), with x*e and xe 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. 2 and Christodoulou and Koutsoupias, 7 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 papers3, 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. 25 These