This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Dunkel, J. Articles by Schulz, A. S. Search for Related Content

On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games

Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
juliane{at}mit.edu
schulz{at}mit.edu

Rosenthal's congestion games constitute one of the few known classes of noncooperative games possessing pure-strategy Nash equilibria. In the network version, each player wants to route one unit of flow on a single path from her origin to her destination at minimum cost, and the cost of using an arc depends only on the total number of players using that arc. A natural extension is to allow for players controlling different amounts of flow, which results in so-called weighted congestion games. While examples have been exhibited showing that pure-strategy Nash equilibria need not exist anymore, we prove that it is actually strongly NP-hard to determine whether a given weighted network congestion game has a pure-strategy Nash equilibrium. This is true regardless of whether flow is unsplittable or not. In the unsplittable case, the problem remains strongly NP-hard for a fixed number of players. In addition to congestion games, we provide complexity results on the existence and computability of pure-strategy Nash equilibria for the closely related family of bidirectional local-effect games. Therein, the cost of a player taking a particular action depends not only on the number of players choosing the same action, but also on the number of players settling for (locally) related actions.

Key Words: noncooperative games; pure-strategy Nash equilibria; computational complexity; congestion games; local-effect games
History: Received: May 21, 2007; revision received: December 20, 2007;