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 − m) factor larger than that of the optimal
outcome, where (λ, m) 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 C. Of
course, precisely computing the exact value of the worst-case
POA is not trivial, even for simple sets C. Arguments in Aland
1 and Olver18 imply a (complex) closed-form expression for
the worst-case POA when C is a set of polynomials with nonnegative coefficients. Similar computations should be possible for some other simple sets C. 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 C 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 C,
the worst-case POA is always achieved in two-node two-link
5. FuRtheR ReLateD WoRK
The price of anarchy was first studied in Koutsoupias and
Papadimitriou14 for makespan minimization in scheduling
games. This is not a sum objective function, and the worst-case POA in this model was immediately recognized to be
different for different equilibrium concepts.
3, 14 See Chapter
20 of Nisan et al.
17 for a survey of the literature on this model.
The POA with a sum objective was first studied in Roughgarden and Tardos24 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.
2 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
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
1 Awerbuch et al.,
2 Christodoulou and Koutsoupias,
Vetta25 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,
6 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.
3 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 games25 and the (suboptimal) bounds
of Awerbuch et al.
2 and Christodoulou and Koutsoupias7 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: Perakis19 for a nonatomic routing model
with nonseparable cost functions, Christodoulou and
Koutsoupias6 for congestion games with affine cost functions, and Harks11 for splittable congestion games.
Pure-strategy Nash equilibria—where each player deter-ministically 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
d Since the conference version of this article, the definition of smooth games
has been refined and extended in several ways, and new smoothness arguments have been discovered for a number of interesting models. See the full
version22 for details and references.