On the complexity of pure Nash equilibria in player-specific network congestion games

Heiner Ackermann*, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

Abstract

Network congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. We therefore address the computational complexity of the corresponding decision problem, and show that it is NP-complete to decide whether such games possess pure Nash equilibria. This negative result still holds in the case of games with two players only. In contrast, we show that one can decide in polynomial time whether an equilibrium exists if the number of resources is constant. In addition, we introduce a family of player-specific network congestion games which are guaranteed to possess equilibria. In these games players have identical delay functions, however, each player may only use a certain subset of the edges. For this class of games we prove that finding a pure Nash equilibrium is PLS-complete even in the case of three players. Again, in the case of a constant number of edges an equilibrium can be computed in polynomial time. We conclude that the number of resources has a bigger impact on the computation complexity of certain problems related to network congestion games than the number of players.

Original languageEnglish
Title of host publicationInternet and Network Economics
Subtitle of host publicationThird International Workshop, WINE 2007, Proceedings
EditorsXiaotie Deng, Fan Chung Graham
Pages419-430
Number of pages12
ISBN (Electronic)978-3-540-77105-0
DOIs
Publication statusPublished - 1 Dec 2007
Externally publishedYes
Event3rd International Workshop on Internet and Network Economics, WINE 2007 - San Diego, United States
Duration: 12 Dec 200714 Dec 2007
Conference number: 3

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4858 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Workshop on Internet and Network Economics, WINE 2007
Abbreviated titleWINE 2007
CountryUnited States
CitySan Diego
Period12/12/0714/12/07

Fingerprint Dive into the research topics of 'On the complexity of pure Nash equilibria in player-specific network congestion games'. Together they form a unique fingerprint.

Cite this