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

Research Article

Convergence Dynamics of Resource-Homogeneous Congestion Games

Download98 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-30373-9_20,
        author={Richard Southwell and Jianwei Huang},
        title={Convergence Dynamics of Resource-Homogeneous 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={congestion game resource allocation cognitive radio games on graphs convergence time},
        doi={10.1007/978-3-642-30373-9_20}
    }
    
  • Richard Southwell
    Jianwei Huang
    Year: 2012
    Convergence Dynamics of Resource-Homogeneous Congestion Games
    GAMENETS
    Springer
    DOI: 10.1007/978-3-642-30373-9_20
Richard Southwell1,*, Jianwei Huang1,*
  • 1: The Chinese University of Hong Kong Shatin
*Contact email: richardsouthwell254@gmail.com, jianweihuang@gmail.com

Abstract

Many resource sharing scenarios can be modeled as congestion games. A nice property of congestion games is that simple dynamics are guaranteed to converge to Nash equilibria. Loose bounds on the convergence time are known, but exact results are difficult to obtain in general. We investigate congestion games where the resources are homogeneous but can be player-specific. In these games, players always prefer less used resources. We derive exact conditions for the longest and shortest convergence times. We also extend the results to games on graphs, where individuals only cause congestions to their neighbors. As an example, we apply our results to study cognitive radio networks, where selfish users share wireless spectrum opportunities that are constantly changing. We demonstrate how fast the users need to be able to switch channels in order to track the time-variant channel availabilities.