@inproceedings{f588b4954571476486a55842aefd6ec7,

title = "How hard is it to find extreme Nash equilibria in network congestion games?",

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.",

author = "E. Gassner and J. Hatzl and S.O. Krumke and H. Sperber and G.J. Woeginger",

year = "2008",

doi = "10.1007/978-3-540-92185-1_17",

language = "English",

isbn = "978-3-540-92184-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "82--93",

editor = "C. Papadimitriou and S. Zhang",

booktitle = "Internet and Network Economics (Proceedings 4th International Workshop, WINE'08, Shanghai, China, December 17-20, 2008)",

address = "Germany",

}