How to find Nash equilibria with extreme total latency in network congestion games?

  • We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it depends on the graph topology and the number of users. In our context best and worst equilibria are those with minimum respectively maximum total latency. We establish that both problems can be solved by a Greedy algorithm with a suitable tie breaking rule on parallel links. On series-parallel graphs finding a worst Nash equilibrium is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. Additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Heike Sperber
URN (permanent link):urn:nbn:de:hbz:386-kluedo-15786
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (116)
Document Type:Report
Language of publication:English
Year of Completion:2008
Year of Publication:2008
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2008/10/29
Tag:complexity; extreme equilibria; network congestion game; total latency
GND-Keyword:Berechnungskomplexität; Spieltheorie
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011