Research Article
Bottleneck Routing Games on Grids
@INPROCEEDINGS{10.1007/978-3-642-30373-9_21, author={Costas Busch and Rajgopal Kannan and Alfred Samman}, title={Bottleneck Routing Games on Grids}, proceedings={Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers}, proceedings_a={GAMENETS}, year={2012}, month={10}, keywords={algorithmic game theory bottleneck games routing games price of anarchy grid networks}, doi={10.1007/978-3-642-30373-9_21} }- Costas Busch
Rajgopal Kannan
Alfred Samman
Year: 2012
Bottleneck Routing Games on Grids
GAMENETS
Springer
DOI: 10.1007/978-3-642-30373-9_21
Abstract
We consider routing games on grid network topologies. The social cost is the worst congestion in any of the network edges (bottleneck congestion). Each player’s objective is to find a path that minimizes the bottleneck congestion in its path. We show that the price of anarchy in bottleneck games in grids is proportional to the number of bends that the paths are allowed to take in the grids’ space. We present games where the price of anarchy is . We also give a respective lower bound of Ω() which shows that our upper bound is within only a poly-log factor from the best achievable price of anarchy. A significant impact of our analysis is that there exist bottleneck routing games with small number of bends which give a poly-log approximation to the optimal coordinated solution that may use an arbitrary number of bends. To our knowledge, this is the first tight analysis of bottleneck games on grids.