nach oben

Theory of Computing Systems

Erschienen in:

26.12.2017

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

verfasst von: Pieter Kleer, Guido Schäfer

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We introduce a unifying model to study the impact of worst-case latency deviations in non-atomic selfish routing games. In our model, latencies are subject to (bounded) deviations which are taken into account by the players. The quality deterioration caused by such deviations is assessed by the Deviation Ratio, i.e., the worst case ratio of the cost of a Nash flow with respect to deviated latencies and the cost of a Nash flow with respect to the unaltered latencies. This notion is inspired by the Price of Risk Aversion recently studied by Nikolova and Stier-Moses (Nikolova and Stier-Moses 2015). Here we generalize their model and results. In particular, we derive tight bounds on the Deviation Ratio for multi-commodity instances with a common source and arbitrary non-negative and non-decreasing latency functions. These bounds exhibit a linear dependency on the size of the network (besides other parameters). In contrast, we show that for general multi-commodity networks an exponential dependency is inevitable. We also improve recent smoothness results to bound the Price of Risk Aversion.

Vorheriger Artikel Logarithmic Query Complexity for Approximate Nash Computation in Large Games

Nächster Artikel Price of Anarchy for Highly Congested Routing Games in Parallel Networks

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

Nur mit Berechtigung zugänglich

We remark that for certain types of (0, β)-deviations, e.g., scaled marginal tolls, better bounds can be obtained; see the section “Relations to network toll problems” in Appendix B for relevant literature.

For example, there are parallel-arc networks for which the Biased Price of Anarchy is unbounded, whereas the Deviation Ratio is a constant.

Meir and Parkes [13] define a function l to be (1, μ)-smooth if xl(y) ≤ μyl(y) + xl(x) for all x, y ≥ 0 (which is slightly different from Roughgarden’s original smoothness definition [19]). Lineas et al. [11] only require local smoothness where y is taken fixed.

The existence of a risk-averse Nash flow is proven in [15].

Note that the values l_P(x) + δ_P(x)are the same for all flow-carrying paths, but this is not necessarily true for the valuesl_P(x).

Note that η_i ≤⌈(n − 1)/2⌉.

Note that the pathsP_lcan overlap, use parts of B, or even be subpaths of each other.

We use the standard notation δ⁻(v) and δ⁺(v) to refer to the set of outgoing and incoming edges of a node v, respectively.

Note that the value ⌈(n − 1)/2⌉is the same for n ∈{2m, 2m + 1}with \(m \in \mathbb {N}\).The example shows tightness for n = 2m.The tightness for n = 2m + 1then follows trivially by adding a dummy node.

For example \(y_{m}(g) = m(m-1)\beta \max \{0,(g - \frac {1}{m})\}\).That is, we define y_mto be zero for 0 ≤ g ≤ 1/m and we let it increase with constant rate toβ in 1/(m − 1).

We assume that the infimum and supremum are attained in the set Δ(𝜃); in particular, this is true for (α, β)-deviations.

Beckmann, M., McGuire, B., Winsten, C.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)

Bonifaci, V., Salek, M., Schäfer, G.: On the efficiency of restricted tolls in network routing games. Lecture Notes in Computer Science (2011)

Chen, P.-A., Kempe, D.: Altruism, selfishness, and spite in traffic routing. In: Proceedings of the 9th ACM conference on electronic commerce, pp 140–149. ACM (2008)

Christodoulou, G., Koutsoupias, E., Spirakis, P. G.: On the performance of approximate equilibria in congestion games. Algorithmica 61(1), 116–140 (2011)MathSciNetCrossRefMATH

Cominetti, R.: Equilibrium routing under uncertainty. Math. Program. 151 (1), 117–151 (2015)MathSciNetCrossRefMATH

Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: A geometric approach to the price of anarchy in nonatomic congestion games. Games and Economic Behavior 64 (2), 457–469 (2008). Special Issue in Honor of Michael B. MaschlerMathSciNetCrossRefMATH

Englert, M., Franke, T., Olbrich, L.: Sensitivity of Wardrop Equilibria, pp. 158–169. Springer, Berlin (2008)MATH

Fotakis, D., Kalimeris, D., Lianeas, T.: Improving selfish routing for risk-averse players. In: Proceedings of Web and Internet Economics - 11th International Conference, WINE 2015, Amsterdam, the netherlands, december 9–12, 2015, pp 328–342 (2015)

Hoefer, M., Olbrich, L., Skopalik, A.: Taxing subnetworks. In: Papadimitriou, C.H., Zhang, S. (eds.) WINE, volume 5385 of Lecture Notes in Computer Science, pp. 286–294. Springer (2008)

10.

Kleer, P., Schäfer, G.: Path Deviations Outperform Approximate Stability in Heterogeneous Congestion Games, pp. 212–224. Springer International Publishing Cham, Berlin (2017)

11.

Lianeas, T., Nikolova, E., Stier-Moses, N.E.: Asymptotically tight bounds for inefficiency in risk-averse selfish routing. CoRR, arXiv:1510.02067(2015)

12.

Lin, H., Roughgarden, T., Tardos, É., Walkover, A.: Stronger bounds on braess’s paradox and the maximum latency of selfish routing. SIAM J. Discret. Math. 25(4), 1667–1686 (2011)MathSciNetCrossRefMATH

13.

Meir, R., Parkes, D.: Playing the wrong game smoothness bounds for congestion games with behavioral biases. SIGMETRICS Perform. Eval. Rev. 43(3), 67–70 (2015)CrossRef

14.

Meir, R., Parkes, D.C.: Congestion games with distance-based strict uncertainty. CoRR, arXiv:1411.4943 (2014)

15.

Nikolova, E., Stier-Moses, N.E.: A mean-risk model for the traffic assignment problem with stochastic travel times. Oper. Res. 62(2), 366–382 (2014)MathSciNetCrossRefMATH

16.

Nikolova, E., Stier-Moses, N.E.: The Burden of Risk Aversion in Mean-Risk Selfish Routing. In: Proceedings of the 16th ACM Conference on Economics and Computation, EC ’15, pp. 489–506. ACM, New York (2015)

17.

Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)CrossRefMATH

18.

Roughgarden, T.: On the severity of braess’s paradox: Designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922–953 (2006)MathSciNetCrossRefMATH

19.

Roughgarden, T.: Intrinsic robustness of the price of anarchy. J. ACM 62(5), 32 (2015)MathSciNetCrossRefMATH

20.

Wardrop, J. G.: Some theoretical aspects of road traffic research. Proc. Inst. Civ. Eng. 1, 325–378 (1952)

Titel: The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games
verfasst von: Pieter Kleer
Guido Schäfer
Publikationsdatum: 26.12.2017
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-9829-y

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

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2019

The Stable Roommates Problem with Short Lists

Analyzing Power in Weighted Voting Games with Super-Increasing Weights

Price of Anarchy for Highly Congested Routing Games in Parallel Networks

Logarithmic Query Complexity for Approximate Nash Computation in Large Games

A Message from the Springer Editorial Team

Designing Cost-Sharing Methods for Bayesian Games