research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleSelfish Unsplittable Flows
Bibtex cite IDRACTI-RU1-2004-11
Booktitle 31st International Colloquium on Automata, Languages and Programming(ICALP 2004)
Year published 2004
Month July
Pages 593-605
Publisher Springer - Verlag Berlin Heidelberg 2004
Organization ICALP 2004
Location Turku, Finland
What is the price of anarchy when unsplittable demands are routed selfishly in general networks with load-dependent edge delays? Motivated by this question we generalize the model of [14] to the case of weighted congestion games.We show that varying demands of users crucially affect the nature of these games, which are no longer isomorphic to exact potential games, even for very simple instances. Indeed we construct examples where even a single-commodity (weighted) network congestion game may have no pure Nash equilibrium. On the other hand, we study a special family of networks (which we call the -layered networks) and we prove that any weighted congestion game on such a network with resource delays equal to the congestions, possesses a pure Nash Equilibrium. We also show how to construct one in pseudo-polynomial time. Finally, we give a surprising answer to the question above for such games: The price of anarchy of any weighted -layered network congestion game with m edges and edge delays equal to the loads, is È  logm log logm.
Fotakis, Dimitris
Kontogiannis, Spyros
Spirakis, Paul
LNCS3142[pp593-605].pdf (main file)
Publication ID217