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

Research Article

Optimal Price of Anarchy of Polynomial and Super-Polynomial Bottleneck Congestion Games

Download33 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-30373-9_22,
        author={Rajgopal Kannan and Costas Busch and Athanasios Vasilakos},
        title={Optimal Price of Anarchy of Polynomial and Super-Polynomial Bottleneck Congestion Games},
        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={},
        doi={10.1007/978-3-642-30373-9_22}
    }
    
  • Rajgopal Kannan
    Costas Busch
    Athanasios Vasilakos
    Year: 2012
    Optimal Price of Anarchy of Polynomial and Super-Polynomial Bottleneck Congestion Games
    GAMENETS
    Springer
    DOI: 10.1007/978-3-642-30373-9_22
Rajgopal Kannan1,*, Costas Busch1,*, Athanasios Vasilakos2,*
  • 1: Louisiana State University
  • 2: Univ. of Western Macedonia
*Contact email: rkannan@csc.lsu.edu, busch@csc.lsu.edu, vasilako@ath.forthnet.gr

Abstract

We introduce , where the utility costs of the players are (super) polynomial functions of the congestion of the resources that they use, and the social cost is determined by the worst congestion of any resource. In particular, the delay function for any resource is of the form , where is the congestion measured as the number of players that use , and the degree of the delay function is bounded as . The utility cost of a player is the sum of the individual delays of the resources that it uses. The social cost of the game is the worst bottleneck resource congestion: max

            , where  is the set of resources. We show that for super-polynomial bottleneck games with , the price of anarchy is , specifically . We also consider general polynomial bottleneck games where each resource can have a distinct monomial latency function but the degree is bounded i.e  with constants  and derive the price of anarchy as , where 
             is the bottleneck congestion in the socially optimal state. We then demonstrate matching lower bounds for both games showing that this price of anarchy is tight.