How hard is it to find extreme Nash equilibria in network congestion games?

E. Gassner, J. Hatzl, S.O. Krumke, H. Sperber, G.J. Woeginger

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

2 Citations (Scopus)

Abstract

We study the complexity of finding extreme pure Nash equilibria in symmetric (unweighted) network congestion games. In our context best and worst equilibria are those with minimum respectively maximum makespan. On series-parallel graphs a worst Nash equilibrium can be found by a Greedy approach while finding a best equilibrium is NP-hard. For a fixed number of users we give a pseudo-polynomial algorithm to find the best equilibrium in series-parallel networks. For general network topologies also finding a worst equilibrium is NP-hard.
Original languageEnglish
Title of host publicationInternet and Network Economics (Proceedings 4th International Workshop, WINE'08, Shanghai, China, December 17-20, 2008)
EditorsC. Papadimitriou, S. Zhang
Place of PublicationBerlin
PublisherSpringer
Pages82-93
ISBN (Print)978-3-540-92184-4
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
Volume5385
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'How hard is it to find extreme Nash equilibria in network congestion games?'. Together they form a unique fingerprint.

Cite this