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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65–67 (1973)
Tennenholtz, M., Zohar, A.: Learning equilibria in repeated congestion games. In: Proceedings of AAMAS 2009 (2009)
Liu, M., Wu, Y.: Spectum sharing as congestion games. In: Proceedings the 46th Annual Allterton Conference on Communication, Control, and Computing (2008)
Law, L., Huang, J., Liu, M., Li, S.: Price of Anarchy for Cognitive MAC Games. In: Proceedings of IEEE GLOBECOM (2009)
Chen, X., Huang, J.: Evolutionarily Stable Spectrum Access in a Many-Users Regime. In: Proceedings of IEEE GLOBECOM (2011)
Southwell, R., Huang, J.: Spectrum Mobility Games. In: IEEE INFOCOM (2012)
Vöcking, B., Aachen, R.: Congestion games: Optimization in competition. In: Proceedings of the Second ACiD Workshop (2006)
Tardos, E., Wexler, T.: Network formation games and the potential function method. In: Algorithmic Game Theory. ch.19, pp. 487–516 (2007)
Fretwell, S.D., Lucas, H.L.: On Territorial Behavior and Other Factors Influencing Habitat Distribution in Birds. Acta Biotheor. 19, 16–36 (1969)
Lachapelle, A., Wolfram, M.: On a mean field game approach modeling congestion and aversion in pedestrian crowds. Transportation Research Part B: Methodological. 45, 1572–1589 (2011)
Godin, J., Keenleyside, M.: Foraging on Patchily Distributed Preyby a Cichlid Fish (Teleostei, Cichlidae): A Test of the Ideal Free Distribution Theory. Anim. Behav. 32, 120–131 (1984)
Ackermann, H., Röglin, H., Vöcking, B.: On the Impact of Combinatorial Structure on Congestion Games. In: Proceedings of FOCS 2006 (2006)
Southwell, R., Huang, J.: Convergence Dynamics of Resource-Homogeneous Congestion Games. In: Jain, R., Kannan, R. (eds.) GameNets 2011. LNICST, vol. 75, pp. 281–293. Springer, Heidelberg (2012)
Milchtaich, I.: Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior 13, 111–124 (1996)
Chen, X., Huang, J.: Spatial Spectrum Access Game: Nash Equilibria and Distributed Learning. In: ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Hilton Head Island, South Carolina, USA (June 2012)
Ackermann, H., Röglin, H., Vöcking, B.: Pure Nash Equilibria in Player-Specific and Weighted Congestion Games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 50–61. Springer, Heidelberg (2006)
Tekin, C., Liu, M., Southwell, R., Huang, J., Ahmad, S.: Atomic Congestion Games on Graphs and its Applications in Networking. IEEE Transactions on Networking (to appear, 2012)
Etkin, R., Parekh, A., Tse, D.: Spectrum sharing for unlicensed bands. IEEE Journal on Selected Areas in Communications 25, 517–528 (2007)
Bilo, V., Fanelli, A., Flammini, M., Moscardelli, L.: Graphical congestion games. Algorithmica 61, 274–297 (2008)
Fotakis, D., Gkatzelis, V., Kaporis, A.C., Spirakis, P.G.: The Impact of Social Ignorance on Weighted Congestion Games. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 316–327. Springer, Heidelberg (2009)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Matroids, Trees, Stable Sets, Volume B, 39–69 (2009)
Werneck, R., Setubal, J., Conceicao, A.: Finding minimum congestion spanning trees. Journal of Experimental Algorithmics 5 (2000)
Goemans, M., Li, L., Mirrokni, V., Thottan, M.: Market sharing games applied to content distribution in ad-hoc networks. In: Proceedings of MobiHoc 2004 (2004)
Southwell, R., Chen, Y., Huang, J., Zhang, Q.: Convergence Dynamics of Graphical Congestion Games, Technical Report, http://jianwei.ie.cuhk.edu.hk/publication/GCCConvergenceTechReport.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 ICST Institute for Computer Science, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Southwell, R., Chen, Y., Huang, J., Zhang, Q. (2012). Convergence Dynamics of Graphical Congestion Games. In: Krishnamurthy, V., Zhao, Q., Huang, M., Wen, Y. (eds) Game Theory for Networks. GameNets 2012. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 105. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35582-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-35582-0_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35581-3
Online ISBN: 978-3-642-35582-0
eBook Packages: Computer ScienceComputer Science (R0)