Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers

Research Article

Bottleneck Routing Games on Grids

Download51 downloads
  • @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
Costas Busch1,*, Rajgopal Kannan1,*, Alfred Samman1,*
  • 1: Louisiana State University
*Contact email: busch@csc.lsu.edu, rkannan@csc.lsu.edu, samman@csc.lsu.edu

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.