nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Equilibria in Routing Games with Edge Priorities

verfasst von : Robert Scheffler, Martin Strehler, Laura Vargas Koch

Erschienen in: Web and Internet Economics

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we present a new routing model with edge priorities. We consider network users that route packages selfishly through a network over time and try to reach their destinations as fast as possible. If the number of packages that want to enter an edge at the same time exceeds the inflow capacity of this edge, edge priorities with respect to the preceding edge solve these conflicts. For this class of games, we show the existence of equilibrium solutions for single-source-single-sink games and we analyze structural properties of these solutions. We present an algorithm that computes Nash equilibria and we prove bounds both on the Price of Stability and on the Price of Anarchy. Moreover, we introduce the new concept of the Price of Mistrust and analyze the connection to earliest arrival flows.

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 "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

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

Vorheriges Kapitel Robust Bounds on Choosing from Large Tournaments

Nächstes Kapitel Cost-Sharing Games in Real-Time Scheduling Systems

Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)MathSciNetCrossRef

Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 57–66. ACM (2005)

Braess, D.: Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)MathSciNetMATH

Cao, Z., Chen, B., Chen, X., Wang, C.: A network game of dynamic traffic. arXiv preprint arXiv:1705.01784 (2017)

Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 67–73. ACM (2005)

Cominetti, R., Correa, J.R., Larré, O.: Existence and uniqueness of equilibria for flows over time. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 552–563. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22012-8_44CrossRefMATH

Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959). https://doi.org/10.1007/BF01386390MathSciNetCrossRefMATH

Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6, 419–433 (1958)MathSciNetCrossRef

Ford, L.R., Fulkerson, D.R.: Flow in Networks. Princeton University Press, Princeton (1962)MATH

10.

Gale, D.: Transient flows in networks. Mich. Math. J. 6, 59–63 (1959)MathSciNetCrossRef

11.

Harks, T., Peis, B., Schmand, D., Koch, L.V.: Competitive packet routing with priority lists. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st MFCS 2016. LIPIcs, vol. 58, pp. 49:1–49:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)MathSciNetCrossRef

12.

Hoefer, M., Mirrokni, V.S., Röglin, H., Teng, S.-H.: Competitive routing over time. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 18–29. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10841-9_4CrossRef

13.

Koch, R., Skutella, M.: Nash equilibria and the price of anarchy for flows over time. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol. 5814, pp. 323–334. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04645-2_29CrossRef

14.

Koch, R., Skutella, M.: Nash equilibria and the price of anarchy for flows over time. Theory Comput. Syst. 49(1), 71–97 (2011)MathSciNetCrossRef

15.

Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_38CrossRef

16.

Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V.: Algorithmic Game Theory, vol. 1. Cambridge University Press, Cambridge (2007)CrossRef

17.

Rosenthal, R.W.: The network equilibrium problem in integers. Networks 3(1), 53–59 (1973)MathSciNetCrossRef

18.

Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM (JACM) 49(2), 236–259 (2002)MathSciNetCrossRef

19.

Scheffler, R., Strehler, M., Koch, L.V.: Nash equilibria in routing games with edge priorities. arXiv preprint arXiv:1803.00865 (2018)

20.

Skutella, M.: An introduction to network flows over time. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Berlin Heidelberg (2009). https://doi.org/10.1007/978-3-540-76796-1_21CrossRef

Titel: Equilibria in Routing Games with Edge Priorities
verfasst von: Robert Scheffler
Martin Strehler
Laura Vargas Koch
Verlag: Springer International Publishing
Buch: Web and Internet Economics
Print ISBN: 978-3-030-04611-8

Electronic ISBN: 978-3-030-04612-5

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-04612-5_27

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"