BOUNDING THE PRICE OF ANARCHY FOR GAMES WITH PLAYER-SPECIFIC COST FUNCTIONS

Abstract. We study the efficiency of equilibria in atomic splittable congestion games on networks. We consider the general case where players are not affected in the same way by the congestion. Extending a result by Cominetti, Correa, and Stier-Moses (The impact of oligopolistic competition in networks, Oper. Res., 57, 1421–1437 (2009)), we prove a general bound on the price of anarchy for games with player-specific cost functions. This bound generalizes some of their results, especially the bound they obtain for the affine case. However our bound still requires some dependence between the cost functions of the players. In the general case, we prove that the price of anarchy is unbounded, by exhibiting an example with affine cost functions and only two players. 1