Braess-Paradoxon
Das Braess-Paradoxon (nach dem Mathematiker Dietrich Braess) ist eine Veranschaulichung der Tatsache, dass eine zusätzliche Handlungsalternative unter der Annahme rationaler Einzelentscheidungen zu einer Verschlechterung der Situation für alle führen kann.
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 gleichbleibendem Verkehrsaufkommen die Fahrtdauer für alle Autofahrer erhöht (d.h. die Kapazität des Netzwerkes reduziert wird). Dabei wird von der Annahme ausgegangen, dass jeder Verkehrsteilnehmer seine Route so wählt, dass es für ihn keine Alternative mit kürzerer Fahrtzeit gibt. Einen solchen Zustand nennt man in der Spieltheorie Nash-Gleichgewicht.
Darüber hinaus ist das Braess-Paradoxon ein Beispiel dafür, dass die rationale Optimierung von Einzelinteressen im Zusammenhang mit einem öffentlich bereit gestellten Gut zu einem für jeden Einzelnen suboptimalen Zustand führen kann.
Erläuterung anhand des originalen Zahlenbeispieles
 |
 |
Das im Folgenden präsentierte Zahlenbeispiel ist in Anlehnung an die Originalarbeit Über ein Paradoxon aus der Verkehrsplanung von Braess aus dem Jahr 1968 dem Straßenverkehr entnommen. Die grundlegenden mathematischen Zusammenhänge sind jedoch allgemeinerer Natur, so dass die Grundaussagen auch auf andere komplexe Systeme übertragen werden können.
Szenario vor dem Bau einer zusätzlichen Straße
Vier Städte (A,B,C und D) sind wie in der Skizze in Bild 1 gezeigt durch vier Straßen (L1, A2, L3 und A4) verbunden.
Zwei der Straßen (A2 und A4, blau) sind gut ausgebaute Autobahnen, auf denen die übliche Verkehrsdichte so gering ist, dass die Fahrtdauer nur wenig von ihr abhängt. Die Autobahnen führen jedoch nur auf Umwegen zum Ziel.
Die Landstraßen (L1 und L3, gelb) führen auf direkterem Weg zum Ziel. Sie sind jedoch schlechter ausgebaut, so dass der über sie fließende Verkehrsstrom zu einem deutlich stärkeren Einfluss auf die Fahrtdauer führt als bei den Autobahnen.
Angenommene Fahrtdauern: Die Fahrtdauer setzt sich auf allen Straßen aus einem festen Grundwert (in Minuten) und einem vom auf diesem Abschnitt vorhandenen Fluss (in "1.000 Fahrzeuge pro Stunde") zusammen. Wenn 3.000 Autos pro Stunde einen Streckenabschnitt passieren, ist also
- Auf den Autobahnen von A nach C oder von B nach D: Minuten
- Auf den Landstraßen von A nach B oder von C nach D: Minuten
Hierbei ist der Strom an Fahrzeugen auf der jeweiligen Straße.
Man betrachtet nun die Fahrzeuge und deren Fahrtdauern von A nach D. Der angenommene Gesamtstrom ist 6.000 Fahrzeuge pro Stunde. Man kann an eine typische Pendlersituation denken. A ist der Arbeits-, D der Wohnort. Die Situation wiederholt sich Tag für Tag. Jeder Fahrer kennt die Strecken und die typischen Verkehrsdichten. Änderungen der Routenwahl ergeben sich wenn überhaupt, immer nur bei wenigen Fahrern; man kann annehmen, dass jeder Fahrer seine Route so wählt, dass es keine Route mit kürzerer Fahrtzeit gibt. Es ist offensichtlich, dass das Optimum (siehe Bild 2) erreicht wird, wenn jeweils die Hälfte (also 3.000 pro Stunde) der Fahrzeuge die Strecke ABD und die Hälfte die Strecke ACD wählen. Die Fahrtdauern sind in diesem Fall auf beiden Strecken 83 Minuten.
Detaillierte Rechnung: Minuten und Minuten, somit ergibt sich auf beiden Strecken die Fahrtdauer Minuten .
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.
Auf dieser zusätzlichen Strecke gilt für die Fahrtdauer Minuten
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:
- 2.000 Fahrer wählen die Strecke ABD
- 2.000 Fahrer wählen die Strecke ACD
- 2.000 Fahrer wählen die Strecke ABCD
- Somit befindet sich auf den Landstraßen ein Strom von 4.000 Fahrzeugen pro Stunde, auf den Autobahnen und der Neubaustrecke ein Strom von 2.000 Fahrzeugen pro Stunde.
Die Fahrtdauer ist in diesem Fall für alle Fahrer gleich 92 Minuten und somit neun Minuten länger als ohne die Neubaustrecke.
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.
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 1.000 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 die gleiche Richtung.
|
|
|
|
|
|
Man beachte, dass auf allen Strecken mit 3.000 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 gleich zu tun. 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.
Mechanisches Analogon
Es gibt ein Analogon zum Braess-Paradoxon in der Mechanik. Dabei handelt es sich um ein System von Federn und Fäden, an denen ein Gewicht hängt (siehe Bild rechts). Intuitiv würde man vermuten, dass das Gewicht weiter nach unten absackt, wenn der rote Faden durchschnitten wird, weil dann ein tragendes Element weniger vorhanden ist. Tatsächlich kommt das Gewicht in einer höheren Lage zur Ruhe. Ursprünglich wurde die gesamte Gewichtskraft durch die Kette 'Feder-Roter Faden-Feder' gehalten und jede Feder somit mit der gesamten Gewichtskraft belastet und entsprechend gedehnt (elektrotechnisches Analogon: Strom durch Widerstände in Reihenschaltung). Durch Durchschneiden des roten Fadens wird die bisherige Tragekette aufgelöst und durch die zwei parallelen Trageketten 'Feder-blauer Faden' und 'blauer Faden-Feder' ersetzt. Die gesamte Gewichtskraft wird nun auf zwei Ketten aufgeteilt und damit jede Feder mit nur der halben Gewichtskraft belastet und folglich nur halb so stark gedehnt (elektrotechnisches Analogon: Strom durch Widerstände in Parallelschaltung).
Verwandtschaft mit anderen Problemen
- Es konnte gezeigt werden, dass das Braess-Paradoxon zu Newcombs Problem äquivalent ist (siehe Literatur).
- 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 nicht absprechen oder zentral organisieren.
- Das Gefangenendilemma ist eine andere Illustration eines Nash-Gleichgewichts.
- Gelegentlich wird das Braess-Paradoxon auch bei Selfish-Routern diskutiert.
Literatur
- Dietrich Braess: "Über ein Paradoxon aus der Verkehrsplanung" in: Unternehmensforschung 12, 258-268 (1968) (841 KB PDF)
- Katharina Belaga-Werbitzky: "Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern" ISBN 3899591232 (Dissertation) (1 MB PDF)
- A. D. Irvine: "How Braess' Paradox Solves Newcomb's Problem." International Studies in Philosophy of Science, Vol. 7 (1993), no. 2, 145-164.
- Jörg Esser: "Simulation von Stadtverkehr auf der Basis zellularer Automaten" Kapitel 8 - (Dissertation) (621 KB PS)