On the inefficiency of equilibria in linear bottleneck congestion games
Presented at the International Symposium on Algorithmic Game Theory, Athens, Greece
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.
|Keywords||PoA, SPoA, congestion, bottleneck, game theory, Price of Anarchy, Strong Price of Anarchy|
|THEME||Logistics (theme 3)|
|Editor||S. Kontogiannis (Spyros) , E. Koutsoupias (Elias) , P.G. Spirakis (Paul)|
|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