Research Article
Convergence Dynamics of Graphical Congestion Games
@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
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.
