Figure 1. Generalizations of pure nash equilibria. “Pne” stands for
pure nash equilibria, “mne” for mixed nash equilibria, “Coreq” for
correlated equilibria, and “no Regret (CCe)” for coarse correlated
equilibria, which are the empirical distributions corresponding to
repeated joint play in which every player has no (external) regret.
No Regret (CCE)
(B) 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
(C) 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.
2. smooth Games
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
16 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.
17). 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.
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 (λ, m)-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 (λ, m)-smooth, with λ>0 and
m < 1, then each of its pure Nash equilibria s has cost at most
λ/( 1− m) times that of an optimal solution s*. In proof, we
1. 2. overview
Our contributions can be divided into three parts.
(A) 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
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 s*i ; 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.