Wiederholte Spiele erklärt
Elf Stücke mit demselben wachsenden Beispiel: zwei Spediteure fahren dieselbe Relation und können jede Woche eine Rückladung anbieten oder die des anderen nur nutzen. Die Wurzel fragt, ab welchem Gewicht der Zukunft Kooperation als Gleichgewicht trägt (Tit-for-Tat ab 2/3, Grim Trigger schon ab 1/2). Danach fragt die Linie, welche Strategie in einem Turnier gewinnt (in keinem der hier gebauten Felder Tit-for-Tat), was Fehler anrichten (zwei Tit-for-Tat zahlen unter Rauschen langfristig genau 2,25 statt 3,00) und wer sich in einer Population durchsetzt (nur Immer-Defektieren ist evolutionär stabil).
Dazu zwei Gegenstücke, was überhaupt tragbar ist (die volle Gleichgewichtsmenge, ab δ = 1/2 die ganze Region) und was ein bekanntes Ende kostet (genau 2 Punkte Vorteil des letzten Zuges, für jede Länge). Es folgen Preiskriege im Gleichgewicht ohne jede Abweichung (Green und Porter), indirekte Reziprozität mit wechselnden Partnern und öffentlichem Ruf (nur Image Scoring ist instabil), die Erpressung durch Zero-Determinant-Strategien (sie wirkt exakt und setzt sich trotzdem nicht durch), Kooperation in Netzen (die Schwelle b/c > k gilt nur für große Netze) und als Zusammenfluss die algorithmische Kollusion: zwei Q-Lernende landen im Median bei einem Index von 0,79 zwischen Nash und Monopol, und hohe Preise brauchen dabei keine gelernte Vergeltung. Alle Zahlen stehen in den README der Demos, jede Demo prüft ihren Kern gegen eine unabhängige Referenz (Orakel-Tests). Die Linie macht Aussagen über Modelle mit festen Auszahlungen, keine über reale Märkte.
In short: Covers repeated games: tit-for-tat, grim trigger, the folk theorem, Green-Porter price wars and algorithmic collusion by learning pricing algorithms. Interactive demos follow two carriers who meet each week in a growing example.
Hintergrund zum Thema: Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Tit-for-Tat verständlich erklärt
Warum zwei Spediteure, die sich jede Woche wiedertreffen, allein durch die Drohung der Vergeltung beim Tauschen von Rückladungen bleiben können und wie wahrscheinlich das Wiedertreffen dafür sein muss: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die elf Stücke im Überblick
Das Tit-for-Tat-Stück ist die Wurzel: die Schwelle, ab der Kooperation trägt. Daraus verzweigt die Linie nach der Schwäche, die jeweils behoben wird: das Axelrod-Turnier (welche Strategie ist gut?), danach die Fehler (Rauschen, großzügiges Tit-for-Tat, Pavlov) und die Evolution (wer setzt sich in einer Population durch). Von den Fehlern führen Preiskriege im Gleichgewicht zu Green und Porter (Strafe ohne Abweichung) und, als Idee, zur Erpressung durch Zero-Determinant-Strategien (dieselbe Kette, andere Frage). Von der Evolution führen wechselnde Partner zur indirekten Reziprozität (Ruf statt Gedächtnis) und Struktur statt Durchmischung zur Kooperation in Netzen.
Zwei Kontraste liegen quer zum Hauptstrang: das Folk-Theorem (was überhaupt tragbar ist) und die endlichen Horizonte (ein bekanntes Ende statt eines unbekannten). Die algorithmische Kollusion ist der Zusammenfluss: Sie nimmt aus dem Folk-Theorem, was tragbar ist, aus Green und Porter die Strafen bei Beobachtungsrauschen und von außen das Lernen. Die gestrichelten Fremdknoten sind Bausteine anderer Linien: das Nash-Gleichgewicht als Einmalspiel-Wurzel und No-Regret-Lernen aus der Spieltheorie, Q-Learning aus dem Reinforcement Learning.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Verwandt in anderen Linien
- Spieltheorie — Das Nash-Gleichgewicht der Spieltheorie ist das Einmalspiel, auf dem die Wurzel dieser Linie aufsetzt: Hier wird es unendlich oft wiederholt, und Kooperation trägt als Gleichgewicht. Das No-Regret-Lernen dort lernt mit Regret-Garantie gegen beliebige Gegner, die algorithmische Kollusion hier lässt zwei einfache Q-Lernende gegeneinander laufen und misst, wo sie landen.
- Reinforcement Learning — Das Lernverfahren der algorithmischen Kollusion ist das tabellarische Q-Learning der Q-Learning-Demo, hier mit zwei Agenten gleichzeitig: Jeder sieht den anderen nur als Teil seiner Umgebung, und diese Umgebung ist nicht stationär.
- Ranking — Die Tabelle nach Siegen der Ranking-Linie rechnet das Muster „Rang hängt am Feld“ mit bekannter wahrer Stärke nach: Dort lässt sich der Fehler messen, den das Axelrod-Turnier mangels Stärke nicht angeben kann, und Spielplan-Ungleichgewicht und Lücken kommen hinzu.
- Netzwerkanalyse — Dieselbe Frage, wie sich Betriebe in einem Netz angleichen, stellt die Linie Netzwerkanalyse ohne Auszahlungen: die Meinungsbildung mittelt, das Voter-Modell übernimmt zufällig, das begrenzte Vertrauen hört nur auf nahe Einschätzungen.
Tit-for-Tat und der Schatten der Zukunft
Sehen Sie, wie zwei Spediteure, die sich jede Woche wiedertreffen, Kooperation allein mit der Drohung der Vergeltung sichern. Ein Regler für die Chance, dass die Beziehung weiterläuft (δ), zeigt, ab wann Tit-for-Tat (den anderen spiegeln) trägt und warum Grim Trigger (nie wieder kooperieren) früher trägt. Haken: bei den gewählten Auszahlungen erst ab δ = 2/3, Grim schon ab 1/2; Kooperation ist nur eine von mehreren stabilen Lösungen, keine Vorhersage.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Axelrod-Turnier: wer gewinnt, hängt am Feld
Verfolgen Sie, wie 16 klassische Strategien im wiederholten Gefangenendilemma jeder gegen jeden antreten, und fragen Sie, wie viel vom Ergebnis am Feld, am Rauschen (zufälligen Fehlaktionen) und am Training hängt. Zufällige Teilfelder und ein Rauschen-Regler zeigen, wie sich die Rangfolge verschiebt. Haken: Tit-for-Tat gewinnt hier nicht, es belegt Rang 6 von 16, und das Originalfeld von 1980 ist nicht nachgebaut: Die Aussage gilt für dieses Feld.
Demo starten →Fehler und Vergebung: Rauschen, großzügiges Tit-for-Tat und Pavlov
Sehen Sie, wie ein einziger Fehler zwei Tit-for-Tat-Spieler in ein Echo gegenseitiger Vergeltung schickt, bis ein zweiter Fehler es beendet. Ein Regler für die Fehlerrate zeigt, was das langfristig kostet (2,25 statt 3,00) und wie großzügiges Tit-for-Tat und Pavlov (bleibt bei Erfolg, wechselt bei Misserfolg) sich erholen. Haken: Fehlertoleranz kostet gegen Ausbeuter, und Pavlov verliert gegen Dauer-Defektierer am meisten.
Demo starten →Evolutionäre Dynamik: warum Tit-for-Tat nicht stabil ist
Sehen Sie, wie sich Strategien in einer Population nach Erfolg ausbreiten und warum Tit-for-Tat trotz stabiler Kooperation nicht evolutionär stabil ist: Eindringlinge, die gegen es genauso viel verdienen, werden nicht verdrängt. Die Demo vergleicht eine deterministische Dynamik mit einem Zufallsprozess in endlicher Population. Haken: Die deterministische Rechnung zeigt keinen Einbruch, und bei 50 Spielern kippt die Population nur in 5 von 20 Läufen mindestens einmal.
Demo starten →Folk-Theorem: was Wiederholung tragen kann
Verfolgen Sie, welche Auszahlungspaare zwei Spediteure, die sich unbegrenzt oft treffen, als stabile Lösung tragen können: Je geduldiger sie sind (δ), desto größer die Menge, ab δ = 1/2 jedes Paar, das beiden mindestens so viel sichert wie ständiges Defektieren. Daneben rechnet die Demo, was eine einfache Trigger-Strategie (ewige Defektion bei Abweichung) davon trägt. Haken: bei δ = 0,8 nur 75 % der Region, und tragbar heißt nicht vorhergesagt.
Demo starten →Endliche Horizonte: Rückwärtsinduktion
Sehen Sie, wie die Rückwärtsinduktion Kooperation in einem Rahmenvertrag mit bekanntem Ende aufrollt: Wer in der letzten Runde nichts zu verlieren hat, defektiert, und das wandert Runde für Runde nach vorn. Die Demo zeigt den Vorteil des letzten Zuges und was ein unsicheres Ende daran ändert. Haken: Bei diesen Auszahlungen beträgt er gegen Tit-for-Tat genau 2 Punkte, Unsicherheit verkleinert ihn, beseitigt ihn aber nicht, solange es ein spätestes Ende gibt.
Demo starten →Preiskriege im Gleichgewicht: Green und Porter
Verfolgen Sie, wie zwei Anbieter, die nur den verrauschten Marktpreis sehen, eine Absprache mit Preiskrieg als Strafe stabil halten: Fällt der Preis unter eine Schwelle, folgt der Krieg, auch wenn niemand abgewichen ist. Die Demo rechnet exakt, wie oft das passiert und was es kostet. Haken: In der Voreinstellung herrscht im Mittel 59 % der Zeit Krieg, und bei kurzer Strafe, geringer Geduld oder starkem Rauschen trägt keine Absprache.
Demo starten →Indirekte Reziprozität: Reputation statt Gedächtnis
Sehen Sie, wie Kooperation zwischen wechselnden Partnern ohne Wiederbegegnung trägt, wenn eine öffentliche Reputation entscheidet, wem geholfen wird. Die Demo rechnet vier Bewertungsregeln mit Fehlern exakt durch und zeigt, welche stabil sind. Haken: Die naheliegende Regel Image Scoring (wer hilft, gilt als gut) bricht schon bei 2 % Fehlern ein, und Shunning ist zwar stabil, bringt aber nur 33,8 % guten Ruf: stabil heißt nicht gut.
Demo starten →Zero-Determinant-Strategien: kann man einen Mitspieler erpressen?
Sehen Sie, wie eine Zero-Determinant-Strategie einem Mitspieler eine feste Beziehung der langfristigen Auszahlungen aufzwingt, ganz gleich, was dieser spielt: Bei χ = 3 hat der Erpresser über dem Wert gegenseitiger Defektion den dreifachen Überschuss des Gegners. Ein χ-Regler und ein lernender Gegner zeigen, was das bringt. Haken: Die Erpressung wirkt exakt, setzt sich in einer Population aber bei keinem getesteten χ durch, und gegen Tit-for-Tat gibt es nichts zu holen.
Demo starten →Kooperation in Netzen: warum Nachbarschaft Kooperation trägt
Verfolgen Sie, wie Kooperation auf einem Gitter mit vier Nachbarn überlebt, wenn jeder nur mit Nachbarn spielt und Erfolgreichere nachahmt: Kooperierende bilden Nester, in denen sie sich helfen. Die Demo vergleicht drei Ersetzungsregeln. Haken: Es hängt an der Regel. Bei Death-Birth (ein Ausgeschiedener wird von einem Nachbarn ersetzt) halten sich bei fünfmal so hohem Nutzen wie Kosten 79 % Kooperierende, bei Birth-Death bleibt in keinem der 320 Läufe einer übrig.
Demo starten →Algorithmische Kollusion: lernen zwei Q-Agenten sich zu einigen?
Sehen Sie, wie zwei Preis-Algorithmen, die ohne jede Absprache aus Erfahrung lernen, bei Preisen über dem Wettbewerbspreis landen können. Die Demo misst einen Kollusionsindex von null (Wettbewerb) bis eins (Monopol) und prüft, ob eine gelernte Vergeltung die Preise hält. Haken: Ohne Gedächtnis liegt der Index im Median höher (0,95 gegen 0,79), die hohen Preise brauchen also keine Vergeltung. Es ist ein Simulationsbefund mit zwei Anbietern, keine Aussage über reale Märkte.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle elf Stücke: er fragt danach, wie sich die Spieler begegnen und wie weit die Zukunft reicht, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Alle elf Antworten sind durch die Messreihen der Demos belegt (siehe jede README): wann Kooperation trägt, wer ein Turnier gewinnt, was Fehler anrichten, wer sich durchsetzt, und wo die Aussagen enden.
Weitere Linien in diesem Bereich
Multi-Agenten-Koordination
Aufträge ohne zentrale Instanz verteilen: von Contract Net über Verhandlung, DCOP und Multi-Agenten-Lernen bis zu Auktionen und gelernten Mechanismen.
Spieltheorie
Wer hat welchen Anreiz? Zehn Verfahren zu eigennützigen Lkw und zu Spediteuren, die Kosten teilen, jedes mit seinem gemessenen Befund.
Turnierplanung
Wie plant man ein faires Turnier mit vertretbarer Rundenzahl, und was zählt sonst noch: Heimrecht, Reisedistanz, eine zweite Chance, der Gleichstand? Acht Antworten, jede gegen echte Referenzdaten oder Literatur geprüft.
Adversarische Suche
Wie entscheidet eine Maschine ihren nächsten Zug gegen einen Gegner, der das Gegenteil will? Von der erschöpfenden Minimax-Suche über Effizienz-Tricks und Bewertungsfunktionen bis zum Selbstspiel-Training.
Ranking
Wie wird aus Vergleichen eine Rangfolge, und wie sicher ist sie? Ein simuliertes Turnier mit bekannter Stärke, siebzehn Stücke von der Siegtabelle über Bradley-Terry und Elo bis zu Rangintervallen und Learning to Rank.
Abstimmen und Fair Teilen
Wie aus verschiedenen Wünschen eine Entscheidung oder eine faire Verteilung wird: fünfzehn Stücke von der Wahlregel bis zur Kuchenteilung.