Prof. Dr. Dietrich Braess

      Fakultät für Mathematik
      Ruhr-Universität Bochum
      44780 Bochum

     Tel. neu: (49.234) 322 3405 (neu)
     FAX. neu: (49.234) 321 4750

 Notice

In case you prefer English, please refer to the English homepage

     Wenn Sie gern ein Photo sehen wollen,
     steht nur eins von der homepage von
     Constructive Approximation zur Verfügung.

Derzeitige Forschungsschwerpunkte

Im Rahmen der numerischen Behandlung von elliptischen Differentialgleichungen

 - Mehrgitterverfahren
 - cg-Verfahren mit nichtkonventionellen Vorkonditionierern
 - Finite Elemente in der Strukturmechanik
 - Stokes-Löser, Mortar-Elemente und andere gemischte Elemente

im Rahmen der Approximationstheorie

 - rationale Approximation
 - Approximationsprobleme und Methoden der komplexen Analysis
 - Approximationsprozesse und Lerntheorie

Optimierung

  - Ein Paradoxon aus der Verkehrsplanung

Mitherausgeber bei den Zeitschriften



Bücher    einschl. Korrekturen und Ergänzungen
Preprints
Schriftenverzeichnis
   mit Angabe der verfügbaren reprints
Hobby


  • Electronic Mail
    Dietrich.Braess(at)ruhr-uni-bochum.de
    
    Es ist (at) wegen der SPAM-Seuche nicht durch das übliche Symbol ersetzt.


      Prof. Dr. Dietrich Braess

      Faculty of Mathematics
      Ruhr University Bochum
      44780 Bochum
      Germany

     Tel. (+49.234) 322 3405 (new)
     FAX. (+49.234) 3214 750
 
     If you want to see a photo,
     we offer you one from the homepage of Constructive Approximation.

Areas of actual research

Numerical Treatment of Elliptic Differential Equations

 - Multigrid methods
 - cg-algorithms with nonstandard preconditioners
 - Finite elements in solid mechanics - Locking phenomena
 - Stokes-solvers - Mortar elements in domain decomposition
 - Multigrid methods for saddle point problems

Nonlinear Approximation Theorie

 - rational approximation
 - approximation problems und methods from complex analysis
 - learning theory

Optimization

   - Paradoxes on Traffic Flow

Books    with corrections and extensions
Preprints online
List of publications
   with a list of available reprints
Hobby


Coeditor of the Journals


You can see more about our department or about the Ruhr-University in our home pages.
  • Electronic Mail
    Dietrich.Braess(at)ruhr-uni-bochum.de
    
    For good reasons here (at) was not replaced by the known symbol.




  • A Paradox on Traffic Networks

There may be the situation that a new road deteriorates the situation for all costumers. 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
   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. 

I. Milchtaich,
   Network topology and the efficiency of equilibrium. (June 2001).
   Bar-Ilan University Economics Working Paper No. 12-01.
   Games and Economic Behavior 57, 321 - 346 (2006)

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. 

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

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.

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)

J. Mullins, Less is more.
   NewScientist 18 January 2014, pp. 30 - 33 

  Links to further references

  If you have additional information to be added, please, mail it to me.