Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions

Martin Gairing, Burkhard Monien, Karsten Tiemann

Faculty of CS, EE and Math,
University of Paderborn

In this work we study (weighted) network congestion games with player-specific latency functions where n selfish players wish to route their traffic through a shared network. Most of our results are obtained for linear latency functions. We consider both the case of splittable and unsplittable traffic. We derive several results on the existence and computational complexity of pure Nash equilibria and on the price of anarchy. Our main findings are as follows:

• For routing games on parallel links with linear latency functions without a constant term we introduce two new potential functions for unsplittable and for splittable traffic respectively.
  • In the case of unsplittable traffic we use our potential function to show that games with unweighted players possess the finite improvement property. We also show that games with weighted players do not possess the finite improvement property even if n=3.
  • In the case of splittable traffic we show that our other convex potential function is minimized if and only if the corresponding assignment is an equilibrium. This result implies that an equilibrium can be computed in polynomial time.
  We also show for several generalizations of the above games that such potential functions do not exist.
• We prove upper and lower bounds on the price of anarchy for games with linear latency functions. For the case of unsplittable traffic the upper and lower bound are asymptotically tight. All our results on the price of anarchy translate to general congestion games.