We study the inefficiency of equilibrium outcomes in bottleneck congestion games. These games model situations in which strategic players compete for a limited number of facilities. Each player allocates his weight to a (feasible) subset of the facilities with the goal to minimize the maximum (weight-dependent) latency that he experiences on any of these facilities. We derive upper and (asymptotically) matching lower bounds on the (strong) price of anarchy of linear bottleneck congestion games for a natural load balancing social cost objective (i.e., minimize the maximum latency of a facility). We restrict our studies to linear latency functions. Linear bottleneck congestion games still constitute a rich class of games and generalize, for example, load balancing games with identical or uniformly related machines with or without restricted assignments.
Additional Metadata
Keywords PoA, SPoA, congestion, bottleneck, game theory, Price of Anarchy, Strong Price of Anarchy
THEME Logistics (theme 3)
Publisher Springer
Editor S. Kontogiannis (Spyros) , E. Koutsoupias (Elias) , P.G. Spirakis (Paul)
Persistent URL dx.doi.org/10.1007/978-3-642-16170-4_29
Conference International Symposium on Algorithmic Game Theory
de Keijzer, B, Schäfer, G, & Telelis, O. (2010). On the inefficiency of equilibria in linear bottleneck congestion games. In S Kontogiannis, E Koutsoupias, & P.G Spirakis (Eds.), Algorithmic Game Theory: Third International Symposium, Proceedings. Springer. doi:10.1007/978-3-642-16170-4_29