Spieltheorie und Mechanism Design erklärt
Die Spieltheorie fragt, wer welchen Anreiz hat: Was kommt heraus, wenn jeder Lkw, jeder Spediteur und jede Seite eines Handels nur den eigenen Vorteil verfolgt, wie gut oder schlecht ist das Ergebnis, und wie lässt es sich lenken? Die Gegenfrage stellt die Multi-Agenten-Koordination: was, wenn alle kooperieren? Eigennutz ist eine Modellannahme, kein Befund über echte Terminals: Dort plant meist eine Zentrale, siehe Hof- und Yard-Management.
Zwei durchgehende Beispiele tragen die Linie. Im ersten wählen Lkw eigennützig ein Tor an einem Terminal, dazu kommt ein Straßennetz mit Abkürzung. Im zweiten legen Spediteure ihre Stopps zu einer gemeinsamen Tour zusammen und teilen die Kosten (das Verfahren dahinter ist die Tourenplanung). Die Referenzwerte sind exakt berechnet: durch Aufzählung aller Gleichgewichte bzw. per Held-Karp für die Tour.
In short: Covers game theory and mechanism design: Nash equilibrium, tolls and congestion, the Shapley value and the Myerson-Satterthwaite theorem. Interactive demos treat self-interested trucks and carriers that share costs, each with a measured finding.
Hintergrund zum Thema: Hof- und Yard-Management · 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
Das Braess-Paradox verständlich erklärt
Warum eine zusätzliche Abkürzung alle Lkw langsamer machen kann und was der Preis der Anarchie misst: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die zehn Stücke im Überblick
Der Graph hat zwei Äste. Der linke beginnt beim Nash-Gleichgewicht und fragt in drei Richtungen weiter: wie schlecht das Gleichgewicht sein kann (Preis der Anarchie und Braess-Paradox, dann die Maut, die es lenkt), wie Lkw ohne volles Wissen dorthin kommen (No-Regret-Lernen, dann korrelierte Gleichgewichte) und was ein Erstzug ändert (Stackelberg, als Kontrast, weil dort nicht alle gleichzeitig ziehen).
Der rechte Ast beginnt beim Shapley-Wert, der die Kosten einer gemeinsamen Tour teilt. Der Kern fragt, ob diese Aufteilung stabil ist. Der Moulin-Mechanismus fragt, was passiert, wenn die Werte privat sind und jeder lügen darf, und Myerson-Satterthwaite dehnt das auf beide Seiten eines Handels aus. Die gepunktete Kante von der Maut zum Moulin-Mechanismus verbindet die Äste: beide lenken Eigennutz, einmal durch einen Preis und einmal durch einen Kostenanteil.
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
Der Doppelrahmen (Moulin-Mechanismus) markiert das Stück, in dem zwei Stränge zusammenlaufen: die Kostenteilung aus dem rechten Ast und die Preisidee der Maut.
Verwandt in anderen Linien
- Multi-Agenten-Koordination — Dort liegen die Zahlungsregeln der Auktion (VCG, das hier bei Moulin und Myerson-Satterthwaite als Vergleich dient) und der von RegretNet gelernte Mechanismus.
- Matching-Algorithmen — Stabilität steht auch dort im Mittelpunkt: Gale–Shapley sucht eine stabile Zuordnung nach Vorlieben, Top Trading Cycles tauscht ohne Geld, wie hier der Kern stabile Kostenaufteilungen sucht.
- Netzwerkfluss — Dasselbe Nutzergleichgewicht mit stetigem, teilbarem Verkehr auf einem Stadtgitter rechnet die Frank-Wolfe-Demo der Netzwerkfluss-Linie; sie zeigt, wie lang der Endspurt zur genauen Lösung ist und wie sich das Systemoptimum als Gleichgewicht auf Grenzkosten rechnen lässt (Grenzkosten-Maut siehe die Maut-Demo).
- Standortplanung — Der Standortwettbewerb ist Stackelberg in geometrischer Kulisse (Führer eröffnet Standorte zuerst, ein Folger antwortet): dieselbe Führer-Folger-Struktur wie hier, aber mit Standorten statt Torwahl, und auch dort sind reine Gleichgewichte selten.
- Reinforcement Learning — Das No-Regret-Lernen hier ist derselbe Online-Lern-Gedanke wie der Bandit dort (Erkunden gegen Ausnutzen bei unbekannter Belohnung), aber gegen sich gegenseitig beeinflussende, eigennützige Gegenspieler statt einer stationären Umgebung.
- Wiederholte Spiele — Die Wiederholte-Spiele-Linie setzt das Nash-Gleichgewicht des Einmalspiels unendlich oft fort: Dort trägt Kooperation als Gleichgewicht (Tit-for-Tat), und die algorithmische Kollusion lässt zwei lernende Preis-Algorithmen gegeneinander laufen, statt wie das No-Regret-Lernen hier eine Garantie gegen beliebige Gegner zu geben.
- Ranking — Die Nash-Mittelung der Nicht-Transitivität gewichtet Spieler nach dem Gleichgewicht eines symmetrischen Nullsummenspiels.
- Abstimmen und Fair Teilen — Die unteilbaren Güter der Linie Abstimmen und Fair Teilen verteilen ganze Güter ohne Geld und messen den Neid; die Shapley-Demo dieser Linie teilt Kosten nach dem Beitrag jedes Beteiligten.
Nash-Gleichgewicht und Best-Response bei der Torwahl
Sehen Sie, wie Lkw eigennützig das Tor mit der kürzesten Wartezeit wählen, bis keiner durch einen Alleingang mehr gewinnen kann (Nash-Gleichgewicht). Ein Umschalter zwischen nacheinander und gleichzeitig Reagieren zeigt live, wann die Lkw zur Ruhe kommen. Der Haken: Gleichzeitig schwingen 97,5 % der Läufe, und selbst ein erreichtes Gleichgewicht ist nicht eindeutig; das schlechteste liegt bei 12 Lkw im Mittel 5,9 % über dem Optimum.
Demo starten →Preis der Anarchie und Braess-Paradox im Straßennetz
Sehen Sie, wie das Braess-Paradox den Preis der Anarchie sichtbar macht: Öffnet man eine Abkürzung, wählen alle Lkw sie, und alle werden langsamer. Ein Umschalter für die Abkürzung zeigt es im Braess-Netz live. Der Haken: Das hängt an der Netz-Struktur, bei Netzen von Braess-Bauart schadet die Abkürzung in 48,3 % der Fälle, bei zufälligen Netzen nur in 3,3 %.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Maut und Grenzkosten-Preise im Straßennetz
Sehen Sie, wie eine Grenzkosten-Maut jedem Lkw die Mehrzeit anrechnet, die er anderen aufbürdet, sodass Eigennutz und Gesamtnutzen zusammenfallen. Ein Vergleich mit fester Maut und keiner Maut zeigt live, wie das schlechteste Gleichgewicht im Braess-Netz zum Optimum kommt. Der Haken: Mit gezahlter Maut ist es für die Lkw nur bei einer von 36 Umweg-Längen billiger, und bei der Torwahl mit gemischten Größen werden nur 3,5 % der Instanzen exakt optimal.
Demo starten →No-Regret-Lernen bei der Torwahl
Verfolgen Sie, wie Lkw ohne Wissen über die anderen aus Erfahrung lernen: Täglich ziehen sie ein Tor nach einer Gewichtung, die der Rückblick anpasst. Ein Regler für die Schrittweite und ein Vergleich mit Best-Response zeigen live, wie schnell der Regret, die im Rückblick verlorene Wartezeit, sinkt. Der Haken: Lernen ist hier nicht besser als Best-Response, es braucht nur weniger Wissen; der Ausgang liegt im Mittel 4,4 % über dem Optimum.
Demo starten →Korrelierte Gleichgewichte bei der Torwahl
Sehen Sie, wie ein Vermittler jedem Lkw nur sein Tor empfiehlt, und jeder Lkw der Empfehlung lieber folgt, als abzuweichen. Ein Vergleich von bestem und schlechtestem Vermittler zeigt live, wann er das beste reine Gleichgewicht schlägt: bei 8 Lkw in 73 % der Instanzen. Der Haken: Gehorsam allein garantiert keine gute Lösung, das schlechteste korrelierte Gleichgewicht liegt im Mittel 19,0 % über dem Optimum.
Demo starten →Stackelberg: Anführer-Lkw bei der Torwahl
Sehen Sie, wie Anführer-Lkw sich zuerst verbindlich auf ein Tor festlegen und die übrigen darauf reagieren: Wer festlegt, sucht sich das beste Gleichgewicht aus. Ein Regler für die Anführerzahl zeigt live, wie viel Last eine Disposition steuern muss, um das Optimum zu erreichen. Der Haken: Ein einzelner eigennütziger Erstzug bringt bei 8 Lkw in keiner der 100 Instanzen mehr als das beste Gleichgewicht, er schützt nur vor dem schlechten.
Demo starten →Shapley-Wert bei der Kostenteilung einer Sammeltour
Sehen Sie, wie der Shapley-Wert die Kosten einer Sammeltour teilt: Jeder Spediteur zahlt den Durchschnitt seiner Mehrkosten über alle Beitrittsreihenfolgen. Ein Vergleich mit der proportionalen Aufteilung zeigt live, ob keine Gruppe allein günstiger führe, die Aufteilung also stabil ist. Der Haken: Stabil ist er nicht immer (bei gleichmäßig verteilten Stopps in 85 % der Instanzen); im Beispiel (Zufalls-Seed 12) zahlen sieben der acht Spediteure zusammen mehr, als sie allein führen.
Demo starten →Kern und Nukleolus bei der Kostenteilung einer Sammeltour
Sehen Sie, wie der Kern alle Kostenaufteilungen sammelt, bei denen keine Gruppe allein günstiger führe, und der Nukleolus daraus die stabilste wählt. Eine gezielte Suche nach leeren Kernen zeigt live, ob es Aufteilungen ohne diesen Makel gibt. Der Haken: In keiner von 80 Instanzen mit 8 Spediteuren war der Kern leer, auch die Suche bis 6 Spediteure fand keinen; das beweist nichts über andere Instanzfamilien, die Literatur kennt leere Kerne.
Demo starten →Moulin-Mechanismus bei privater Zahlungsbereitschaft
Sehen Sie, wie der Moulin-Mechanismus Kosten teilt, auch wenn jeder lügen darf: Wer mitfährt und zahlt, folgt allein aus den angemeldeten Geboten, und kein Anteil steigt, wenn die Gruppe wächst. Ein Lügen-Widget und der Vergleich mit dem Grenzkosten-Mechanismus VCG zeigen live, welche Eigenschaft jeder aufgibt. Der Haken: Bei 6 Spediteuren nimmt VCG nur 59 % der Kosten ein, und die Garantie für Shapley-Anteile gilt im Tourenspiel meist nicht.
Demo starten →Myerson-Satterthwaite beim Handel mit einem Laderaum-Slot
Sehen Sie, wie Verkäufer und Käufer einen freien Laderaum-Slot handeln, obwohl jeder nur die eigenen Kosten bzw. den eigenen Wert kennt: Bei überlappenden Werten und Kosten ist kein Mechanismus zugleich effizient, ehrlich, freiwillig und ausgeglichen. Ein Vergleich von fünf Mechanismen zeigt live, welche Eigenschaft jeder opfert; das zweitbeste Verfahren erreicht im Klassiker-Preset 89,2 % des Gewinns. Der Haken: Teilweise ein Gitter-Artefakt, bei 4 Typen je Seite verschwindet der Konflikt.
Demo starten →Welche Frage der Spieltheorie stellt sich bei mir?
Ein Entscheidungsbaum über alle zehn Stücke, entlang der Fragen, die die Linie selbst aufwirft: wählen oder teilen, bewerten oder lenken, wer was weiß. Alle Antworten stützen sich auf Messungen in den Demos.
Welches Stück passt zu meiner Frage?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Stücke bauen aufeinander auf (siehe Graph), der Baum ordnet nur nach der Frage. Und Eigennutz bleibt eine Modellannahme: Wo eine Zentrale plant, ist die zentrale Optimierung der Praxisstandard.
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.
Wiederholte Spiele
Zwei Spediteure, die sich jede Woche wiedersehen: elf Stücke von Tit-for-Tat über das Folk-Theorem und Preiskriege bis zu lernenden Preis-Algorithmen.
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.