Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Excluding Braess’s Paradox in Nonatomic Selfish Routing

Authors : Xujin Chen, Zhuo Diao, Xiaodong Hu

Published in: Algorithmic Game Theory

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Braess’s paradox exposes a counterintuitive phenomenon that when travelers selfishly choose their routes in a network, removing links can improve overall network performance. Under the model of nonatomic selfish routing, we characterize the topologies of k-commodity undirected and directed networks in which Braess’s paradox never occurs. Our results generalize Milchtaich’s series-parallel characterization for the single-commodity undirected case.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter The Web Graph as an Equilibrium
next chapter “Beat-Your-Rival” Routing Games
Footnotes
1
We remark that the definition of paradox-ridden network here is a substantial relaxation the ones given by Roughgarden [11] and Fotakis et al. [4], which admit instances suffering from the most severe performance loss in terms of Braess’s paradox.
 
Literature
1.
Beckmann, M.J., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
2.
Braess, D.: Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung 12(1), 258–268 (1968)MathSciNetMATH
3.
Epstein, A., Feldman, M., Mansour, Y.: Efficient graph topologies in network routing games. Game. Econ. Behav. 66(1), 115–125 (2009)MathSciNetCrossRefMATH
4.
Fotakis, D., Kaporis, A.C., Lianeas, T., Spirakis, P.G.: On the hardness of network design for bottleneck routing games. Theor. Comput. Sci. 521, 107–122 (2014)MathSciNetCrossRefMATH
5.
Holzman, R., Yone (Lev-tov), N.L.: Network structure and strong equilibrium in route selection games. Math. Soc. Sci. 46(2), 193–205 (2003)
6.
Holzman, R., Monderer, D.: Strong equilibrium in network congestion games: increasing versus decreasing costs. Int. J. Game Theory 44, 1–20 (2014)MathSciNetMATH
7.
Lin, H., Roughgarden, T., Tardos, É., Walkover, A.: Stronger bounds on braess’s paradox and the maximum latency of selfish routing. SIAM J. Discrete Math. 25(4), 1667–1686 (2011)MathSciNetCrossRefMATH
8.
9.
Milchtaich, I.: The equilibrium existence problem in finite network congestion games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 87–98. Springer, Heidelberg (2006) CrossRef
10.
11.
Roughgarden, T.: On the severity of braess’s paradox: designing networks for selfish users is hard. J. Compu. Syst. Sci. 72(5), 922–953 (2006)MathSciNetCrossRefMATH
12.
13.
Tutte, W.T.: Graph Theory. Electronic Library of Mathematics. China Machine Press, Beijing (2004)
Metadata
Title
Excluding Braess’s Paradox in Nonatomic Selfish Routing
Authors
Xujin Chen
Zhuo Diao
Xiaodong Hu
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Algorithmic Game Theory

Print ISBN: 978-3-662-48432-6

Electronic ISBN: 978-3-662-48433-3

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48433-3_17

Premium Partner

    Image Credits