Rückwärtsinduktion

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Das Rückwärtsinduktionsverfahren

Ziel der Rückwärtsanalyse ist es, für rationale Spieler die optimalen Strategien in einem Spiel mit sequentiellen Zügen herauszufinden.
Dazu betrachtet man den Spielbaum und analysiert das Spiel von seinem Ende her, man arbeitet sich also “rückwärts” durch den Baum.

Vorgehen

- Bestimme diejenigen Entscheidungsknoten, die von keinen weiteren Entscheidungsknoten gefolgt werden (suche also die verschiedenen Endpunkte, von denen in jedem endlichen Spiel mindestens einer existiert)
- Bestimme für jeden Entscheidungsknoten die beste Aktion (also eine dominante Strategie) des Spielers, der bei diesem Knoten am Zug ist
- Ersetze jeden der betrachteten Entscheidungsknoten durch einen Endknoten mit der eben bestimmten Strategie. Dabei unterstelle man rationales Verhalten aller Spieler. Graphisch ist dieser Schritt als Streichen der dominierten Strategien zu verstehen.
- Wende das bis hierhin beschriebene Verfahren auf den verkürzten Spielbaum erneut an und wiederhole solange, bis man an der Wurzel angelangt ist

Bemerkung

1. In einem endlichen Spiel endet das Rückwärtsinduktionsverfahren nach einer endlichen Anzahl von Wiederholungen.
2. Im Verlaufe des Verfahrens wird für jeden Entscheidungsknoten eines Spielers eine Aktion festgelegt.
3. Das Verfahren erschwert sich, wenn es nicht überall strikte Dominanzen gibt, da die Bestimmung der optimalen Spielpfades nicht mehr ohne Weiteres möglich ist.

Beispiel


In einem Spiel mit zwei Spielern ziehe zuerst Spieler 1 und Spieler 2 reagiere darauf. Es kommt dabei zu folgendem Spielbaum mit den beschreibenen Auszahlungen:

                             o 1
                            / \
                          A/   \B
                          /     o 2
                         /     / \
                        /    a/   \b
                     (4,2) (3,6) (6,3)

Damit Spieler 1 entscheiden kann, ob er A oder B wählen soll, muss er eine Vorhersage über das Verhalten von Spieler 2 nach der Wahl der Aktion B machen.
Spieler 2 wird sich für Aktion a entscheiden, da 6=u2(B,a)> u2(B,b)=3 (also Strategie b von Strategie a strikt dominiert).
Der neue Baum sieht also so aus:

                             o 1
                            / \
                          A/   \B
                          /     o 2       
                         /     / 
                        /    a/  
                     (4,2) (3,6)

Unter dieser Annahme hat Spieler 1 nun die Wahl zwischen Startegie A und B. Da 4=u1(A)>u1(B,a)=3, wird sich Spieler 1 für Startegie A entscheiden.

Abschließende Bemerkung zu dem Beispiel:
In diesem Beispiel wird vorausgesetzt, dass es sich um ein nicht-kooperatives Spiel handelt. Könnten die Spieler (verbindliche) Absprachen treffen, wäre die optimale Startegie (B,b)=(6,3), da sie (4,2) strikt dominiert.

Weitere Anwendung und Beispiel im Artikel Elimination durch Domninanz

Meine Werkzeuge