Braess-Paradoxon

Als Beispiel für das Auftreten des Braess-Paradoxons wird hier ein Straßennetz gewählt. Erweitert man dieses Straßennetz um eine weitere Straße, so verlängert sich für jeden Fahrer die Fahrzeit. Das Beispiel ist Braess’ Originalarbeit Über ein Paradoxon aus der Verkehrsplanung aus dem Jahr 1968 entnommen.[1]

Ausgangssituation

Bild 1: Skizze der Ausgangssituation

Bild 2: Verkehrsdichten bei 6000 Fahrern in der Stunde

Die vier Städte A, B, C und D sind durch vier Straßen verbunden. Sowohl von A nach C als auch von B nach D verläuft jeweils eine Autobahn. Die Autobahnen sind gut ausgebaut, so dass die Fahrtzeit nur wenig von der Verkehrsdichte abhängt. Allerdings müssen die Autobahnen ein Hindernis umwinden und sind deshalb recht lang. Bei einem Verkehrsaufkommen ${\displaystyle x}$ (in Tausend Autos pro Stunde) beträgt die entsprechende Fahrtzeit pro Fahrer

${\displaystyle t_{\mathrm {AC} }(x)=t_{\mathrm {BD} }(x)=(50+x)\,\mathrm {min} }$

Die Städte A und B sind genauso wie die Städte C und D durch eine Landstraße verbunden. Diese Straßen sind zwar kürzer als die Autobahnen, aber dafür viel schlechter ausgebaut. Die Fahrtzeit pro Fahrer hängt deshalb im Wesentlichen nur vom Verkehrsaufkommen ab:

${\displaystyle t_{\mathrm {AB} }(x)=t_{\mathrm {CD} }(x)=(0+10\cdot x)\,\mathrm {min} }$

Alle Autofahrer wollen von A nach D fahren, wobei jeder Fahrer den für ihn schnellsten Weg wählt. Es stellt sich ein sogenanntes Nash-Gleichgewicht ein, bei dem die Hälfte der Fahrer die Strecke über Stadt B benutzt und die andere Hälfte über Stadt C fährt. Bei stündlich 6000 Autofahrern fahren somit auf jeder Strecke 3000 Autos und alle Autofahrer haben eine Fahrtzeit von 83 Minuten.

Dies lässt sich durch folgendes Gleichungssystem nachvollziehen, wobei x das Verkehrsaufkommen in Tausend Autos pro Stunde über die Strecke ABD, y das Verkehrsaufkommen in Tausend Autos pro Stunde über die Strecke ACD und n das gesamte Verkehrsaufkommen ist.

1. ${\displaystyle t_{\mathrm {ABD} }(x)=t_{\mathrm {AB} }(x)+t_{\mathrm {BD} }(x)=(50+x+10x)\,\mathrm {min} =(50+11x)\,\mathrm {min} }$
2. ${\displaystyle t_{\mathrm {ACD} }(y)=t_{\mathrm {AC} }(y)+t_{\mathrm {CBD} }(y)=(10y+50+y)\,\mathrm {min} =(50+11y)\,\mathrm {min} }$
3. ${\displaystyle x+y=n}$

Zur Bestimmung des Gleichgewichts wird ${\displaystyle t_{\mathrm {ABD} }(x)=t_{\mathrm {ACD} }(y)=t_{\mathrm {opt} }}$ gesetzt.

Szenario nach dem Bau der zusätzlichen Straße

Bild 3: Skizze des Szenarios nach dem Bau der zusätzlichen Straße

Bild 4: Gleichgewichtssituation mit Neubaustrecke. Die Ströme (in 1000 Autos pro Stunde) sind an den Strecken angegeben

Die verantwortlichen Politiker entschließen sich nach einiger Zeit, wie in Bild 3 gezeigt einen Tunnel durch den Berg zwischen den Städten B und C zu bauen. Diese Neubaustrecke kann nur in der Richtung B → C befahren werden – das vereinfacht die Betrachtung, ist für das Auftreten des Paradoxons aber nicht relevant.

Auf dieser zusätzlichen Strecke gilt für die Fahrtdauer

${\displaystyle t_{\mathrm {BC} }(x)=(10+x)\,\mathrm {min} }$.

Diese Strecke ist also kurz und hat eine hohe Kapazität.

Auch hier gibt es ein Gleichgewicht (Bild 4), bei dem die Fahrtdauern auf allen Strecken gleich sind:

• 2000 Fahrer wählen die Strecke ABD
• 2000 Fahrer wählen die Strecke ACD
• 2000 Fahrer wählen die Strecke ABCD
• Somit befindet sich auf den Landstraßen ein Strom von 4000 Fahrzeugen pro Stunde, auf den Autobahnen und der Neubaustrecke ein Strom von 2000 Fahrzeugen pro Stunde.

Die Fahrtdauer ist in diesem Fall für alle Fahrer gleich 92 Minuten und somit 9 Minuten länger als ohne die Neubaustrecke.

Diskussion

Man könnte nun vermuten, dass durch andere Routenwahlen einiger Fahrer eine bessere Situation entstünde. Dies ist jedoch nicht so. Ein Fahrer, der sich – sofern das geschilderte Gleichgewicht besteht – am nächsten Tag anders entscheidet, bewirkt durch seine Entscheidung, dass sich die Fahrtdauer auf der Strecke, für die er sich entscheidet – und damit für ihn selbst – verlängert. Dieser Zustand entspricht einem Nash-Gleichgewicht. Auf seiner Vortagesstrecke hingegen verringert sich die Fahrtdauer für alle anderen. Dies ist freilich kein Kriterium, das einen Fahrer zur Änderung seiner Route bewegt. Der Einfachheit halber ändern im folgenden Zahlenbeispiel jeweils 1000 Fahrer ihre Route gegenüber dem Gleichgewicht. Bei Änderung des Verhaltens eines einzelnen Fahrers wären die Änderungen kleiner, gingen jedoch – wegen der monotonen (linearen) Abhängigkeit der Fahrtdauer vom Fluss – immer in dieselbe Richtung.

Bild 5: Durchschnittliche Fahrtzeit, wenn von N=6000 Fahrern p über BD und k über BC fahren. D. h., N−p−k befahren AC, N−p CD, p+k AB, k BC, p BD. Das Minimum liegt bei p=3000, k=0 (roter Bereich).

3000 Fahrer wählen die Strecke ABD und benötigen 93 Minuten. 2000 Fahrer wählen die Strecke ACD und benötigen 82 Minuten. 1000 Fahrer wählen die Strecke ABCD und benötigen 81 Minuten.

3000 Fahrer wählen die Strecke ABD und benötigen 103 Minuten. 1000 Fahrer wählen die Strecke ACD und benötigen 81 Minuten. 2000 Fahrer wählen die Strecke ABCD und benötigen 92 Minuten.

2000 Fahrer wählen die Strecke ABD und benötigen 82 Minuten. 3000 Fahrer wählen die Strecke ACD und benötigen 93 Minuten. 1000 Fahrer wählen die Strecke ABCD und benötigen 81 Minuten.

1000 Fahrer wählen die Strecke ABD und benötigen 81 Minuten. 3000 Fahrer wählen die Strecke ACD und benötigen 103 Minuten. 2000 Fahrer wählen die Strecke ABCD und benötigen 92 Minuten.

1000 Fahrer wählen die Strecke ABD und benötigen 91 Minuten. 2000 Fahrer wählen die Strecke ACD und benötigen 102 Minuten. 3000 Fahrer wählen die Strecke ABCD und benötigen 103 Minuten.

2000 Fahrer wählen die Strecke ABD und benötigen 102 Minuten. 1000 Fahrer wählen die Strecke ACD und benötigen 91 Minuten. 3000 Fahrer wählen die Strecke ABCD und benötigen 103 Minuten.

Man beachte, dass auf allen Strecken mit 3000 Fahrern pro Stunde die Fahrtdauer länger als 92 Minuten ist.

Würden sich alle Fahrer verabreden, die Neubaustrecke zu ignorieren und sich so zu verhalten, wie sie es taten, als es diese noch nicht gab, wäre die Fahrtdauer für alle Verkehrsteilnehmer wieder 83 Minuten. Jedoch wäre die Versuchung groß, die dann freie Neubaustrecke als einziger doch zu nutzen und so die eigene Fahrtdauer von 83 Minuten auf 70 Minuten zu reduzieren. Die übliche menschliche Verhaltensweise ist dann, es den Vertragsbrüchigen gleichzutun. Das System tendiert somit wieder zum oben beschriebenen Gleichgewicht. Als Lösung dieses Dilemmas bleibt keine andere Möglichkeit, als die Neubaustrecke zentral geplant wieder abzureißen oder die Strecken AB und CD in ihrer Kapazität zu verdoppeln.

In seiner ursprünglichen Publikation klassifizierte Braess die Situation nicht als Gefangenendilemma, es ist aber eine Variante eines Mehr-Personen-Gefangenendilemmas mit drei Entscheidungsalternativen.[3]

Es gibt Beispiele, dass das Braess-Paradoxon nicht nur ein theoretisches Konstrukt ist. 1969 führte in Stuttgart die Eröffnung einer neuen Straße dazu, dass sich in der Umgebung des Schlossplatzes der Verkehrsfluss verschlechterte.[4] In New York konnte 1990 das umgekehrte Phänomen beobachtet werden. Eine Sperrung der 42. Straße sorgte für weniger Staus in der Umgebung.[5] Gleichermaßen verbesserten sich 2005 Verkehrsfluss und Fahrzeiten in der südkoreanischen Hauptstadt Seoul, nachdem eine vierspurige querungsfreie Stadtautobahn abgerissen worden war.[6][7] Weitere empirische Berichte über das Auftreten des Paradoxons gibt es von den Straßen Winnipegs.[8] In Neckarsulm verbesserte sich der Verkehrsfluss, nachdem ein oft geschlossener Bahnübergang ganz stillgelegt wurde. Die Wirkung zeigte sich, als er wegen einer Baustelle vorübergehend gesperrt werden musste. In Belgien führte die Stilllegung der Autobahn 601 zu einer verkehrlichen Verbesserung, weil es trotz des Umwegs über Kreuz Vottem durch den Wegfall von gefährlichen Ver- und Entflechtungsbereichen zu einem schnelleren Verkehrsfluss und deutlich weniger Unfällen kommt. Theoretische Überlegungen lassen darüber hinaus erwarten, dass das Braess-Paradoxon in Zufallsnetzen häufig auftritt.[9] Viele Netze der realen Welt sind Zufallsnetze.

Mechanisches Analogon: Ein Gewicht hängt an zwei weichen Federn (gelb) und drei harten Federn (blau und rot)

Es gibt ein Analogon – wenn auch nicht im engen Sinne einer mathematischen Abbildbarkeit – zum Braess-Paradoxon in der Mechanik:[10]

Ein Gewicht (Gewichtskraft 6 N) ist an zwei Federsträngen aufgehängt. Der erste besteht oben aus einer schwachen gelben Feder (zwischen den Punkten A und B) und unten aus einer starken blauen Feder (zwischen B und D), der zweite Strang oben aus einer starken blauen Feder (zwischen A und C) und unten aus einer schwachen gelben Feder (zwischen C und D). Die gelben Federn haben in Abhängigkeit von der auf sie wirkenden Kraft ${\displaystyle F}$ die Länge ${\displaystyle l_{\mathrm {g} }(F)=10\,\mathrm {\tfrac {cm}{N}} \cdot F}$, die blauen Federn die Länge ${\displaystyle l_{\mathrm {b} }(F)=50\,\mathrm {cm} +1\,\mathrm {\tfrac {cm}{N}} \cdot F}$. Das Gewicht teilt sich gleichmäßig auf die Aufhängungen ABD und ACD auf, so dass auf beide Aufhängungen eine Kraft von 3 N wirkt. Die Länge der Federn beträgt dann

${\displaystyle {\begin{matrix}l_{\mathrm {AB} }(3\,\mathrm {N} )=30\,\mathrm {cm} \\l_{\mathrm {BD} }(3\,\mathrm {N} )=53\,\mathrm {cm} \\l_{\mathrm {AC} }(3\,\mathrm {N} )=53\,\mathrm {cm} \\l_{\mathrm {CD} }(3\,\mathrm {N} )=30\,\mathrm {cm} \end{matrix}}}$

Die gesamte Aufhängung ist 83 cm lang.

Werden nun die Punkte B und C mit einer weiteren Feder (in der Skizze rot) verbunden, deren Länge ${\displaystyle l_{\mathrm {r} }(F)=10\,\mathrm {cm} +1\,\mathrm {\tfrac {cm}{N}} \cdot F}$ beträgt, könnte man vermuten, dass diese Feder einen Teil der Kraft aufnimmt und dadurch die anderen Federn entlastet, so dass sich das Gewicht hebt. Tatsächlich werden jedoch nur die blauen Federn entlastet und dafür die gelben Federn stärker belastet. Da die gelben Federn schwächer sind, werden sie stärker ausgedehnt als die blauen sich verkürzen. Dies führt dazu, dass sich das Gewicht senkt. Im Gleichgewichtszustand wirken auf die blauen Federn und die rote Feder Kräfte von je 2 N, auf die gelben Federn Kräfte von je 4 N, so dass sich folgende Längen ergeben:

${\displaystyle {\begin{matrix}l_{\mathrm {AB} }(4\,\mathrm {N} )=40\,\mathrm {cm} \\l_{\mathrm {BD} }(2\,\mathrm {N} )=52\,\mathrm {cm} \\l_{\mathrm {AC} }(2\,\mathrm {N} )=52\,\mathrm {cm} \\l_{\mathrm {CD} }(4\,\mathrm {N} )=40\,\mathrm {cm} \\l_{\mathrm {BC} }(2\,\mathrm {N} )=12\,\mathrm {cm} \end{matrix}}}$

Die Länge der gesamten Aufhängung vergrößert sich damit auf 92 cm.

Anmerkung: Um das Gleichgewicht zu finden, muss folgendes Gleichungssystem für die Kräfte gelöst werden:

${\displaystyle {\begin{matrix}F_{\mathrm {AB} }=F_{\mathrm {BD} }+F_{\mathrm {BC} }\\F_{\mathrm {CD} }=F_{\mathrm {BC} }+F_{\mathrm {AC} }\\F_{\mathrm {AB} }+F_{\mathrm {AC} }=6\,\mathrm {N} \\F_{\mathrm {AB} }=F_{\mathrm {CD} }\\l_{\mathrm {AB} }(F_{\mathrm {AB} })+l_{\mathrm {BC} }(F_{\mathrm {BC} })=l_{\mathrm {AC} }(F_{\mathrm {AC} })\end{matrix}}}$

• Mit Hilfe des Braess-Paradoxons lässt sich eine Variante von Newcombs Problem lösen.[11]
• Das Braess-Paradoxon ist eine Variante des Minderheiten-Spiels, wenn Minderheit so verstanden wird, dass ein Fahrer „gut fährt“, wenn er eine Straße wählt, die weniger befahren ist, als es die Gleichgewichts-Lösung vorsieht. Verallgemeinert man auf Kostenfunktionen, die nicht mehr monoton sind, trifft diese Aussage nicht mehr zu.
• Das Braess-Paradoxon hat eine gewisse Ähnlichkeit mit dem Eisverkäufer-am-Strand-Problem. Dort wird ebenfalls eine Situation beschrieben, wie es theoretisch möglich ist, dass ein Systemoptimum verfehlt werden kann, wenn sich Handelnde weder absprechen noch zentral organisieren.

• Downs-Thomson-Paradoxon
• Jevons-Paradoxon

• Dietrich Braess: Über ein Paradoxon aus der Verkehrsplanung. (PDF; 841 kB) In: Unternehmensforschung. 12, S. 258–268.
• Katharina Belaga-Werbitzky: Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern. ISBN 3-89959-123-2 (Dissertation).
• Jörg Esser: Simulation von Stadtverkehr auf der Basis zellularer Automaten. Duisburg 1997, DNB 953736350, Kapitel 8 (Dissertation, Universität Duisburg).

• Dietrich Braess’ Arbeitsseite mit Literaturverzeichnis zum Thema
• Jane Hagstrom: Braess’s Paradox Examples – Single Origin-Destination Pair
• Jane Hagstrom: Braess’s Paradox Examples – Multiple Origin-Destination Pairs

1. Dietrich Braess: Über ein Paradoxon aus der Verkehrsplanung. In: Unternehmensforschung. Band 12, 1968, S. 258–268 (Online [PDF; 840 kB; abgerufen am 1. Juni 2023]).
2. Benjamin Schäfer, Marc Timme: Energiewende: Wie ein Paradoxon den Netzausbau gefährden kann. In: Spektrum der Wissenschaft. 5. August 2023, abgerufen am 5. August 2023.
3. Andreas Diekmann: Spieltheorie. Rowohlt Taschenbuch Verlag, Reinbek bei Hamburg 2009, ISBN 978-3-499-55701-9, S. 113–122.
4. Wolfgang Blum: Ewig lockt die Schnellstraße. In: Süddeutsche Zeitung. 24. Januar 2006.
5. G. Kolata: What if they closed 42nd Street and nobody noticed? In: New York Times. 25. Dezember 1990, S. 38.
6. J. Vidal: Heart and soul of the city In: The Guardian. 1. November 2006.
7. K. Schön: Stau? Reißt die Stadtautobahn ab! (Memento vom 25. Juli 2017 im Internet Archive) In: urbanist magazin. 7. Februar 2014.
8. C. Fisk, S. Pallotion: Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. In: Transportation Research. Vol. 15A, 1981, no. 3, S. 245–248.
9. Greg Valiant, Tim Roughgarden: Braess’s paradox in large random graphs. In: Proceedings of the 7th ACM conference on Electronic commerce. Ann Arbor 2006, S. 296–305, doi:10.1145/1134707.1134740 (englisch, Online [PDF; 230 kB; abgerufen am 1. Juni 2023]).
10. Joel E. Cohen, Paul Horowitz: Paradoxical behaviour of mechanical and electrical networks. In: Nature. 352, 22. August 1991, S. 699–701, doi:10.1038/352699a0.
11. A. D. Irvine: How Braess’ Paradox Solves Newcomb’s Problem. In: International Studies in Philosophy of Science. Vol. 7, 1993, no. 2, S. 145–164.