On the complexity of pure-strategy Nash equilibria in congestion and local-effect games - Extended abstract

Congestion games are a fundamental class of noncooperative games possessing pure-strategy Nash equilibria. In the network version, each player wants to route one unit of flow on a path from her origin to her destination at minimum cost, and the cost of using an arc only depends on the total number of players using that arc. A natural extension is to allow for players sending 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, we prove that it actually is 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 (has to be routed on a single path for each player) or not. A related family of games are local-effect games, where the disutility of a player taking a particular action depends on the number of players taking the same action and on the number of players choosing related actions. We show that the problem of deciding whether a bidirectional local-effect game has a pure-strategy Nash equilibrium is NP-complete, and that the problem of finding a pure-strategy Nash equilibrium in a bidirectional local-effect game with linear local-effect functions (for which the existence of a pure-strategy Nash equilibrium is guaranteed) is PLS-complete. The latter proof uses a tight PLS-reduction, which implies the existence of instances and initial states for which any sequence of selfish improvement steps needs exponential time to reach a pure-strategy Nash equilibrium.