These questions are interesting for
two reasons. First, algorithms for equilibrium computation can be useful
practically, for example in game-play-ing and for multi-agent reasoning. 41
Second, assuming that players can invest only polynomial computation in
playing a game, resolving the complexity of computing an equilibrium concept has economic implications: a polynomial-time algorithm is an important
step toward establishing the concept’s
credibility, while an intractability result
casts doubt on its predictive power.
There has been a frenzy of recent
work on these questions, for many different fundamental equilibrium concepts. Perhaps the most celebrated
results in the area concern the PPAD-
completeness of computing mixed-strategy Nash equilibria in finite
games with two or more players. 8, 12
To briefly convey the spirit of the area
with a minimum of technical fuss,
we instead discuss the complexity of
converging to and computing pure-strategy Nash equilibria in a variant
of the routing games discussed earlier. We then discuss the key differences between the two settings. For
work on the complexity of computing
other equilibrium concepts, such as
market, correlated, and approximate
Nash equilibria, and for a discussion of equilibrium computation in
extensive-form, compact, randomly
generated, and stochastic games, see
Nisan30 and Roughgarden38 and the
references therein.
Pure Nash Equilibria in Network
Congestion Games. In the atomic variant of selfish routing, there are a finite
number k of players that each control
a non-negligible amount of traffic (say
one unit each) and choose a single route
for it. Each edge cost function ce : { 1, 2,
…, k} ® R+, describing the per-player
cost along an edge as a function of its
number of users, is non-decreasing. An
outcome (P1,…,Pk)—a choice of a path
Pi for each player i—is a pure-strategy
Nash equilibrium (PNE) if each player simultaneously chooses a best response:
a path with minimum possible cost,
given the paths chosen by the other
players. For instance, consider Pigou’s
example (Figure 1a) with the constant
cost on the upper edge raised from 1 to
2. If there are two players (with origin s
and destination t), then there are three
equilibrium
concepts play
a starring role
in game theory.
if nothing else,
a notion of
equilibrium
describes outcomes
that, once reached,
persist under
some model of
individual behavior.
PNE: one with both players on the lower
link, and two in which each link is used
by a single player. In every case, a deviating player would incur cost 2 and be no
better off than in the equilibrium.
Best-response dynamics is a simple
model of experimentation by players
over time: while the current outcome
is not a PNE, choose an arbitrary player
that is not using a best response, and
update its path to a best response. The
update of one player usually changes
the best responses of the others; for
this reason, best-response dynamics
fails to converge in many games (such
as “Rock-Paper-Scissors”). In an atomic
selfish routing network, however, every
iteration of best-response dynamics
strictly decreases the potential function
F ( P1, … , Pk) = ∑
eÎE
[ce ( 1) + ce ( 2) + · · · + ce
(xe)],
where xe denotes the number of paths
Pi that contain edge e, and is thus guaranteed to terminate, necessarily at a
PNE. 26, 34 Does convergence require polynomial or exponential time? Can we
compute a PNE of such a game by other
means in polynomial time?