Spieletheorie - gemischte Strategien - Nash

26.07.2011, 21:40

AlbertH

Spieletheorie - gemischte Strategien - Nash

Hi

im Fach "Einführung in die Spieletheorie" in meinem VWL-Studium habe ich ein Problem zum Nash-Gleichgewicht in gemischten Strategien: Folgendes 2-Spieler Spiel:

$\begin{eqnarray*} \begin{vmatrix} & L & C& R \\ T & 0,4 & 4,0 & 5,3 \\ M & 4,0 & 0,4 & 5,3 \\ B& 3,5 & 3,5 & 6,6 \end{vmatrix} \end{eqnarray*}$

Die Zahl vor dem Komma ist der Pay-off von Spieler 1 (Strategien T, M, B), die dahinter von Spieler 2 (Strategien L, C, R). Die Aufgabe lautet: "Zeigen Sie, dass das Spiel kein Nash-Gleichgewicht in gemischten Strategien (GSNE) hat."

Die Musterlösung untesucht nun drei Szenarien:

1. Spieler 2 mischt positiv über alle drei Strategien -> Spieler 1 kann ohne Widerspruch nicht indifferent zwischen seinen Strategien werden, also kein NE möglich.

2. Spieler 1 mischt jeweils nur über zwei Strategien positiv und spielt eine Strategie gar nicht, dh. es gibt drei Fälle (1. T,B werden gespielt, M nicht. 2. M,B werden gespielt, T nicht 3. T, M werden gespielt, B nicht) -> in den ersten zwei Fällen lässt sich das entstande 2x3 Spiel durch dominante Strategien lösen. Im dritten gibt es zwar ein NE, der Payoff ist aber geringer als bei der weggelassenen Strategie B.

3. nur ein Spieler mischt, der andere spielt eine reine Strategie -> hier gäbe es kein GSNE, da gilt: "Jede reine Strategie hat eine reine Strategie als beste Antwort. Kein GSNE in so einer Situation."

Den ersten Fall verstehe ich: Egal wie Spieler 2 mischt, Spieler 1 wird immer eine seiner drei Strategien bevorzugen.

Den zweiten Fall kann ich nachvollziehn. Ich wäre aber selbst nicht auf die Idee gekommen, jeweils eine Strategie wegzulassen und dann erneut zu prüfen, ob es ein GSNE gibt.

Die Antwort im dritten Fall schließlich verstehe ich nicht, höchstens so: Der Spieler, der mischt, hat eigentlich gar keine Motivation zu mischen, da er genauso gut eine reine Strategie als beste Antwort spielen kann. Aber, dass eine gemischte Strategie nur über solche reinen Strategien positiv mischt, die beste Antworten sind, ist doch gerade die Voraussetzung dafür, dass die gem. Strat. selbst eine beste Antwort ist. (-sinngemäß aus meinem Lehrbuch)

Bitte klärt mich auf. Lieben Dank!

AlbertH

26.07.2011, 22:14

Dopap

Auf diesen Beitrag antworten »

das Matrix-Spiel habe ich so nicht verstanden.

Ist das ein Nullsummenspiel?

Kann man die Elemente $\begin{eqnarray*} a_{ik} \end{eqnarray*}$ nicht als Gewinn für Spieler 1 schreiben?

oder sind die Elemente $\begin{eqnarray*} a_{ik} \end{eqnarray*}$ 2-Tupel, sodass ein Bimatrixspiel vorliegt?

27.07.2011, 10:25

AlbertH

Auf diesen Beitrag antworten »

Hi,

es ist ein denkbar einfaches Spiel: Die Spieler wählen simultan einmal eine Strategie und kennen dabei die Pay-off Tabelle. Bsp.: S1 wählt T, S2 wählt C -> S1 bekommt 4, S2 0.

AlbertH

27.07.2011, 21:06

Dopap

Auf diesen Beitrag antworten »

ja, alles klar, das Spiel ist

Ein Bimatrixspiel, und somit ein Nichtnullsummenspiel

Darf man annehmen, dass es auch nicht kooperativ ist, d.h. die Spieler können sich nicht absprechen und "gemeinsame Sache" machen ?

Die Spielmatrix mit den Elementen $\begin{eqnarray*} (a_{ij},b_{ij}) \end{eqnarray*}$ lässt sich auch so auffassen, dass die Elemente $\begin{eqnarray*} a_{ij} \end{eqnarray*}$ eine eigene Matrix $\begin{eqnarray*} A \end{eqnarray*}$ bilden, ebenso die Elemente $\begin{eqnarray*} b_{ij} \end{eqnarray*}$ die Auszahlungsmatrix $\begin{eqnarray*} B \end{eqnarray*}$ für den Spieler 2.

kurz: Wählt 1 i und 2 j , so erhält 1 den Betrag $\begin{eqnarray*} a_{ij} \end{eqnarray*}$ und Spieler 2 den Betrag $\begin{eqnarray*} b_{ij} \end{eqnarray*}$
Das Spiel heißt nun Bimatrixspiel $\begin{eqnarray*} (A,B) \end{eqnarray*}$

Ein Paar $\begin{eqnarray*} (x^*,y^*) \end{eqnarray*}$ gemischter Strategien ist im Gleichgewicht, wenn für alle gemischten Strategien $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ gilt

$\begin{eqnarray*} x^TAy^* \leq x^{*T}Ay^* \end{eqnarray*}$

$\begin{eqnarray*} x^{*T}By \leq x^{*T}By^* \end{eqnarray*}$

Jetzt gibt es aber den Satz:

Jedes ( nichtkooperative ) Bimatrixspiel besitzt mindestens einen Gleichgewichtspunkt.
Das ist aber nur ein Existenzsatz.

-----------------------------------------------------------
(a)
Bei Nullsummenspielen ( Matrixspiel ) gilt, dass Gleichgewichtspaare austauschbar und äquivalent sind in dem Sinne, Dass für ein Gleichgewichtspaar (x,y) und (x',y') auch die Paare (x,y') und (x',y) im Gleichgewicht und sogar

$\begin{eqnarray*} x^TAy=x^{'T}Ay' \end{eqnarray*}$ erfüllen.

Das bedeutet effektiv, dass die Zugehörigkeit eines Vektors x zu einem Gleichgewichtspaar (x,y) eine Eigenschaft des Vektors allein ( unabhängig von y ) ist.

Ein optimales gemischtes Strategiepaar kann man als Gleichgewichtspaar im NASH-Sinne nennen.
-------------------------------------------

In der Aufgabe ist meiner Meinung nach zu zeigen, dass jedes Gleichgewichtspaar ( auch jedes der 3 Szenarien ) kein Gleichgewichtspaar imNASH-Sinne ist, also (a) nicht erfüllt.

29.07.2011, 23:06

AlbertH

Auf diesen Beitrag antworten »

Hi Dopap,

entschuldige bitte die späte Antwort: Ich habe die Klausur verschoben, da krank.
Ja, das Spiel ist nicht-kooperativ. Ich habe nicht verstanden, wie ich die Theorie in deiner Antwort anwenden kann, fürchte auch, dass das in meinem Fall dem Maschinengewehr auf Spatzen gleich käme.
Hast du eine Idee, wie die Musterlösung für das dritte Szenario zu verstehen ist:

Zitat:

Jede reine Strategie hat eine reine Strategie als beste Antwort. Kein GSNE in so einer Situation."

Ich dachte bisher, dieser Umstand sei generell eine notwendige Bed. für jedes Nash-GG in gem. Strategien?

AlbertH

30.07.2011, 01:53

Dopap

Auf diesen Beitrag antworten »

das mit den Kanonen könnte stimmen Augenzwinkern

Ihr sollt also in VWL an einem(?) Beispiel die angesprochenen Begriffe nachvollziehen können.

Zitat:

Original von AlbertH
...Jede reine Strategie hat eine reine Strategie als beste Antwort (**)...

obigen Satz verstehe ich als Feststellung zum konkreten Spiel, was sich auch leicht Nachprüfen lässt.

Zitat:

..Kein GSNE in so einer Situation.

Demnach kein Gleichgewichtspaar einer Reinen mit einer gemischten Strategie ( im konkreten Spiel ) vorhanden.

Zitat:

Ich dachte bisher, dieser Umstand (**) sei generell eine notwendige Bed. für jedes Nash-GG in gem. Strategien?

eher das Gegenteil. Wenn z.B. Spieler zwei 2 gleichwertige Möglichkeiten bezüglich seiner Auszahlung hätte, dann könnte er auch auf den Beiden eine ( beliebige ) gemischte Strategie wählen.
Dadurch steigt evtl. die Möglichkeit, ein Gleichgewichtspaar an gemischten Strategien dingfest zu machen.

Zum Schluss noch die Bemerkung - und ohne Rechnung - dass das Strategienpaar (0,0,B) und (0,0,R) aus reinen Strategien ein Gleichgewichtspaar ( aber kein GSNE ) bilden.

30.07.2011, 14:28

AlbertH

Auf diesen Beitrag antworten »

Zitat:

Jede reine Strategie hat eine reine Strategie als beste Antwort. Kein GSNE in so einer Situation."

Dopap, mir leuchtet nicht ein, warum aus dieser Festellung das Urteil folgt, es gäbe im obigen Spiel kein NE in gem. Strat? In meinen Augen ist diese Feststellung nichtssagend, da universal gültig. Schließlich gibt es in jedem Spiel auf eine reine Strategie eine reine Strategie als beste Antwort. (Natürlich gibt es Spiele, in denen eine gemischte Strategie absolut besser als eine reine Strategie ist. Nichts desto weniger gibt es auch unter den reinen Antworten immer eine beste.)

Wenn die Feststellung also gemeint ist, dass die reine beste Antwort hier immer besser als eine gemischte beste Antwort ist, dann ist sie eine bloße Behauptung, deren Begründung mir nicht ins Auge springt. Verstehst du meinen Punkt?

Für mich wird erst ein Hut daraus, wenn die Antwort heißen sollte: "Jede reine Strategie ist eine beste Antwort auf eine (bestimmte andere) reine Strategie." Diese Situation ist hier gegeben. Doch auch jetzt wieder die Frage, warum dann folgt, dass es kein gemischtes NE gibt?
Idee: Es gibt für keinen Spieler die Motivation zu mischen. (Vergiss, was ich in meinem 1. Posting zu dieser Idee geschrieben habe)

Docoylinder

30.07.2011, 18:11

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von AlbertH
...Für mich wird erst ein Hut daraus, wenn die Antwort heißen sollte: "Jede reine Strategie ist eine beste Antwort auf eine (bestimmte andere) reine Strategie." Diese Situation ist hier gegeben. Doch auch jetzt wieder die Frage, warum dann folgt, dass es kein gemischtes NE gibt?
Idee: Es gibt für keinen Spieler die Motivation zu mischen. (Vergiss, was ich in meinem 1. Posting zu dieser Idee geschrieben habe)

Da muss ich zustimmen.
Die getroffene Aussage, dass dann kein GSNE existiert, betrifft nur das Beispiel, und wird nur durch deine Argumentation: Es gibt für keinen Spieler die Motivation zu mischen. gestüzt.
Ein Gegenbeispiel könnte hier helfen:

Betrachten wir das Bimatrixspiel

$\begin{eqnarray*} \begin{pmatrix} (4,1) & (0,0) \\ (0,0) & (1,4) \end{pmatrix} \end{eqnarray*}$

Man sieht, dass die reinen Strategien x=(1,0) und y=(1,0) ein Gleichgewichtspaar bilden, ebenso die Strategien x'=(0,1) und y'=(1,0).
Dagegen sind die Paare (x,y') und (x',y) nicht im Gleichgewicht.
Darüberhinaus sind die Auszahlungen für beide Gleichgewichtspaare (x,y) und (x',y') sogar verschieden.
S1 ( Spieler 1 ) wird (x,y) vorziehen und S2 (x',y')
Es ist also nicht klar, ob die beiden Gleichgewichtspaare vollständig stabil sind.
[ und du könntest sagen: es gibt schon ein klein wenig Motivation zu wechseln ]
Auch wenn S1 weiss, dass S2 die reine Strategie y' spielen will, kann er auf x beharren in der Hoffnung, S2 zu y zu bewegen.

Die Folge der nicht sicheren Stabilität ist nun:

Es gibt ein Gleichgewichtspaar gemischter Strategien:

für S1 : x'' = (0.8 , 0.2 )
für S2 : y'' = (0.2 , 0.8 )

und das ist ein Gegenbeispiel.

Demnach gilt: die Existenz eines Gleichgewichtspaares an reinen Strategien ist im Regelfall kein Grund für die Nichtexistenz eines GSNE.

30.07.2011, 23:48

Dopap

Auf diesen Beitrag antworten »

Spieltheorie II
dass die Spieltheorie nicht nur mathematische Aspekte, sondern auch in das Charakterliche hineinreicht, dazu ein Beispiel:

Das Dilemma der Gefangenen.

$\begin{eqnarray*} \begin{pmatrix} (-5,-5) & (0,-10) \\ (-10,0) & (-1,-1) \end{pmatrix} \end{eqnarray*}$

2 westliche Gefangene des Taliban in verschiedenen Zellen ( ohne Kooperation ) können sich für jeweils Stategie 1 oder 2 entscheiden.
Dieses "Spiel" wird nur einmal gespielt! Die negativen Zahlen geben die Jahre an, die der jeweilige Gefangene noch abzusitzen hat.

Offenbar dominiert die 2. Zeile die Erste bzw. die 2. Spalte die Erste ( sofern wir hier den Begriff der Dominanz aus den Nullsummenspielen sinngemäss übernehmen )

Deshalb:
... sagt die Vernunft, Engel

: dass beide Spieler Strategie 2 spielen und somit Beide noch ein Jahr zu sitzen haben.
Wenn man sich das länger anschaut ( man hat ja soviel Zeit in der langen Nacht ) sticht doch irgendwann der Teufel

zu, doch auf Strategie 1 zu wechseln, was dem Strategiewechser sofortige Freiheit und den Anderen 10 harte Jahre aufbürden würde.
.... Nun, dieselben Gedanken beschleichen irgendwann aber auch den anderen Spieler ...
womit wir letztlich bei 5 Jahren TalibanKnast für jeden der Beiden landen.

ist das eine "Lösung" des "Spiels" ? oder doch etwa (-1,-1)?

Ich möchte es jedem selbst überlassen, was er in einer solchen fatalen Spielsituation spielen würde...
-----------------------------------
p.s. Ich würde Strategie 2 nur wählen, wenn ich wüsste, dass mein Co-Gefangener Mathematiker wäre Augenzwinkern

31.07.2011, 10:33

Huggy

Auf diesen Beitrag antworten »

RE: Spieltheorie II
Von der Theorie der Spieltheorie habe ich keine Ahnung. Das hat mich noch nie gehindert, konkrete Spiele zu analysieren. Also habe ich mich an diesem Spiel versucht und den Eindruck bekommen, dass der in der Aufgabe geforderte Nachweis sich sehr geradlinig und ohne großen Aufwand erbringen lässt.

Bei Matrixspielen ist das Ergebnis (payoff) eines Spielers eine lineare Funktion seiner Strategie und der zulässige Bereich für die Strategien ist ein konvexer Polyeder im $\begin{eqnarray*} \mathbb R^n \end{eqnarray*}$ . Die optimalen Strategien lassen sich deshalb mit den Mitteln der linearen Optimierung bestimmen. Nun besagt der Ausgangssatz der linearen Optimierung, dass sich das Maximum/Minimum der Zielfunktion immer an einer Ecke des zulässigen Bereichs befindet. Die Ecken sind hier aber gerade die reinen Strategien.

Damit eine gemischte Strategie optimal sein kann, müssen 2 benachbarte Ecken das gleiche Ergebnis haben und die anderen Ecken dürfen kein besseres Ergebnis liefern. Dann hat die gesamte Verbindungsstrecke zwischen den beiden Ecken ebenfalls das optimale Ergebnis und abgesehen von den Enden der Strecke sind das gemischte Strategien.

Man kann also erst mal untersuchen, unter welchen Bedingungen 2 reine Strategien für einen Spieler das gleiche Ergebnis haben. Dann prüft man, ob eine der weiteren reinen Strategien ein besseres Ergebnis liefert. Falls nein, ist nur noch zu prüfen, ob die erhaltenen Bedingungen mit einer optimalen Strategie für den anderen Spieler verträglich sind. Und die muss dann ebenfalls an einer Ecke, also mit einer reinen Strategie, erreichbar sein.

Die Strategien der beiden Spieler seien a1, a2, a3 und b1, b2, b3. Wegen

$\begin{eqnarray*} a_1+a_2+a_3=b_1+b_2+b_3=1 \end{eqnarray*}$

genügen a1, a2 und b1, b2 zur Charakterisierung der Strategien. Es ist dann

$\begin{eqnarray*} a_3=1-a_1-a_2 \quad b_3=1-b_1-b_2 \end{eqnarray*}$

Die zulässigen Bereiche der Strategien sind gegeben durch:

$\begin{eqnarray*} 0 \leq a_1, a_2 \leq 1 \quad a_1+a_2 \leq 1 \end{eqnarray*}$

$\begin{eqnarray*} 0 \leq b_1, b_2 \leq 1 \quad b_1+b_2 \leq 1 \end{eqnarray*}$

Das ist jeweils ein Dreieck mit den Ecken (0, 0), (1, 0), (0, 1). Die Ergebnisse für Spieler 1 bei reinen Strategien von ihm sind:

$\begin{eqnarray*} E(1, 0, 0)=5-5b_1-b_2 \end{eqnarray*}$

$\begin{eqnarray*} E(0, 1, 0)=5-b_1-5b_2 \end{eqnarray*}$

$\begin{eqnarray*} E(0, 0, 1) = 6-3b_1-3b_2 \end{eqnarray*}$

Die Forderung nach gleichem Ergebnis für 2 reine Strategien ergibt:

$\begin{eqnarray*} a) \quad E(1, 0, 0)=E(0, 1, 0) \Rightarrow b_2 = b_1 \end{eqnarray*}$

Dann ist $\begin{eqnarray*} E(1, 0, 0)=E(0, 1, 0)=5-6b_1 \end{eqnarray*}$ . Es ist aber $\begin{eqnarray*} E(0, 0, 1) =6- 6b_1 \end{eqnarray*}$ besser.

$\begin{eqnarray*} b) \quad E(1, 0, 0)=E(0, 0, 1) \Rightarrow b_2=b_1+\frac{1}{2} \end{eqnarray*}$

Diesmal liefert die dritte Ecke kein besseres Ergebnis. Aber diese Bedingung ist nicht kompatibel mit einer optimalen Strategie für Spieler 2 an einer Ecke des zulässigen Gebiets, denn b1 = 0 ergibt b2= 1/2 und b1 =1 ergibt einen unzulässigen Wert für b2.

Der Fall c) verläuft analog dem Fall b). Schlussfolgerung: Es gibt bei diesem Spiel kein Nash-Gleichgewicht mit gemischten Strategien.

01.08.2011, 23:53

Dopap

Auf diesen Beitrag antworten »

RE: Spieltheorie II

Zitat:

Original von Huggy
Von der Theorie der Spieltheorie habe ich keine Ahnung. Das hat mich noch nie gehindert,(*) konkrete Spiele zu analysieren. Also habe ich mich an diesem Spiel versucht und den Eindruck bekommen, dass der in der Aufgabe geforderte Nachweis sich sehr geradlinig und ohne großen Aufwand erbringen lässt...

(*)Diese Einstellung gefällt mir: immer hart am Ball bleiben und selber denken!

Zitat
Die Theorie des linearen Programmierens besitzt neben der Spieltheorie noch andere Anwendungen ...
G.Owen: Spieltheorie Springer Verlag Berlin 1971 S.67

somit sind deine Ausführungen genau passend und richtig. Freude

----------------------------------------------------------------
Ich hoffe nur, dass "AlbertH" nochmal vorbeischaut

Neue Frage »

Antworten »

Spieletheorie - gemischte Strategien - Nash

Verwandte Themen