@inproceedings{19dd012967164c0abcf33ed86625cf2c,
title = "Bottleneck routing games on grids",
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 {\~O}(β). 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.",
keywords = "algorithmic game theory, bottleneck games, grid networks, price of anarchy, routing games",
author = "Costas Busch and Rajgopal Kannan and Alfred Samman",
year = "2012",
doi = "10.1007/978-3-642-30373-9_21",
language = "English (US)",
isbn = "9783642303722",
series = "Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering",
pages = "294--307",
booktitle = "Game Theory for Networks - Second International ICST Conference, GAMENETS 2011, Revised Selected Papers",
note = "2nd International ICST Conference on Game Theory in Networks, GAMENETS 2011 ; Conference date: 16-04-2011 Through 18-04-2011",
}