THE PRICE OF ROUTING UNSPLITTABLE FLOW

In this paper we study the "price of anarchy" for the general class of (weighted and unweighted) atomic "congestion games" with the sum of players' costs as the objective function. We show that for linear resource cost functions the price of anarchy is exactly 3+root 5/2 approximate to 2.618 for weighted congestion games and exactly 2.5 for unweighted congestion games. We show that for resource cost functions that are polynomials of degree d the price of anarchy is d(Theta(d)). Our results also hold for mixed strategies. In particular, these results apply to atomic routing games where the traffic demand from a source to a destination must be satisfied by choosing a single path between source and destination.