Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 1/2019

03.01.2018

Price of Anarchy for Highly Congested Routing Games in Parallel Networks

verfasst von: Riccardo Colini-Baldeschi, Roberto Cominetti, Marco Scarsini

Erschienen in: Theory of Computing Systems | Ausgabe 1/2019

Einloggen

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

search-config
loading …

Abstract

We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.
Vorheriger Artikel The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games
Nächster Artikel An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Attouch, H.: Variational Convergence for Functions and Operators. Pitman, Boston (1984)MATH
2.
Beckmann, M.J., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
3.
Bingham, N.H., Goldie, C.M., Teugels, J.L.: Regular Variation, volume 27 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1989)
4.
Cole, R., Tao, Y.: Large market games with near optimal efficiency. In: Conitzer, V., Bergemann, D., Chen, Y. (eds.) Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, July 24–28, 2016, pp. 791–808. ACM, Maastricht (2016)
5.
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004)MathSciNetCrossRefMATH
6.
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Fast, fair, and efficient flows in networks. Oper. Res. 55(2), 215–225 (2007)MathSciNetCrossRefMATH
7.
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: A geometric approach to the price of anarchy in nonatomic congestion games. Games Econ. Behav. 64(2), 457–469 (2008)MathSciNetCrossRefMATH
8.
de Haan, L.: On Regular Variation and its Application to the Weak Convergence of Sample Extremes, volume 32 of Mathematical Centre Tracts. Mathematisch Centrum, Amsterdam (1970)
9.
Dumrauf, D., Gairing, M.: Price of anarchy for polynomial Wardrop games. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds.) Internet and Network Economics: Second International Workshop, WINE 2006, Patras, Greece, December 15–17, 2006. Proceedings, pp. 978–3-540-68141-0. Springer, Berlin (2006)
10.
11.
Feldman, M., Immorlica, N., Lucier, B., Roughgarden, T., Syrgkanis, V.: The price of anarchy in large games. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, June 18–21, vol. 2016, pp. 963–976. ACM, Cambridge (2016)
12.
Florian, M., Hearn, D.: Network equilibrium and pricing. In: Hall, R.W. (ed.) Handbook of Transportation Science, pp. 373–411. Springer US, Boston (2003)
13.
González Vayá, M., Grammatico, S., Andersson, G., Lygeros, J.: On the price of being selfish in large populations of plug-in electric vehicles. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp. 6542–6547 (2015)
14.
Josefsson, M., Patriksson, M.: Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design. Transp. Res. B Methodol. 41(1), 4–31, 1 (2007)CrossRef
15.
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: STACS 99 (Trier), volume 1563 of Lecture Notes in Computer Science, pp. 404–413. Springer, Berlin (1999)
16.
Law, L.M., Huang, J., Liu, M.: Price of anarchy for congestion games in cognitive radio networks. IEEE Trans. Wirel. Commun. 11(10), 3778–3787 (2012)CrossRef
17.
18.
19.
20.
O’Hare, S.J., Connors, R.D., Watling, D.P.: Mechanisms that govern how the price of anarchy varies with travel demand. Transp. Res. B Methodol. 84, 55–80, 2 (2016)CrossRef
21.
Panageas, I., Piliouras, G.: Approximating the geometry of dynamics inppotential games. Technical report, arXiv:1403.​3885v5 (2015)
22.
Papadimitriou, C.: Algorithms, games, and the Internet. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 749–753. ACM, New York (2001)
23.
Patriksson, M.: Sensitivity analysis of traffic equilibria. Transp. Sci. 38(3), 258–281 (2004)CrossRef
24.
Pigou, A.C.: The Economics of Welfare, 1st edn. Macmillan and Co., London (1920)
25.
Piliouras, G., Nikolova, E., Shamma, J.S.: Risk sensitivity of price of anarchy under uncertainty. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC ’13, pp. 715–732. ACM, New York (2013)
26.
27.
Roughgarden, T.: Routing games. In: Algorithmic Game Theory, pp. 461–486. Cambridge University Press, Cambridge (2007)
28.
29.
Roughgarden, T., Tardos, É.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav. 47(2), 389–403 (2004)MathSciNetCrossRefMATH
30.
Roughgarden, T., Tardos, É.: Introduction to the inefficiency of equilibria. In: Algorithmic Game Theory, pp. 443–459. Cambridge University Press, Cambridge (2007)
31.
32.
Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952)
33.
Youn, H., Gastner, M.T., Jeong, H.: Price of anarchy in transportation networks: efficiency and optimality control. Phys. Rev. Lett. 101, 128701 (2008)CrossRef
Metadaten
Titel
Price of Anarchy for Highly Congested Routing Games in Parallel Networks
verfasst von
Riccardo Colini-Baldeschi
Roberto Cominetti
Marco Scarsini
Publikationsdatum
03.01.2018
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 1/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-017-9834-1

Weitere Artikel der Ausgabe 1/2019

Theory of Computing Systems 1/2019 Zur Ausgabe

EditorialNotes

Preface to the Special Issue on Algorithmic Game Theory

OriginalPaper

The Stable Roommates Problem with Short Lists

OriginalPaper

An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling

OriginalPaper

Analyzing Power in Weighted Voting Games with Super-Increasing Weights

News

A Message from the Springer Editorial Team

OriginalPaper

The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games