Part of the book series:Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering ((LNICST,volume 105))
Included in the following conference series:
1491Accesses
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
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
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
Information Engineering Department, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong
Richard Southwell & Jianwei Huang
Computer Science and Engineering Department, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
Yanjiao Chen & Qian Zhang
- Richard Southwell
You can also search for this author inPubMed Google Scholar
- Yanjiao Chen
You can also search for this author inPubMed Google Scholar
- Jianwei Huang
You can also search for this author inPubMed Google Scholar
- Qian Zhang
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
University of British Columbia, V6T 1Z4, Vancouver, BC, Canada
Vikram Krishnamurthy
Electrical and Computer Engineering, University of California, 95616, Davis, CA, USA
Qing Zhao
Carleton University, K1S 5B6, Ottawa, ON, Canada
Minyi Huang
Nanyang Technological University, 639798, Singapore
Yonggang Wen
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
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)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative