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

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.