Rückwärtsinduktion

John von Neumann (1940)

Die Rückwärtsinduktion ist ein zuerst von John von Neumann und Oskar Morgenstern (1944) angewandtes spieltheoretisches Lösungskonzept, um teilspielperfekte Nash-Gleichgewichte in sequentiellen und wiederholten Spielen herauszuarbeiten.

Ausgangspunkt ist im Gegensatz zur Vorwärtsinduktion der letzte Entscheidungsknoten des letzten (echten) Teilspiels am Spielbaum. Demnach wird im Laufe des Verfahrens rückwärts, also in Richtung des ersten Entscheidungsknotens, derjenige Pfad hervorgehoben, welcher für den Akteur die maximale Auszahlung generieren soll. Da dieser Pfad ein Nash-Gleichgewicht in jedem Teilspiel induziert, ist das resultierende Gleichgewicht auch teilspielperfekt.

Voraussetzungen zur Anwendbarkeit

Die notwendigen, sowie hinreichenden Bedingungen an das Spiel sind:

• es ist endlich, d. h., es gibt eine beschränkte Anzahl an Runden, die gespielt werden.
• es wird sequentiell gespielt, d. h., Spieler agieren nacheinander.
• es ist in Extensivform darstellbar, d. h., man kann es als Spielbaum abbilden.
• seine Spieler handeln unter den Annahmen von rationalem Verhalten, d. h., Aktionen werden auszahlungsmaximierend gewählt.
• und die Spieler besitzen allgemein bekanntes, gegenseitiges Wissen von rationalem Verhalten (Common Knowledge), d. h., jeder Spieler weiß auch vom rationalen Verhalten der anderen und diese wiederum wissen davon, dass man es weiß usw. (Infiniter Regress)

Modifizierte Arten der Rückwärtsinduktion erlauben es z. B. die Endlichkeit des Spiels als Restriktion zu umgehen, werden aber meistens nur in Spezialfällen angewendet.

Ablauf

Verbal

1. Vergleiche die Auszahlungen desjenigen Spielers Z, welcher zeitlich gesehen am letzten Entscheidungsknoten im letzten Teilspiel agieren soll.
2. Wähle diejenige Aktion, welche die Auszahlung maximiert, und streiche alle anderen. (Daraufhin verkürzt sich der Spielbaum, sodass der maximierende Auszahlungsvektor für Spieler Z an die Stelle des ehemals letzten Entscheidungsknotens tritt. Das erste Teilspiel ist somit gelöst.)
3. Nun betrachtet man die an diesem Punkt möglichen Auszahlungen des Spielers Y, der als vorletztes entscheiden soll. Man wählt bezugnehmend auf die vorherige Streichung der anderen Optionen die auszahlungsmaximierende Aktion für Spieler Y und reduziert den Spielbaum erneut um die Aktionen, die für den Spieler, der am Zuge ist, eine kleinere Auszahlung generieren würden.
4. Anschließend führt man diesen Vorgang für den Spieler durch, der anfangs als drittletzter an der Reihe war usw.
5. Man erhält genau dann ein teilspielperfektes Gleichgewicht, wenn man keine weiteren Aktionen mehr effektiv streichen kann; folglich hat man eine wechselseitig beste Strategienkombination gefunden, die in jedem Teilspiel ein Nash-Gleichgewicht darstellt.

Grafische und mathematische Veranschaulichung

Ein sequentielles Beispiel

Gegeben sei ein einfach-gespieltes sequentielles Spiel:

• drei Spieler i wobei ${\begin{aligned}i\in (X,Y,Z)\end{aligned}}$,

• jeweils zwei Aktionen und Strategien ${\begin{aligned}({\text{Links}}),({\text{Rechts}})\end{aligned}}$.

Das Spiel ist somit formal definiert als: $G=\lbrace (L_{i}),\dots ,(R_{i});\ u_{i}(L_{X},L_{Y},L_{Z}),u_{i}(L_{X},L_{Y},R_{Z}),\dots ,u_{i}(R_{X},R_{Y},R_{Z})\rbrace$

Die Rückwärtsinduktionsschritte in Extensivform:

Vergleich der Auszahlungen (u)	Schaubilder
Schaubild 1: Das letzte Teilspiel (GRÜN) wird betrachtet: ${\begin{aligned}u_{Z}(s_{X},s_{Y},L_{Z})=2>0=u_{Z}(s_{X},s_{Y},R_{Z})\end{aligned}}$
Schaubild 2: Das zweite Teilspiel wurde vereinfacht (ROT mit rationaler Auszahlung aus GRÜN): ${\begin{aligned}u_{Y}(s_{X},L_{Y},s_{Z})=2>1=u_{Y}(s_{X},R_{Y},s_{Z})\end{aligned}}$
Schaubild 3: Das komplett induzierte Spiel (BLAU mit rationalen Auszahlungen aus ROT und GRÜN): ${\begin{aligned}u_{X}(R_{X},s_{Y},s_{Z})=2>1=u_{X}(L_{X},s_{Y},s_{Z})\end{aligned}}$

Ergebnis

→ Die jeweils besten Aktionen sind: Spieler $X\,$ spielt RECHTS, $Y\,$ spielt LINKS und $Z\,$ spielt LINKS.

→ Das daraus resultierende teilspielperfekte Nash-Gleichgewicht lautet: $t^{\star }=(R_{X},L_{Y},L_{Z})\,$

Wiederholtes Gefangenendilemma

→ Hauptartikel: Gefangenendilemma

Ein weiteres geeignetes Beispiel zur Veranschaulichung des Vorgangs ist das Gefangenendilemma. Es ist ein simultan gespielter Klassiker in der Spieltheorie und zeigt in seiner wiederholten Form die reale und praktische Anwendbarkeit der Rückwärtsinduktion. Es zeigt das Konfliktpotenzial (Pareto-Optimalität sowie individuelle vs. kollektive Rationalität), welches die Rückwärtsinduktion als Lösungskonzept mit sich bringt.

Aufbau eines wiederholten Spiels

Das einfach wiederholte ( = 2-Runden) Spiel besteht aus:

• imperfekter Information, (mehrelementige Informationsmengen)

• vier echten Teilspielen und einem unechten (das gesamte Spiel), sowie

• zwei Spielern i wobei ${\begin{aligned}i\in (1;2)\end{aligned}}$ denen jeweils zwei Aktionen ${\begin{aligned}(K_{1},D_{1})\end{aligned}}$ und ${\begin{aligned}(k_{2},d_{2})\end{aligned}}$, kooperieren und defektieren, zur Verfügung stehen

• ${\begin{aligned}2^{5}=32\end{aligned}}$ Strategien: ${\begin{aligned}S_{i}=\lbrace (s_{i}^{1},\dots ,s_{i}^{32})\rbrace \end{aligned}}$ wobei ${\begin{aligned}s_{1}^{1}=(K_{1},K_{1}K_{1}K_{1}K_{1}),s_{2}^{1}=(k_{2},k_{2}k_{2}k_{2}k_{2}),\dots ,s_{1}^{32}=(D_{1},D_{1}D_{1}D_{1}D_{1}),s_{2}^{32}=(d_{2},d_{2}d_{2}d_{2}d_{2})\end{aligned}}$

Das Spiel ist definiert als: ${\begin{aligned}G=\lbrace S_{1},S_{2};u_{i}(s_{1}^{1},s_{2}^{1}),\dots ,u_{i}(s_{1}^{32},s_{2}^{32})\rbrace \end{aligned}}$

Zweimal gespieltes Gefangenendilemma

Vergleich der Auszahlungen	Schaubilder
Schaubild 4 zeigt den gesamten Spielbaum über 2 Runden. Die Auszahlungen wurden den Runden entsprechend aufsummiert. Die 4 Teilspiele sind grün umrandet. In jedem der 4 Teilspiele muss nun ein Nash-Gleichgewicht gesucht werden. Dies ist im Fall des wiederholten Gefangenendilemmas besonders einfach, da es strikt dominant ist zu defektieren. Teilergebnis: In jedem grün umrandeten Teilspiel existiert nur ein Nash-Gleichgewicht, (defektieren, defektieren). Die jeweils zu diesem Nashgleichgewicht gehörende Auszahlung wird für die weitere Rückwärtsinduktion benutzt.
Schaubild 5: Das Spiel ist nun soweit bearbeitet, dass es das einfach-gespielte Gefangenendilemma abbildet, mit dem einzigen Unterschied, dass die Auszahlungen die herausgearbeiteten Nash-Gleichgewichte aus den Teilspielen darstellen. Die letzten beiden Schritte können zusammengefasst werden. Auch in diesem zusammengefassten Spiel ist defektieren strikt dominant, so dass es wieder nur ein Nash-Gleichgewicht gibt, (defektieren, defektieren). Das bedeutet für das Gesamtspiel, dass beide Spieler an jedem ihrer Entscheidungsknoten defektieren werden. Das einzige Teilspielperfekte Gleichgewicht ist somit: ${\begin{aligned}\lbrace (D_{1},D_{1}D_{1}D_{1}D_{1}),(d_{2},d_{2}d_{2}d_{2}d_{2})\rbrace \end{aligned}}$

Ergebnis

→ Das Spiel ist gelöst; das teilspielperfekte Nash-Gleichgewicht lautet: ${\begin{aligned}t^{\star }=(D_{1},D_{1}D_{1}D_{1}D_{1};d_{2},d_{2}d_{2}d_{2}d_{2})\end{aligned}}$. Die Spieler konnten vor dem Spiel keine Informationen austauschen, besaßen kein gegenseitiges Vertrauen und konnten somit keine Versicherungen eingehen. Diese wiederum wären notwendig gewesen, um zur kollektiv rationalen (d. h. simultan-optimal für alle Beteiligten) Lösung mit der Auszahlung ${\begin{aligned}(-6;-6)\end{aligned}}$ zu gelangen. (Spekulativ und erfolgreich zu kooperieren wäre in diesen Beispielen nur jeweils risikoaffinen Spielern gelungen, da wir aber von einer Risikoneutralität ausgehen müssen, spielen Elemente, die sich außerhalb des absoluten und nominalen Auszahlungswertvergleichs befinden, bei diesem Verfahren keine weitere Rolle.)

Divergenz zwischen Theorie und Empirie

Differenzierung und Kritik

Die Rückwärtsinduktion ist ein theoretisches Konstrukt und stellt eine Möglichkeit dar, bestimmte Spiele in Form von teilspielperfekten Gleichgewichten zu lösen. Diese Art der Lösungen ist jedoch nur mit Hinblick auf die Einfachheit der oben dargestellten Muster zu bewerten. Sie stellt jedoch keine Dauerlösung dar, die immer kollektiv rational oder Pareto-optimal ist. Das ist auch nicht Aufgabe der Rückwärtsinduktion. Gerade deshalb sollte man die Lösungen jedes Spiels, die mit diesem Verfahren gefunden wurden, auf ihre Konsistenz (im rationalen Sinne) überprüfen, wie die folgenden Beispiele zeigen:

Das Kaufhauskettenspiel (Chainstore-Paradoxon nach Selten 1978)

→ Hauptartikel: Chainstore-Paradoxon

In diesem von Reinhard Selten entwickelten sequentiellen Kaufhauskettenspiel beherrscht ein Unternehmen den Angebotsmarkt. Dieser Monopolist bekommt nun abwechselnd neue potenzielle Konkurrenten dazu. Die Konkurrenten haben die Wahl, in den Markt einzutreten („IN“) oder es zu unterlassen („OUT“). Wenn ein Konkurrent eintritt, dann kann der Monopolist entscheiden, ob er ihn durch das Verändern der eigenen Preise „Bekämpfen“ oder „Dulden“ wird. Die Originalfassung Seltens umfasst dabei 20 Märkte und Konkurrenten. Selten erstellte nun auf Basis dieses Spiels ein Modell, um die Rationalität des Verhaltens marktbeherrschender Unternehmen bei Markteintritt eines Konkurrenten zu untersuchen.

Chainstore-Paradoxon auf zwei Märkte modifiziert. Die Konkurrenten (K1,K2) entscheiden, ob sie in den Markt eintreten wollen oder nicht; der Monopolist (M) kann sie bei Eintritt bekämpfen oder dulden. Der Gleichgewichtspfad ist grün markiert.

Die jeweils möglichen Aktionen haben dabei folgende Auswirkungen auf die Auszahlungen:

• „IN“: tritt der Konkurrent in den Markt ein und der Monopolist duldet ihn, erhalten beide (2); beide erhalten (0) wenn er ihn bekämpft.
• „OUT“: ein Konkurrent erhält (1), wenn er draußen bleibt. Der Monopolist kann daraufhin keine Aktion wählen, er erhält dann immer (5).

Ablauf

Das folgende Beispiel ist der Einfachheit halber und ohne Verzicht der Anwendbarkeit oder Aussagekraft auf zwei Märkte und Konkurrenten beschränkt.

Die Rückwärtsinduktion beginnt wieder mit den Auszahlungsvergleichen an den letzten Entscheidungsknoten, die in diesem Beispiel dem Monopolisten ${\begin{aligned}M\end{aligned}}$ angeschrieben werden. Hierbei müssen die Auszahlungen der Zweige, die keine spezielle Aktion enthalten, ignoriert werden, da der Monopolist keinen Einfluss auf sie hat; sie dienen an dieser Stelle lediglich der Veranschaulichung und könnten genauso gut eine Station vorher (bei ${\begin{aligned}K_{2}out\end{aligned}}$) stehen.

Die Auszahlungsvergleiche ergeben für den Monopolisten alle, dass „Dulden“ strikt besser ist als „Bekämpfen“:

${\begin{aligned}u_{M}(D_{M},D_{M};IN_{K1};in_{K2})=4>2=u_{M}(D_{M},B_{M};IN_{K1};in_{K2})\end{aligned}}$ … usw.,

Für die Konkurrenten ${\begin{aligned}K_{2}\end{aligned}}$ und ${\begin{aligned}K_{1}\end{aligned}}$, dass Einsteigen („IN“, oder „in“) immer strikt besser ist als Draußenbleiben („OUT“, oder „out“):

${\begin{aligned}u_{K2}(D_{M},D_{M};s_{K1}^{i};in_{K2})=2>1=u_{K2}(D_{M},D_{M};s_{K1}^{i};out_{K2})\end{aligned}}$

${\begin{aligned}u_{K1}(D_{M},D_{M};IN_{K1};s_{K2}^{i})=2>1=u_{K1}(D_{M},D_{M};OUT_{K1};s_{K2}^{i})\end{aligned}}$,

Ergebnis

→ Die Rückwärtsinduktion liefert das teilspielperfekte Nash-Gleichgewicht: ${\begin{aligned}t^{\star }=(D_{M},D_{M};IN_{K1};in_{K2})\end{aligned}}$. Empirisch wird aber immer wieder festgestellt, dass Monopolunternehmen beim Eintritt eines Konkurrenten einen Preiskampf führen wollen („Bekämpfen“) und so nicht nur dem Konkurrenten, sondern auch sich selbst schaden. Selten begründet dieses irrationale Verhalten auf der Unfähigkeit des Monopolisten die Rückwärtsinduktion in der Praxis über mehrere Perioden anzuwenden. Psychologische Ansätze begründen es mit der Präferenz des Beharrens auf eine Vorherrschaftsstellung; der Monopolist will nicht einsehen, dass es auch für ihn besser ist, einen anderen Anbieter einfach zu tolerieren, anstatt ihn mit Gewinneinbußen zu bekämpfen.

Das Tausendfüßlerspiel (Centipede-Game nach Rosenthal 1981)

Spielbaum eines 4-stufigen „Tausendfüßler“-Spiels. Die Spieler 1 und 2 (über den Knotenpunkten beschriftet) können den Geldtopf entweder nehmen (D,d) oder weitergeben (R,r).

Das Tausendfüßler-Spiel ist ein sequentielles und endliches Spiel, in dem zwei Spieler i wobei ${\begin{aligned}i\in (1;2)\end{aligned}}$ jeweils abwechselnd die Möglichkeit haben, einen ständig anwachsenden Geldtopf zu wählen oder weiterzugeben. Dieses Spiel geht in der Originalfassung von Rosenthal (1981) über 100 Runden, daher die Bezeichnung „Centipede-Game“. Es kann aber auf jede endliche Anzahl von Runden ${\begin{aligned}R\end{aligned}}$ modifiziert werden die ${\begin{aligned}R>1\end{aligned}}$ beträgt. Das folgende Beispiel soll über maximal 4 Runden gehen. Die möglichen Aktionen lauten: ${\begin{aligned}(R_{1},r_{2})\end{aligned}}$ für „row“ (in der Reihe bleiben) und ${\begin{aligned}(D_{1},d_{2})\end{aligned}}$ für „down“ (nach unten gehen).

Ablauf

Wird der Geldtopf gewählt, ist das Spiel automatisch beendet und die Spieler erhalten ihre jeweiligen Auszahlungen.

Wird er weitergereicht, verändern sich die Auszahlungen wie folgt:

• ${\begin{aligned}u_{i}-1\end{aligned}}$, für den Spieler, der weiterreicht,

• ${\begin{aligned}u_{i}+2\end{aligned}}$, für den Spieler, der die nächste Entscheidung treffen soll.

• die letzte mit „Weitergeben“ erreichbare Auszahlung ist jedoch immer für beide Spieler gleich groß: ${\begin{aligned}u_{1}=u_{2}\end{aligned}}$

Beginnend am letzten Entscheidungsknoten ergeben sich mittels Rückwärtsinduktion die folgenden Auszahlungsvergleiche:

Nutzen für Spieler 2: ${\begin{aligned}u_{2}(s_{1};r_{2},r_{2})=3<4=u_{2}(s_{1};d_{2},d_{2})\end{aligned}}$. Der letzte „r-Zweig“ kann durchgestrichen werden.

Spieler 1: ${\begin{aligned}u_{1}(R_{1},R_{1};s_{2})=2<3=u_{1}(D_{1},D_{1};s_{2})\end{aligned}}$. Wieder wird ein „R-Zweig“ gestrichen.

Spieler 2: ${\begin{aligned}u_{2}(s_{1};r_{2},r_{2})=1<2=u_{2}(s_{1};d_{2},d_{2})\end{aligned}}$ … usw.

Ergebnis

→ Die Aktion „R“ (den Topf weiterzugeben) wird in jeder Runde bei jedem Spieler durch die Aktion „D“ (den Geldtopf selbst zu wählen) dominiert. Das teilspielperfekte Nash-Gleichgewicht lautet ${\begin{aligned}t^{\star }=(D_{1},D_{1};d_{2},d_{2})\end{aligned}}$. Wenn also nicht auf gegenseitiges und wohlwollendes Vertrauen spekuliert wird, endet dieses Spiel sofort in der ersten Runde mit dem Annehmen des Geldtopfes. Das Eigeninteresse beziehungsweise das Misstrauen dem anderen Akteur gegenüber verhindert die kollektiv rationalere Wahl „Weitergeben“. Gäbe es eine Versicherung dafür, dass der jeweils andere Spieler kooperieren würde, könnten auch hier höhere Auszahlungen für beide Spieler realisiert werden. Empirische Studien zeigen jedoch, dass die sofortige Wahl von „D“ bzw. „d“ nur sehr selten beobachtet wird. Meistens werde erst über mehrere Runden "R"(„r“) gespielt, sodass sich der Topf vergrößert bis schließlich jemand "D"(„d“) spielt. Die Realisierung durch das Spielen von „immer R,r“ ist dennoch genauso selten beobachtet worden wie „immer D,d“. Dieses Beispiel zeigt somit, dass die Rückwärtsinduktion trotz korrekter Anwendung, nicht immer zur Pareto-optimalen Auszahlungsallokation führt.

Übergreifendes Beispiel

Das Henkerparadoxon

→ Hauptartikel: Paradoxon der unerwarteten Hinrichtung

Dieses aus der Mathematik und Philosophie stammende Paradoxon wird wie folgt beschrieben.

Ein verurteilter Gefangener bekommt von seinem Henker mitgeteilt:

1. er soll an einem Mittag der nächsten Wochentage (Montag–Freitag) gehenkt werden.
2. es werde für ihn völlig unerwartet stattfinden. (Aufgrund der zusätzlichen Qualen der Unvorhersehbarkeit soll er keine zusätzlichen Informationen darüber erhalten, an welchem der folgenden fünf Tage die Exekution stattfinden soll.)

Er überlegt sich daraufhin folgendes (Lösung durch ähnliche Vorhergehensweise wie bei der Rückwärtsinduktion): „Überlebe ich am vorletzten Tag der Woche den Mittag, so muss ich am Freitagmittag hingerichtet werden, das wäre dann aber nicht unerwartet. Also kann der letztmögliche Termin ausgeschlossen werden. Lebe ich am Mittag vor dem vorletzten Termin (Mittwoch) noch, könnte die Hinrichtung für den letzten (am Freitag) oder vorletzten Termin (Donnerstag) angesetzt sein, den Letzten habe ich aber bereits ausgeschlossen, es bleibt also nur der Vorletzte; das wäre jedoch dann nicht unerwartet da dann der Donnerstag zum letztmöglichen Termin werden würde. Lebe ich am Mittag vor dem zweitletzten Termin noch …“ usw.

„… die einzige Möglichkeit wäre, dass ich am Montag gehenkt werde, aber da ich das jetzt bereits weiß, ist auch dieser Tag nicht mehr überraschend für mich!“

Ergebnis

Der Gefangene kommt zu dem Schluss, dass er überhaupt nicht unerwartet gehenkt werden kann. In den ersten bekannten Fassungen dieses Paradoxons wird sogar beschrieben, dass er daraus ableitet, er werde wohl überhaupt nicht gehenkt werden. Ihm unterläuft dabei ein logischer Fehlschluss, da er aufgrund der erfolgreichen Falsifizierung der 2. Aussage des Henkers/Richters mittels seiner Überlegung davon ausgeht, die 1. Aussage sei damit ebenfalls widerlegt (cum hoc ergo propter hoc). Er geht demnach wohl davon aus, dass beide Annahmen in einem korrelierten, womöglich sogar kausalen Zusammenhang miteinander stehen würden.

Siehe auch

• Normalform eines Spiels

Literatur

• R. Gibbons: „A Primer in Game Theory“ Harvester Wheatsheaf, London 2001
• H. Wiese: „Entscheidungs- und Spieltheorie“ Springer, Berlin 2002
• C. Rieck „Spieltheorie – eine Einführung“ Rieck, Eschborn 2007
• T. Pries: „Kampfpreismissbrauch im ökonomisierten EG-Kartellrecht“ Mohr Siebeck, 2009
• M.J. Holler, G. Illing: „Einführung in die Spieltheorie“, Springer 6. Auflage, Berlin, 2005
• S. Berninghaus, K.M. Ehrhart: Strategische Spiele: Eine Einführung in die Spieltheorie, Springer 3. Auflage, Berlin 2010
• A. Diekmann: „Spieltheorie: Einführung, Beispiele, Experimente“, rororo 2. Auflage, 2009
• J. Neumann und O. Morgenstern: Theory of Games and Economic Behavior, Princeton University Press, 1944, online bei archive.org (PDF; 31,6 MB)
• R. Aumann: „Backward Induction and Common Knowledge of Rationality“, Games and Economic Behavior Vol. 8 Seiten 6–19, 1995
• M. J. Osborne, A. Rubinstein: „A Course in Game Theory“. MIT Press S. 135, 1994
• R. Selten: „The chain store paradox“, Theory and Decision Vol. 9 Seiten 127–159, 1978
• R. McKelvey und T. Palfrey: „An experimental study of the centipede game“, Econometrica Vol. 60, Seiten 803–836, 1992
• T. Y. Chow, „The surprise examination or unexpected hanging paradox,“ The American Mathematical Monthly Jan 1998

Weblinks

• Solving sequential games with backward induction
• Glossary of game theory terms
• Problems with backward induction
• Spieltheorie-Eintrag im Wirtschaftslexikon