Skip to main content

2014 | OriginalPaper | Buchkapitel

Competition for Resources

The Equilibrium Existence Problem in Congestion Games

verfasst von : Max Klimm

Erschienen in: Operations Research Proceedings 2013

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Congestion games are an elegant model to study the effects of selfish usage of resources. In my thesis—of the same title as this note—we characterized the maximal conditions for which the existence of a pure Nash equilibrium can be guaranteed for four variants of congestion games: weighted congestion games, congestion games with resource-dependent demands, congestion games with variable demands, and bottleneck congestion games. This note reviews the main results obtained there.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Ackermann, H., Röglin, H., & Vöcking, B. (2008). On the impact of combinatorial structure on congestion games. Journal of the ACM, 55(6), 1–22.CrossRef Ackermann, H., Röglin, H., & Vöcking, B. (2008). On the impact of combinatorial structure on congestion games. Journal of the ACM, 55(6), 1–22.CrossRef
2.
Zurück zum Zitat Andelman, N., Feldman, M., & Mansour, Y. (2009). Strong price of anarchy. Games and Economic Behavior, 65(2), 289–317.CrossRef Andelman, N., Feldman, M., & Mansour, Y. (2009). Strong price of anarchy. Games and Economic Behavior, 65(2), 289–317.CrossRef
3.
Zurück zum Zitat Awerbuch, B., Azar, Y., Richter, Y., & Tsur, D. (2006). Tradeoffs in worst-case equilibria. Theoretical Computer Science, 361(2–3), 200–209.CrossRef Awerbuch, B., Azar, Y., Richter, Y., & Tsur, D. (2006). Tradeoffs in worst-case equilibria. Theoretical Computer Science, 361(2–3), 200–209.CrossRef
4.
Zurück zum Zitat Banner, R., & Orda, A. (2007). Bottleneck routing games in communication networks. IEEE Journal on Selected Areas in Communications, 25(6), 1173–1179.CrossRef Banner, R., & Orda, A. (2007). Bottleneck routing games in communication networks. IEEE Journal on Selected Areas in Communications, 25(6), 1173–1179.CrossRef
5.
Zurück zum Zitat Even-Dar, E., Kesselman, A., & Mansour, Y. (2007). Convergence time to Nash equilibrium in load balancing. ACM Transactions on Algorithms, 3(3), 1–21.CrossRef Even-Dar, E., Kesselman, A., & Mansour, Y. (2007). Convergence time to Nash equilibrium in load balancing. ACM Transactions on Algorithms, 3(3), 1–21.CrossRef
6.
Zurück zum Zitat Fabrikant, A., Papadimitriou, C., Talwar, K. (2004). The complexity of pure Nash equilibria. In Proceedings of the thirty-sixth annual ACM symposium on theory of computing, pp. 604–612. Fabrikant, A., Papadimitriou, C., Talwar, K. (2004). The complexity of pure Nash equilibria. In Proceedings of the thirty-sixth annual ACM symposium on theory of computing, pp. 604–612.
7.
Zurück zum Zitat Fotakis, D., Kontogiannis, S., & Spirakis, P. (2005). Selfish unsplittable flows. Theoretical Computer Science, 348(2–3), 226–239.CrossRef Fotakis, D., Kontogiannis, S., & Spirakis, P. (2005). Selfish unsplittable flows. Theoretical Computer Science, 348(2–3), 226–239.CrossRef
8.
Zurück zum Zitat Goemans, M., Mirrokni, V., Vetta, A. (2005). Sink equilibria and convergence. In Proceedings of 46th annual IEEE symposium on foundations of computer science, pp. 142–154. Goemans, M., Mirrokni, V., Vetta, A. (2005). Sink equilibria and convergence. In Proceedings of 46th annual IEEE symposium on foundations of computer science, pp. 142–154.
9.
Zurück zum Zitat Harks, T., Klimm, M. (2011). Congestion games with variable demands. In Proceedings of the 13th conference on theoretical aspects of rationality and knowledge, pp. 111–120. Harks, T., Klimm, M. (2011). Congestion games with variable demands. In Proceedings of the 13th conference on theoretical aspects of rationality and knowledge, pp. 111–120.
10.
Zurück zum Zitat Harks, T., & Klimm, M. (2012). On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research, 37(3), 419–436.CrossRef Harks, T., & Klimm, M. (2012). On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research, 37(3), 419–436.CrossRef
11.
Zurück zum Zitat Harks, T., Klimm, M., & Möhring, R. (2011). Characterizing the existence of potential functions in weighted congestion games. Theory of Computing Systems, 49(1), 46–70.CrossRef Harks, T., Klimm, M., & Möhring, R. (2011). Characterizing the existence of potential functions in weighted congestion games. Theory of Computing Systems, 49(1), 46–70.CrossRef
12.
Zurück zum Zitat Harks, T., Hoefer, M., Klimm, M., & Skopalik, A. (2012a). Computing pure Nash and strong equilibria in bottleneck congestion games. To appear: Mathematical Programming. Harks, T., Hoefer, M., Klimm, M., & Skopalik, A. (2012a). Computing pure Nash and strong equilibria in bottleneck congestion games. To appear: Mathematical Programming.
13.
Zurück zum Zitat Harks, T., Klimm, M., & Möhring, R. (2012b). Strong equilibria in games with the lexicographical improvement property. International Journal of Game Theory, 42(2), 461–482.CrossRef Harks, T., Klimm, M., & Möhring, R. (2012b). Strong equilibria in games with the lexicographical improvement property. International Journal of Game Theory, 42(2), 461–482.CrossRef
14.
Zurück zum Zitat Klimm, M. (2012). Competition for resources: The equilibrium existence problem in congestion games. PhD thesis. Klimm, M. (2012). Competition for resources: The equilibrium existence problem in congestion games. PhD thesis.
15.
Zurück zum Zitat Libman, L., & Orda, A. (2001). Atomic resource sharing in noncooperative networks. Telecommunication Systems, 17(4), 385–409.CrossRef Libman, L., & Orda, A. (2001). Atomic resource sharing in noncooperative networks. Telecommunication Systems, 17(4), 385–409.CrossRef
16.
Zurück zum Zitat Nash, J. (1950). Equilibrium points in \(n\)-person games. Proceedings of the National Academy of Sciences, 36, 48–49.CrossRef Nash, J. (1950). Equilibrium points in \(n\)-person games. Proceedings of the National Academy of Sciences, 36, 48–49.CrossRef
17.
Zurück zum Zitat Panagopoulou, P., & Spirakis, P. (2006). Algorithms for pure Nash equilibria in weighted congestion games. Journal of Experimental Algorithmics, 11, 1–19. Panagopoulou, P., & Spirakis, P. (2006). Algorithms for pure Nash equilibria in weighted congestion games. Journal of Experimental Algorithmics, 11, 1–19.
18.
Zurück zum Zitat Rosenthal, R. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1), 65–67.CrossRef Rosenthal, R. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1), 65–67.CrossRef
Metadaten
Titel
Competition for Resources
verfasst von
Max Klimm
Copyright-Jahr
2014
DOI
https://doi.org/10.1007/978-3-319-07001-8_34