mini|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.J. Neumann und O. Morgenstern: Theory of Games and Economic Behavior, Princeton University Press, 1944.
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.Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow, Seite 95, 1992R. Aumann: „Backward Induction and Common Knowledge of Rationality“, Games and Economic Behavior Vol. 8 Seiten 6–19, 1995. doi:10.1016/S0899-8256(05)80015-6M. J. Osborne, A. Rubinstein: „A Course in Game Theory“. MIT Press, S. 135 1994
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)D. Balkenborg und E. Winter: "A necessary and sufficient epistemic condition for playing backward induction" Journal of Mathematical Economics, 1995.
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
Vergleiche die Auszahlungen desjenigen Spielers Z, welcher zeitlich gesehen am letzten Entscheidungsknoten im letzten Teilspiel agieren soll. 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.) 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. Anschließend führt man diesen Vorgang für den Spieler durch, der anfangs als drittletzter an der Reihe war usw. 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 ,
jeweils zwei Aktionen und Strategien .
Das Spiel ist somit formal definiert als:
+ Die Rückwärtsinduktionsschritte in Extensivform: Vergleich der Auszahlungen (u) Schaubilder Schaubild 1: Das letzte Teilspiel (GRÜN) wird betrachtet: 400px|Ein 3-Stufenspiel in ExtensivformMcKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. (2010). Gambit: Software Tools for Game Theory, Version 0.2010.09.01. https://www.gambit-project.org. Schaubild 2: Das zweite Teilspiel wurde vereinfacht (ROT mit rationaler Auszahlung aus GRÜN): 350px|Vereinfachte Darstellung des Spiels durch Streichung der dominierten Aktion Schaubild 3: Das komplett induzierte Spiel (BLAU mit rationalen Auszahlungen aus ROT und GRÜN): 250px|Streichen des zweitletzten dominierten Zweiges Ergebnis
→ Die jeweils besten Aktionen sind: Spieler spielt RECHTS, spielt LINKS und spielt LINKS.
→ Das daraus resultierende teilspielperfekte Nash-Gleichgewicht lautet:
Wiederholtes 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 denen jeweils zwei Aktionen und , kooperieren und defektieren, zur Verfügung stehen
Strategien: wobei
Das Spiel ist definiert als:
+ Zweimal gespieltes Gefangenendilemma Vergleich der Auszahlungen SchaubilderSchaubild 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.300px|Wiederholtes Gefangenendilemma mit 4 TeilspielenSchaubild 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: 380px
Ergebnis
→ Das Spiel ist gelöst; das teilspielperfekte Nash-Gleichgewicht lautet: . 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 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)
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. 400px|mini|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 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 ) stehen.
Die Auszahlungsvergleiche ergeben für den Monopolisten alle, dass „Dulden“ strikt besser ist als „Bekämpfen“:
… usw.,
Für die Konkurrenten und , dass Einsteigen („IN“, oder „in“) immer strikt besser ist als Draußenbleiben („OUT“, oder „out“):
,
Ergebnis
→ Die Rückwärtsinduktion liefert das teilspielperfekte Nash-Gleichgewicht: . 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.R. Selten: „The chain store paradox“, Theory and Decision Vol. 9, Seiten 127–159, 1978. doi:10.1007/BF00131770T. Pries: „Kampfpreismissbrauch im ökonomisierten EG-Kartellrecht“ Seiten 25–27, Mohr Siebeck, 2009, ISBN 3-16-150166-7
Das Tausendfüßlerspiel (Centipede-Game nach Rosenthal 1981)
450px|mini|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 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“.