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?