TY - JOUR

T1 - Complexity of pure nash equilibria in player-specific network congestion games

AU - Ackermann, Heiner

AU - Skopalik, Alexander

PY - 2008/1/1

Y1 - 2008/1/1

N2 - Network congestion games with player-specific delay functions do not possess pure Nash equilibria in general. We therefore address the computational complexity of the corresponding decision problem and prove that it is NP-complete to decide whether a pure Nash equilibrium exists. This result is true for games with directed edges as well as for networks with undirected edges, and still holds for games with two players only. In contrast to games with networks of arbitrary size, we present a polynomial-time algorithm deciding whether there exists a Nash equilibrium in games with networks of constant size. Additionally, we introduce a family of player-specific network congestion games that are guaranteed to possess equilibria. In these games players have identical delay functions. However, each player may use only a certain subset of the edges. For this class of games we prove that finding a pure Nash equilibrium is PLS-complete. Again, this result is true for networks with directed edges as well as for networks with undirected edges, and still holds for games with three players only. In games with networks of constant size, however, we prove that pure Nash equilibria can be computed in polynomial time.

AB - Network congestion games with player-specific delay functions do not possess pure Nash equilibria in general. We therefore address the computational complexity of the corresponding decision problem and prove that it is NP-complete to decide whether a pure Nash equilibrium exists. This result is true for games with directed edges as well as for networks with undirected edges, and still holds for games with two players only. In contrast to games with networks of arbitrary size, we present a polynomial-time algorithm deciding whether there exists a Nash equilibrium in games with networks of constant size. Additionally, we introduce a family of player-specific network congestion games that are guaranteed to possess equilibria. In these games players have identical delay functions. However, each player may use only a certain subset of the edges. For this class of games we prove that finding a pure Nash equilibrium is PLS-complete. Again, this result is true for networks with directed edges as well as for networks with undirected edges, and still holds for games with three players only. In games with networks of constant size, however, we prove that pure Nash equilibria can be computed in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=84920156702&partnerID=8YFLogxK

U2 - 10.1080/15427951.2008.10129170

DO - 10.1080/15427951.2008.10129170

M3 - Article

AN - SCOPUS:84920156702

VL - 5

SP - 323

EP - 342

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

IS - 4

ER -