About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Computing
Paper
The price of routing unsplittable flow
Abstract
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+ √5/2 ≈ 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Θ(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. © 2013 Society for Industrial and Applied Mathematics.