Koordinationsspiele · Verständlich erklärt

Hirschjagd und Risikodominanz verständlich erklärt

Zwei Spediteure wollen am selben Terminal ein neues, besseres Slot-Raster einführen. Es lohnt sich für jeden nur, wenn der andere mitzieht; wer allein umstellt, verliert Zeit. Beide wissen, dass das neue Raster für alle am besten wäre, und doch kann es schiefgehen, weil das alte Raster das sichere ist. Diese Seite erklärt zuerst ohne Formeln, warum Gleichwahl belohnt wird und trotzdem scheitern kann, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert:

Teil 1 · Für Einsteiger

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein neues Raster, das nur gemeinsam etwas bringt

Zwei Spediteure, Süd und Nord, laden am selben Terminal. Der Betreiber bietet ein neues Slot-Raster an, also eine neue Einteilung der Zeitfenster an den Toren. Es spart beiden Zeit, aber nur, wenn beide es nutzen. Stellt nur einer um, passen die Fenster nicht mehr zueinander, und er wartet länger als vorher. Jeder entscheidet für sich, ohne den anderen vorher zu fragen: umstellen oder beim alten Raster bleiben.

Die vier möglichen Ausgänge, wenn man annimmt, dass das alte Raster immer dieselbe Zeit kostet, egal was der andere tut:

Nord stellt umNord bleibt beim alten Raster
Süd stellt umBeide sparen am meisten ZeitSüd verliert Zeit, Nord bleibt wie bisher
Süd bleibt beim alten RasterSüd bleibt wie bisher, Nord verliert ZeitBeide bleiben wie bisher

In der Spieltheorie heißt diese Lage Hirschjagd, nach dem Bild zweier Jäger: Einen Hirsch erlegen sie nur gemeinsam, einen Hasen kann jeder auch allein fangen. Das neue Raster ist der Hirsch, das alte der sichere Hase. Die zugehörige Demo, ein Programm zum Ausprobieren im Browser, rechnet ein verwandtes Beispiel: Betriebe entscheiden, ob sie Sendungen am Umschlagplatz bündeln oder direkt fahren. Bündeln lohnt nur, wenn genug andere mitmachen; wer allein bündelt, verliert Zeit.

Zwei Zustände, in denen keiner allein zurückweicht

Stellen beide um, will keiner allein zum alten Raster zurück, denn dann verliert er den Gewinn. Bleiben beide beim alten Raster, will keiner allein umstellen, denn dann verliert er Zeit. Solche Zustände heißen Gleichgewichte: Keiner hat einen Grund, allein etwas zu ändern. Beide sind stabil, obwohl der erste für beide besser ist. Ein besserer Zustand garantiert also nicht, dass die Betriebe dort ankommen.

Dazwischen liegt ein dritter, wackliger Zustand: Jeder stellt nur mit einer bestimmten Wahrscheinlichkeit um, genau so, dass dem anderen beides gleich recht ist. Eine kleine Abweichung kippt beide in einen der stabilen Zustände.

Viele Betriebe: ab welchem Anteil lohnt das Umstellen?

Am Terminal laden viele Betriebe. Für jeden gibt es eine Schwelle: Stellt mindestens dieser Anteil der anderen um, lohnt es sich auch für ihn. Die Schwelle ist hoch, wenn man beim Alleingang viel verliert und beim gemeinsamen Umstellen wenig gewinnt; im umgekehrten Fall ist sie niedrig.

Wohin sich die Gruppe entwickelt, hängt davon ab, wie viele am Anfang schon umgestellt haben. Liegt dieser Anteil über der Schwelle, setzt sich das neue Raster durch, darunter das alte. Der Bereich der Anfangsanteile, der zu einem Zustand führt, heißt sein Einzugsbereich. Je größer er ist, desto leichter landet eine Gruppe dort.

Das für alle beste Ziel ist nicht automatisch das gewählte

Das neue Raster kann für alle am besten sein und trotzdem die höhere Schwelle haben: Der Gewinn beim gemeinsamen Umstellen ist kleiner als der Verlust beim Alleingang. Dann hat das alte Raster den größeren Einzugsbereich, obwohl es schlechter ist. Fachleute sagen: Das alte Raster ist risikodominant, das neue auszahlungsdominant. Wer nicht weiß, was die anderen tun, wählt das Sichere.

Wie oft das vorkommt, zählt die Demo für Zufallsspiele. Werden die Auszahlungen unabhängig gleichverteilt gewählt, ist das für alle beste Ziel in rund einem Drittel der Koordinationsspiele das riskantere. Gibt es einen sicheren Hasen, sind es die Hälfte der Fälle. Beide Anteile hängen an der gewählten Verteilung der Auszahlungen.

Ein Beispiel der Demo mit fünfzig Betrieben, die unabhängig voneinander mit gleicher Wahrscheinlichkeit umstellen oder nicht: Obwohl „alle bündeln“ für jeden der beste Zustand ist, endet die Gruppe nur in gut einem von hundert Läufen dort. In den Läufen wechselt ein zufällig gewählter Betrieb nur, wenn er sich dadurch klar verbessert.

Wenn Betriebe sich gelegentlich irren

Die Demo rechnet noch eine zweite Lernregel: Betriebe wählen die bessere Möglichkeit nur mit einer Wahrscheinlichkeit, die mit dem Vorteil wächst, und irren sich also gelegentlich (Fachwort: Logit). Sind die Fehler selten genug, gehört in den Rechnungen der Demo auf lange Sicht die größere Wahrscheinlichkeit dem risikodominanten Zustand; im Beispiel mit fünfzig Betrieben ist es fast die gesamte. Wo das Risiko die Schwelle hochtreibt, setzt sich also nicht das beste, sondern das sicherere Raster durch.

Was die Demo außerdem zeigt

  • Zwei Rollen: Zwei Betriebsarten müssen sich auf ein Format einigen, mögen aber verschiedene. Wohin sie laufen, hängt von der Stärke beider Vorlieben ab. Eine einfache Formel dafür nennt die Demo nicht, sie misst es nur.
  • Unterschiedlich hohe Schwellen: Hat jeder Betrieb seine eigene Schwelle, kann eine Gruppe ins Kippen kommen, die bei gleichen Schwellen stillstünde. Liegt die Streuung der Schwellen nahe an der Grenze, entscheidet der Zufall der Ziehung, ob es kippt.
  • Der Gegenfall: Wo Gleichwahl bestraft wird, etwa wenn zwei Lkw dasselbe Tor ansteuern und sich im Weg stehen, ist ein Mischzustand stabil, und eine Absprache bringt mehr als das Mischen: im einen Beispiel der Demo dreimal so viel, in einem anderen deutlich weniger.

Wie ernst sind die Ergebnisse der Demo zu nehmen?

Die Auszahlungen der Demo sind gewählt, nicht gemessen, und die Regeln, nach denen Betriebe wechseln, sind Annahmen des Modells, keine Beobachtungen an Menschen oder Terminals. Die Gruppe ist vollständig durchmischt: Jeder trifft jeden. Bei festen Nachbarn gilt die Schwelle nicht einfach als Einzugsbereich der Gruppe.

Woran Sie es im Betrieb merken:

  • Eine Umstellung, die sich für alle rechnen würde, kommt nicht in Gang, obwohl jeder sie gut findet: Vermutlich liegt die Schwelle hoch, weil der Alleingang teuer ist.
  • Ein Alleingang kostet mehr, als die gemeinsame Umstellung bringt: Dann bleibt das alte Verfahren der sichere Zustand, und ein Anstoß muss viele Betriebe auf einmal bewegen.

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.

Teil 2 · Für Fachleute

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.

  • Spiel: symmetrisches 2×2-Spiel mit den Auszahlungen \(a\) (beide bündeln), \(b\) (beide direkt), \(c\) (ich bündele, der andere fährt direkt) und \(d\) (ich fahre direkt, der andere bündelt); Auszahlung ist die Zeitersparnis je Sendung in Minuten, gewählt und nicht gemessen. Klassen: Koordination (\(a > d\), \(b > c\)), Anti-Koordination (\(a < d\), \(b < c\)), dominant (verschiedene Vorzeichen), entartet (\(a = d\) oder \(b = c\)). Die Gleichgewichte kommen aus einer Aufzählung (Indifferenzbedingungen, exakt in Brüchen), \(p^*\) ist die Probe.
  • Population: \(n\) Betriebe, vollständig durchmischt, Zustand ist die Zahl \(k\) der Bündelnden. Beste Antwort: ein zufällig gezogener Betrieb wechselt nur bei strikter Verbesserung, ganzzahlig über Zählungen gerechnet; die Wahrscheinlichkeit, bei „alle bündeln“ zu enden, folgt exakt aus der Geburts-Sterbe-Kette über \(k\) (in Brüchen, keine Zufallsläufe nötig). Replikator: Runge-Kutta 4. Logit: Wahl von S mit Wahrscheinlichkeit \(1/(1 + e^{-\beta\Delta})\), \(\Delta\) der mittlere Vorteil gegen die \(n - 1\) anderen.
  • Zwei Rollen: Auszahlungsmatrizen A = [[r₁, 0], [0, 1]] und B = [[1, 0], [0, r₂]]; jede Rolle antwortet auf den Anteil der anderen. Schwellen: Person \(i\) macht mit, wenn mindestens ihre Schwelle der Personen mitmacht; Normalverteilung der Schwellen, bei 0 gekappt, Vergleich über Personenzahlen.
  • Zufall: Alle Zufallszahlen kommen aus einem eigenen SplitMix64-Strom (gleiche Eingabe, gleiche Zahlen auf jeder Plattform); wo Zufallsläufe vorkommen, sind es vier feste Ströme (SWEEP_SEEDS), die angegebene Streuung ist die zwischen ihnen.

Die Formeln

Auszahlung gegen einen Anteil \(x\) der Bündelnden unter den anderen (S = bündeln, H = direkt fahren):

\[u_S(x) = x\,a + (1-x)\,c, \qquad u_H(x) = x\,d + (1-x)\,b\]

Schwelle des gemischten Gleichgewichts. Wegen \(u_S(x) - u_H(x) = x\,(a-d) - (1-x)\,(b-c)\) wechselt der Vorteil des Bündelns bei

\[p^* = \frac{b-c}{(a-d) + (b-c)}\]

das Vorzeichen (Koordination: \(a > d\) und \(b > c\)); die Steigung \(s = (a-d) + (b-c)\) entscheidet, ob ein Koordinationsspiel vorliegt. Für „alle bündeln“ ist der Einzugsbereich der Anteil \(1 - p^*\).

Replikatordynamik für den Anteil \(x\):

\[\dot x = x\,(1-x)\,\bigl(u_S(x) - u_H(x)\bigr)\]

Risikodominanz. Bündeln ist risikodominant, wenn der Verlust beim einsamen Abweichen von „alle bündeln“ größer ist als der von „alle direkt“, das heißt, wenn

\[a - d > b - c \iff p^* < \tfrac12\]

gilt. Auszahlungsdominant ist das Gleichgewicht mit der größeren Auszahlung (\(a\) gegen \(b\)); beide können auseinanderfallen.

Potential des Spiels und, für \(k\) Bündelnde unter \(n\) (alle Paare gezählt):

\[\Phi(S,S) = a-d, \qquad \Phi(H,H) = b-c, \qquad \Phi(S,H) = \Phi(H,S) = 0\]

\[\Phi(k) = \frac{(a-d)\binom{k}{2} + (b-c)\binom{n-k}{2}}{n-1}\]

Logit-Wahl eines gezogenen Betriebs mit Vorteil \(\Delta\) der Strategie S, und die stationäre Verteilung der Logit-Kette (Gibbs-Maß des Potentials):

\[\Pr(S) = \frac{1}{1 + e^{-\beta\Delta}}\]

\[\pi(k) \propto \binom{n}{k}\, e^{\beta\,\Phi(k)}\]

Dass die Kette das Gibbs-Maß trifft, ist hier ein Messbefund gegen die volle Übergangsmatrix (siehe Befunde), kein Beweis.

Verteilte Schwellen. Der Anteil, dessen Schwelle bei Stand \(x\) erreicht ist, und der Endstand ab dem Anfangsanteil \(s_0\) (\(\Phi_N\) die Verteilungsfunktion der Standardnormalverteilung, \(\mu\) und \(\sigma\) Mittel und Streuung der Schwellen):

\[F(x) = \Phi_N\!\left(\frac{x-\mu}{\sigma}\right), \qquad x_{t+1} = \max\bigl(s_0,\ F(x_t)\bigr)\]

Befunde

Alle Zahlen stammen aus der README der Demo (jede steht in deren Tests, tests/test_claims.py) und gelten für erzeugte Daten und die genannten Voraussetzungen. Die Hypothesen des Einzelplans wurden im Bau mit dem eigenen SplitMix64-Strom neu gemessen; wo Zufallsläufe vorkommen, sind es vier feste Ströme.

FrageBefund
Wie viele Gleichgewichte hat ein 2×2-Spiel?Alle 10.000 ganzzahligen Spiele mit Auszahlungen 0 bis 9: 2.025 Koordination, 2.025 Anti-Koordination, 4.050 dominant, 1.900 entartet. In den 8.100 nicht entarteten Spielen hat jedes Koordinations- und Anti-Koordinationsspiel genau 3 Gleichgewichte, jedes dominante genau 1, das gemischte bei \(p^*\); Zahl und Lage stimmen ohne Ausnahme.
Wo liegt die Grenze des Einzugsbereichs?Vier Spiele: Replikator 0,25 / 0,50 / 0,667 / 0,25 gegen \(p^*\) ebenso (Abweichung unter 10⁻⁴); beste Antwort bei \(n = 100\) exakt 0,25 / 0,50 / 0,67 / 0,25. Im 2×2-Fall mit einer Population ist das ein Orakel-Abgleich, kein Befund über die Dynamik.
Wie oft ist das auszahlungsdominante Gleichgewicht risikodominiert?Zufallsspiele \((a, b, c, d)\) unabhängig gleichverteilt auf [0, 10), nur \(a > d\), \(b > c\), \(a \ne b\), 4 Ströme zu 100.000 Ziehungen (je Strom rund 25.000 Spiele): in 33,4 % der Koordinationsspiele (Stichprobenwert, Streuung über die Ströme 0,3 Pp, die letzte Stelle trägt nicht; eine unabhängige Rechnung mit 5·10⁷ Spielen gibt 33,33 %, also rund ein Drittel), sein mittlerer Einzugsbereich 0,590; mit „sicherem Hasen“ (\(d = b\)) 50,0 % (Einzugsbereich 0,500). Gegenprobe mit vier anderen Strömen zu 400.000 Ziehungen: 33,2 % und 50,2 %. Alle ganzzahligen Koordinationsspiele 0 bis 9 mit \(a \ne b\) und \(a - d \ne b - c\) (1.500 von 1.740; ausgeschlossen sind 240 Spiele mit gleich großen Einzugsbereichen): 28,0 % (420 von 1.500; die Gleichstände als „nicht riskant“ gezählt: 420 von 1.740 = 24,1 %). Die Häufigkeit gehört zur gewählten Verteilung der Auszahlungen, kein Naturgesetz.
Wie wahrscheinlich ist „alle bündeln“ bei unabhängigem Start ohne Absprache?Bündeln-Spiel \((6, 4, 0, 4)\), \(n = 50\), jeder startet mit 50 %: „alle bündeln“ mit Wahrscheinlichkeit 1,06 % (exakt; Simulation mit 20.000 Läufen im Test auf 0,4 Pp genau). Hirschjagd \((5, 2, 1, 2)\): 99,98 %; \((6, 4, 3, 4)\): 98,94 %; bei \(p^* = 1/2\) genau 50 %.
Trifft das Gibbs-Maß die Logit-Kette, und welcher Rand trägt die Masse?Stationäre Verteilung der Kette gegen Gibbs-Maß: größte Abweichung unter 10⁻¹² über 120 Zellen (4 Spiele × \(n \in \{4, 10, 30, 100, 200\}\) × \(\beta \in \{0{,}1; 0{,}5; 1; 2; 5; 10\}\)); die gemessene größte Abweichung ist Rundungsrauschen (größer als 0); dazu 300 Zufallsspiele (Orakel). Bündeln-Spiel, \(n = 50\): Masse bei höchstens 10 % Bündelnden 0,114 / 0,998 / mehr als 0,999 für \(\beta = 0{,}5\) / 1 / 2, bei mindestens 90 % unter 10⁻⁹. In allen 1.500 ganzzahligen Spielen hat bei \(n = 50\), \(\beta = 2\) der risikodominante Rand die größere Masse, der auszahlungsdominante nur in 1.080 (72,0 %).
Wohin läuft der Kampf der Geschlechter (zwei Rollen)?Replikator, 2.500 Anfangspunkte (Gitter): Anteil „beide Option 0“ 0,49 (Rollenwerte 2 gegen 2), 0,58 (3 gegen 2), 0,49 (4 gegen 4); alle laufen ein. Die Quadranten um das gemischte Gleichgewicht erklären im symmetrischen Fall nur 4/9 = 44 % der Starts direkt. Beste Antwort mit 30 + 30 Spielern, Start 1/2: rund 0,5 / 0,8 / rund 0,5 (Band 0,76 bis 0,86 für 3 gegen 2). Die Startverteilungen beider Verfahren sind verschieden, die Zahlen nur je Verfahren zu lesen; eine Formel für den Anteil gibt es nicht.
Öffnet die Streuung der Schwellen das Kippen?Mittlere Schwelle 30 %, kein Anfangsanteil, 1.000 Personen, 100 Ziehungen je Zelle: Endanteil im Mittel 0,0 % (Streuung 5 %), 0,14 % (10 %), etwa 9 % (15 %; gemessen 9,2 %, Standardfehler rund 2 Pp; Fixpunkt 4,4 %), 99,97 % (20 %), 98,9 % (30 %), 87,4 % (50 %). Bei Streuung 15 % kippt in rund 4 bis 7 % der Ziehungen mindestens die Hälfte (je Strom mit 400 Ziehungen 3,75 bis 7 %), die meisten enden unter 6 %; das Mittel (8 bis 11 %) liegt über dem Fixpunkt, weil die gekippten Läufe es heben.
Wie viele stabile Fixpunkte hat das Schwellenmodell?Auf dem Raster \(\mu \in \{0{,}2; 0{,}3; 0{,}5; 0{,}7\}\) × \(\sigma \in \{0{,}02 \dots 1\}\) einen oder zwei: in 16 von 32 Zellen zwei, sonst einer; ein zweites Verfahren (Iteration von 81 Startwerten) zählt gleich. Der Grund: \(F\) ist positiv und bleibt unter 1, bei drei Schnittpunkten mit der Diagonale sind zwei stabil. Eine frühere Vormessung nannte drei in schmalen Bändern; das war eine Doppelzählung (ein Randpunkt nahe 0 und derselbe Vorzeichenwechsel).
Was ändert sich, wenn Gleichwahl bestraft wird?Replikator von 1.000 Anfangsanteilen: bei \((5, 2, 1, 2)\) und \((6, 4, 0, 4)\) 0 % nahe \(p^*\), 100 % am Rand; bei \((-1, 2, 4, 0)\) und \((0, 3, 4, 2)\) (\(s = -3\)) 100 % nahe \(p^*\), 0 % am Rand. Das gemischte Gleichgewicht ist also bei \(s > 0\) instabil, bei \(s < 0\) stabil.
Was gewinnt eine Absprache im Feiglingsspiel?Feiglingsspiel \(V = 4\), \(C = 6\): mittlere Auszahlung im gemischten Gleichgewicht 2/3, bei abwechselnder Absprache 2 (ein Drittel); im Spiel \((0, 3, 4, 2)\) 8/3 gegen 3 (8/9). Der Gewinn hängt also an den Auszahlungen. Beste Antwort mit \(n = 50\) bleibt bei 33 Bündelnden stehen; Logit-Mittel des Anteils 0,545 / 0,571 / 0,599 / 0,629 für \(\beta = 0{,}5\) / 1 / 2 / 5, von unten gegen \(V/C = 2/3\) (Ursache nicht untersucht).

Grenzen

  • Gewählte Auszahlungen: Die Häufigkeit in der dritten Zeile der Tabelle (33,4 % bei unabhängig gleichverteilten Auszahlungen, 50,0 % mit „sicherem Hasen“, 28,0 % bei den ganzzahligen Spielen 0 bis 9) gehört zur gewählten Verteilung, kein Naturgesetz. Alles ist nur an erfundenen Auszahlungen geprüft; es gibt keine Messung an Terminals oder Menschen, und Eigennutz und Lernregeln (beste Antwort, Replikator, Logit) sind Modellannahmen.
  • 2×2 und vollständige Durchmischung: In Netzen und Nachbarschaften gilt \(p^*\) nicht als Einzugsbereich der Population. Beste Antwort und Replikator haben im 2×2-Fall dieselbe Grenze; das ist eine Probe, keine Entdeckung. Unterschiede zeigen sich nur in der Zwei-Rollen-Fassung, dort mit verschiedenen Startverteilungen.
  • Kampf der Geschlechter: gemessen, keine Formel für den Anteil; das Ergebnis des symmetrischen Falls (0,49) ist per Symmetrie 0,5 plus Gitterfehler.
  • Logit im Feiglingsspiel: Das Mittel nähert sich \(V/C\) von unten; die Ursache (Endlichkeit von \(n\), Wahl der Nachbarzahl \(n - 1\)) wurde nicht untersucht.
  • Granovetter: Normalverteilung der Schwellen und 1.000 Personen sind Annahmen; das Mittel der Endanteile verdeckt die Zweigipfligkeit (die meisten Läufe enden nahe dem Fixpunkt, wenige kippen).
  • Bewusst nicht umgesetzt: dauerndes Rauschen und Wechselzeit der Konvention (die Demo zeigt nur die Identität „stationäre Verteilung = Gibbs-Maß“, nicht, wie oft oder wie schnell eine Konvention kippt), Netze und Nachbarschaften, gemeinsame Signale und Vermittler, Fokalpunkte ohne Absprache, Menschenexperimente.

Quellen

Nach der README der Demo am Abstract oder an der bibliographischen Angabe geprüft, nicht im Volltext gelesen:

  • Kandori, M., Mailath, G. J., & Rob, R. (1993): Learning, Mutation, and Long Run Equilibria in Games. Econometrica 61(1), 29–56 (in 2×2-Spielen mit zwei strikten Gleichgewichten wird bei großer Population das risikodominante gewählt).
  • Monderer, D., & Shapley, L. S. (1996): Potential Games. Games and Economic Behavior 14, 124–143.
  • Blume, L. E. (1993): The Statistical Mechanics of Strategic Interaction. Games and Economic Behavior 5(3), 387–424 (Logit-ähnliche Wahl und Gleichgewichtsauswahl in 2×2-Koordinationsspielen).
  • Granovetter, M. (1978): Threshold Models of Collective Behavior. American Journal of Sociology 83(6), 1420–1443.
  • Harsanyi, J. C., & Selten, R. (1988): A General Theory of Equilibrium Selection in Games (Risikodominanz und Auszahlungsdominanz; Verlag nicht geprüft).
  • Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/koordinationsspiel-demo.

Auch für diese Seite wurden die genannten Arbeiten nicht nachgeschlagen; die Angaben stammen aus der README der Demo. Nach der README sind Hirschjagd, Risikodominanz und der Einzugsbereich \(1 - p^*\) Lehrbuchstoff; eigene Messungen der Demo sind die Zahlen über Zufallsspiele, der exakte Start ohne Absprache, der Abgleich des Gibbs-Maßes mit der Logit-Kette, die gemessenen Einzugsbereiche im Kampf der Geschlechter und die Streuung im Granovetter-Modell.