Abstract | 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. |