Das Braess-Paradox verständlich erklärt
Eine zusätzliche Abkürzung kann alle Lkw langsamer machen, obwohl jeder für sich den schnellsten Weg wählt. Der Preis der Anarchie misst, wie schlecht solche Ergebnisse werden können, und das Braess-Paradox ist der Extremfall. Die zugehörige Demo ist eine von mehreren zum Thema Spieltheorie. Diese Seite erklärt zuerst ohne Formeln, was dahintersteckt, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.
Zuletzt aktualisiert:
Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.
Wenn jeder den schnellsten Weg nimmt
Viele Lkw wollen von einem Start zu einem Ziel, und jeder wählt den Weg, der für ihn selbst am schnellsten ist. Irgendwann ist ein Zustand erreicht, in dem kein einzelner Lkw durch einen Wechsel schneller würde. Ein solcher Zustand heißt Gleichgewicht, in der Fachsprache Nash-Gleichgewicht.
Gut für alle ist ein Gleichgewicht nicht unbedingt. Jeder denkt nur an die eigene Fahrzeit, und so kann ein Ergebnis entstehen, bei dem alle zusammen mehr Zeit verlieren, als nötig wäre.
Das Braess-Paradox: mehr Straße, alle langsamer
Stellen Sie sich ein kleines Straßennetz vor. Vom Start zum Ziel führen zwei Wege. Jeder besteht aus einem Stück, das mit jedem Lkw darauf langsamer wird, und einem Umweg mit fester Fahrzeit. Ohne Abkürzung verteilen sich die Lkw gleichmäßig auf beide Wege.
Nun wird eine Abkürzung zwischen den beiden Wegen geöffnet. Sie bietet einen dritten Weg, der beide Stücke nutzt, die mit der Last langsamer werden. Für jeden einzelnen Lkw lohnt sich die Abkürzung, also wählen alle sie. Dann sind beide Stücke voll, und alle brauchen länger als vorher. Sind die Umwege lang genug, will kein einzelner Lkw zurück auf einen Umweg, denn das wäre für ihn wieder langsamer. Das ist das Braess-Paradox: Mehr Straße, und alle verlieren.
Der Preis der Anarchie
Der Preis der Anarchie misst, wie viel schlechter das schlechteste Gleichgewicht ist als die beste denkbare Zuordnung, die eine Stelle von außen vorgeben würde. Ein Wert von eins bedeutet, dass Eigennutz nichts kostet. Je höher der Wert, desto mehr kostet es, dass alle für sich entscheiden. Das Braess-Netz ist der Extremfall, in dem eine zusätzliche Straße alle schlechterstellt.
Wann schadet eine zusätzliche Straße?
Nicht immer. Das Paradox hängt von der Länge der Umwege ab: Ist der Umweg lang genug, hilft die Abkürzung sogar, in einem mittleren Bereich schadet sie. Macht man die Abkürzung selbst teurer, hilft das nur teilweise: Erst wenn sie lang genug ist, ist das Ergebnis so gut wie ohne sie.
Es hängt auch an der Bauart des Netzes. In zufälligen Netzen mit beliebigen Fahrzeiten schadet eine neue Abkürzung selten und ändert meist nichts. Hat das Netz dagegen die Bauart des Braess-Netzes, mit Zufahrten, die von der Last abhängen, und festen Umwegen, schadet sie sehr oft. Das Paradox ist keine Eigenschaft jeder neuen Straße.
Wie schlecht kann es werden?
Die Demo untersucht den Preis der Anarchie auch in einem zweiten Spiel, bei dem Lkw ein Tor wählen. Zufällige Beispiele liegen dort nahe bei eins, Eigennutz kostet also wenig. Eine gezielte Suche nach schlechten Beispielen findet deutlich höhere Werte, bleibt aber weit unter den Grenzen, die die Theorie für den schlimmsten Fall angibt. Ein Beweis ist das nicht, nur das Ergebnis dieser Suche. Die Zahlen stehen im Fachteil.
Wie ernst ist das Modell zu nehmen?
Die Demo ist ein kleines Modell: ein festes Netz mit wenigen Knoten, gleich große Lkw, Fahrzeiten, die einfach mit der Last wachsen. Jeder kennt alle Fahrzeiten und reagiert perfekt, und alle entscheiden gleichzeitig. Eigennutz ist eine Modellannahme, kein Befund über echte Terminals.
Wer das Ergebnis verbessern will, kann von außen eingreifen, etwa mit Preisen, die die Kosten für andere einpreisen. Das behandelt eine weitere Demo zum Thema.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Modell und Annahmen
Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.
- Braess-Netz: vier Knoten \(s\), \(A\), \(B\), \(t\), fünf Kanten mit affiner Fahrzeit \(a_e + b_e x_e\) (\(x_e\) = Lkw auf der Kante). Die Kanten \(sA\) und \(Bt\) sind lastabhängig (\(b\) Minuten je Lkw), die Umwege \(At\) und \(sB\) haben die feste Fahrzeit \(c\), die Abkürzung \(AB\) die feste Fahrzeit \(e\). Drei Wege: \(P_1 = (sA, At)\), \(P_2 = (sB, Bt)\), \(P_3 = (sA, AB, Bt)\).
- Gleichgewicht: Jeder Lkw wählt den für ihn schnellsten Weg, bei Gleichstand bleibt er. Alle Lkw sind gleich groß, deshalb genügt die Anzahl je Weg; alle (reinen) Gleichgewichte lassen sich bis 40 Lkw exakt aufzählen, nicht aus der Dynamik, sondern aus der Definition.
- Best-Response: Ein Lkw nach dem anderen wechselt zu seinem schnellsten Weg. Weil das Spiel ein Potenzialspiel ist (Rosenthal 1973), endet das immer in einem Gleichgewicht.
- Optimum: die kleinste Summe der Fahrzeiten über alle Zustände.
- Schranken aus der Literatur (per Recherche geprüft, nicht im Test nachbewiesen): 4/3 für unendlich viele infinitesimal kleine Fahrer, 5/2 für endlich viele gleich große Spieler und \((3+\sqrt5)/2 \approx 2{,}618\) für verschieden große.
- Torwahl-Vehikel: wortgleich aus der Vorgänger-Demo nash-demo übernommen (Tore mit Wartezeit \(a_g + b_g\) mal Last, Lkw mit Größe 1, 2 oder 3), samt Vollaufzählung aller reinen Gleichgewichte. Gezielte Suche nach schlechten Instanzen: beste von 200 Zufallsinstanzen, dann 3000 Hill-Climbing-Schritte über beliebige Tor-Parameter.
Preis der Anarchie
Mit der Summe der Fahrzeiten \(SC(s) = \sum_i c_i(s)\) über alle Lkw im Zustand \(s\) ist der Preis der Anarchie das Verhältnis aus dem schlechtesten Gleichgewicht und dem Optimum:
\[\mathrm{PoA} = \max_{s \in NE} SC(s) \,/\, \min_{s} SC(s)\]
Ein Wert von 1 hieße, Eigennutz kostet nichts. Das Optimum ist von außen gesteuert, das Gleichgewicht nicht.
Wann schadet die Abkürzung?
Sind alle \(n\) Lkw auf dem Weg \(P_3\), brauchen sie je \(2bn + e\). Wechselt einer auf \(P_1\) oder \(P_2\), braucht er \(bn + c\). Also ist „alle auf \(P_3\)“ genau dann ein Gleichgewicht, wenn
\[c \ge bn + e\]
Ohne Abkürzung teilen sich die Lkw zu gleichen Teilen auf \(P_1\) und \(P_2\) auf und brauchen \(bn/2 + c\) je Lkw. Die Abkürzung schadet, sobald
\[2bn + e > bn/2 + c\]
bei \(e = 0\) also für \(bn \le c < 1{,}5\,bn\). Bei \(c = bn\) ist das Verhältnis
\[2bn \,/\, 1{,}5\,bn = 4/3\]
die Schranke für affine Kosten, die hier bei endlich vielen Lkw genau erreicht wird.
Befunde
Alle Zahlen stammen aus den Messungen der Demo (jede steht in deren Tests); Zahlen über viele Instanzen (Zufallsnetze, Torwahl-Instanzen, Suche) sind im Test nur in großzügigen Bändern geprüft. Es gelten reine Gleichgewichte, exakt aufgezählt. \(c/(bn)\) und \(e/(bn)\) sind die Fahrzeiten der Umwege bzw. der Abkürzung im Verhältnis zur Fahrzeit \(bn\) einer lastabhängigen Kante bei voller Auslastung. Wo nichts anderes steht, ist das Maß die mittlere Fahrzeit je Lkw im schlechtesten Gleichgewicht.
| Frage | Befund |
|---|---|
| Wann schadet die Abkürzung? | Bei 20 Lkw und kostenloser Abkürzung verschlechtert sie das schlechteste Gleichgewicht für \(c/(bn)\) von 0,55 bis 1,45; bei 1,5 ändert sie nichts, ab 1,55 hilft sie. Analytisch schadet sie für \(bn \le c < 1{,}5\,bn\); dazu kommt ein Bereich mit gemischten Gleichgewichten darunter. |
| Wie groß wird der Preis der Anarchie im Netz? | Maximum bei \(c = bn\): genau 4/3 (bei 20 Lkw 15 min je Lkw ohne, 20 min mit Abkürzung), für 4, 12 und 40 Lkw gleich. Nie darüber. |
| Standardinstanz | 12 Lkw, Zufalls-Seed 7: Die Best-Response endet nach 4 Wechseln bei 11,1 min je Lkw. Schlechtestes Gleichgewicht mit Abkürzung 12,0 min, ohne 9,0 min (+33 %, mit gegenüber ohne). Bei gesperrter Abkürzung endet sie nach 2 Wechseln mit 6 / 6 Lkw bei 9,0 min. |
| Hilft es, die Abkürzung teurer zu machen? | Nur teilweise. Mit \(e = 0{,}3\,bn\) ist das Gleichgewicht eindeutig (4 / 4 / 4 Lkw), aber mit 9,9 min noch schlechter als ohne Abkürzung (9,0 min). Bei 20 und 40 Lkw ist die Abkürzung erst ab \(e = 0{,}5\,bn\) gleichauf (bei 12 Lkw schon ab 0,45). |
| Schadet jede neue Straße? | Nein. Verglichen wird das erreichte Gleichgewicht mit und ohne Abkürzung in 300 Zufallsnetzen je Art. Bei beliebigen Kantenwerten schadet sie nur in 3,3 % der Netze (nie um mehr als 5 %), ändert in 88,3 % nichts und hilft in 8,3 %. In Netzen von Braess-Bauart (Zufahrten lastabhängig, Umwege konstant) schadet sie in 48,3 % (in 33,3 % um mehr als 5 %, höchstens um 26,4 %) und hilft in 33,0 %. Das Paradox hängt an der Netz-Struktur. |
| Wie schlecht ist das Torwahl-Spiel? | Zufällige Instanzen (6 Lkw, 3 Tore): Preis der Anarchie im Mittel 1,058 (gemischte Größen, Maximum 1,155) und 1,023 (einheitliche Größen, Maximum 1,163). Die gezielte Suche findet 1,62 (gemischte) und 1,32 (einheitliche Größen), weit unter den allgemeinen Schranken 2,618 und 5/2. Das sind Ergebnisse dieser Suche, keine bewiesenen Grenzen. |
Grenzen
- Gleich große Lkw: Bei verschieden großen Lkw steigt die Schranke von 5/2 auf 2,618; im Torwahl-Spiel zeigt die Suche höhere Werte als bei einheitlichen Größen.
- Festes Netz: Das Paradox tritt in vielen Netzen auf, aber nicht in jedem (siehe Zufallsnetze). Die Demo betrachtet nur diese eine Form mit vier Knoten.
- Affine Fahrzeiten: Bei stärker überlastungsabhängigen Kosten wächst der Preis der Anarchie über alle Grenzen. Hier nicht untersucht.
- Reine Gleichgewichte: Gemischte und korrelierte Gleichgewichte behandeln weitere Demos zum Thema. Die Suche nach schlechten Torwahl-Instanzen ist ein einfacher Hill Climber mit festem Zufalls-Seed; ein stärkerer Suchalgorithmus könnte höhere Werte finden.
- Gleichstände: Bei Gleichstand bleibt ein Lkw, deshalb gibt es im Netz oft mehrere fast gleich gute Gleichgewichte.
- Schranken: Sie gelten für beliebige Strategiemengen; das Torwahl-Spiel ist der Sonderfall paralleler Wege. Sie sind per Recherche geprüft, im Test nicht nachbewiesen.
- Verhalten: Eigennutz ist eine Modellannahme, kein Befund über echte Terminals. Die Demo nimmt an, dass alle gleichzeitig entscheiden und perfekt reagieren; ein Anführer, der sich zuerst festlegt (Stackelberg), Lernen ohne Kenntnis aller Fahrzeiten (No-Regret-Lernen) und Eingriffe von außen wie eine Maut behandeln weitere Demos zum Thema oder sind nicht umgesetzt.
Quellen
- Braess (1968): das Braess-Paradox.
- Rosenthal (1973): Potenzialspiele, die sichern, dass die Best-Response in einem Gleichgewicht endet.
- Roughgarden/Tardos (2002): Schranke 4/3 für unendlich viele infinitesimal kleine Fahrer.
- Christodoulou/Koutsoupias (2005) und Awerbuch/Azar/Epstein (2005): Schranken für endlich viele Spieler.
- Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/poa-braess-demo.
Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise (nur Autoren und Jahr) stammen aus der README der Demo.