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)

CorEq
MNE
Easy to
compute/
learn
Always
exists, hard
to compute

(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 Figure 1.

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

 

PNE
Need not
exist, hard
to compute

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

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*,
( 2)

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
derive
( 3)

( 4)

( 5)

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

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.