Matching Pennies

Aus Wikiludia
Wechseln zu: Navigation, Suche

Bei Matching Pennies handelt es sich um ein einfaches Beispiel für ein Spiel mit endlichem Strategieraum, in dem kein Nash - Gleichgewicht in reinen Strategien existiert. Das Spiel gehört zu den Nullsummenspielen für zwei Personen.

Inhaltsverzeichnis

Spielszenario

Man stelle sich folgende Situation vor:

Um zu entscheiden, wer die Hausarbeit erledigen muss, spielen zwei Kinder ein Spiel. Zuerst entscheiden sie, wer durch die Strategie "gleich" -Spieler 1 (Zeilenspieler)- und wer durch die Vorgehensweise "verschieden" -Spieler 2 (Spaltenspieler)- repräsentiert wird. Anschließend nimmt jedes von beiden einen Cent - mit Kopf oder Zahl nach oben - so in die Hand, dass das andere Kind dies nicht sehen kann. Nun decken sie gleichzeitig auf:

Falls die Oberseiten zusammenpassen (entweder beide Kopf oder beide Zahl) hat Spieler 1 gewonnen und erhält beide Cents. Passen sie nicht (einmal Kopf, einmal Zahl), so siegt die Strategie "verschieden", d.h. Spieler 2 muss an seinen Gegenspieler einen Cent zahlen.

Mathematische Beschreibung des Modells

Das Nullsummenspiel Matching Pennies in Normalform besteht aus

  • der Spielermenge M = {1,2}, wobei die Ziffern "1" bzw."2" nach obigem Beispiel Kind 1 bzw. Kind 2 darstellen sollen,
  • der Strategiemenge S1 = S2 = {K,Z} (K: Kopf, Z: Zahl) sowie
  • den Nutzenfunktionen - u_i: S_1 \times S_2 \rightarrow \mathbb R (i = 1,2) - der beiden Spieler:
    • Nutzenfunktion von Spieler 1: u1(s1,s2) = 1, wenn s1 = s2 (d.h. (Z,Z) oder (K,K))) bzw. u1(s1,s2) = - 1, wenn s_1\ne s_2 (d.h. (K,Z) oder (Z,K)),
    • Nutzenfunktion von Spieler 2: u2(s1,s2) = - 1, wenn s1 = s2 bzw. u2(s1,s2) = 1, wenn s_1\ne s_2.


Mit Hilfe dieser Auszahlungsmatrix lässt sich das Spiel veranschaulichen:

Kopf Zahl
Kopf 1, -1 -1, 1
Zahl -1, 1 1, -1

\Rightarrow Es ergibt sich folgende Beobachtung: u1 = − u2. Die beiden Nutzenfunktionen verhalten sich also komplementär zueinander (= Bedingung für Nullsummenspiele).


Satz: Existenz und Eindeutigkeit des Nash - Gleichgewichts

  • Das Spiel Matching Pennies besitzt kein Nash - Gleichgewicht in reinen Strategien.
  • Stattdessen existiert nur ein Nash - Gleichgewicht in gemischten Strategien ( s* =(\textstyle \frac{1}{2}, \textstyle \frac{1}{2})) und zwar die Strategiekombination, in der sich beide Spieler mit Wahrscheinlichkeit \textstyle\frac {1} {2} für Kopf und mit Wahrscheinlichkeit \textstyle\frac {1} {2} für Zahl entscheiden.

Beweis

Sei \sigma_1 \in \Delta S_1 eine durch p gegebene gemischte Strategie für Spieler 1:

\sigma_1 = pA+(1-p)Z, \, p\in[0,1]

und \sigma_2 \in \Delta S_2 durch q gegebene gemischte Strategie für Spieler 2:

\sigma_2 = qA+(1-q)Z, q\in[0,1]


Beste Antwort p auf q?


 u_1(\sigma_1,\sigma_2) = u_1(pA+(1-p)Z \ , \ qA+(1-q)Z) =

= pqu1(A,A) + p(1 − q)u1(A,Z) + (1 − p)qu1(Z,A) + (1 − p)(1 − q)u1(Z,Z) =
= pqp(1 − q) − q(1 − p) + (1 − p)(1 − q) = (4q − 2)p + 1 − 2q

Und da u2 = − u1 gilt:

u2 = (2 − 4q)p − 1 + 2q

Sei q vorgegeben: Fallunterscheidung nach q:

q > {1 \over 2} \Rightarrow p = 1 ist beste Antwort. Grund: Der erste Klammerterm (4q − 2) ist positiv, d.h. die erwartete Auszahlung stellt also eine steigende Funktion von p dar.

q = {1 \over 2} \Rightarrow p \in [0,1] ist beste Antwort. Grund: Der Erwartungsnutzen (erwartete Auszahlung) ist null, d.h. der Spieler ist indifferent bezüglich der zu wählenden Wahrscheinlichkeitsverteilung.

q < {1 \over 2} \Rightarrow p = 0 ist beste Antwort. Grund: Der erste Klammerterm ist negativ, d.h. die erwartete Auszahlung stellt eine fallende Funktion von p dar.


Sei nun p vorgegeben:

p > {1 \over 2} \Rightarrow q = 0 ist beste Antwort. Grund jeweils analog (wegen der komplementären Nutzenfunktionen genau umgekehrte Entscheidungen)

p = {1 \over 2} \Rightarrow q \in [0,1] ist beste Antwort

p < {1 \over 2} \Rightarrow q = 1 ist beste Antwort

Die Strategiekombination (\textstyle \frac 1 2 , \textstyle \frac 1 2) ist also Nash-Gleichgewicht (in gemischten Strategien), weil \textstyle \frac 1 2 jeweils beste Antwort auf  \textstyle \frac 1 2 ist (s.o.).
Sei jetzt (p*,q*) ein beliebiges Nash - Gleichgewicht. Dann lässt sich daraus folgern, dass q^* > \textstyle\frac{1}{2} nicht gelten kann, weil p = 1 die einzige beste Antwort auf q^*> \textstyle \frac{1}{2} ist (s.o.), also p* = 1 gelten müsste, und weil p* = 1 als die einzige beste Antwort q* = 0 hätte. Ebenso wenig ist q^* < \textstyle \frac{1}{2} möglich. Also bleiben q^* = \textstyle \frac{1}{2} und analog p^* = \textstyle \frac{1}{2} übrig, so dass man s^* = ( \textstyle \frac{1} {2}, \textstyle \frac{1} {2}) als einziges Nash - Gleichgewicht erhält.

Damit ist der Satz bewiesen.


Andere Interpretationsmöglichkeiten des Spiels

"Fingerschnippen"

Die strategische Situation von Matching Pennies entspricht der des Spieles "Fingerschnippen" (engl.: "odds and evens"[1] oder "Morra" [2] - wie im Allgemeinen das Spiel im Mittelmeerraum bezeichnet wird):


1F 2F
1F 1, -1 -1, 1
2F -1, 1 1, -1


Bei diesem Spiel strecken zwei Spieler gleichzeitig ihre Hand aus und zeigen dabei einen oder zwei Finger. Dabei wird zwischen gerader und ungerader Anzahl der Finger unterschieden. Beide müssen sich jedoch zuvor auf ihre Strategie einigen: Spieler 1 siegt bei gerader Summe, Spieler 2 dagegen bei ungerader. Es ergeben sich also folgende Strategiekombinationen: {(F,F), (F,2F), (2F,F), (2F,2F)}.

Ersetzt man die Ziffer "-1" durch "0" - während der eine Spieler also 1 Einheit hinzugewinnt, behält sein Gegenspieler seine ursprüngliche Geldsumme - , so erhält man eine neue Variante des Spiels.

Elfmeterschießen

Auch das Modell vom Strafstoß beim Fußball lässt sich sehr gut mit obigem Spiel vergleichen:


Links Rechts
Links 1, -1 -1, 1
Rechts -1, 1 1, -1


Im Falle eines Strafstoßes haben der Elfmeterschütze (Spieler 1) und der Torwart (Spieler 2) die Strategien (Links, Links), (Links, Rechts),(Rechts, Links) und (Rechts, Rechts) zur Auswahl. Spieler 1 versucht den Ball so zu schießen, dass Spieler 2 keine Chance zur Abwehr des Balles hat und er somit für seine Mannschaft ein Tor erzielt. Dabei wird allerdings nur die Schussrichtung "Links" bzw. "Rechts" berücksichtigt, d.h. ein Schuss ins linke obere Eck beispielsweise ist gleichbedeutend mit einem Schuss ins linke untere Eck. Betrachtet man obiges Modell aus Sicht des Torwarts, so stellt man fest, dass dieser ebenfalls nur zwischen der rechten und der linken Torhälfte unterscheidet. Wird der Ball also z.B. in Richtung der linken Torhälfte geschossen, so versucht der Torwart diesen zum Nutzen seiner Mannschaft zu fangen, bevor er die Torlinie überquert.

Entscheiden sich beide Spieler nun vor dem Elfmeterschießen für die gleiche Seite des Tores {(Rechts, Rechts), (Links, Links)}, so gewinnt - wie man obiger Auszahlungsmatrix entnehmen kann - der Schütze, andernfalls ist der Torwart der Sieger.

Meine Werkzeuge