Tausendfüssler-Spiel

Aus Wikiludia
(Weitergeleitet von Centipede Spiele)
Wechseln zu: Navigation, Suche

Das Tausendfüssler-Spiel ist ein Beispiel dafür, dass teilspielperfekte Gleichgewichte, die durch Rückwärtsinduktion gefunden werden, zu suboptimalen Auszahlungen für alle Spieler führen können. Das Tausendfüssler-Spiel wurde im Jahre 1981 von Rosenthal eingeführt und wird seither immer wieder neu untersucht.

Inhaltsverzeichnis

Das Tausendfüssler-Spiel nach Rosenthal

Das Tausendfüssler-Spiel ist ein Spiel in extensiver Form, in dem zwei Spieler jeweils abwechselnd die Möglichkeit haben entweder die Auszahlung eines höheren Anteils eines ständig anwachsenden Topfes Geld zu wählen, oder den Topf an den nächsten Spieler zu überreichen.

Die Auszahlungen sind dabei so gewählt, dass wenn man den Topf an den Gegner überreicht und dieser sich dann für die Auszahlung entscheidet, man eine geringere Auszahlung erhält, als wenn man selbst die Option Auszahlung gewählt hätte.

Das von Rosenthal ursprünglich analysierte Spiel bestand aus 100 Runden. Man nennt jedoch jedes Spiel von oben genannter Form und mit einer festen Anzahl von Runden ein Tausendfüssler-Spiel.


Modellierung und Analyse anhand eines Beispiels

Beschreibung des Spieles

Zwei Personen spielen ein extensives, nicht-kooperatives Spiel, bei dem sie an fünf Zügen jeweils abwechselnd zwischen "Spiel beenden" (B) und "Spiel fortsetzen" (F). Die Auszahlungen betragen: (1,0) für B beim ersten Zug, (0,2) für B beim zweiten, (3,1) für B beim dritten, (2,4) für B beim vierten, (5,3) für B beim fünften und (4,6) bzw. (6,5) für B bzw. F beim sechsten.

Gegeben ist also G = (M, H, j, u) mit

  • der Spielermenge M = {1,2},
  • der Historie  H = \{\emptyset, (F), (B), (F,F), (F,B), (F,F,F), (F,F,B), (F,F,F,F), (F,F,F,B), (F,F,F,F,F), (F,F,F,F,B), (F,F,F,F,F,F),(F,F,F,F,F,B)\}, mit
  • der Entscheidungsmenge E = \{\emptyset,(F), (F,F), (F,F,F), (F,F,F,F), (F,F,F,F,F)\} und
  • den Endknoten  Z:=H \setminus E = \{(B), (F,B), (F,F,B), (F,F,F,B), (F,F,F,F,B), (F,F,F,F,F,F), (F,F,F,F,F,B)\} ,
  • der Spielerfunktion j:E \longrightarrow M mit
    • j((\emptyset)) = j((F,F)) = j((F,F,F,F)) = 1 und
    •  j((F)) = j((F,F,F)) = j((F,F,F,F,F)) = 2 \ sowie
  • der Nutzenfunktion u mit den oben und im Spielbaum angegeben Auszahlungen:


Spielbaum:

                          F               F                F               F               F              F
                 [1]-------------[2]-------------[1]-------------[2]-------------[1]-------------[2]------------- (6,5)
                  |               |               |               |               |               |
                  |               |               |               |               |               |
                B |             B |             B |             B |             B |             B |
                  |               |               |               |               |               |
                  |               |               |               |               |               |
                (1,0)           (0,2)           (3,1)           (2,4)           (5,3)           (4,6)
  


(Paradoxe) Lösung durch Rückwärtsinduktion

Das teilspielperfekte Gleichgewicht findet man durch Rückwärtsinduktion: Beim letzten Zug wird Spieler 2 B wählen, um seine Auszahlung zu maximieren, Spieler 1 antizipiert dies und wählt daher beim fünften Zug lieber selbst B, was wiederum Spieler 2 antizipiert und zuvor lieber B wählt usw. bis zum ersten Zug, wo Spieler 1 lieber B wählt als F, da die Auszahlung (1,0) im Vergleich zu (0,2) für ihn die beste Antwort ist.

Die optimale Strategie s_i^* ist also für beide Spieler s_i^* = (B,B,B),  (i \in \{1,2\}) Damit ergeben sich als teilspielperfekte Nash-Gleichgewichte (s_1^*, s_2^*) = ((B,X,X), (X,X,X)) mit X \in \{B,F\} mit der Auszahlung (1,0).

Interessant und paradox daran ist, dass beide Spieler damit wesentlich schlechter abschneiden, als sie könnten (wenn das Spiel z.B. beim sechsten Zug mit F (6,5) oder B (4,6) beendet wird). Man kann das Ergebnis also als Variante des Prinzips "Lieber einen Spatz in der Hand, als eine Taube auf dem Dach" interpretieren: Dadurch, dass sie sich beim folgenden Zug stets verschlechtern können, wählen rational handelnde Spieler lieber einen sicheren kleinen Nutzen und verwerfen damit die Möglichkeit auf größere Gewinne, als dass sie das (erwartbar eintretende) Risiko eingehen, den kleinen Gewinn zu verlieren.

Bei dieser Auszahlungsgestaltung ist zudem die Entwicklung einer kooperativen Lösung schwierig, weil immer einer der beiden Spieler auf die Höchstauszahlung von 6 verzichten müsste: Entweder Spieler 1 fällt auf 4 zurück, wenn Spieler 2 B statt F wählt, oder Spieler 2 auf 5, wenn er - irrationalerweise - F statt B wählt. Jede Vereinbarung, z.B. eine Vereinbarung, stets F zu wählen, wäre an irgendeinem Entscheidungsknoten irrational und damit unglaubwürdig.

Abweichende Ergebnisse in der Realität

Es existieren verschiedene Verhaltensstudien über das Tausendfüssler-Spiel (mit verschiedener Anzahl von Zügen), welche zeigen, dass die Spieler sich nur selten die theoretischen Vorhersagen halten. In der Realität wird sich der erste Spieler also nur selten für den Payoff in der ersten Runde entscheiden. Für dieses "unlogische" Verhalten gibt es mehrere Erklärungsversuche:

  • Beide Spieler sind sich der optimalen Theorie bewusst, streben allerdings nach mehr. Dabei versuchen sie den Gegenspieler selbstloses Verhalten vorzutäuschen, um damit den Gegenspieler selbst zu so einer unlogischen Handlung zu verführen. Wenn Spieler 1 anfangs die Entscheidung weiter gibt, weiss Spieler 2 schon mal, dass sein Gegenspieler sich nicht strikt logisch verhält, was ihn verbunden mit den höheren Payouts selbst zu einer unlogischen Entscheidung verführt.
  • Eine anderer Grund ist die Möglichkeit von Aktionsfehler. Die Spieler experimentieren dabei mit verschiedenen Strategien und weichen dabei von ihrem logischem Verhalten ab.


Mögliche Auflösung des Tausendfüssler-Spiels

Das oben beschriebene Dilemma/Paradox eines Tausendfüssler-Spiels bedeutet nichts anderes, als dass die Auszahlung am Ende des Spieles nicht pareto-optimal ist. Man kann das Spiel aber unter zusätzliche Annahmen zu einem pareto-optimalen Gleichgewicht führen. Da untenstehender Lösungsansatz generell für (paradoxe) Tausendfüssler-Spiele gültig ist, ist es sinnvoll das Spiel allgemein zu definieren.

Formale Beschreibung des Tausendfüssler-Spiels

Notationen

Sei  N=\{1,...,n+1\} \quad \overline{N}=\{1,...,n\} \quad \forall n \in \mathbb{N} ,  K=\{k \in N | k \ \ {\rm gerade}\} und  L=\{l \in N | l \ \ {\rm ungerade}\} . Weiter sei  \overline{L}=L \cap \overline{N} und  \overline{K}=K \cap \overline{N} .

Defintion: Tausendfüssler

Ein Tausendfüssler ist ein 2-Personen Spiel in extensiver Form mit vollständiger und vollkommener Information und  n>1 \ Entscheidungsknoten. An jedem Entscheidungsknoten  m \in \overline{N} spielt Spieler 1, falls m gerade und Spieler 2 falls m ungerade. Jeder Spieler i = 1,2 hat in jedem Entscheidungsknoten m die Strategien  s_i^m \in \{B,F\} zur Auswahl, wobei B für "Beenden" und F für "Fortsetzen" steht. Die Wahl von  s_i^m=B führt zu einer Auszahlung (am,bm), wobei am die Auszahlung von Spieler 1 und bm die Auszahlung von Spieler 2 bezeichnet. Die Wahl von  s_i^m=F führt zu dem nächsten Entscheidungsknoten, falls m < n und der Endauszahlung (an + 1,bn + 1), falls m = n.

Defintion: paradoxer Tausendfüssler

Ein Tausendfüssler heißt paradoxer Tausendfüssler, falls für jedes  m \in N gilt:

a) Falls  m+1 \in N , so ist  a_m > a_{m+1} \ für  m \in L und  b_m > b_{m+1} \ für  m \in K

b) Falls  m+2 \in N , so ist  a_m < a_{m+2} \ und  b_m \leq b_{m+2} für  m \in L , während  a_m \leq a_{m+2} und  b_m < b_{m+2} \ für  m \in K

Behavioristischer Lösungsansatz

Dieses Paradox - die nicht pareto-optimale Auszahlung - lädt dazu ein sich Gedanken über eine mögliche Lösung zu machen. Murat Sertel und Fangruo Chen taten dies indem sie die Theorie des "homo erraticus", dem sich "irrenden" bzw. "unberechenbaren" Menschen, entwickelten.

Hierbei ist es das Ziel auf einem Weg der nicht über Kooperation führt eine Lösung des Tausendfüssler Spieles zu finden, die zu einer pareto-optimalen Auszahlung führt, die für beide Spieler akzeptabel ist.

Definition: homo erraticus Modell für einen Tausendfüssler

Ein homo erraticus Modell für einen Tausendfüssler mit  n>1 \ Entscheidungsknoten ist jedes n-Tupel  p=(p_1,...,p_n) \in [0,1]^n , wobei für alle  m \in \overline{N} ,  p_m \ für die Wahrscheinlichkeit der Wahl von F steht.

Das homo erraticus Modell für einen Tausendfüssler nennt man gelöst, falls:

a)  a_m < \overline{a}_{m+1} für jedes  m \in \overline{L} mit  m<n \ , wobei  \overline{a}_m = p_m \cdot \overline{a}_{m+1} + (1-p_m) \cdot a_m und  \overline{a}_{n+1} = a_{n+1}

b)  b_m < \overline{b}_{m+1} für jedes  m \in \overline{K} mit  m<n \ , wobei  \overline{b}_m = p_m \cdot \overline{b}_{m+1} + (1-p_m) \cdot b_m und  \overline{b}_{n+1} = b_{n+1}

c)  a_1 \leq a_n und  b_1 \leq b_n

Eine solche Lösung nennt man behavioristische Lösung.

Bemerkung

  • Nimmt man nun an, dass p das homo erraticus Modell eines Tausendfüsslers löst.
Dann wird Spieler 1 an jedem Entscheidungsknoten  l \in \overline{L} mit  l < n \ die Strategie  s_1^l=F wählen, da die Auszahlung  a_l \ kleiner ist als die erwartete Auszahlung  \overline{a}_{l+1} . Falls  n \in L wird Spieler 1 für  l=n \ die Strategie  s_1^n=B wählen.
  • Ebenso wird Spieler 2 an jedem Entscheidungsknoten  k \in \overline{K} mit  k < n \ die Strategie  s_2^k=F wählen, da die Auszahlung  b_k \ kleiner ist als die erwartete Auszahlung  \overline{b}_{k+1} . Falls  n \in L wird Spieler 1 für  k=n \ die Strategie  s_2^n=B wählen.
  • Zu beachten ist, dass die beiden Spieler das homo erraticus Modell gemeinsam unterhalten. Dies bedeutet, dass es gemeinsames Wissen ist, dass beide Spieler glauben, dass das n-Tupel  p \in [0,1]^n die Wahrscheinlichkeit der Strategie "Fortsetzen" in jedem Schritt beschreibt. Es wird jedoch nicht vorausgesetzt, dass p auch die tatsächlichen Wahrscheinlichkeiten beschreibt, also muss p nicht gemeinsames Wissen sein.

Behavioristische Lösung des Beispiels

Behauptung:

Das obige Beispiel lässt sich behavioristisch lösen zum Beispiel durch  p=(\frac{2}{3},\frac{2}{3},\frac{2}{3},\frac{2}{3},\frac{2}{3},\frac{2}{3}) .

Beweis:

m=6: Spieler 2 ist am Zug und wählt natürlich die Strategie B mit der Auszahlung (4,6).

m=5: Spieler 1 ist am Zug und es gilt:  a_5 = 5 \ und  p_6 = \frac{2}{3}


5 = a_5 < \overline{a}_6 = p_6 \cdot \overline{a}_7 + (1-p_6) \cdot a_6
= p_6 \cdot a_7 + (1-p_6) \cdot a_6
= \frac{2}{3} \cdot 6 + (1- \frac{2}{3}) \cdot 4
= 5 + \frac{1}{3}
.

Also:  a_5 < \overline{a}_6 und somit wird Spieler 1 die Strategie F wählen.

m=4: Spieler 2 ist am Zug und es gilt:  b_4 = 4 \ und  p_5 = \frac{2}{3}


4 = b_4 < \overline{b}_5 = p_5 \cdot \overline{b}_6 + (1-p_5) \cdot b_5
= \frac{2}{3} \cdot (p_6 \cdot \overline{b}_7 + (1-p_6) \cdot b_6) + \frac{1}{3} \cdot 3
= \frac{2}{3} \cdot (\frac{2}{3} \cdot 5 + \frac{1}{3} \cdot 6)+1
= 4 + \frac{5}{9}
.

Also:  b_4 < \overline{b}_5 und somit wird Spieler 2 die Strategie F wählen.

m=3: Spieler 1 ist am Zug und es gilt:  a_3 = 3 \ und  p_4 = \frac{2}{3}


3 = a_3 < \overline{a}_4 = p_4 \cdot \overline{a}_5 + (1-p_4) \cdot a_4
= \frac{2}{3} \cdot (p_5 \cdot \overline{a}_6 + (1-p_5) \cdot a_5) + \frac{1}{3} \cdot 2
= \frac{2}{3} \cdot (\frac{2}{3} \cdot 5 \frac{1}{3} + \frac{1}{3} \cdot 5)+ \frac{2}{3}
= 4 + \frac{4}{27}
.

Also:  a_3 < \overline{a}_4 und somit wird Spieler 1 die Strategie F wählen.

m=2: Spieler 2 ist am Zug und es gilt:  b_2 = 2 \ und  p_3 = \frac{2}{3}


2 = b_2 < \overline{b}_3 = p_3 \cdot \overline{b}_4 + (1-p_3) \cdot b_3
= \frac{2}{3} \cdot (p_4 \cdot \overline{b}_5 + (1-p_4) \cdot b_4) + \frac{1}{3} \cdot 1
= \frac{2}{3} \cdot (\frac{2}{3} \cdot 4 \frac{4}{9} + \frac{1}{3} \cdot 4)+ \frac{1}{3}
= 3 + \frac{20}{81}
.

Also:  b_2 < \overline{b}_3 und somit wird Spieler 2 die Strategie F wählen.

m=1: Spieler 1 ist am Zug und es gilt:  a_1 = 1 \ und  p_2 = \frac{2}{3}


1 = a_1 < \overline{a}_2 = p_2 \cdot \overline{a}_3 + (1-p_2) \cdot a_2
= \frac{2}{3} \cdot (p_3 \cdot \overline{a}_4 + (1-p_3) \cdot a_3) + \frac{1}{3} \cdot \frac{1}{3} \cdot 0
= \frac{2}{3} \cdot (\frac{2}{3} \cdot 4 \frac{4}{27} + \frac{1}{3} \cdot 3)+ 0
= 2 + \frac{124}{243}
.

Also:  a_1 < \overline{a}_2 und somit wird Spieler 1 die Strategie F wählen.

Spielbaum:

                          F               F                F               F               F              F
                 [1]-------------[2]-------------[1]-------------[2]-------------[1]-------------[2]------------- (6,5)
                  |               |               |               |               |               |
                  |               |               |               |               |               |
                B |             B |             B |             B |             B |             B |
                  |               |               |               |               |               |
                  |               |               |               |               |               |
Auszahlungen:   (1,0)           (0,2)           (3,1)           (2,4)           (5,3)           (4,6)
erwartete Auszahlungen:      (2.51,2.83)     (3.77,3.25)     (5.22,4.30)     (4.15,4.56)     (5.33,5.33)


Quellen

  • Schlee, Walter: Einführung in die Spieltheorie, Vieweg, Wiesbaden, 1. Aufl. 2004, ISBN 3-528-03214-6, S. 105
  • Sertel, Chen: Resolving Paradoxical Centipedes Behavioristically or by Unilateral Pre-donations. In: Dutta et al: Game Theory and Economic Applications, Springer, 1992, S. 249-286
Meine Werkzeuge