Ein einfaches Kartenspiel

Aus Wikiludia
Wechseln zu: Navigation, Suche

Das hier ausführlich beschriebene Beispiel eines einfaches Kartenspiels erfüllt mehrere Zwecke:

  • Es ist ein Beispiel eines extensiven Spiels mit einem Zufallspieler.
  • Es ein extensives Spiel ohne vollkommene Information.
  • Es ist ein Beispiel eines Spieles, in dem die ursprünglich unvollständige Information durch ein Spiel modelliert ist, welches einen Zufallspieler hat und ohne vollkommene Information ist, welches aber ansonsten ein Spiel mit vollständiger Information ist.
  • Das Beispiel illustriert den Begriff der Strategie bei Spielen mit unvollkommener Information.
  • Es zeigt auch,, wie das Spielergebnis bzw. der Erwartungswert einer Strategiekombination zustande kommt, wenn ein Zufallspieler vorhanden ist.
  • Es zeigt ferner, wie ein extensives Spiel in eine Normalform überführt wird.
  • Das Beispiel illustriert außerdem, wie bei ein Normalformenspiel mit unvollständiger Information als ein Bayes-Spiel modelliert wird

Inhaltsverzeichnis

Das Spiel

Vor der mathematischen Darstellung des Spiels in spieltheoretischen Formen soll es umgangssprachlich beschrieben werden:

  • Zu Beginn des Spiels setzen die beiden Spieler 1 und 2 je einen EURO.
  • Als nächstes zieht Spieler 1 eine Karte aus einem gut gemischten Stoß von 52 Karten (die zur Hälfte aus schwarzen und zur anderen Hälfte aus roten Karten bestehen). Spieler 1 kennt danach die Farbe der Karte, Spieler 2 kennt sie nicht. Das ist der Mangel an Information, der bei diesem Spiel vorliegt!
  • Spieler 1 ist jetzt am Zug und er muss zwischen Aufgeben (A ~ "fold") oder Erhöhen (E ~ "raise") wählen. Wenn Spieler 1 erhöht, so hat er einen weiteren EURO einzusetzen. Wenn Spieler 1 aufgibt, so ist das Spiel zu Ende. Spieler 1 hat dann die die Karte zu zeigen.
Ergebnis: Spieler 1 erhält den "Topf" also die 2 EURO, wenn die Karte rot ist und Spieler 2 erhält den Topf, wenn die Karte schwarz ist. Das entspricht unter Berücksichtigung des Einsatzes von je einem EURO einer Auszahlung von (1,-1) bei rot und (-1,1) bei schwarz.
  • Wenn Spieler 1 erhöht und seinen Euro eingesetzt hat, so ist Spieler 2 am Zug. Er muss zwischen Passen (P ~ "pass") und weiter Erhöhen (M ~ "meet") wählen. Wenn Spieler 2 erhöht, so muss er wie Spieler 1 einen zweiten EURO setzen. Das Spiel ist nach diesem Zug in jedem Fall beendet.
Ergebnis im Falle P: Wenn Spieler 2 gepasst hat, so erhält Spieler 1 den Topf, die Auszahlung entspricht (1,-1).
Ergebnis im Falle M: Die Karte wird aufgedeckt und 1 erhält den Topf, wenn sie rot ist (Auszahlung (2,-2)) und 2 erhält den Topf, wenn sie schwarz ist (Auszahlung (-2,2)).

In extensiver Form

Der Mangel an Information des zweiten Spielers wird in der Modellierung als Spiel in extensiver Form durch den Zufallsspieler 0 beschrieben, der zu Beginn mit der Wahrscheinlichkeit  \textstyle \frac 1 2 eine schwarze bzw. eine rote Karte zieht.
Wir erhalten das folgende Spiel in extensiver Form mit unvollkommener aber vollständiger Information:

                                        Vor dem ersten Zug setzt jeder 
                                           Spieler jeweils 1 €. Danach: 
                 o 0                    Der Zufall zieht die Karte r (rot)
                / \                        oder s (schwarz) jeweils mit
             s /   \ r (je 1/2)            der Wahrscheinlichkeit 1/2.    
              /     \                   Spieler 1 erhält diese Karte. 
             /       \                    
            o 1       o 1               Spieler 1 wählt zwischen 
           /|         |\                   Aussteigen (A) oder Erhöhen  
          / |         | \                  (E)um 1 €.
      A  /  |         |  \ A
        /   |         |   \
       o    |E       E|    o
    (-1,1)  |         |  (1,-1)
            |         |
            |         |
          2 o ======= o 2               Spieler 2 entscheidet zwischen
           /|         |\                   Passen (P) oder Erhöhen (M)
          / |         | \                  um 1 €.  
       P /  |         |  \ P            Er kennt die Farbe der Karte
        /   |M       M|   \                nicht.
       o    |         |    o
    (1,-1)  |         |  (1,-1)         
            |         |                 Die Auszahlungen sind als 
            |         |                    Zahlenpaare bei den termi-
            o         o                    nalen Historien notiert. 
         (-2,2)     (2,-2)

Die Informationsmenge wird durch die Linie ======= illustriert, welche die zwei Entscheidungsknoten von Spieler 2 verbindet..

Spielstruktur: In der Folgendarstellung ist das "einfache Kartenspiel" Γ in extensiver Form als

 \Gamma = (M,H,P,\mathcal J, f,u)

gegeben mit den folgenden Bestandteilen:

  • M = {1,2} ist die Spielermenge.
  •  H = \{\emptyset, (s),(r), (s,E),(r,E),(s,A),(r,A), (s,E,P),(r,E,P),(s,E,M),(r,E,M), \} ist der Spielbaum (Menge der Historien) mit der Zerlegung  H = E\cup Z in die Menge E=\{\emptyset, (s),(r), (s,E),(r,E)\} der Entscheidungshistorien und die Menge Z = {(s,A),(r,A),(s,E,P),(r,E,P),(s,E,M),(r,E,M),} der terminalen Historien.
  •  P : E \to \{0\}\cup M ist die Spielerfunktion, definiert durch P(\emptyset)=0\,,\, P((i))=1\,,\, P((i,E))=2\,,\, i=r,s\,. Daher hat E die Zerlegung E= E_0\cup E_1 \cup E_2 mit  E_0= \{\emptyset\}\,,\, E_1=\{(s),(r)\}\,,\, E_2 = \{(r,E),(s,E)\} \,, wobei  E_k = P^{-1}(k)\,,\, k=0,1,2\,.
  •  \mathcal J = (\mathcal J_1, \mathcal J_2) ist die Informationszerlegung mit  \mathcal J_1 = \{\{(s)\},\{(r)\}\} \,,\, \mathcal J_2 = \{E_2\}\,. Die Informationsmengen von Spieler 1 sind einpunktig, der Spieler 2 hat die eine Informationsmenge I: = E2. Die gesamte Unvollständigkeit an Information liegt in diesem Spiel also bei Spieler 2 und ist durch die eine Informationsmenge I gegeben.
  •  f(i|\emptyset) = \textstyle \frac 1 2 \,,\, i=s,r\,,\, ist die Wahrscheinlichkeit auf der Aktionsmenge  A_\emptyset = E_1 des Zufallsspielers 0.
  •  u: Z \to \mathbb R^2 lässt sich aus der obigen Spielbaumdarstellung ablesen.


Strategien und assoziierte Normalform

Aktionsmengen:

Spieler 1 hat im Knoten (s) die Aktionsmenge A(s) = A((s)) = {A,E} und in (r) die Aktionsmenge A((r)) = {A,E}.
Spieler 2 hat die Informationsmenge I = {(s,E),r,E)} mit der dazugehörigen Aktionsmenge A(I) = {P,M}.

Reine Strategien:
Daher hat Spieler 1 die folgenden 4 Strategien

 (E,E) : (s) \mapsto E\,,\, (r) \mapsto E
 (E,A) : (s) \mapsto E\,,\, (r) \mapsto A
 (A,E) : (s) \mapsto E\,,\, (r) \mapsto A
 (A,A) : (s) \mapsto A\,,\, (r) \mapsto A\,,

und Spieler 2 hat die folgenden 2 Strategien

 (P) : I \mapsto P
 (M) : I \mapsto M\,.

Assoziierte Normalform:
Wir erhalten die Auszahlungen der reinen Strategien und damit die assoziierte Normalform:

Spieler 2
(P) (M)
Spieler 1 (E,E) (1,-1) (0,0)
(E,A) (1,-1) (-\textstyle \frac 1 2,\textstyle \frac 1 2)
(A,E) (0,0) (\textstyle \frac 1 2,-\textstyle \frac 1 2)
(A,A) (0,0) (0,0)

Wie kommen die angegebenen Auszahlungen zustande?

  • Für das Strategieprofil t = ((E,E),(P)) werden die terminalen Historien (s,E,P) und (r,E,P) als Ergebnisse der Strategie t jeweils mit der Wahrscheinlichkeit \textstyle \frac 1 2 erreicht. Daher ist die Auszahlung
u(t) = \textstyle \frac 1 2u((s,E,P)) + \textstyle \frac 1 2u((r,E,P)) = \textstyle \frac 1 2(1,-1) + \textstyle \frac 1 2(1,-1) = (1,-1).
  • Analog werden für t = ((E,E),(M)) die Historien (s,E,M) und (r,E,M) mit Wahrscheinlichkeit \textstyle \frac 1 2 erreicht. Also
u(t) = \textstyle \frac 1 2u((s,E,M)) + \textstyle \frac 1 2u((r,E,M)) = \textstyle \frac 1 2(-2,2) + \textstyle \frac 1 2(2,-2) = (0,0).
  • Für t = ((E,A),(P)) werden (s,E,P) und (r,A) mit Wahrscheinlichkeit \textstyle \frac 1 2 erreicht. Also
u(t) = \textstyle \frac 1 2(1,-1) + \textstyle \frac 1 2(1,-1) = (1,-1).
  • Für t = ((E,A),(M)) werden die Historien (s,E,M) und (r,A) mit Wahrscheinlichkeit \textstyle \frac 1 2 erreicht. Auszahlung:
u(t) = \textstyle \frac 1 2u((s,E,M)) + \textstyle \frac 1 2u((r,A)) = \textstyle \frac 1 2(-2,2) + \textstyle \frac 1 2(1,-1) = (-\textstyle \frac 1 2,\textstyle \frac 1 2).
  • Für t = ((A,E),(P)) werden (s,A) und (r,E,P) erreicht. Also
u(t) = \textstyle \frac 1 2(-1,1) + \textstyle \frac 1 2(1,-1) = (0,0).
  • Für t = ((A,E),(M)) werden (s,A) und (r,E,M) erreicht. Also
u(t) = \textstyle \frac 1 2(-1,1) + \textstyle \frac 1 2(2,-2) = (\textstyle \frac 1 2,-\textstyle \frac 1 2).
  • u((A,A),(P)) = (0,0).
  • u((A,A),(M)) = (0,0).

Bemerkung: das assoziierte Normalformenspiel ist ein Nullsummenspiel mit zwei Spielern. Damit stehen die Methoden für solche Nullsummenspiele zur Verfügung.

Nash-Gleichgewicht

Satz 1: Das einzige Nash-Gleichgewicht der assozierten Normalform und damit auch der extensiven Form ist die gemischte Strategiekombination

 (\sigma^*_1,\sigma^*_2) = \left( \textstyle \frac 1 3 (E,E)+ \textstyle \frac 2 3 (A,E), \textstyle \frac 1 3 (P) + \textstyle \frac 2 3 (M) \right)\,.

Beweis: Für  \sigma_1 = a(E,E) + b (A,E) + c(E,A) + d(A,A)\,, \,a+b+c+d = 1\,, und  \sigma_2 = q (P) +(1-q)(M) \,,\, 0 \leq q \leq 1 \,, ist der Nutzen für Spieler 1

 u_1(\sigma_1,\sigma_2) = aq (+1)+ bq (0)+ cq (+1) + dq (0) + a(1-q) (0)+b(1-q) (\textstyle \frac 1 2) +c (1-q)(-\textstyle \frac 1 2) +d(1-q)(0) =
 \quad\quad = (a+c)q + \textstyle \frac 1 2 (b-c)(1-q) \,.

Im Falle q = 0 ist das  \textstyle \frac 1 2 (b-c), also liefert b = 0 eine beste Antwort des Spielers 1.
Im Falle q = 1 ist das a + c , also liefert a + c = 1 eine beste Antwort, d.h. b = d = 0.
Im Falle 0 < q < 1 erfordert eine beste Antwort zunächst d = 0 und dann auch c = 0. Mit b = 1 - a gilt es also den Ausdruck

  aq + \textstyle \frac 1 2 b(1-q) = \textstyle \frac 1 2 a(3q-1) +  \textstyle \frac 1 2 (1-q)\,

bei vorgegebenen q zu maximieren.
Im Falle 3q -1 < 0 liefert dann a = 0 (b = 1) die beste Antwort.
Im Falle 3q -1 > 0 liefert dann a = 1 die beste Antwort.
Im Falle 3q -1 = 0, das ist der interessante Fall, ist jede Wahl von a aus [0,1] mit b = 1 - a eine beste Antwort.
Die besten Antworten σ2 des Spielers 2 auf a(E,E) + (1 − a)(A,E) findet man wegen

 u_2(a(E,E) + (1-a)(A,E),q(P) + (1-q)(M)) = -aq -\textstyle \frac 1 2 (1-a)(1-q) = \textstyle \frac 1 2 q (1- 3a) - \textstyle \frac 1 2(1-a)

ganz analog:
Im Falle 1 - 3a < 0 liefert q = 1 beste Antwort.
Im Falle 1 - 3a > 0 liefert q = 0 beste Antwort.
Im Falle 1 - 3a = 0 liefert jedes q aus dem Einheitsintervall eine beste Antwort.
Gegenseitig beste Antwort erhält man also genau für

 a = \textstyle \frac 1 3 \,,\, q = \textstyle \frac 1 3 \,.

Damit ist der Satz bewiesen.

Folgerung 1: Das Spiel hat kein Nash-Gleichgewicht in reinen Strategien.

Folgerung 2: Das angegebene Nash-Gleichgewicht ist auch teilspielperfekt.

Denn es gibt keine echten Teilspiele, die die Informationsmenge nicht zerschneiden würden.


Perfektes Gleichgewicht

Satz 2: Das in Satz 1 angegebene Nash-Gleichgewicht ist auch ein perfektes Gleichgewicht der assoziierten Normalform.

Beweis: Diese Aussage folgt bereits aus dem Existenzsatz: Es gibt immer ein perfektes Gleichgewicht in gemischten Strategien und dieses ist auch Nash-Gleichgewicht. Da nach Satz 1 nur ein Nash-Gleichgewicht existiert, ist dieses auch ein perfektes Gleichgewicht.
Wir wollen die Perfektheit aber auch direkt nachweisen. Dazu müssen wir eine Folge  \sigma^m = (\sigma_1^m,\sigma_2^m) von voll gemischten Strategien angeben, die punktweise gegen  \sigma^* =(\sigma_1^*,\sigma_2^*) konvergiert, so dass

1.  \sigma_1^* beste Antwort auf alle  \sigma_2^m ist, und
2.  \sigma_2^* beste Antwort auf alle  \sigma_1^m ist.

 \sigma_2^* ist bereits voll gemischt, daher setzen wir der Einfachheit halber

 \sigma _2^m := \sigma _2^*\,, \, m\in \mathbb N\,.

Wir wissen bereits, dass  \sigma_1^* beste Antwort auf  \sigma_2^* = \sigma _2^m ist, weil ja  \sigma^* = (\sigma_1^*,\sigma_2^*) Nash-Gleichgewicht ist, wie gerade im vorangehende Satz bewiesen. Also ist 1. erfüllt.
Um  \sigma_1^m geeignet wählen zu können, führen wir mit dem Ansatz (Entwicklung um das Nash-Gleichgewicht σ * )

 \sigma_1(v) := (\textstyle \frac 1 3 + a)(E,E) + b (A,E) + (\textstyle \frac 2 3 +c)(E,A) + d (A,A)\,\, , \,\, \sigma_2(t):=  (\textstyle \frac 1 3 +t)(P) + (\textstyle \frac 2 3 - t)(M)\,,

v = (a,b,c,d), die Berechnung von u21(v),σ2(t)) durch. Es gilt

 u_2(\sigma_1(v),\sigma_2(t)) = (\textstyle \frac 1 3 +a) (\textstyle \frac 1 3 + t)(-1) + b (\textstyle \frac 1 3 + t)(-1) + b (\textstyle \frac 2 3 -t)(\textstyle \frac 1 2 ) + (\textstyle \frac 2 3 +c)(\textstyle \frac 2 3 - t)(-\textstyle \frac 1 2)

wegen  u_2 ((E,E),(P)) = u_2((A,E),(P))= -1 \, und  u_2((E,A),(M))= \textstyle \frac 1 2 = -u_2((A,E),(M))\,. Wir erhalten daher:

 u_2(\sigma_1(v),\sigma_2(t)) = -(\textstyle \frac 1 3 + t)(\textstyle \frac 1 3 +a+b ) + (\textstyle \frac 2 3 -t)(\textstyle \frac 1 2 b - \textstyle \frac 1 2 (\textstyle \frac 2 3 +c)) = -\textstyle \frac 1 3 - \textstyle \frac 1 3(a+b) - t(a+ \textstyle \frac 2 3 b - \textstyle \frac 1 2 c) \,.

Im Falle 2a+3b-c= 0 =a+b+c+d, also  a+ \textstyle \frac 2 3 b - \textstyle \frac 1 2 c=0 ist

 u_2(\sigma_1(v),\sigma_2^*) = u_2(\sigma_1(v),\sigma_2(0)) = -\textstyle \frac 1 3 - \textstyle \frac 1 3(a+b)=  u_2(\sigma_1(v),\sigma_2(t))

für alle  t\in \mathbb R\,,\, -\textstyle \frac 1 3\leq t \leq \textstyle \frac 2 3\,. Setzen wir jetzt  v_m :=(-\textstyle\frac 2 m, \textstyle\frac 1 m,-\textstyle\frac 1 m,\textstyle\frac 2 m )\,, so erhalten wir die Folge

 \sigma_1^m := \sigma_1(v_m) = (\textstyle\frac 1 3 -\textstyle\frac 2 m)(E.E) + \textstyle\frac 1 m (A,E) + (\textstyle\frac 2 3 - \textstyle\frac 1 m)(E,A) + \textstyle\frac 2 m (A,A)

von voll gemischten Strategien  \sigma_1^m mit  \sigma_1^m \to \sigma_1^*\,. Es folgt  u_2(\sigma_1^m,\sigma_2^*) \geq  u_2(\sigma_1^m,\sigma_2(t)) für alle  m\in \mathbb R\,,\,,m>6\,, und für alle  t\,,\, -\textstyle \frac 1 3 \leq t \leq \textstyle \frac 2 3 \,, und daher auch

 u_2(\sigma_1^m,\sigma_2^*) \geq  u_2(\sigma_1^m,\sigma_2)

für beliebige gemischte Strategien σ2, weil jede solche Strategie die Form σ2(t) hat. Also ist auch 2. erfüllt. Damit ist gezeigt, dass das Nash-Gleichgewicht ein perfektes Gleichgewicht ist.

Das Spiel als Bayes-Spiel

Meine Werkzeuge