Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Convergence Dynamics of Graphical Congestion Games

  • Conference paper

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

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65–67 (1973)

    Article MathSciNet MATH  Google Scholar 

  2. Tennenholtz, M., Zohar, A.: Learning equilibria in repeated congestion games. In: Proceedings of AAMAS 2009 (2009)

    Google Scholar 

  3. Liu, M., Wu, Y.: Spectum sharing as congestion games. In: Proceedings the 46th Annual Allterton Conference on Communication, Control, and Computing (2008)

    Google Scholar 

  4. Law, L., Huang, J., Liu, M., Li, S.: Price of Anarchy for Cognitive MAC Games. In: Proceedings of IEEE GLOBECOM (2009)

    Google Scholar 

  5. Chen, X., Huang, J.: Evolutionarily Stable Spectrum Access in a Many-Users Regime. In: Proceedings of IEEE GLOBECOM (2011)

    Google Scholar 

  6. Southwell, R., Huang, J.: Spectrum Mobility Games. In: IEEE INFOCOM (2012)

    Google Scholar 

  7. Vöcking, B., Aachen, R.: Congestion games: Optimization in competition. In: Proceedings of the Second ACiD Workshop (2006)

    Google Scholar 

  8. Tardos, E., Wexler, T.: Network formation games and the potential function method. In: Algorithmic Game Theory. ch.19, pp. 487–516 (2007)

    Google Scholar 

  9. Fretwell, S.D., Lucas, H.L.: On Territorial Behavior and Other Factors Influencing Habitat Distribution in Birds. Acta Biotheor. 19, 16–36 (1969)

    Article  Google Scholar 

  10. 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)

    Article  Google Scholar 

  11. 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)

    Article  Google Scholar 

  12. Ackermann, H., Röglin, H., Vöcking, B.: On the Impact of Combinatorial Structure on Congestion Games. In: Proceedings of FOCS 2006 (2006)

    Google Scholar 

  13. 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)

    Chapter  Google Scholar 

  14. Milchtaich, I.: Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior 13, 111–124 (1996)

    Article MathSciNet MATH  Google Scholar 

  15. 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)

    Google Scholar 

  16. 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)

    Chapter  Google Scholar 

  17. 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)

    Google Scholar 

  18. Etkin, R., Parekh, A., Tse, D.: Spectrum sharing for unlicensed bands. IEEE Journal on Selected Areas in Communications 25, 517–528 (2007)

    Article  Google Scholar 

  19. Bilo, V., Fanelli, A., Flammini, M., Moscardelli, L.: Graphical congestion games. Algorithmica 61, 274–297 (2008)

    Article MathSciNet MATH  Google Scholar 

  20. 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)

    Chapter  Google Scholar 

  21. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Matroids, Trees, Stable Sets, Volume B, 39–69 (2009)

    Google Scholar 

  22. Werneck, R., Setubal, J., Conceicao, A.: Finding minimum congestion spanning trees. Journal of Experimental Algorithmics 5 (2000)

    Google Scholar 

  23. 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)

    Google Scholar 

  24. 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

Download references

Author information

Authors and Affiliations

  1. Information Engineering Department, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong

    Richard Southwell & Jianwei Huang

  2. Computer Science and Engineering Department, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong

    Yanjiao Chen & Qian Zhang

Authors
  1. Richard Southwell

    You can also search for this author inPubMed Google Scholar

  2. Yanjiao Chen

    You can also search for this author inPubMed Google Scholar

  3. Jianwei Huang

    You can also search for this author inPubMed Google Scholar

  4. Qian Zhang

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of British Columbia, V6T 1Z4, Vancouver, BC, Canada

    Vikram Krishnamurthy

  2. Electrical and Computer Engineering, University of California, 95616, Davis, CA, USA

    Qing Zhao

  3. Carleton University, K1S 5B6, Ottawa, ON, Canada

    Minyi Huang

  4. 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

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp