„Habe nun ach! Philosophie, Juristerei und Medizin, und leider auch Theologie! durchaus studiert mit heißem Bemühn. Da steh ich nun, ich armer Tor! und bin so klug als wie zuvor; heiße Magister, heiße Doktor gar, und ziehe schon an die zehen Jahr herauf, herab und quer und krumm meine Schüler an der Nase herum – und sehe, dass wir nichts wissen können!

Das will mir schier das Herz verbrennen!“ 

- Faust I, S. 354–365

Braess-Paradoxon

Das Braess-Paradoxon ist eine Veranschaulichung der Tatsache, dass eine zusätzliche Handlungsoption unter der Annahme rationaler Einzelentscheidungen zu einer Verschlechterung der Situation für alle führen kann. Das Paradoxon wurde 1968 vom deutschen Mathematiker Dietrich Braess veröffentlicht.

Braess’ originale Arbeit zeigt eine paradoxe Situation, in der der Bau einer zusätzlichen Straße (also einer Kapazitätserhöhung) dazu führt, dass sich bei gleich bleibendem Verkehrsaufkommen die Fahrtdauer für alle Autofahrer erhöht (d. h. die Kapazität des Netzes reduziert wird). Dabei wird von der Annahme ausgegangen, dass jeder Verkehrsteilnehmer seine Route so wählt, dass es für ihn keine andere Möglichkeit mit kürzerer Fahrtzeit gibt.

Gelegentlich wird das Paradox auch bei Selfish-Routern diskutiert. Darüber hinaus ist das Braess-Paradoxon ein Beispiel dafür, dass die rationale Optimierungvon Einzelinteressen im Zusammenhang mit einem öffentlich bereitgestellten Gut zu einem für jeden Einzelnen suboptimalen Zustand führen kann.

1. Beispiel

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.

a. Ausgangssituation

Bild 1: Skizze der Ausgangssituation.
Bild 1: Skizze der Ausgangssituation.

Die vier Städte A, B, C und D werden 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 x (in Tausend Autos pro Stunde) beträgt die entsprechende Fahrtzeit pro Fahrer:

t_{AC}(x)=t_{BD}(x)=(50+x)~{\rm {min}}

Die Städte A und B werden 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:

t_{AB}(x)=t_{CD}(x)=(0+10\cdot x)~{\rm {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.

Bild 2: Verkehrsdichten bei 6000 Fahrern in der Stunde.
Bild 2: Verkehrsdichten bei 6000 Fahrern in der Stunde.

b. Szenario nach dem Bau der zusätzlichen Straße

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

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.

c. Veranschaulichung

Anschaulich betrachtet stellt sich jeweils für die Fahrer, welche eine der Autobahnen benutzen, der eine zwangsläufig zu benutzende Landstraßenabschnitt als Nadelöhr dar. Dort hängt die Geschwindigkeit des Verkehrsflusses stark von der Anzahl der Straßennutzer ab bzw. wird durch diese verringert. Der Straßenneubau bewirkt nun aber, dass einige Fahrer die Landstraße auf voller Länge nutzen und diese somit zusätzlich verstopfen – sie benutzen zusätzlich zur Neubaustrecke nun beide Landstraßenabschnitte und nicht nur einen, wie die Autobahnbenutzer. Nunmehr ist die Nadelöhrsituation deutlicher geworden, da auch die Autobahnbenutzer für ihren zwangsläufig genutzten Landstraßenabschnitt deutlich länger brauchen. In dem Beispiel kann die damit korrespondierende Verkehrsentlastung auf den kapazitätsstarken Autobahnen keinen ausgleichenden Zeitvorteil bewirken.

d. Diskussion

Man könnte nun vermuten, dass durch andere Routenwahlen einiger Fahrer eine bessere Situation entstünde. Dem 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.

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.

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).
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).

Auftreten von Braess-Paradoxa in der realen Welt

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.[1] Auch in New York konnte das umgekehrte Phänomen 1990 beobachtet werden. Eine Sperrung der 42. Straße sorgte für weniger Staus in der Umgebung.[2] Weitere empirische Berichte über das Auftreten des Paradoxons gibt es von den Straßen Winnipegs.[3] In Neckarsulm verbesserte sich der Verkehrsfluss, nachdem ein oft geschlossener Bahnübergang ganz aufgehoben wurde. Die Sinnhaftigkeit zeigte sich, als er wegen einer Baustelle vorübergehend gesperrt werden musste. Theoretische Überlegungen lassen darüber hinaus erwarten, dass das Braess-Paradoxon in Zufallsnetzen häufig auftritt.[4] Viele Netze der realen Welt sind Zufallsnetze.

Einzelnachweise

1.    Wolfgang Blum: Ewig lockt die Schnellstraße. In: Süddeutsche Zeitung. 24. Januar 2006.

2.    G. Kolata: What if they closed 42nd Street and nobody noticed? In: New York Times. 25. Dezember 1990, S. 38.

3.    C. Fisk, S. Pallotion: Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. In: Transport. Res. Vol. 15A, 1981, no. 3, S. 245–248.

4.    Greg Valiant, Tim Roughgarden: Braess’s paradox in large random graphs. In: Proceedings of the 7th ACM conference on Electronic commerce. Ann Arbor MI 2006.

Dieser Beitrag ist der Wikipedia entnommen.

zum vorherigen Blogeintrag                                                                               zum nächsten Blogeintrag 

 

Liste aller Blogeinträge

Kommentare: 0

Impressum | Datenschutz | Sitemap
Diese Website darf gerne zitiert werden, für die Weiterverwendung ganzer Texte bitte ich jedoch um kurze Rücksprache.