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 a...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2008-11, Vol.33 (4), p.851-868
Main Authors: Dunkel, Juliane, Schulz, Andreas S
Format: Article
Language:English
Subjects:
Analysis
Complexity theory
Computational complexity
congestion games
Cost functions
Game theory
Integers
local-effect games
Mathematical analysis
Mathematical functions
Mathematical theorems
Nash equilibrium
noncooperative games
Operations research
Polynomials
pure-strategy Nash equilibria
Studies
Unit costs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.1080.0322