Routing (Un-) splittable flow in games with player-specific affine latency functions

摘要

In this work we studyweighted network congestion gameswith player-specific latency functionswhere selfish players wish to route their traffic through a shared network. We consider both the case of splittable and unsplittable traffic. Our main findings are as follows. For routing games on parallel links with linear latency functions, we introduce two new potential functions for unsplittable and for splittable traffic, respectively. We use these functions to derive results on the convergence to pure Nash equilibria and the computation of equilibria. For several generalizations of these routing games, we show that such potential functions do not exist. We prove tight upper and lower bounds on the price of anarchy for games with polynomial latency functions. All our results on the price of anarchy translate to general congestion games.