-
A Paradox on Traffic Networks
There may be the situation that a new road deteriorates the situation for
all custumers. This is not a real paradox but only a situation which is
counterintuitive. The mathematical reason is the fact that one has to
distinguish between an equilibrium and an optimum.
There is a recent interest in the study of this phenomenon since the
same may happen in computer networks and not only in traffic networks.
References
D. Braess, Über ein Paradoxon aus der Verkehrsplanung.
Unternehmensforschung 12, 258 - 268 (1968)
PDF-file [In der eingescanten Datei ist auf S. 264 (ubcz) durch (abcz) zu ersetzen.]
On a paradox of traffic planning.
Translation from the original German by D. Braess, A. Nagurney and T. Wakolbinger.
Transportation Science 39, 446-450 (2005) PDF-file
Some earlier definitions are found in the following:
J.G. Wardrop, Some theoretical aspects of road traffic Research.
in Proc. of the Inst. of Civil Engineers, Part II, 325-378 (1952)
M.J. Beckmann, C.B. McGuire, C.B. Winston,
Studies in the Economics of Transportation.
Yale Univ. Press, New Haven 1956
W. Knödel, Graphentheoretische Methoden und ihre Anwendungen.
Springer-Verlag 1969, pp 57 - 59
J.D. Murchland, Braess's paradox of traffic flow.
Transpn. Res. 4, 391 - 394 (1970)
L.J. Leblanc, An algorithm for the discrete network design problem.
Transpn. Sci. 9, 183 - 199 (1975)
M.J. Smith, In a road network, increasing delay locally
can reduce delay globally.
Transpn. Res. 12, 419 - 422 (1978)
M.J. Smith, Traffic control and route choice; a simple example.
Transpn. Res. 13 B, 289 - 295 (1979)
C. Fisk, More paradoxes in the equilibrium assignment problem.
Transpn. Res. 13 B, 305 - 309 (1979)
N.F. Stewart, Equilibrium vs system-optimal flow: some examples.
Transpn. Res. 14 A, 81 - 84 (1980)
M. Frank, The Braess paradox.
Math. Programming 20, 283 - 302 (1981)
W.I. Zangwill and C.B. Garcia,
Pathways to Solutions. Fixed Points and Equilibria, p. 176.
Prentice-Hall, Englewood Cliffs 1981
A. Taguchi, Braess' paradox in a two-terminal transportation network.
J. Oper. Res. Soc. of Japan 25, 376 - 388 (1982)
R. Steinberg and W. Zangwill, The prevalent of Braess' paradox.
Transpn. Sci. 17, 301 - 318 (1983)
S. Dafermos and A. Nagurney, On some traffic equilibrium theory paradoxes.
Transpn. Res. B 18, 101 - 110 (1984)
M.J. Smith,
Transpn. Res. B 18, 63 - 65 (1984)
J. Liebman, L. Lasdon, L. Schrage, and A. Waren,
Modeling and Optimization with GINO. p. 53.
Boyd & Fraser/The Scientific Press, Danvers, MA (1986). (Out of sale)
R. Steinberg and R. Stone, The prevalence of paradoxes
in transportation equilibrium problems.
Transpn. Sci. 22, 231 - 141 (1988)
J.E. Cohen and F.P. Kelly, A paradox of congestion in a queuing network.
J. Appl. Prob. 27, 730 - 734 (1990)
New York Times. What if they closed 42nd Street and nobody noticed?
NYT 25 December 1990, p.38.
J.E. Cohen and P. Horowitz, Paradoxial behaviour of mechanical and
electrical networks. Nature 352, 699 - 701 (August 1991)
F.P. Kelly, Network routing.
Phil. Trans. R. Soc. London A 337, 343 - 367 (1991)
I. Peterson, Strings and springs net mechanical surprise.
Science News 140, 118 (August 1991)
S. Catoni and S Pallottino, Traffic equilibrium paradoxes.
Transpn. Sci. 25, 240 - 244 (1991)
M. De Luca and A. Maugeri, Variational inequalities applied to the study
of paradoxes in equilibrium problems.
Optimization 25, 249 - 259 (1992)
Laurence R. Rilett and M. Van Aerde,
Modelling distributed real-time route guidance strategies in a traffic
network that exhibits the Braess paradox.
Proc. 2nd International Vehicle Navigation and Information Systems
Conference (Dearborn, Mich., Oct. 1991) pp. 577-587.
Ch. Pöppe, Paradoxes Verhalten physikalischer und ökonomischer Systeme.
Spektrum der Wissenschaft, 23 - 26, Nov. 1992
T. Bass. Road to ruin. Discover 56 - 61, May 1992
P.A. Samuelson, Tragedy of the open road:
Avoiding paradox by use of regulated public utilities
that charge corrected Knightian tolls.
J. of Int. and Comparative Econ. 1, 3 - 12 (1992)
P.A. Samuelson, Tragedy of the commons:
Efficiency rents to the rescue of the free-road inefficiencies and paradoxes.
In "Does Economic Space Matter?"
(Essays in honor of Mei Greenhut. H. Ohta and J.-F. Thisse, eds),
pp. 71 - 80. St. Martin's Press, New York (1992)
B. Calvert and G. Keady, Braess's paradox and power-law nonlinearities
in networks. J. Australian Math. Soc. B 35, 1 - 22 (1993)
A. Knop, Warum mehr Strassen den Verkehrsfluss bremsen.
nature 76 - 77, 3/1993
G. Alperovich, Neglected welfare aspects in Braess's paradox.
Int. J. Transport Economics XX (2), 215 - 220 (1993)
A. D. Irvine, How Braess's paradox solves Newcomb's problem.
Int. Studies Philosophy Science 7, 141 - 160 (1993)
reprinted in Peter Danielson (ed.), Modeling Moral and Rational Agents,
Oxford: Oxford University Press, 1997/98
R. Arnott and K. Small, The economics of traffic congestion.
American Scientist 82, 446 - 455, Sept/Oct 1994
A. Hallefjord, K. Joernsten, and S. Storoey,
Traffic equilibrium paradoxes when travel demand is elastic.
Asia-Pacific J. Operational Res. 11, 41 - 50 (1994)
N.G. Bean and P.G. Taylor, Can Braess's paradox occur in loss networks?
University of Adelaide, Nov 1994
Y.A. Korilis, A.A. Lazar, and A. Orda, Architecting noncooperative networks.
IEEE J. on Selected Areas in Communications 13, 1241 - 1251 (1995)
A. Maugeri, Variational and quasi-variational inequalities in network
flow models. Recent developments in theory and algorithms.
In "Variational inequalities and network equilibrium problems."
(F. Giannessi and A. Maugeri, eds.), pp. 195 - 211,
Plenum, New York 1995
N. Bean, Secrets of network success. Physics World (Feb. 1996), 30 - 33
B. Calvert and G. Keady, Braess's paradox and power-law nonlinearities
in networks. II.
In "Proceedings of the First World Congress of Nonlinear Analysts,
WC 528", Florida Aug 92, Volume III, pp. 2223 - 2230.
(V. Lakshmanthan, ed.), W. de Gruyter 1996
T.W. Körner, The Pleasures of Counting. pp. 268 - 275
Cambridge University Press 1996
deutsch: Mathematisches Denken, SS 370 - 378, 1998
C. Daganzo, Two paradoxes of traffic flow on networks
with physical queues. II Symposium Ingeneria de los Transportes,
Madrid, 22-24 May 1996, pp. 55 - 62
L. Marinoff, How Braess' paradox solves Newcomb's problem: Not!
International Studies in the Philosophy of Science 10, 217 - 237 (1996)
E.I. Pas and S.L. Principio, Braess' paradox: Some new insight.
Transpn. Res. B 31, 265 - 276 (1997)
W. Blum, Die Logik des Paradoxen. Die Zeit Nr. 52 (1997), S. 36
C.M. Penchina, Braess paradox: maximum penalty in a minimal
critical network. Transpn. Res. A 31 (5), 379 - 388 (1997)
G. Alperovich, An economic interpretation of Braess' paradox.
Int. J. Transport Economics 145 - 155 (1997)
Y.A. Korilis, A.A. Lazar, and A. Orda.
Capacity allocation under noncooperative routing.
IEEE Trans. on Automatic Control 42 (3) 309 - 325 (1997)
N. Arora, S. Sen and M. Gordin,
Resolving social dilemmas using genetic algorithms: Initial results.
The Seventh International Conference on Genetic Algorithms.
July 19-23, 1997, Michigan State University
Hai Yang, Sensitivity analysis for the elastic-demand network
equilibrium problem with applications.
Transpn. Res. 31 B, 55 - 70 (1997)
B. Calvert, W. Solomon, and I. Ziedins,
Braess's paradox in a queuing network with state depending routing.
J. Applied Probability 34, 134 - 154 (1997)
N.G. Bean, F.P. Kelly, and P.G. Taylor, Braess's paradox in loss networks.
J. Applied Probability 34, 155 - 159 (1997)
B. Calvert, The Downs-Thomson effect in a Markov process.
Prob. in the Engineering and Info. Sciences, 11, 327 - 340, (1997)
N.G. Bean and P.G. Taylor, Braess's paradox in communication networks?
EMAC '98 (E.O. Tuck and J.A.K. Stott, eds.) pp. 107 - 110.
The Institution of Engineers, Australia, 1998
G. Keady, The Colebrook-White formula for pipe networks.
(Preprint Jan. 1995)
J. Hydraulic Engineering (Amer.Soc.Civil Engineers) 1998
J.E. Cohen, Cooperation and self-interest: Pareto-inefficiency of
Nash equilibria in finite random games.
Proc. Natl. Acad. Sci. USA 95, 9724 - 9731 (1998)
C. Gawron, An iterative algorithm to determine the dynamic user
equilibrium in a traffic simulation model.
Int. J. Mod. Phys. C 9(3), 393 - 407 (1998)
Hai Yang and M.G.H. Bell,
A capacity paradox in network design and how to avoid it.
Transpn. Res. 32 A, 539 - 545 (1998)
C. Daganzo, Queue spillovers in transportation networks with choices.
Transpn. Sci. 32, 3 - 11 (1998)
Y.A. Korilis, A.A. Lazar, and A. Orda,
Avoiding the Braess paradox in non-cooperative networks,
J. Appl. Prob. 36, 211 - 222 (1999)
H-K. Chen, C-F. Hsueh, and C-Y. Wang,
The dynamic system-optimal route choice problem and toll policies.
Transp. Planning and Technol. 22, 201 - 228 (1999)
A. Nagurney, Network Economics: A Variational Approach, pp 163 - 166.
Kluwer, Boston 1999
K. Tumer and D.H. Wolpert,
Collective intelligence and Braess' paradox,
In "Proc. Seventeenth National Conference
on Artificial Intelligence", pp. 104 - 109,
Austin, TX, August 2000.
H. Kameda, E. Altman, T. Kozawa, and Y. Hosokawa,
Braess-like paradoxes in distributed computer systems.
IEEE Trans. on Automatic Control 45 (9) 1687 - 1690 (2000)
T. Akamatsu, A dynamic traffic equilibrium asignment paradox.
Transpn. Res. 34 B, 515 - 531.
A. Nagurney, Sustainable Transportation Networks, pp. 43 - 51,
Edward Elgar, Cheltenham 2000.
J. N. Hagstrom, R. A. Abrams,
Characterizing Braess's paradox for traffic networks.
Proc. of IEEE 2001 Conference on Intelligent Transportation Systems,
pp. 837 - 842 (2001)
A. Nagurney and J. Dong,
Paradoxes in networks with zero emission links:
Implications for telecommunications versus transportation.
Transpn. Res. D 6, 283 - 296 (2001)
T. Roughgarden,
On the severity of Braess's paradox:
Designing networks for selfish users is hard.
J. of Computer and System Sciences 72, 922 - 953 (2006)
A preliminary version is found in the Proc. of the 42nd Annual
IEEE Symposium on FOCS 2001, pp. 472 - 481.
T. Roughgarden and É. Tardos, How bad is selfish routing?
Journal of the ACM, 49(2), 236 - 259 (2002)
H. Kameda and O. Pourtallier,
Paradoxes in distributed decisions on optimal load balancing
for networks of homogeneous computers.
J. of the ACM 49, 407 - 433 (2002)
H. Kameda,
How harmful the paradox can be in Braess/Cohen-Kelly-Jeffries networks,
Proc. IEEE INFOCOM 2002, New York, June 2002.
A. Nagurney and J. Dong, Supernetworks, pp.277 - 280,
Edward Elgar, Cheltenham 2002.
C.M. Penchina and L.J. Penchina,
The Braess paradox in mechanical, traffic, and other networks.
Amer. J. Phys. 71, 479 - 482 (2003)
A. Nagurney,
Influence of Beckmann, McGuire, and Winsten's Studies in the Economis
of Transportation on Innovation in Modeling, Methodological Developments and Applications.
(Presented at the Panel: Studies in the Economics of Transportation:
A Retrospective, at the 50th North American Regional Science Association Meeting
in Philadelphia, Pennsylvania, November 2003).
UMASS preprint 2003.
H. Lin, T. Roughgarden, and É. Tardos,
1. Bounding Braess's Paradox.
2. A stronger bound on Braess's paradox.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms,
2004, pp. 333 - 334.
H. Lin, T. Roughgarden, and É. Tardos,
A. Walkover: Braess's paradox, Fibonacci numbers,
and exponential inapproximability.
Proceedings ICALP 2005, pp. 497-512.
T. Roughgarden. "The Price of Anarchy."
MIT Press, Cambridge, MA, 2005.
S. Robinson, The price of anarchy,
SIAM news 37/Number 5 (June 2004)
G. M. Ziegler, Was denkt der Mathematiker im Stau?
DMV-Mitteilungen 13-2, 106 - 108 (2005)
A. Rapoport, T. Kugler, S. Dugar and E.J. Gisches,
Braess Paradox in the Laboratory: An Experimental Study of Route Choice
in Traffic Networks with Asymmetric Costs.
(August 8, 2005)
A. Nagurney and D. Boyce, Preface to On a paradox of traffic flow.
Transportation Science 39, 443 - 445 (2005)
D. Braess, A. Nagurney, and T. Wakolbinger,
On a paradox of traffic planning.
Translation from the original German
Transportation Science 39, 446 - 450 (2005)
H.-H. Dubben and H.-P. Beck-Bornholdt,
Mehr Stau durch mehr Straßen. Das Braess'sche Paradoxon.
Kapitel 8 in "Mit an Wahrscheinlichkeit grenzender Sicherheit"
Rowohlt, Reinbek bei Hamburg 2005, ISBN 3-499-61902-4
I. Milchtaich,
Network topology and the efficiency of equilibrium.
Games and Economic Behavior 57, 321 - 346 (2006)
gsz (G. Szpiro), Irrationales bei Airlines und Passagieren.
Das Braess-Paradoxon am Beispiel der Flugroutenwahl.
Neue Zürcher Zeitung 9. Jan. 2006, S. 5
W. Blum, Ewig lockt die Schnellstraße.
Psychologen bestätigen ein mathematisches Paradoxon:
Manchmal lösen zusätzliche Strecken den Stau erst aus.
Süddeutsche Zeitung 24. Jan. 2006, S. 9
A. Rooch. Auf Umwegen schneller zum Ziel.
6. Folge der WAZ-Serie "Was ist Mathematik?" - Das Braess-Paradoxon.
Westdeutsche Allgemeine Zeitung 5. August 2006.
A. Nagurney, D. Parkes and P. Daniele,
The Internet, evolutionary variational inequalities,
and the time-dependent Braess paradox.
Computational Management Science 4, 355 - 375 (2007)
W. Blum, Neue Straßen und mehr Stau.
In Was ist Was. Band 12 Mathematik S. 35 - 36.
Tessloff-Verlag Nürnberg 2008.
D. Easley, and J. Kleinberg,
Networks. Cornell Store Press. (2008), p. 71.
H. Youn, M.T. Gastner, and H. Jeong,
Price of Anarchy in Transportation Networks: Efficiency and Optimality Control.
Erratum: Physical Review Letters 102, 049905 (2009)
L. Baker. Detours by design.
Scientic American February 2009, 11 - 12.
C.M. Penchina, Braess's paradox and power-law nonlinearities in
five-arc and six-arc two-terminal networks.
The Open Trnsportation Journal 3, 8 - 14 (2009).
(Take the title of the 1968-article from this web page.)
E. Cascetta, Transportation System Analysis, p. 333.
Springer Verlag.
W. H. Lin and H. K. Lo,
Investigating Braess' Paradox with Time Dependent Queues,
Transportation Science 43, 117 - 126 (2009).
M. Schreckenberg, Es braessiert.
OR News 38, 18 - 20 (2010)
A. Nagurney. The negation of the Braess paradox as demand increases:
The wisdom of crowds in transportation networks.
Europhysics Letters, 91 (2010)
S.F. Chung and S.J. Young. Braess's paradox in large sparse graphs.
In Proc. of the 6th Workshop on Internet and Network Economics
(WINE '10), LNCS 6484, pp. 194 - 208, 2010.
H. Lin, T.Roughgarden, É. Tardos, and A. Walkover,
Stronger bouds on Braess` paradox and the maximum latency of selfish routing.
SIAM J. Discrete Math. 25, 1667 - 1686 (2011)
D. Witthaut and M. Timme,
Braess's paradox in oscillator networks, desynchronization and power outage.
New J. Physics 14, 083036 (2012)
M. G. Pala et al.,
Transport inefficiency in branched-out mesoscopic networks:
an analog of the Braess paradox.
Phys. Rev. Lett. 108, 076802 (2012)
L. F. Ayala and S. Blumsack,
The Braess paradox and its impact on natural-gas-network performance.
Oil Gas Facilities 2, 52 - 64 (2013)
J. Mullins, Less is more.
New Scientist 18 January 2014, pp. 30 - 33.
A. Dal Forno, U. Merlone, and V. Avrutin,
Dynamics in Braess paradox with non-impulsive commuters.
Discrete Dynamics in Nature and Society, Vol. 2015.
T. Revell, Man vs Mathematics,
Understanding the Curious Mathematics that Power Our World.
Aurum 2016
A. E. Motter and M. Timme,
Antagonistic phenomena in network dynamics.
Annual Review of Condensed Matter Physics 2018, 463 - 484.
D. J. Case, Y. Liu, I. Z. Kiss, J.-R. Angilella and A. E. Motter,
Braess’s paradox and programmable behaviour in microfluidic networks.
Nature 574, 647 - 655 (2019)
Links to further references
If you have additional information to be added, please, mail it to me.
|
