Game Theory for Networks. Third International ICST Conference, GameNets 2012, Vancouver, BC, Canada, May 24-26, 2012, Revised Selected Papers

Research Article

Convergence Dynamics of Graphical Congestion Games

Download126 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-35582-0_3,
        author={Richard Southwell and Yanjiao Chen and Jianwei Huang and Qian Zhang},
        title={Convergence Dynamics of Graphical Congestion Games},
        proceedings={Game Theory for Networks. Third International ICST Conference, GameNets 2012, Vancouver, BC, Canada, May 24-26, 2012, Revised Selected Papers},
        proceedings_a={GAMENETS},
        year={2012},
        month={12},
        keywords={congestion game resource allocation matroid games on graphs graphical},
        doi={10.1007/978-3-642-35582-0_3}
    }
    
  • Richard Southwell
    Yanjiao Chen
    Jianwei Huang
    Qian Zhang
    Year: 2012
    Convergence Dynamics of Graphical Congestion Games
    GAMENETS
    Springer
    DOI: 10.1007/978-3-642-35582-0_3
Richard Southwell1,*, Yanjiao Chen2,*, Jianwei Huang1,*, Qian Zhang2,*
  • 1: The Chinese University of Hong Kong
  • 2: Hong Kong University of Science and Technology
*Contact email: richardsouthwell254@gmail.com, chenyj.thu@gmail.com, jianweihuang@gmail.com, qianzh@cse.ust.hk

Abstract

Graphical congestion games provide powerful models for a wide range of scenarios where spatially distributed individuals share resources. Understanding when graphical congestion game dynamics converge to pure Nash equilibria yields important engineering insights into when spatially distributed individuals can reach a stable resource allocation. In this paper, we study the convergence dynamics of graphical congestion games where players can use multiple resources simultaneously. We show that when the players are free to use any subset of resources the game always converges to a pure Nash equilibrium in polynomial time via lazy best response updates. When the collection of sets of resources available to each player is a matroid, we show that pure Nash equilibria may not exist in the most general case. However, if the resources are homogenous, the game can converge to a Nash equilibrium in polynomial time.