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.
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 G denote a set of cost-minimization
games, and assume that a nonnegative objective function
has been defined on the outcomes of these games. Let A(G)
denote the parameter values (λ, m) such that every game of
G is (λ, m)-smooth. Let G ⊆ G denote the games with at least
one pure Nash equilibrium, and rpure(G) the POA of pure
Nash equilibria in a game G ∈ G. The canonical three-line
proof ( 3)–( 5) shows that for every (λ, m) ∈A(G) and every G ∈
G, rpure(G) ≤ λ/( 1 − m). We call a set of games tight if equality
holds for suitable choices of (λ, m) ∈A(G) and G ∈ G.
Definition 4. 1 (Tight Class of Games): A set G 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 G—
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.
c See Nadav and Roughgarden15 for a formal treatment of the duality bet ween
equilibrium concepts and POA bounds.
Recall from Example 2. 4 the definition of and notation for
congestion games. Here, we consider arbitrary nonnegative
and nondecreasing cost functions ce. 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 G 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.
Christodoulou and Koutsoupias7 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
22 For the following discussion, fix a set C of cost
functions. The first step is to use the fact that, in a conges-
tion game, the objective function and players’ cost functions
are additive over the resources E. This reduces the search for
parameters (λ, m) that satisfy condition ( 2) of Definition 2. 1—
which imposes one constraint for every congestion game
with cost functions in C, and every pair s, s of outcomes in
that game—to the search for parameters (λ, m) that satisfy
for every cost function c ∈ C, nonnegative integer x, and positive integer x *. This condition is the same as ( 6) in Example 2. 4
for the case where C 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 − m) over the “feasible region” A(C), where A(C) denotes
the set of values (λ, m) 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 m—so A(C) is
contained in the plane. Second, while there are an infinite
number of constraints ( 21), each is linear in λ and m. Thus,
A(C) is the intersection of halfplanes. Third, the objective
function λ/( 1 − m) is decreasing is both decision variables.
Thus, ignoring some edge cases that can be handled separately, the choice of (λ, m) that minimizes the objective function lies on the “southwestern boundary” of A(C), and can
be characterized as the unique point of A(C) that satisfies
with equality a particular pair of constraints of the form ( 21).