Existenz eines symmetrischen Nash-Gleichgewichtes in symmetrischen 2- Personenspielen: Zwei Beweise

Aus Wikiludia

Version vom 12. Dezember 2008, 22:07 Uhr von Schotten (Diskussion | Beiträge)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Satz.
Jedes symmetrische 2-Personenspiel mit endlich vielen Strategien S hat ein symmetrisches Nash-Gleichgewicht in gemischten Strategien, d.h. ein Nash-Gleichgewicht $s^* = (p,p) \in \Delta \times \Delta$ .

Beweis mit dem Satz von Kakutani.

Wir betrachten ein endliches symmetrisches 2-Personen-Spiel in Normalform, d.h. ein Spiel der Form G=(M,s,u) mit

M={1,2}
$S_1 = S_2 = S_0 =\{s_1, \ldots,s_m\}$ , $S = S_0 \times S_0$
$u 1 (t 1, t 2) = u 2 (t 2, t 1) = u (t 1, t 2)$ mit $t_1,t_2 \in S_0$ .

Die Menge der gemischten Strategien sei

$\Delta:= \left\{ \sum_{s\in S_0} p_s \cdot s \ | p_s \geq 0, \sum_{s\in S_0} p_s = 1\right\}$ .

Nun definieren wir für jede reine Strategie $s \in S_0$ eine eine stetige Funktion

$g_s: \Delta \rightarrow \mathbb R ,\ \ \ g_s( \sigma)= max \{ 0; u_1(s, \sigma ) - u ( \sigma , \sigma) \}$ .

Ausserdem definieren wir $y_s:\Delta \longrightarrow [0,1]$ , sodass für eine gemischte Strategie

$\sigma = \sum_{s\in S_0} p_s \cdot s$

gilt

$y_s( \sigma ) = \frac{p_s+g_s ( \sigma) }{1+\sum_{t \in S} g_t(\sigma) }$

Weiter sei

$y:\ \Delta \longrightarrow \Delta,\ \ \sigma \mapsto \sum_{s\in S_0}y_s(\sigma)\cdot s$

eine Abbildung der Menge gemischten Strategien in sich selbst, denn es gilt:

$\sum_{s \in S_0} \frac{p_s+g_s( \sigma)}{1+ \sum_{t \in S_0}g_t( \sigma)} = 1$ .

Schritt 1: Fixpunkte von y sind symmetrische Nash-Gleichgewichte in gemischten Strategien
Es muss offensichtlich eine reine Strategie $w \in S_0$ geben, für die

$u(w,\sigma)\geq u(\sigma ,\sigma)$ .

Für dieses w gilt dann

g w (σ) = 0

.

Nehmen wir also an, dass $y (σ) = σ$ , d.h.

$y_s(\sigma)=p_s\ \ \forall s\in S_0$ .

Aus $u(w,\sigma)\geq u(\sigma ,\sigma)$ folgt aber, dass $g w (σ) = 0$ , also

$y_w(\sigma)=\frac{p_w}{1+\sum_{t \in S}g_t(\sigma)}$ .

Es folgt, dass

$\sum_{t \in S}g_t(\sigma)=0$ ,

d.h.

$g_s(\sigma)=0\ \ \forall s \in S_0$ .

Somit ist für Spieler 1 $σ$ beste Antwort auf die Strategie $σ$ von Spieler 1. Analog folgt, dass für Spieler 2 $σ$ beste Antwort auf die Strategie $σ$ von Spieler 2 ist.
$\Rightarrow (\sigma , \sigma) \in \Delta$ ist ein symmertisches Nash-Gleichgewicht in gemischten Strategien.

Umgekehrt folgt auch, wenn $(σ,σ)$ ein Nash-Gleichgewicht ist, dass alle $g s$ verschwinden, also $(σ,σ)$ ein Fixpunkt von y ist.

Schritt 2: y besitzt mindestens einen Fixpunkt
Es gilt:

$Δ$ ist eine kompakte und konvexe Menge.
Wir definieren $y':\ \Delta \rightarrow \mathcal P (\Delta)$ , also eine Korrespondenz $y':\Delta \rightarrow \Delta$ , mit $y'(σ) = {y (σ)}$ $\forall \sigma \in \Delta$ .
Dann ist $y'$ eine abgeschlossene Korrespondenz, denn für je zwei konvergente Folgen $x_k \rightarrow x$ in $Δ$ , $y_k \rightarrow y$ in $Δ$ für $k \rightarrow \infty$ mit $y_k \in f(x_k)$ gilt: $y \in f(x)$ , da y mit $g s$ und $y s$ ( $s \in S$ ) stetig ist.

$\Rightarrow$ Somit ist der Fixpunktsatz von Kakutani anwendbar:

$y'$ besitzt also einen Fixpunkt und somit auch y nach Definition von $y'$ .

$\Rightarrow$ Mit Schritt 1 folgt somit die Aussage des Satzes.

Zweiter Beweis.

Folgendes Theorem liefert die Existenz eines Nash-Gleichgewichtes in einem symmetrischen 2-Personenspiel mit endlich vielen Strategien:

Theorem von Nash.
Ein endliches Normalformenspiel hat immer ein Nash-Gleichgewicht in gemischten Strategien.

Sei nun $(p 1, p 2)$ ein Nash-Gleichgewicht des symmetrischen Spiels.

1.Fall: $p 1 = p 2$

Dann ist das Nash-Gleichgewicht bereits symmetrisch und man ist fertig.

2.Fall: $p_1 \ne p_2$

Dann ist auch $(p 2, p 1)$ ein Nash-Gleichgewicht des symmetrischen Spiels:

$u_1(p_2,p_1)=u_2(p_1,p_2) \ge u_2(p_1,s_1)=u_1(s_1,p_1) \forall s_1 \in S$ $u_2(p_2,p_1)=u_1(p_1,p_2) \ge u_1(s_2,p_2)=u_2(p_2,s_2) \forall s_2 \in S$

Aus diesen beiden Gleichgewichten kann man ein symmetrisches Gleichgewicht konstruieren:

$s* = (\frac{1}{2}(p_1+p_2),\frac{1}{2}(p_1+p_2))$

Dass s* ein Nash-Gleichgewicht ist, zeigt man unter der Annahme, dass Spieler 1 davon abweicht und die gemischte Strategie $\frac{1}{2}u_1(p_1+q)$ wählt, wobei q so ist, dass $\frac{1}{2}u_1(p_1+q)$ die Eigenschaften einer gemischten Strategie erfüllt.

$u_1(\frac{1}{2}(p_1+q),\frac{1}{2}(p_1+p_2))$ $= \frac{1}{4}u_1((p_1),(p_1)) + \frac{1}{4}u_1((p_1),(p_2)) + \frac{1}{4}u_1((q),(p_1))+\frac{1}{4}u_1((q),(p_2))$ $\le \frac{1}{4}u_1((p_1),(p_1)) + \frac{1}{4}u_1((p_1),(p_2)) + \frac{1}{4}u_1((p_1),(p_1))+\frac{1}{4}u_1((p_1),(p_2))$ $= (\frac{1}{2}(p_1+p_2),\frac{1}{2}(p_1+p_2)) = s*$

Aufgrund der Symmetrie der Auszahlung ergibt sich daraus, dass es sich für keinen der beiden Spieler lohnt von der $\frac{1}{2}u_1(p_1+q)$ Strategie abzuweichen, wenn der andere diese wählt. Somit folgt, dass $s* = (\frac{1}{2}(p_1+p_2),\frac{1}{2}(p_1+p_2))$ ein Nash-Gleichgewicht ist.

Existenz eines symmetrischen Nash-Gleichgewichtes in symmetrischen 2- Personenspielen: Zwei Beweise

Ansichten

Meine Werkzeuge

Navigation

Suche

Werkzeuge