SPIELTHEORIE

SPIELTHEORIE
Das Gefangenendilemma (Prisoner’s Dilemma)
2

Zwei Herren (Braun und Blau) haben eine Bank überfallen. Der Sheriff hat sie gefasst, kann
aber nur ein minder schweres Verbrechen nachweisen (unerlaubter Waffenbesitz). Die beiden
Herren sitzen in getrennten Zellen und bekommen unabhängig voneinander den folgenden
Vorschlag vom Sheriff:
 Wenn ihr beide schweigt, werdet ihr nur wegen unerlaubtem Waffenbesitz verurteilt
(Auszahlungen von - 1);
 Wenn nur einer gesteht, wird er freigelassen und der andere bekommt eine lange
Gefängnisstrafe (Auszahlung von - 9);
 Wenn ihr beide gesteht, werdet ihr milde bestraft (Auszahlungen von - 6).
Blau
Braun
NG
G
NG
-1 , -1
-9 , 0
G
0 , -9
-6 , -6
Spieltheorie
Beschreibung eines Spiels
3


Identifizierung der Spieler, die den noch zu definierenden
Spielregeln unterworfen werden.
Spiel = System von Regeln über






zulässige Entscheidungen (Aktionen) der Spieler,
(externe) Zufallsentscheidungen,
Reihenfolge der Entscheidungen,
Informationslage der Spieler,
Ende des Spiels,
Auszahlung als Bewertung einer realisierten Endsituation (in
Abhängigkeit der getroffenen Entscheidungen).
Spieltheorie
Beschreibung eines Spiels
4


Verhaltenshypothese: Jeder Spieler ist bestrebt seine Auszahlung
zu maximieren (in Kenntnis der Regeln des Spiels und dem
Wissen, dass alle Mitspieler diese Regeln kennen).
Common-Knowledge-Annahme: Die Regeln des Spiels sind allen
Spielern bekannt, und alle wissen, dass diese allen bekannt sind.
Ebenso wissen alle, dass allen bekannt ist, dass dies alle wissen,
etc. ad infinitum.
Spieltheorie
Spiele in Normalform
5

Ein Spiel in Normalform ist durch 3 Elemente beschrieben: die Spieler,
ihre Aktions- (bzw. Strategie-) Mengen und ihre Auszahlungsfunktionen.



N = {1, 2, …, n} – Spielermenge,
S = S1 × S2 × … × Sn – die Menge der (zulässigen) Strategiekombinationen
s = (s1, s2, …, sn), wobei Si die Strategiemenge von Spieler i ∈ N darstellt,
u1, u2, …, un – Auszahlungsfunktionen, wobei ui : S → R die
Auszahlungsfunktion von Spieler i ∈ N ist, die seine Auszahlung bei der
Wahl der Strategiekombination s = (s1, s2, …, sn) ∈ S angibt.
Spieltheorie
Spiele in Normalform
6

Bemerkungen:


si ∈ Si heißt auch reine Strategie für Spieler i
s = (s1, s2, …, sn) wird oft zerlegt in



si – Aktion von Spieler i und
s-i = (s1, s2, …, si-1, si+1, …, sn) – Aktionen aller übrigen Spieler außer i, d.h.
si ∈ Si und s-i ∈ S-i = S1 × S2 × … × Si-1 × Si+1 × … × Sn
Gefangenendilemma




N = {Braun, Blau};
SBraun = SBlau = {G, NG};
uBraun(NG, NG) = - 1, uBraun(G, NG) = 0, uBraun(NG, G) = - 9,
uBraun(G, G) = - 6;
uBlau(NG, NG) = - 1, uBlau(G, NG) = - 9, uBlau(NG, G) = 0, uBlau(G, G) = - 6.
Spieltheorie
7
Anderes (Bei)Spiel: Kopf oder Zahl (Matching
Pennies)





Von zwei Spielern hat jeder eine Münze;
Jeder Spieler muss die Münze entweder mit Kopf oder Zahl nach oben auf einen
Tisch legen;
Die Spieler machen dies gleichzeitig;
Zeigen die beiden Münzen die selben Zeichen, gewinnt Spieler 1; zeigen sie
verschiedene, so gewinnt Spieler 2;
Spieler 2
Sie spielen um 10 Euro.
Kopf
Zahl
Spieler 1
Kopf
10 , -10
-10 , 10
Zahl
-10 , 10
10 , -10
Spieltheorie
Anderes (Bei)Spiel: Kopf oder Zahl
8

N = {Spieler 1, Spieler 2};

S1 = S2 = {Kopf, Zahl};


u1(Kopf, Kopf) = u1(Zahl, Zahl) = u2(Kopf, Zahl) = u2(Zahl, Kopf) =
10;
u1(Kopf, Zahl) = u1(Zahl, Kopf) = u2(Kopf, Kopf) = u2(Zahl, Zahl) =
- 10.
Spieltheorie
9
Anderes (Bei)Spiel: Kampf der Geschlechter
(Battle of the Sexes)



Sven und Tina müssen entscheiden, wie sie den heutigen Abend verbringen und haben
die Wahl zwischen “ins Kino gehen” und “ins Stadion gehen”.
Zum Zeitpunkt der Entscheidung befinden sich Sven und Tina in verschiedenen Städten
ohne jede Möglichkeit zu kommunizieren.
Beide wissen das folgende:
 Beide würden gerne den Abend gemeinsam verbringen.
 Sven zieht vor ins Stadion zu gehen.
 Tina zieht vor ins Kino zu gehen.
Sven
Tina
Stadion
Kino
Stadion
2 , 1
0 , 0
Kino
0 , 0
1 , 2
Spieltheorie
Anderes (Bei)Spiel: Kampf der Geschlechter
10

N = {Sven, Tina};

SSven = STina = {Stadion, Kino};

uSven(Stadion, Stadion) = uTina(Kino, Kino) = 2;

uSven(Kino, Kino) = uTina(Stadion, Stadion) = 1;

ui(Stadion, Kino) = ui(Kino, Stadion) = 0 für i ∈ {Sven, Tina}.
Spieltheorie
Letztes (Bei)Spiel: Das Duopol von Cournot
11





Zwei Firmen (1 und 2) produzieren das gleiche Gut. Die entsprechenden
Mengen sind q1 und q2.
Jede Firma wählt ihre Menge, ohne zu wissen, welche Menge die
andere Firma gewählt hat.
Preisabsatzfunktion: P(Q) = a – Q, wobei Q = q1 + q2.
Kostenfunktionen: Ci(qi) = cqi für i ∈ {1, 2}.
Die Normalform:



Spielermenge:
{Firma 1, Firma 2}
Strategiemengen:
S1 = [0, + ∞), S2 = [0, + ∞)
Auszahlungsfunktionen:


u1(q1, q2) = P(Q)q1 – cq1 = q1(a – (q1 + q2) – c)
u2(q1, q2) = P(Q)q2 – cq2 = q2(a – (q1 + q2) – c)
Spieltheorie
Dominante Strategien
12

Eine Strategie si ∈ Si dominiert die Strategie si‘ ∈ Si, für Spieler i, falls


Eine Strategie si* ∈ Si ist dominant für Spieler i, falls


ui(si*, s-i) > ui(si, s-i) für alle si ≠ si* und für alle s-i ∈ S-i.
Eine Strategie si ∈ Si dominiert schwach die Strategie si‘ ∈ Si, für Spieler i, falls



ui(si, s-i) > ui(si‘, s-i) für alle s-i ∈ S-i.
ui(si, s-i) ≥ ui(si‘, s-i) für alle s-i ∈ S-i und
ui(si, s-i) > ui(si‘, s-i) für zumindest ein s-i ∈ S-i.
Eine Strategie si* ∈ Si ist schwach dominant für Spieler i, falls


ui(si*, s-i) ≥ ui(si, s-i) für alle si ≠ si* und für alle s-i ∈ S-i und
ui(si*, s-i) > ui(si, s-i) für einige s-i ∈ S-i.
Spieltheorie
Dominante Strategien
13



Rationalitätsforderung: Benutze nie eine dominierte Strategie!
Vorsicht: Es kann dominierte Strategien geben, ohne dass eine Strategie
selbst (gegen alle andere) dominant ist!
Ein Spiel ist dominant lösbar, wenn jeder Spieler (genau) eine
dominante Strategie besitzt (Gleichgewicht in dominanten Strategien).
Spieltheorie
Das Gefangenendilemma ist dominant lösbar
14


Beweis: Es muss gezeigt werden, dass jeder Spieler eine dominante Strategie hat.
Spieler Braun:



G dominiert NG, da uBraun(G, NG) = 0 > - 1 = uBraun(NG, NG), d.h. falls Blau NG
spielt, ist G besser für Braun als NG, und uBraun(G, G) = - 6 > - 9 = uBraun(NG, G),
d.h. falls Blau G spielt, ist G besser für Braun als NG.
Spieler Blau: G dominiert NG.
Das Gleichgewicht in dominanten Strategien ist (G, G) mit Auszahlungen (- 6, - 6).
NG
Braun
Blau
G
NG
-1 , -1 -9 , 0
G
0 , -9 -6 , -6
Spieltheorie
15
Das “Kampf der Geschlechter” - Spiel ist nicht
dominant lösbar


Keine dominante Strategie für Sven:
 uSven(Stadion, Stadion) = 2 > 0 = uSven(Kino, Stadion),
 uSven(Kino, Kino) = 1 > 0 = uSven(Stadion, Kino).
Keine dominante Strategie für Tina:
 uTina(Stadion, Stadion) = 1 > 0 = uTina(Stadion, Kino),
 uTina(Kino, Kino) = 2 > 0 = uTina(Kino, Stadion).
Tina
Stadion
Kino
Sven
Stadion
2 , 1
0 , 0
Kino
0 , 0
1 , 2
Spieltheorie
16
Wiederholtes Eliminieren dominierter
Strategien

Der Grundsatz, dass ein Spieler nie eine dominierte Strategie
benutzen sollte, kann iterativ zur Lösung von Spielen benutzt
werden:



Falls eine Strategie dominiert wird, eliminiere sie! (Die Komplexität
des Spiels wird dadurch reduziert)
Falls eine Strategie im reduzierten Spiel dominiert wird, eliminiere
sie!
Mach weiter so!
Spieltheorie
17
Wiederholtes Eliminieren dominierter
Strategien
Spieler 2
Links
Spieler 1
Mitte
Rechts
Oben
1 , 0
1 , 2
0 , 1
Unten
0 , 3
0 , 1
2 , 0
Spieler 2
Links
Spieler 1
Mitte
Oben
1 , 0
1 , 2
Unten
0 , 3
0 , 1
Spieltheorie
18
Wiederholtes Eliminieren schwach dominierter
Strategien
Spieler 2
Links
Spieler 1
Rechts
Oben
3 , 2
2 , 2
Unten
0 , 0
1 , 1
Spieler 2
Spieler 1
Links
Rechts
Oben
3 , 2
2 , 2
Unten
0 , 0
1 , 1
Spieltheorie
19
Wiederholtes Eliminieren schwach dominierter
Strategien



Das Ergebnis hängt von der Reihenfolge des Eliminierens ab!
Es gibt Spiele, in denen es keine (schwach) dominierten Strategien
gibt (Kampf der Geschlechter).
⇒ Nash-Gleichgewicht.
Spieltheorie
Beste Antworten: Ein Beispiel
20
Spieler 2
Spieler 1






L
M
R
O
0 , 4
4 , 0
3 , 3
M
4 , 0
0 , 4
3 , 3
U
3 , 3
3 , 3
3.5 , 3.6
M ist die beste Antwort von Spieler 1 auf die Strategie L von Spieler 2;
O ist die beste Antwort von Spieler 1 auf die Strategie M von Spieler 2;
U ist die beste Antwort von Spieler 1 auf die Strategie R von Spieler 2.
L ist die beste Antwort von Spieler 2 auf die Strategie O von Spieler 1;
M ist die beste Antwort von Spieler 2 auf die Strategie M von Spieler 1;
R ist die beste Antwort von Spieler 2 auf die Strategie U von Spieler 1.
Spieltheorie
Beste Antworten: “Kampf der Geschlechter”
21





Die Strategie a ist die beste Antwort von Spieler 1 auf die Strategie a von Spieler 2;
Die Strategie b ist die beste Antwort von Spieler 1 auf die Strategie b von Spieler 2.
Die Strategie a ist die beste Antwort von Spieler 2 auf die Strategie a von Spieler 1;
Die Strategie b ist die beste Antwort von Spieler 2 auf die Strategie b von Spieler 1.
Die Strategiekombinationen (a, a) und (b, b) bestehen aus Strategien, die gegenseitig
beste Antworten sind.
Spieler 2
Spieler 1
a
b
a
2 , 1
0 , 0
b
0 , 0
1 , 2
Spieltheorie
Beste Antworten und Nash-Gleichgewicht
22

Eine Strategie si ∈ Si ist (eine) beste Antwort für Spieler i auf die
Strategien s-i ∈ S-i der anderen Spieler, falls ui(si, s-i) ≥ ui(si‘, s-i) für alle
si‘ ∈ Si.


Eine Strategiekombination s* = (s1*, s2*, …, sn*) ist ein NashGleichgewicht, falls für alle i = 1, 2, …, n gilt: ui(si*, s-i*) ≥ ui(si, s-i*) für
alle si ∈ Si.


bi(s-i) = {si ∈ Si : ui(si, s-i) ≥ ui(si‘, s-i) ∀ si‘ ∈ Si}.
d.h., si* ∈ bi(s-i*) für alle i = 1, 2, …, n.
Beispiel (n = 2): s* = (s1*, s2*) ist ein Nash-Gleichgewicht, falls


u1(s1*, s2*) ≥ u1(s1, s2*) für alle s1 ∈ S1 (s1* ist beste Antwort auf s2*),
u2(s1*, s2*) ≥ u2(s1*, s2) für alle s2 ∈ S2 (s2* ist beste Antwort auf s1*).
Spieltheorie
23
Beste Antworten im GefangenendilemmaSpiel

b1(NG) = G und b1(G) = G,

b2(NG) = G und b2(G) = G.

Nur die Strategiekombination (G, G) besteht aus Strategien, die
gegenseitig beste Antworten sind, d.h. das einzige Nash-Gleichgewicht in
diesem Spiel ist (G, G).
Spieler 2
NG
Spieler 1
G
NG
-1 , -1
-9 , 0
G
0 , -9
-6 , -6
Spieltheorie
24
Wiederholtes Eliminieren dominierter
Strategien und Nash-Gleichgewichte
Spieler 2
Spieler 1
Links
Mitte
Rechts
Oben
1 , 0
1 , 2
0 , 1
Unten
0 , 3
0 , 1
2 , 0
Spieler 2
Spieler 1
Links
Mitte
Oben
1 , 0
1 , 2
Unten
0 , 3
0 , 1
Spieltheorie
25
Wiederholtes Eliminieren dominierter
Strategien und Nash-Gleichgewichte
Spieler 2
Spieler 1
L
M
R
O
0 , 4
4 , 0
3 , 3
M
4 , 0
0 , 4
3 , 3
U
3 , 3
3 , 3
3.5 , 3.6
Spieltheorie
Das “Elfmeterduell”
26



Zwei Spieler: Spieler 1 (= Schütze) und Spieler 2 (= Torwart).
Die Strategiemengen sind für beide Spieler gleich: L (linke Ecke) und R (rechte Ecke).
Die Auszahlungen sind wie in der Matrix angegeben.

b1(L) = R und b1(R) = L,
b2(L) = L und b2(R) = R.

Kein Nash-Gleichgewicht in reinen Strategien!

Spieler 1
Spieler 2
L
R
L
0 , 1
1 , 0
R
1 , 0
0 , 1
Spieltheorie

Download Report