Mitschrift Entscheidungs- und Spieltheorie 2004

Spieltheorie I Manfred Nermuth

Sommersemester 2004

Beispiele fr Matrixspiele

Gefangenen-Dilemma

D-Strategie dominiert

Es wre irrational nicht zu gestehen (C), da D immer besser ist,

aber D ist Pareto-ineffizient individuell rationales Verhalten muss nicht zu Pareto-Effizienz fhren (gegen 1. Hauptsatz der

Wohlfahrtstheorie)

i = 2 C D

C -1, -1 -100, 0 i = 1 D 0, -100 -20, -20

Chicken Game

keine Strategie dominiert, einmal C besser einmal D besser

i = 2 C D

C 3, 3 2, 4 i = 1 D 4, 2 1, 1

Matching Pennies

T top

B bottom

kein Gleichgewicht : wenn andere wei, was ich tue, verliere ich

i = 2 T B

T 1, -1 -1, 1 i = 1 B -1, 1 1, -1 nur durch zufllige Wahl Gewinnmglichkeit

Battle of the Sexes

keine theoretische Mglichkeit ohne weitere Informationen den

Ausgang zu bestimmen

sie K B

K 1, -1 -1, 1 er B -1, 1 1, -1

Beispiele fr Differentialspiele

Lady in the Lake

um zu entkommen muss sie in einer Spirale gegen das Ufer

schwimmen und ab einem bestimmten Punkt gerade.

Homicidal Chauffeur

man muss im richtigen Augenblick zur Seite hpfen. Das Auto kann

nicht beliebig scharfe Kurven fahren

- 1 -


Sommersemester 2004

1. Spiele in strategischer Form 1.1. Beschreibung des Spiels Ein n-Personenspiel G ist gegeben durch

(1) die Menge der Spieler I = {1, 2, ..., n}

und fr jeden Spieler i I: (2) die Menge der mglichen Strategien fr Spieler i Si si Si Strategie von Spieler i s = (s1, s2, , sn) n i

i 1S S

== Strategiekombinationen / Strategieprofile

(3) eine Auszahlungsfunktion (payoff function) ui von Spieler i:

ui: S R

s = (s1, , sn) # ui(s) = ui(s1, , sn)

ui(s) = ui(s1, , sn) Auszahlung (Nutzen) von Spieler i, wenn die Strategiekombination

s = (s1, ..., sn) gewhlt/gespielt wird

G = {I, S1, , Sn, u1, , un} = {I, (Si), (ui)} Spiel in strategischer Form

ABLAUF: Spieler whlen Strategien gleichzeitig (i whlt ein si Si ohne zu wissen, was die anderen tun) .... Ergebnis (outcome) resultiert - Spieler haben Nutzen davon - dieser hngt letztlich von

der gewhlten Strategie s1, ..., sn ab (weil die Strategie das Ergebnis determiniert) -

daher ui = ui(s1, ..., sn)

NOTATION (Spieler i hervorheben)

s-i = (s1, s2, ..., si-1, si+1, , sn) Strategienkombination der anderen

schreibe s = (si, s-1) fr (s1, ...., si, ..., sn)

S-i := n

jj 1j i

S= = S1 S2 Si-1 Si+1 ... Sn Summe aller mglichen Strategienkombinationen

der anderen

s-i S-i

1.2. Dominante Strategie Def.: Seien si, si zwei mgliche Strategien von Spieler i.

Strategie si wird strikt dominiert von si, wenn si immer besser ist fr Spieler i als si, egal was

die anderen tun, d.h. wenn gilt:

ui(si, s-i) < ui(si, s-i) fr alle s-i S-iEin rationaler Spieler wird nie eine strickt dominierte Strategie spielen.

- 2 -


Sommersemester 2004

Beispiel

Gibbons: Fig. 1.1.1.

i = 2 L C R

T 1, 0 1, 2 0, 1 i = 1 B 0, 3 0, 1 8, 0

Notation:

I = {1, 2}

S1 = {T, B} S2 = {L, C, R} S = S1 S2 = {TL, TC, TR, BL, BC, BR} s = (s1, s2) = (T, L)

z.B. s = (T, L) u1(s) = u1(T, L) = 1

u2(s) = u2(T, L) = 0

s = (B, C) u1(s) = u1(B, C) = 0

u2(s) = u2(B, C) = 1

i = 1 S-1 = S2 (bei drei Spielern: S-1 = S2 S3)

i = 1 hat keine strikt dominierte Strategie

i = 2 R strikt dominiert durch C eliminiere R

i = 2 L C R

T 1, 0 1, 2 0, 1 i = 1 B 0, 3 0, 1 8, 0

danach:

i = 1 B strikt dominiert von T eliminiere B

i = 2 L C R

T 1, 0 1, 2 0, 1 i = 1 B 0, 3 0, 1 8, 0

danach:

i = 2 L strikt dominiert von C eliminiere L

i = 2 L C R

T 1, 0 1, 2 0, 1

i = 1 B 0, 3 0, 1 8, 0

verbleibt: s* = (s1*, s2*) = (T, C)

Dieser Prozess heit iterierte Elimination strikt dominierter Strategien.

Er kann, muss aber nicht zu einer eindeutigen Lsung fhren.

Gibbons: Fig. 1.1.4.

L C R T 0, 4 4, 0 5, 3 M 4, 0 0, 4 5, 3 B 3, 5 3, 5 6, 6 strikt dominierte Strategien - 3 -


Sommersemester 2004

1.3. NASH-Gleichgewicht

Def.: Sei i 1 i 1 i 1 ns (s , ..., s , s , ..., s ) S += i eine Strategienkombination der anderen. Eine Strategie si Si von Spieler i heit beste Antwort (best response/reply) von Spieler i auf is , wenn gilt: i i iu (s ', s ) s i i i i iu (s , s ) s S d.h. gegeben is maximiert Spieler i seinen payoff durch Wahl von si:

i i

i i i i i is Su (s ', s ) max u (s , s )

=

Achtung: die beste Antwort muss nicht eindeutig sein !!

Beispiel sei i = 1, 1s = L => beste Antwort von i = 1 auf 1s = L ist s1 = T

sei i = 2, 2s = T => beste Antwort von i = 2 auf 2s = T ist s2 = L

oder s2 = C (nicht eindeutig)

i = 2 L C R

T 4, 7 -1, 7 0, 0 i = 1 B 3, 2 0, 0 4, 1

def.: ri( is ) := {si Si | si ist beste Antwort auf is } beste-Antwort-Korrespondenz z.B. r1(L) = {T}, r2(T) = {L, C}

falls die beste Antwort von Spieler i immer eindeutig ist, schreiben wir si = ri( is ) und nennen die

Funktion: ri: S-i Si

s-i # si = ri( is ) die Reaktionsfunktion von Spieler i

Def.: sei G = {I, (Si), (ui)} ein n-Personenspiel in strategischer Form.

Eine Strategienkombination s* = (s1*, ..., sn*) S heit nicht-kooperatives Gleichgewicht oder NASH-Gleichgewicht des Spiels G, wenn gilt:

fr jeden Spieler i I ist si* eine beste Antwort auf s-i* d.h. ui(s*) s ui(si, s-1*) si Si si* ri(s-i*)

Interpretation: Gleichgewicht s ist stabil (self-enforcing) - kein Spieler hat einen Anreiz von seiner

Strategie si* abzuweichen, solange die anderen bei s-i* bleiben

umgekehrt: sei s = (s1, ..., sn) kein Gleichgewicht, d.h. mindestens ein Spieler i, dessen Strategie si nicht beste Antwort auf s-i ist. Dieser knnte sich verbessern durch

abweichen zu einer anderen Strategie si mit ui(si, s-i) > ui(s) i wird abweichen s nicht stabil

andere Interpreation: NASH-Gleichgewicht als soziale Konvention

- 4 -


Sommersemester 2004

Beispiel

Fig. 1.1.4

Fr jeden Spieler i und jede Strategie unterstreiche die beste Antwort L C R T 0, 4 4, 0 5, 3 M 4, 0 0, 4 5, 3 B 3, 5 3, 5 6, 6

des Gegners. Wenn in einem Kstchen zwei Striche sind, ist es ein

NASH-Gleichgewicht

s* = (B, R)

3 Probleme:

1. Ineffizienz (Bsp. Gefangenen-Dilemma)

2. nicht Eindeutigkeit (Bsp. Battle of the Sexes)

3. nicht Existenz (Bsp. Matching Pennies)

1.4. Gemischte (mixed, randomized) Strategien sei G gegeben

si Si reine / pure Strategie

Beispiel: G = Mathing Pennies

I = {1, 2}

S1 = {K, A} = S2 S = S1 S2 = {KK, KA, AK, AA}

u1(KK) = u1(AA) = 1

u1(KA) = u2(AK) = -1

i = 2 T B

T 1, -1 -1, 1 i = 1 B -1, 1 1, -1 (= Nullsummenspiel u2(s) = -u1(s) s S zero sum ame)

hat kein Gleichgewicht in reinen Strategien

Fhren gemischte Strategien ein. Spieler knnen reine Strategien mit bestimmten

Wahrscheinlichkeiten zufllig whlen.

Eine gemischte Strategie von Spieler i = 1 hat die Form:

1 = (1(K), 1(A)) , wo 1(K) die Wahrscheinlichkeit ist, dass i = 1 K spielt

1(K) s 0

1(A) s 0

1(K) + 1(A) = 1

1 ist eine Wahrscheinlichkeitsverteilung auf S1 = {K, A}

z.B.: 1 = 1 1, 2 2

1 = 1 2, 3 3

1 = (0, 1)

analog: 2(K) ist die Wahrscheinlichkeit, dass i = 2 K spielt

- 5 -


Sommersemester 2004

Allgemein: eine gemischte Strategie i von Spieler i ist eine Wahrscheinlichkeitsverteilung auf der

Menge Si seiner reinen Strategien

(jede reine Strategie si kann auch als gemischte Strategie aufgefasst werden: spielt si mit

Wahrscheinlichkeit 1)

es sei i die Menge aller gemischten Strategien von Spieler i

sei eine Kombination von gemischten Strategien = (1, 2) gegeben, und die Spieler whlen ihre

reinen Strategien zufllig gem i unabhngig voneinander, dann gilt:

die reine Strategienkombination s = KK tritt mit der Wahrscheinlichkeit 1(K) . 2(K) ein

die reine Strategienkombination s = KA tritt mit der Wahrscheinlichkeit 1(K) . 2(A) ein

wenn s = KK eintritt, ist der payoff von i = 1: u1(KK) = 1

wenn s = KA eintritt, ist der payoff von i = 1: u1(KA) = -1

der erwartete payoff v1 von Spieler 1 bei gemischter Strategienkombination = (1, 2) ist:

v1() = v1(1, 2) = u1(KK) . 1(K) . 2(K) +

+ u1(KA) . 1(K) . 2(A) +

+ u1(AK) . 1(A) . 2(K) +

+ u1(AA) . 1(A) . 2(A) =

= u (s) . (s ) . (s=

1 2

1 1 1 2s (s ,s ) S

2 )

analog: i = 2

z.B.: = (1, 2)

1 = 1 1, 2 2

2 = 1 1, 2 2

v1() =

1 1 1 1 1 + (-1) + (-1) + 1 = 04 4 4 4

z.B.: = (1, 2)

1 = 1 2, 3 3

2 = 1 1, 2 2

v1() =

1 1 2 2 1 + (-1) + (-1) + 1 = 06 6 6 6

z.B.: = (1, 2)

1 = ( )1, 0 2 =

1 1, 2 2

v1() =

1 1 1 + (-1) + 0 (-1) + 0 1 = 02 2

Ergebnis: wenn i = 2 die gemischte Strategie mit 2 = 1 1, 2 2

spielt, dann sind die reinen Strategien

s1 = K und s1 = A beide beste Antwort von Spieler 1 auf 2 und jede Mischung 1 von K

und A ist auch beste Antwort auf 2.

- 6 -


Sommersemester 2004

Insbesondere ist 1* = 1 1, 2 2

beste Antwort auf 2* = 1 1, 2 2

. Nach einer

symmetrischen berlegung ist auch 2* = 1 1, 2 2

beste Antwort auf 1* = 1 1, 2 2

. Das

Paar * = (1*, 2*) heit NASH-Gleichgewicht in gemischten Strategien vom Spiel G.

NOTATION:

sei Z eine endliche Menge

|Z| = #Z Anzahl der Elemente von Z

def.: eine Wahrscheinlichkeitsverteilung p auf Z ist eine Funktion:

p: Z R z # p(z)

mit p(z) s 0 und z Z

p(Z) 1

=

p(z) ist die Wahrscheinlichkeit, dass z gewhlt wird

(Z) Menge aller Wahrscheinlichkeitsverteilungen auf Z

|Z| = 2

Z = {z1, z2} pi = p(zi) p = (p1, p2)

(Z) = {p = (p1, p2) R2 | p1 s 0, p2 s 0 und p1 + p2 = 1}

= {(q, 1 - q | 0 c q c 1}

p1

p2

1

1

0

p2

p1

(Z)

|Z| = 3

Z = {z1, z2, z3} pi = p(zi) p = (p1, p2, p3)

(Z) = {p = (p1, p2, p3) R3 | pi s 0 i = 1, 2, 3 und 3 ii 1

p= = 1}

(Z)

(simplex) 1

1

Allgemein: (Z) ist kompakt und konvex im Rn

p12

p3

1

p

- 7 -


Sommersemester 2004

sei

I = {1, ..., n}

Si endliche Menge fr alle i I G = {I, (Si), (ui)} allgemeines endliches n-Personenspiel

def.: i = Si Menge der gemischten Strategien von i

i i von der Form: i = (i(si)) si Si i(si) s 0 Wahrscheinlichkeit, dass die reine Strategie si gewhlt wird

z.B.: Si = {a, b, c}

i = 1 1 1, , 2 3 6

fr si = b : i(b) = 13

= (1, ..., n) = n-tupel (=Liste von n Elementen) von gemischten Strategien n ii 1

=

Wenn jeder Spieler i = 1, ..., n seine reine Strategie si zufllig gem der

Wahrscheinlichkeitsverteilung i whlt und die Spieler dies unabhngig voneinander tun, dann ist die

Wahrscheinlichkeit, dass eine bestimmte reine Strategienkombination s = (s1, ..., sn) S =

gewhlt wird, gegeben durch:

ni

i 1S

=

Prob(s) = 1(s1) . 2(s2) . ... . n(sn) = n

i ii 1 (s )

=

die erwartete Auszahlung von Spieler i bei ist gegeben durch:

vi() = vi(1, ..., n) = n

i is S s S j 1

u (s) Pr ob(s) u (s) (s ) =

= j j

vi(1, ..., n) = 1 n

ni 1 n j j

(s ,...,s ) S j 1u (s , ..., s ) (s )

=

vi ist eine Funktion:

vi: R = (1, ..., n) # vi()

def.: die gemischte Erweiterung Ggem des ursprnglichen Spiels G, ist das folgende Spiel in

strategischer Form:

Ggem = {I, (i), (vi)}

I alle Spieler

i gemischte Strategien von i

vi erwartete Auszahlung von i

- 8 -


Sommersemester 2004

Def.: ein NASH-Gleichgewicht * = (1*, ..., n*) von Ggem heit ein Gleichgewicht in gemischten

Strategien von G.

Klar: * = (1*, ..., n*) ist ein Gleichgewicht, wenn fr i I gilt: vi(*) s vi(i, -i*) i i (= Abweichung zu einer anderen gemischten Strategie lohnt sich nicht)

Def.: ein Spiel G = {I, (Si), (ui)} heit endlich, wenn die Spielermenge endlich ist (I = {1, ..., n} mit

n < ) und die Strategienmenge Si endlich ist fr jeden Spieler i I.

THEOREM (NASH) Jedes endliche Spiel hat mindestens ein Gleichgewicht - mglicherweise in gemischten Strategien.

G = {I, (Si), (ui)}

sei * = (1*, ..., n*) ein Gleichgewicht

betrachte i = 1

S1 = {s1a, s1b, s1c, ..., s1l} reine Strategien von i

1* = (1*(s1a), 1*(s1b), ..., 1*(s1l)) wo 1*(s1a) s 0 die Wahrscheinlichkeit, dass s1a gewhlt wird, ist

erwarteter payoff:

v1(*) = v1(1*, -1*) = 1*(s1a) . v1(s1a, -1*) + 1*(s1b) . v1(s1b, -1*) + ... + 1*(s1l) . v1(s1a, -1l)

sei * ein Gleichgewicht in gemischten Strategien:

wenn i* i(s ) > 0 (Spieler i spielt is Si mit positiver Wahrscheinlichkeit), dann ist diese Strategie is

beste Antwort auf -1*; wenn mehrere reine Strategien is , is Si mit positiver Wahrscheinlichkeit

gespielt werden (d.h. i* i(s ) > 0, i* i(s ) > 0), dann mssen sie alle den gleichen (maximalen)

erwarteten payoff gegen -i* geben. Deswegen ist Spieler i dann auch bereit zu randomisieren.

1(K) = r 1(A) = 1 - r 0 c r c 1

2(K) = q 2(A) = 1 - q 0 c q c 1

i = 2 K A

K 1, -1 -1, 1 i = 1 A -1, 1 1, -1

r = r1(q) beste-Antwort-Korrespondenz von i = 1

r = r2(r) beste-Antwort-Korrespondenz von i = 2

Gleichgewicht

r

q

1 2

1

1

0 12

- 9 -


Sommersemester 2004 gem = {I, (G ), (v )} i i

konvexe stetige Funktion

kompakte linear in i Menge quasi konkav in i

2. Spiele in extensiver Form mit vollstndiger (complete) Information bisher: Spiele in strategischer Form: Spieler agieren simultan

nun: explizite Zeitstruktur: Spieler agieren nicht notwendigerweise simultan

2.1. einfachster Fall

i I = {1, 2} zwei Spieler A Menge der mglichen Aktionen (Zge) von Spieler i i

Ablauf:

- Spieler i = 1 whlt eine Aktion a1 A1 - Spieler i = 2 beobachtet a1 und whlt eine Aktion a2 A2 payoffs: u1(a1, a2), u2(a1, a2), u = (u1, u2) Auszahlungsvektor

Beispiel:

A1 = {T, M, B}

A2 = {L, C, R}

u(5, 3) 1(T, L) = 5 L

ui = 2

2(T, L) = 3

# u2(B, R) = 0

Lsung durch Rckwrtsinduktion (backwards induction)

Spielbaum

game tree

allg.: Menge der Aktionen von Spieler 2 hngt von a1 ab A2 = A2(a1)

C

i = 2

i = 2

R

R

i = 1

T

M

L B

(0, 8)

(0, 0)

(1, -1

(8, 11

)

(3, 10)

)

(2, 0)

C

(4, 7)

(100

L C

, 7)

R

- 10 -


Sommersemester 2004

der Spielbaum muss nicht regelmig sein:

R

L

L

i = 2

i = 2

i = 2

C

i = 1

T

M

B

C

noch allgemeiner: Spieler knnen fter am Zug sein

(dieses Spiel ist sofort aus: i = 1 geht nach links) i = 1

i = 2

i = 1

R

R

R

L

L

L

(2, 0)

(1, 1)

(0, 3)

(2, 0)

Allgemein:

n Spieler, jeder kann fter ziehen

die extensive Form eines Spiels gibt an:

1. die Spieler

2.a. wann jeder Spieler am Zug ist

2.b. was er tun kann, wenn er am Zug ist (Menge der mglichen Zge)

2.c. was er wei, wenn er am Zug ist (Informationsmenge)

3. Auszahlungen

(Spielbaum gibt alles an, auer 2.c.)

Das Spiel hat vollkommene (perfect) Information, wenn in 2.c. jeder Spieler immer die ganze

Vorgeschichte kennt, d.h. die Zge aller Spieler die vorausgegangen sind.

Darstellung des Spielbaums - zunchst mit vollkommener Information

0002

2110

0100

1002

0980

2101

84

35

0000

72

105

0000

i = 1

i = 2

i = 1

i = 3

i = 2

i = 2

i = 4

A1

B2

C1

D3

E2

F2

G4

L1R1

R2L2

l1 r1

R3

L3 M3

l2 m2r2

a2 b2

R4L4

- 11 -


Sommersemester 2004

Knoten (nodes):

Knoten, wo i am Zug ist Entscheidungsknoten: XiEnknoten: payoffs

Zweige: die von einem Knoten ausgehenden Zweige, beschreiben die mglichen Zge

Def.: eine Strategie fr Spieler i ist ein vollstndiger Plan fr das Spiel, d.h. die Strategie gibt fr

jeden Entscheidungsknoten X an, welchen Zug er whlt. i

Def.: ein Teilspiel beginnt bei einem Knoten und enthlt alles Folgende. (das ganze Spiel ist auch ein

Teilspiel von sich selbst.)

Wenn jeder Spieler i eine Strategie (d.h. einen Plan) gewhlt hat, ist der Pfad durch den Spielbaum

eindeutig bestimmt sind die payoffs im ganzen Spiel (und auch in jedem Teilspiel) bestimmt. z.B. s1 = (R1, r1) S1 = {R1r1, R l1 1, L1r1, L1l1}

s2 = (R2, m , b2 2)

s3 = (M3)

s4 = (L4)

u1(s1, s2, s3, s4) = -7

s

u2(s1, s2, s3, s4) = 2

u3(s1, s2, s3, s4) = 10

u4(s1, s2, s3, s4) = 5

Die Menge aller mglichen Strategien mit zugehrigen payoffs beschreibt ein Spiel in strategischer

Form, dieses heit die Normalform des extensiven Spiels.

Def.: ein NASH-Gleichgewicht eines Spiels in extensiver Form ist ein NASH-Gleichgewicht seiner

Normalform.

Beispiel: G3

i = 1

i = 1

i = 1

i = 2 i = 2

A.1

B.2 C.2

D.1 E.1

L1 R1

L2 R2 l2 r2

x1 y1 w1z1

12

34

56

78

910

1112

- 12 -


Sommersemester 2004

- 13 -

Strategien von i = 1:

A.1 D.1 E.1

L1 x1 z1 S1 = {L1x1z1, L1x1w1, L1y1z1, L1y1w1, R1x1z1, R1x1w1, R1y1z1, R1y1w1}

R1 y1 w1 23 = 8 Strategien

Strategien von i = 2:

S2 = {L2l2, L2r2, R2l2, R2r2}

Normalform von G3:

i = 2

(u1, u2) L2l2 L2r2 R2l2 R2r2

L1x1z1 1, 2 1, 2 5, 6 5, 6

L1x1w1 1, 2 1, 2 5, 6 5, 6

L1y1z1 3, 4 3, 4 5, 6 5, 6

L1y1w1 3, 4 3, 4 5, 6 5, 6

R1x1z1 7, 8 9, 10 7, 8 9, 10

R1x1w1 7, 8 11, 12 * 7, 8 11, 12 *

R1y1z1 7, 8 9, 10 7, 8 9, 10

i = 1

R1y1w1 7, 8 11, 12 * 7, 8 11, 12 *

4 NASH-Gleichgewicht (NASH-Gleichgewichte nicht payoff, sondern Strategiekombination):

s* = (s1*, s2*) = (R1x1w1, L2r2) erzeugen alle selben Pfad Gleichgewichtspfad eindeutig s* = (s1*, s2*) = (R1y1x1, L2r2) alle mit payoffs:

s* = (s1*, s2*) = (R1x1w1, R2r2) u1(s*) = 11

s* = (s1*, s2*) = (R1y1w1, R2r2) u2(s*) = 12

Beispiel: G4

Normalform von G4:

S1 = {L, R} S2 = {l, r}

2 Gleichgewicht:

s** = Lr mit payoffs 10, 8

s* = Rl mit payoffs 5, 20

i = 2 l r

L 0, 0 10, 8 ** i = 1

R 5, 20 * 5, 20

i = 1

i = 2

A.1

B.2

R

L

l

r

(0, 0)

(10, 8)

(5, 20)


Sommersemester 2004

was bedeutet s* = Rl?

Spieler 2 droht mit l bei B.2, aber die Drohung ist unglaubwrdig, weil es irrational wre, daher ist es

in extensiver form ein unbefriedigendes Gleichgewicht. R. SELTEN: solche Gleichgewichte eliminieren

Def.: (R. SELTEN) ein NASH-Gleichgewicht eines extensiven Spiels heit teilspiel-perfekt (subgame

perfect), wenn die Strategien der Spieler auch in jedem Teilspiel ein NASH-Gleichgewicht bilden

G4: in dem Teilspiel , das bei B.2 beginnt, ist s2 = l kein Gleichgewicht mehr einziges Gleichgewicht: s** = Lr

G3: s* = (s1*, s2*) = (R1x1w1, L2r2) nicht teilspiel-perfekt (L nicht Gleichgewicht ab B.2)

s* = (s1*, s2*) = (R1y1x1, L2r2) nicht teilspiel-perfekt (x nicht Gleichgewicht ab D.1)

s* = (s1*, s2*) = (R1x1w1, R2r2) nicht teilspiel-perfekt (L nicht Gleichgewicht ab B.2)

s* = (s1*, s2*) = (R1y1w1, R2r2) ist teilspiel-perfekt!

SATZ (R. SELTEN) Jedes endliche extensive Spiel mit vollkommener Information hat mindestens 1 teilspiel-perfektes

Gleichgewicht in reinen Strategien

Beweis: backwards induction

i = 1

i = 2

i = 1 i = 1

i = 1

i = 1

i = 2 i = 2 i = 2 i = 2

i = 2

i = 2 i = 2

A.1

B.1

C.1

D.1

E.1

Z.2

Y.2

X.2 W.2 V.2 U.2 T.2 S.2

a b

d e f

g h

i j c

l m n o p q r s t u v

w x

y z

k

00

10

11

23

24

11

14

1011

20

78

12

33

43

02

S1 A.1 B.1 C.1 D.1 E.1 z.B. s1 = acfgj

a c e g i

b d f h j

S2 Z.2 Y.2 X.2 W.2 V.2 U.2 T.2 S.2

z x v t r p n l

y w u s q o m k

- 14 -


Sommersemester 2004

NASH-Gleichgewicht:

s1* = bdehj s2* = ywvsqonl

s2* = ywusqonl

=> 2 NASH-Gleichgewichte:

s* = (bdehj, ywvsqonl)

s* = (bdehj, ywusqonl)

Beispiel: Tausendfler (centipede)

i = 1 i = 1 i = 1 i = 2 i = 2 i = 2

A.1 B.2 C.1 E.1 D.2 F.2

a a a a a a

w w w w w w 3029

1930

2019

920

109

0

10

10

i = 1 spielt gleich a, obwohl mit Kooperation mglich gewesen wre 3029

Extensive Spiele mit vollstndiger (complete) aber unvollkommener (imperfect) Information die extensive Form ist beschrieben durch:

1. die Spieler

2.a. wann jeder Spieler am Zug ist

2.b. was er tun kann, wenn er am Zug ist (Menge der mglichen Zge)

2.c. was er wei, wenn er am Zug ist (Informationsmenge)

3. Auszahlungen

aber in 2.c., wenn ein Spieler am Zug ist, kennt er nicht unbedingt die ganze Vorgeschichte

Beispiel

i I = {1, 2} - i = 1 whlt Aktion a1 = L, M, oder R a1 {L, M, R} - i = 2 kann nur beobachten, ob R gewhlt wurde oder nicht (d.h. wenn nicht, wei er nur, dass

a1 = L oder a = M) 1wenn a1 = R, dann whlt i = 2: a2 {T, C, B} wenn a1 {L, M}, dann whlt i = 2: a2 {t, b}

- payoffs: u1(a1, a2), u2(a1, a ) 2

- 15 -


Sommersemester 2004

i = 1

i = 2 i = 2

A.1

B.2 C.2 D.2

R L M

t t b b T C B

I1

I2 I2

08

0

10

11

81

00

2

7

100

i = 1 kann die Knoten B.2 und C.2 nicht unterscheiden (verbunden durch ). Wenn er am Zug ist,

wei er nur, ob er sich in I2 = {B.2, C.2} oder in I2 = {D.2} befindet.

I2 und I2 heien Informationsmengen von Spieler 2 i = 2

allgemein: eine Informationsmenge Ii von Spieler i ist eine Menge von Knoten, bei denen i am Zug ist,

und wenn das Spiel einen Knoten in I erreicht, dann wei i nur, dass er in Ii i ist, aber nicht

bei welchem Knoten.

(Iklar: bei allen Knoten einer Informationsmenge I muss i die selbe Menge Ai i i) mglicher Zge

haben (sonst knnte er ja unterscheiden bei welchem Knoten er ist)

z.B. A2(I2) = {t, b} A2(I2) = {T, M, B}

klar: Jeder Knoten (auer Endknoten) liegt in genauer einer Informationsmenge irgendeines Spielers

Def.: ein Spiel hat unvollkommene (imperfect) Information, wenn mindestens eine Informationsmenge

eines Spielers mehr als einen Knoten enthlt.

vollkommene (perfect) Information ein Spiel hat , wenn alle Informationsmengen aller Spieler

1-elementig sind. [singletons = Menge mit einem Element]

Beispiel: Fig. 2.4.4.

I3 D.3

I2 I2 i = 2 i = 2

B.2 C.2

R L

i = 1 A.1

I1

l l r r

E.3 F.3 G.3 i = 3

a a a b b b c d

123

321

I3 i = 3

132

231

000

740

100

330

- 16 -


Sommersemester 2004

Informationsmengen und Mengen mglicher Zge:

i = 1: I1 = {A.1} A1(I1) = {L, R}

i = 2: I2 = {B.2}, I2 = {C.2} A2(I2) = {l, r}, A2(I2) = {l, r}

i = 3: I3 = {D.3, E.3, F.3}, I3 = {G.3} A3(I3) = {a, b}, A3(I3) = {c, d}

Beachte: kann gleichzeitige Zge durch Informationsmengen darstellen

z.B. Prisoners Dilemma

i = 2 C D2 2 C -1, -1 -100, 0 1i = 1 D 0, -100 -20, -201

I1 = {A.1}

I

C

i = 1

A.1

B.2 C.2

C D

C D

11

2020

1000

0100

I1

2 2 = {B.2, C.2} I i = 2

D

Def.: eine (reine) Strategie fr Spieler i ist ein vollstndiger Plan, der fr jede Informationsmenge von

Spieler i einen Zug vorsieht.

S Menge aller solchen Plne i S wenn jeder Spieler i eine Strategie si i gewhlt hat, ist der Pfad durch den Spielbaum, damit

die Endknoten (outcome), damit die payoffs determiniert. n

jj 1

S= => u (si 1, ..., sn) ... is payoff bei Strategiekombinationen s = (s1, ..., sn) S =

=> Normalform des Spiels (ist ein Spiel in strategischer Form): G = {I, (S ), (u )} i i

wissen: hat mindestens 1 NASH-Gleichgewicht in gemischten Strategien

Erinnerung: eine gemischte Strategie (Si i) von Spieler i ist eine Wahrscheinlichkeitsverteilung auf der Menge S seiner reinen Strategien i

- 17 -


Sommersemester 2004

Beispiel: Fig. 2.4.4.

I3 D.3

I2 I2 i = 2 i = 2

B.2 C.2

R L

i = 1 A.1

I1

l l r r

E.3 F.3 G.3 i = 3

a a a b b b c d

123

321

132

231

000

740

100

330

I3 i = 3

reine Strategien der 3 Spieler:

s1 gibt einen Zug bei I1 = {A.1} an: s1 S1 = {L, R} s2 gibt je einen Zug bei I2 und I2 an: z.B. s2 = ll, s2 S2 = {ll, lr, rl, rr} s3 gibt je einen Zug bei I3 und I3 an: z.B. s3 = ac, s3 S = {ac, ad, bc, bd} 3

gemischte Strategie fr z.B. i = 3:

ist von der Form: 3 = (3(ac), 3(ad), 3(bc), 3(bd)) (S3) 4 1 2 3, , ,

10 10 10 10 = z.B. 3

4 1 510 10 10

+ = => wenn er zu I3 kommt, spielt er a mit Wahrscheinlichkeit

2 3 510 10 10

+ = wenn er zu I3 kommt, spielt er b mit Wahrscheinlichkeit

4 2 610 10 10

+ = wenn er zu I3 kommt, spielt er c mit Wahrscheinlichkeit

1 3 410 10 10

+ = wenn er zu I3 kommt, spielt er a mit Wahrscheinlichkeit

Ergebnis: eine gemischte Strategie 3, bei der Spieler i = 3 einen ganzen Plan zu fllig whlt

(z.B. s 4103

= ac, a bei I3 und c bei I3 mit Wahrscheinlichkeit 3(ac) = ), induziert

bestimmte Wahrscheinlichkeiten mit denen der Zge bei Informationsmengen macht (z.B.

bei I 4103

den Zug d mit Wahrscheinlichkeit )

ALSO: kann das Verhalten eines Spielers, der eine gemischte Strategie spielt, auch so

beschreiben:

fr jede Informationsmenge von ihm, gebe ich eine Wahrscheinlichkeitsverteilung ber die

dort mglichen Zge an

- 18 -


Sommersemester 2004

so etwas heit Verhaltensstrategie (behavioural strategy) und bedeutet, der Spieler whlt

bei jeder Informationsmenge von ihm seinen Zug zufllig

12

12

z.B. bei I3: ( , ), bei I3: (0,6 , 0,4)

Def.: ein Spiel hat perfect recall (Erinnerung), wenn ein Spieler nie vergisst, was er schon wusste

(insbesondere nicht seine eigenen frheren Zge)

[im folgenden treffen wir die Annahme von perfect recall]

SATZ von Th. KUHN

bei perfect recall sind Verhaltensstrategien und gemischte Strategien quivalent

Folgerung: Jedes endliche Spiel (mit perfect recall) hat mindestens 1 NASH-Gleichgewicht in

Verhaltensstrategien

Beweis: weil es mindestens 1 NASH-Gleichgewicht in gemischten Strategien gibt

Wiederholung

- eine reine Strategie si fr Spieler i ist ein Plan, der fr jede Informationsmenge von Spieler i einen Zug angibt

- eine gemischte Strategie i fr Sieler i ist eine Wahrscheinlichkeitsverteilung auf die Menge seiner reinen Strategien (d.h. er whlt zufllig eine reine Strategie und spielt diese dann)

- eine Verhaltensstrategie i fr Spieler i ist ein Plan, der fr jede Informationsmenge von i eine Wahrscheinlichkeitsverteilung auf der Menge der dort mglichen Zgen angibt (d.h. heit wenn i

zu dieser Informationsmenge gelangt, whlt er dort seinen Zug zufllig)

Beispiel

i = 2

x I1

I2

i = 1

i = 2

A.1

B.2

C.2

D.1

E.1 i = 1

i = 1

I1

I1

y

L

R

L

R

a

b

c

d

(-1, 1)()

(-1, 1)()

(-1, 1)

(-1, 1)

(1, -1)

(1, -1)()

1 0

L R xac -1, 1 1

NASH-Gleichgewicht in reinen Strategien

, -1 0 xad -1, 1 1, -1 0 xbc -1, 1 -1, 10 xbd -1, 1 -1, 10 yac -1, 1 -1, 1

i = 1

0 yad 1, -1 -1, 10 ybc -1, 1 -1, 1 ybd 1, -1 -1, 1

- 19 -


Sommersemester 2004

gemischte Strategien fr Spieler i = 1:

12

12

12

z.B. 1 = [xac] + [ybd] spielt mit Wahrscheinlichkeit die reine Strategie xac / ybd

12

12

1 = [xbd] + [yac]

Spieler i = 2:

z.B. 2 = 1[L]

erwarteter payoff von Spieler i = 1:

u1(1, 2) = 12

u1(xac, L) + 12

u1(ybd, L) = 12

(-1) + 12

1 = 0 () ()

u1(1, 2) = 12

u1(xbd, L) + 12

u1(yac, L) = 12

(-1) + 12

(-1) = -1 () ()

Verhaltensstrategie so: 1 induziert die folgende Verhaltensstrategie 1

12

12

1 so: bei I1: [x] + [y]

bei I1: 1[a] weil er xac spielt, wenn er berhaupt zu D.1 kommt

bei I1: 1[d] weil er ybd spielt, wenn er berhaupt zu E.1 kommt

erwarteter payoff bei Verhaltensstrategie:

u1(1, 2 = L) = 12

(-1) + 12

1 = 0 () ()

1 induziert die Verhaltensstrategie 1:

12

12

1 so: bei I1: [x] + [y]

bei I1: 1[b]

bei I1: 1[c]

u1(1, L) = 12

(-1) + 12

(-1) = -1 () ()

bei perfect recall sind Verhaltensstrategien und gemischte Strategien quivalent ( SATZ von KUHN)

ohne perfect recall:

gemischte Strategien von Spieler i = 1

12

12

z.B. 1 = [xa] + [yb]

12

12

1 = [xb] + [ya]

Spieler i = 2

z.B. 2 = L

- 20 -


Sommersemester 2004

Verhaltensstrategien:

1 : bei I1: 12

[x] + 12

[y]

bei I1: 12

[a] + 12

[b]

1 = 1 : die gemischten Strategien 1 und 1 erzeugen das

1 : bei I1: 12

[x] + 12

[y] gleiche Verhalten - behavioural equivalent

bei I1: 12

[b] + 12

[a]

payoffs:

u1(1, L) = 12

(-1) + 12

1 = 0 () ()

u1(1, L) = 12

12

(-1) + (-1) = -1 () ()

12

12

12

12

12

u1(1 = 1, L) = (-1) + [ (-1) + 1] = -

x y a b

Def.: ein Teilspiel eines extensiven Spieles mit unvollkommener Information hat 2 Eigenschaften:

1. beginnt bei einem Knoten K0 und enthlt alles Folgende

2. wenn ein Knoten im Teilspiel liegt, dann auch alle anderen Knoten, die zur selben

Informationsmenge gehren

insbesondere: der Anfangsknoten K0 eines Teilspiels muss in einer Informationsmenge liegen,

die ein singleton ist, d.h. der Spieler der bei K0 zieht, wei, dass er bei K0 ist, d.h.

er kennt die ganze Vorgeschichte bis K0 Bedingung 2 stellt sicher, dass auch jeder andere Spieler, wenn er im Teilspiel

am Zug kommt, wei, dass die Vorgeschichte (der bisherige Spielverlauf) den

Knoten K0 enthlt

=> das Teilspiel kann als unabhngiges extensives Spiel mit Anfangsknoten K0

analysiert werden

Klar: eine Verhaltensstrategie fr das ganze Spiel induziert auch eine Verhaltensstrategie fr jedes

Teilspiel (Zugwahrscheinlichkeiten bei den verschiedenen Informationsmengen)

Def.: ein Gleichgewicht in Verhaltensstrategien heit teilspiel-perfekt, wenn es auch in jedem

Teilspiel ein Gleichgewicht ist

SATZ (SELTEN)

jedes Spiel mit perfect recall hat mindestens 1 teilspiel-perfektes Gleichgewicht

- 21 -


Sommersemester 2004

Beweis: backwards induction durch alle Teilspiele

Beispiel

I1 D.1

I2 I2 i = 2 i = 2

B.2 C.2

b a

i = 1 A.1

I10

c e d f

E.1 F.1 G.1 i = 1

g g k h h l k l

11

1

1

11

11

00

02

33

21

I1 i = 1

2 echte Teilspiele, beginnend bei B.2 und C.2

ab B.2: ab C.2

Normalform: Normalform:

g h k l c 1, -1 -1, 1 1e 0, 0 -2, d -1, 1 1, -1 f 3

Gleichgewicht: ( 12

[c] + 12

[d], 12

[g] + 12

[h] ) Gleichgewicht: (k, f)

erwartete payoffs: (0, 0) erwartete payoffs: (3, 3)

Gleichgewicht: b

teilspiel-prefektes Gleichgewicht des ganzen Spieles so:

bei I10 macht Spieler i = 1 b, danach plant jeder Spieler Gleichgewichtsstrategie fr Teilspiele

, 3* 0, 2

33

00

a b

B.2 C.2

i = 1

- 22 -


Sommersemester 2004

Wiederholte Spiele (repeated game) sei G = {I, (A ), (u )} ein Spiel in strategischer Form i ii I = {1, ..., n} Spieler a A Aktionen (Strategien) von Spieler i [schreibe A statt S ] i i i i

ni

i 1A

=A = a = (a1, ..., an) A

: A R ui

a # u (A) = u (ai i 1, , a ) n

G heit Basisspiel (stage game, Stufenspiel)

NUN: t = 1, 2, ..., T Perioden

Das T-mal wiederholte Spiel G(T) (Superspiel) luft so ab:

in jeder Periode t = 1, ..., T:

jeder Spieler i I whlt eine Aktion a (t) A (alle Spieler simultan) i i outcome a(t) = (a1(t), ..., an(t)) A payoffs: (t) = u (a(t)) i i

Notation:

a(t) = (a1(t), ..., an(t)) A outsome in Periode t h(t) = (a(1), a(2), ..., a(t)) t-history: Geschichte bis Periode t (inkl.)

h(t) A A ... A = At Menge aller mglichen t-histories (1 t T) speziell: h(T) = (a(1), ..., a(T)) ganzer Spielverlauf

schreibe: h(0) = A0 := {} (fiktive) Vorgeschichte vor Beginn des Spieles (= fix, z.B. mit h(0) = bezeichnet) H = Menge aller mglichen t-histories fr t = 0, 1 , ..., T - 1

T 1 t

t 0A

=

3

i 1 2i 1

A A A A=

= 3

Def.: eine (reine) Strategie s fr Spieler i im Superspiel G(T) ist eine Abbildung i si: H Ai

h(t - 1) # a (t) = s (h(t - 1)) 1 t T i i

Interpretation: in Periode t kennt jeder Spieler die Vorgeschichte h(t - 1) und kann die Wahl

seiner Aktion a (t) davon abhngig machen i

s ist ein vollstndiger Plan, der fr jede Periode t und fr jede mgliche Vorgeschichte h(t - 1) i festlegt, welche Aktion a (t) = s (h(t - 1)) der Spieler in Periode t whlt i i

Menge aller mglichen Abbildungen von H nach A = Menge aller reinen Strategien von Si i Spieler i im Superspiel G(T)

s Si i

- 23 -


Sommersemester 2004

s = (s1, .., sn) S = alle mglichen Strategienkombinationen n ii 1

S=

SWenn jeder Spieler i eine Strategie si i gewhlt hat, ist der Spielverlauf durch die Kombination s = (s1, ..., sn) bestimmt

(1) = s (h(0)) = s () A i I in t = 1: ai i i i Anfangszug von i

=> a(1) = (a1(1), ..., an(1)) bestimmt

=> h(1) = (a(1)) bestimmt

in t = 2: ai(2) = s (h(1)) i I i => a(2) = (a1(2), ..., an(2)) bestimmt

=> h(2) = (a(1), a(2)) bestimmt

in t = 3: ai(3) = s (h(2)) = s (a(1), a(2)) i I i i => a(3) = (a1(3), ..., an(3)) bestimmt

=> h(3) = (a(1), a(2), a(3)) bestimmt

# in t = T: ai(T) = s (h(T - 1)) = s (a(1), a(2), ..., a(T - 1)) i I i i => a(T) = (a1(T), ..., an(T)) bestimmt

=> h(T) = (a(1), a(2), ..., a(T)) (der ganze Spielverlauf) bestimmt

Superspiel-payoffs:

(t) = u (a(t)) in Periode t bekommt Spieler i den payoff i i Auszahlungsstrom: (1), (2), ..., (T) i i i

Gesamt-payoff U von Spieler i im Superspiel G(T) kann auf verschiedene Weisen definiert werden: i- ohne Diskontierung:

- U = Summe der Perioden-payoffs iT

it 1 (t)

=

- Ui = T

it 1

1 (t)

T = Durchschnitt der Perioden-payoffs

- mit Diskontierung:

- Ui = (0 < < 1) diskontierte Summe T t 1

it 1 (t)

=

= 0 . i(1) + 1 . i(2) + 2 . i(3) + ... + T-1 . i(T)

- Ui = T t 1

it t 1

1 (t)

1

= diskontierter Durchschnitt

strategisch quivalent

strategisch quivalent

die payoffs U sind determiniert durch die Strategien s der Spieler i i = U (s=> kann schreiben Ui i 1, ..., sn) = U (s) Auszahlungsfunktion in G(T) i

=> {I, (S ), (U )} Normalform von G(T) i i=> NACH-Gleichgewicht s* = (s1*, ..., sn*) im Superspiel G(T) definiert

- 24 -


Sommersemester 2004

G = {I, (A ), (u )} Basisspiel i iI = {1, ..., n} Spielermenge

a A Aktionen i i: A R ui

a # u (a) = u (ai i 1, , a ) n

t = 1, ..., T G(T) Superspiel

a(t) = (a1(t), ..., an(t)) A (t) = u (a(t)) i i

h(t) = (a(1), a(2), ..., a(t)) t-history

s (h(t-1)) Aktion von i in Periode t nach Vorgeschichte h(t - 1) bei Strategie si is S reine Strategien i is = (s1, ..., sn) S = damit Ablauf des Spiels und payoffs jeder Periode determiniert n i

i 1S

=

Auszahlungsstrom: (1), (2), ..., (T) i i i

z.B. U (s) = T

it 1 (t)

=i

oder

U (s) = (0 < < 1) T t 1

it 1 (t)

=i

damit: G(T) = {I, (S ), (U )} strategische Form i i => NASH-Gleichgewicht s* = (s1*, ..., sn*) des Superspiels definiert

ein wiederholtes Spiel ist ein Spezialfall eines Spieles in extensiver Form (mit unvollkommener

Information)

z.B. Prisoners Dilemma

Basisspiel G:

I = {1, 2}

A1 = A2 = {C, D}

i = 2 C D

C 10, 10 0, 20 i = 1 D 20, 0 1, 1*

dies in strategischer Form:

G

C

i = 1

C D

C D

1010

11

020

200

i = 2

D

- 25 -


Sommersemester 2004

wiederholt: T = 2

C C C C C C D D D D D D C D

C C

C C C D D D D

D

i = 1

C

D

C

D

z.B. ui = i(1) + i(2)

1. Runde

s1 = (D; D, D, D, D)

s2 = (D; D, D, D, D)

SATZ

Falls das Basisspiel ein eindeutiges NASH-Gleichgewicht a* = (a1*, ..., an*) A hat, dann hat jedes endlich oft wiederholte Superspiel G(T) auch ein eindeutiges teilspiel-perfektes Gleichgewicht, und

dieses besteht darin, dass in jeder Periode das Gleichgewicht des Basisspiels gespielt wird:

si(h(t - 1)) = si* fr alle h(t - 1), t = 1, ..., T

(in diesem Fall bringt die Wiederholung nicht Neues)

Beweis: backwards induction

bygones are bygones: Entscheidungen hngen nur von der Zukunft ab, nicht von der Vergangenheit

Unendlich oft wiederholte Spiele G = {I, (Ai), (ui)} Basisspiel

t = 1, 2, 3, ... Perioden

a(t) = (a1(t), ..., an(t)) A = n ii 1

A= Aktionen n-tupel in t

i(t) = ui(a(t)) is payoff in t

h(t) = (a(1), ..., a(t)) At t-history H Menge aller histories (aller Lngen)

Strategie: si: H Ai schreibt nach jeder mglichen history h(t - 1) eine Aktion ai = si(h(t - 1)) Ai vor fr t = 1, 2, ...

Si Menge aller Strategien fr Spieler i

i = 2 C D

C 11, 11 1, 21 i = 1 D 21, 1 2, 2*

2020

i = 2

i = 1 i = 1 i = 1 i = 1

i = 2 i = 2 i = 2 i = 2

D C

1030

3010

040

1111

1030

2020

121

3010

2020

400

211

1111

121

22

211

- 26 -


Sommersemester 2004

s = (s1, ..., sn) S = Strategienkombinatiionen n ii 1

S=

gegeben s, ist der Spielablauf bestimmt:

a(1) = (s1(h(0)), s2(h(0)), ..., sn(h(0))) Anfangszge

a(2) = (s1(a(1)), s2(a(1)), ..., sn(a(1)))

a(3) = (s1(a(1), a(2)), s2(a(1), a(2)), ..., sn(a(1), a(2)))

=> Auszahlungsstrme:

(1) = u (a(1)) i i(2) = u (a(2)) i i

fr jeden Spieler i Auszahlungsstrom: (1), (2), (3), ... i i i

Superspiel-payoffs Ui:

Annahme: Auszahlungen im Basisspiel G beschrnkt T

iT t 1

1lim (t)T =

= Durchschnitt: Ui z.B. ( (1), (2), (3), ...) = (10, 20, 30, 10, 20, 30, ...) U = 20 i i i i konvergiert nicht immer:

z.B. ( (1), (2), (3), ...) = (10, 0, 10, 10, 10, 10, 10, 0, 0, ..., 0, 0, ..., 0, 10, ...) i i i

Diskontierung: U = konvergiert immer, falls T t 1

it 1 (t)

= beschrnkt sind i i

= T t 1

it 1

(1 ) (t)=

diskontierter Durchschnitt: Ui(t) = c = const. falls i

T Tt 1 t 1

t 1 t 1

c c c

1

= = = = diskontierte Summe:

diskontierter Durchschnitt: T t 1

t 1(1 ) c c

= =

U hngt letztendlich von den Strategien s ab i i => U = U (s) = U (si i i 1, ..., sn)

=> Superspiel: G(, ) = {I, (S ), (U )} strategische Form i i

wo Ui = U = T t 1

it 1 (t)

=i

= T t 1

it 1

(1 ) (t)=

oder Ui => NASH-Gleichgewicht im -Superspiel definiert

Extensive Form: unendlicher Spielbaum

in jeder Runde beginnt ein neues Teilspiel, die alle isomorph zum ganzen Superspiel sind

=> teilspiel-perfektes Gleichgewicht definiert

- 27 -


Sommersemester 2004

Spiele mit unvollstndiger (incomplete) Information (BAYES-Spiele) Wiederholung: Spiel in strategischer Form mit vollstndiger Information

I = {1, ..., n} Spieler

a A Aktionen i in

ii 1

A= a = (a1, ..., a ) A = n

u : A R i

a # u (a) = u (ai i 1, , a ) Auszahlungsfunktion von I n

G = {I, (A ), (u )} i i

NUN: Spiel mit unvollstndiger Information (HARSANYI)

fr jeden Spieler I = 1, , n

T Menge der mglichen Typen it T Typ von i i it = (t1, ..., tn) T = Typenprofil n i

i 1T

=

, tt = (ti -1) wo t-1 = (t1, ..., t , ti-1 i+1, ..., t ) Typen der anderen n

Ablauf:

- am Anfang (vor Spielbeginn): Natur (Spieler 0) whlt ein Typenprofil t T zufllig gem einer Wahrscheinlichkeitsverteilung p (T) (p ist eine a priori Verteilung)

(T) Menge aller Wahrscheinlichkeitsverteilungen auf T

Z = {z1, z2, z3} (Z) = {p = (p1, p2, p3) R3 | p s 0, p = 1, i = 1, 2, 3} i i- jeder Spieler i erfhrt eigenen Typ t (aber nicht ti -i)

- jeder Spieler i whlt eine Aktion a A (alle Spieler simultan) i i- Auszahlung von i hngt ab vom Aktionenprofil a = (a1, ..., an) und vom Typenprofil t = (t1, ..., tn):

u : AT R i

(a, t) # u (a, t) = u (ai i 1, , an; t , , t1 n)

=> G = {I, (A ), (T ), (u ), p} Normalform des BAYES-Spiels i i i

i = 2 prob(a) = 6

10 p(t

prob(b) = 4

10

prob(c) = 710

T1 = {a, b} T2 = {c, d} T = {ac, ad, bc, bd} prob(d) = 3

10

p = 5 1 2 2, , , 10 10 10 10

1, t2) t2 = c t2 = d

510

110

t1 = a i = 1

t1 = b 2

10 2

10

610

410

- 28 -


Sommersemester 2004

i = 1 erfhrt, dass er t1 = a ist, daher glaubt er ber i = 2:

5106

10

56

prob(t1 = c| t2 = a) = prob(c | a) = =

16

p(d | a) =

i = 2 p(t hier: Typen stochastisch unabhngig => eigener Typ

gibt keine Information ber anderen Typen

beliefs jeder Spieler i wei seinen eigenen Typ ti und bildet beliefs ber das Typenprofil des anderen t-i

gem der Regel von BAYES aus der a priori Verteilung p:

pi(t-i | ti) = i ii

p(t , t )p(t )

wo p(ti) die a priori Wahrscheinlichkeit von ti ist

= Wahrscheinlichkeit mit der Spieler i, wenn er selbst vom Typ ti ist, erwartete, dass der

andere das Profil t-i hat = beliefs

pi( | ti) (T-i)

Anmerkungen:

1. hufig ist es so, dass die Typen unabhngig sind => die beliefs ber die Typen der anderen sind

immer gleich => a posteriori belief = a priori belief

2. COMMON PRIOR: verschiedene beliefs mssen an unterschiedlichen Informationen liegen

(HARSANYI Theorem)

3. hufig ist es sinnvoll ui nur vom eigenen Typ abhngen zu lassen, trotzdem wird ui im allgemeinen

so ui(a1, a2; t1, t2) geschrieben

Def.: eine reine Strategie si fr Spieler i gibt fr jeden mglichen Typ ti Ti von Spieler i eine Aktion ai Ai an, d.h. si ist eine Funktion: si: Ti Ai ti # ai = si(ti)

Die Menge aller mglichen Strategien fr Spieler i Si ist die Menge aller Funktionen von Ti nach

Ai Si = iTiA

1, t2) t2 = c t2 = d

16

26

t1 = a i = 1

t1 = b 16

26

12

12

13

23

- 29 -


Sommersemester 2004

a = s (t ) ist die Aktion, die Spieler I zu tun plant, wenn er t ist i i i i wenn T und A beide endliche Mengen sind, dann ist auch S eine endliche Menge i i i

eine gemischte Strategie ist eine Wahrscheinlichkeitsverteilung auf S i) Menge aller gemischten Strategien (Si

s = (s1, ..., sn) S = Strategienprofil sn ii 1

S= -i S-i

Ablauf:

S- jeder Spieler whlt eine Strategie s (bevor er noch seinen Typ kennt) i i- Natur whlt Typenprofil t = (t1, ..., tn) T gem p - jeder Spieler i erfhrt seinen Typ t und spielt Aktion a = s (t ) i i i i- Auszahlung u (si 1(t1), ..., sn(tn); t) (ist Auszahlung, die ex post realisiert wird)

wenn ein Spieler i seine Aktion a whlt, wei er die Strategien si -i der anderen, aber nicht deren Typen

t-i, d.h. er kennt nicht die Auszahlungen, er wei nur die Wahrscheinlichkeitsverteilung p ( | ti i) ber die

Typen der anderen

T A ist und awenn Spieler i vom Typ ti i i i whlt und die anderen die Strategien s-i = (s1, ..., si-1, s , ..., si+1 n) spielen, dann ist is erwarteter payoff:

Ui(ai, s-i, t ) = . ui i

i i it T

p (t | t )

((si i 1(t1), ..., si-1(ti-1), a , s (t ), ..., si i+1 i+1 n(tn)), (t-i, t )) i

a = (a1, ..., a ) t n

Def.: eine Strategie ist eine beste Antwortis von Spieler i auf s-i, wenn fr alle mglichen Typen

t T von Spieler i gilt: U (i i i i is (t ) , s-i, t ) = U (a , sii ia A

max i i -i

, t ) i

a = i is (t )i fr jeden Typen maximiert diese Funktion den erwarteten

payoff

Def.: eine Strategienkombination s* = (s1*, ..., sn*) S ist ein BAYES-NASH-Gleichgewicht (in reinen Strategien) des BAYES-Spiels G = {I, (A ), p}, wenn fr jeden Spieler i I gilt: ), (T ), (ui i i s * ist beste Antwort auf si -i*

SATZ

in endlichen Spielen existiert immer ein BAYES-NASH-Gleichgewicht (mglicherweise in gemischten

Strategien)

- 30 -


Sommersemester 2004

Spiel in extensiver Form:

wenn i = 0 (Zufall) am Zug ist, whlt er einen Zug zufllig mit gegebenen Wahrscheinlichkeiten (sind

den anderen Spielern bekannt). i = 0 hat keinen payoff.

i = 2 wei nicht, was

Zufall gewhlt hat,

i = 1 schon

aa bb cc dd ee

i = 0

i = 1

= alternative Art Spiele mit unvollstndiger Information darzustellen

Perfektes BAYES-Gleichgewicht Beispiel

I1 = {a}

I2 = {b, c}

S1 = {L, M, R}

S2 = {L, R}

Normalform:

zwei NASH-Gleichgewichte:

s** = (L, L) mit payoff (2, 1)

s* = (R, R) mit payoff (1, 3)

echte Teilspiele => s*, s** teilspielperfekt

R ist eine unglaubwrdige Drohung: gegeben I2, dominiert L strikt R falls i = 2 zum Zug kommt, wird i = 2 L spielen i = 1 wird L spielen

sei G ein Spiel in extensiver Form (mit unvollkommener Information)

sei s = (s1, ..., sn) ein Strategieprofil: si schreibt fr jede Informationsmenge Ii von i einen Zug vor

ZIEL: Bedingungen an s, damit s ein vernnftiges (perfektes) Gleichgewicht ist

ALSO: sei s* = s1*, ..., sn*) ein NASH-Gleichgewicht (in der Normalform)

i = 2 L R

L 2, 1** 0, 0 M 0, 2 0, 3i = 1 R 1, 3 1, 3*

i 2 = i = 2

i = 1

RS

L

1/3 2/3

R L

I2

I2 R

i = 1

L

L M

21

03

00

02

L R

i = 2

R

R 13 a

b c

I1

2I

- 31 -


Sommersemester 2004

vier Bedingungen:

R.1 : Fr jede Informationsmenge I von Spieler i hat Spieler i beliefsi i darber an welchem Knoten

der Informationsmenge er sich befindet. Diese beliefs i sind eine Wahrscheinlichkeitsverteilung

ber den Knoten von I (I: ) i i iR.2 : Gegeben diese beliefs = (1, ..., n), sind die Strategien der Spieler sequentiell rational, d.h.

bei jeder Informationsmenge I eines Spielers i ist der durch seine Strategie si i vorgeschriebene

Zug - und auch alle folgende Zge des selben Spielers - optimal gegeben seiner beliefs und

gegeben die Strategie s-i aller anderen Spieler

z.B. 1(a) = 1 (weil die Informationsmenge I1 = {a} einen singleton darstellt)

I2 = {b, c}, 2(b) = p (c) = 1 - p

gegeben diese beliefs ist der erwartete payoff von i = 2

bei L so: 1 . p + 2(1 - p) = 2 - p

bei R so: 0 . p + 3(1 - p) = 3 - 3p ==> spielt L iff 2 - p 3 - 3p p 1/2 R.2

Def.: gegeben die Gleichgewichtsstrategie s* = (s1*, ..., sn*) liegt eine Informationsmenge auf dem

Gleichgewichtspfad (on the equilibrium path), wenn sie mit positiver Wahrscheinlichkeit erreicht

wird, falls die anderen Spieler gem s* spielen; sonst liegt sie nicht auf dem

Gleichgewichtspfad (off the equilibirum path)

R.3 : Bei Informationsmengen auf dem Gleichgewichtspfad werden die beliefs gem der Regel von

Bayes aus den Strategien abgelietet (rationale beliefs)

z.B. bei s* = (R, R): I2 ist nicht auf dem Gleichgewichtspfad

bei s* = (L, L): I2 liegt auf dem Gleichgewichtspfad

Knoten b wird mit Wahrscheinlichkeit p = 1 erreicht bei (L, L) ==>

R.3 2(b) = 1, 2(c) = 0

wenn es ein gemischtes Gleichgewicht gbe mit 1* = (qL, qM, q ) qR L, qM, q 0 R = 1, ist I qL + qM + qR 2 auf dem Gelcihgewichtspfad, wenn qL + qM > 0.

L2

L M

q (b)

q q= +

M2

L M

q (c)

q q= + In diesem Fall sind die beliefs von i = 2 so:

R.4 : bei Informationsmenge auerhalb des Gleichgewichtpfades werden die beliefs so weit wie

mglich nur noch aus den Gleichgewichtsstrategien nach der Regel von Bayes abgeleitet

(Beliefs auerhalb des Gleichgewichtspfade sind eine schwierige Frage)

- 32 -


Sommersemester 2004

Beispiel

Teilspiel ab b : i = 1

s* = (L, R)

=> s* = (D, L, R)

beliefs von i = 3 gegeben s*:

3(c) = 1

3(d) = 0

s* = (A, L, L) ist auch ein Gleichgewicht

beliefs von i = 3:

3(c) = p = 0

3(d) = 1 - p = 1

R.1 - R.3 erfllt, aber nicht R.4: 3(d) = 1 ist inkonsistent mit s2 = L

Def.: ein NASH-Gleichgewicht s* = (s1*, ..., sn*) eines Spiels in extensiver Form heit perfektes

BAYES-Gleichgewicht, wenn die beliefs * = (1*, ..., n*) fr die Spieler existieren, sodass

(s*, *) R.1 bis R.4 erfllt

THEORIE VOM ERWARTETEN NUTZEN

Risiko: objektive Wahrscheinlichkeiten (Roulette Lotterie)

Unsicherheit: keine objektiven Wahrscheinlichkeiten (horse Lotterie) (KNIGHT)

subjektive Wahrscheinlichkeiten (SAVAGE)

1. Entscheidung bei Sicherheit X Menge von mglichen Alternativen (outcomes)

Prferenzordnung auf X : vollstndige transitive binre Relation auf X vollstndig: x, y X gilt: x y oder y x (oder beides) transitiv: x y und y z => x z

i = 2 L R

L 2, 1 3, 3* i = 1 R 1, 2 1, 1

1/2 1/2 L R

T 10, 5 0, 4 B -5, 3 20, -7

d L

L R

L R

121

011

333

012

i = 3

R

200

c

A

a D i = 2

b

p 1-p

1/2

T

1/2

1/2 10

0

B

1/2 -5

20

- 33 -


Sommersemester 2004

x y schwach vorgezogen

x ~ y indifferent [x y und y x] x y strikt vorgezogen [x y aber nicht y x]

sei gegeben B X Menge tatschlich verfgbarer Alternativen (z.B. Budgetmenge) (Nebenbedingung, constraint set)

Def.: z B heit grtes (bestes) Elemente von B bezglich , wenn z x x B (B, ) := {z B | z x x B} Auswahlmenge Prinzip der rationalen Wahl: whle z (B) (Optimierung unter Nebenbedingungen) Def.: eine Funktion u: X R reprsentiert die Prferenzordnung , wenn gilt: x # u(x)

x y u(x) s u(y)

u (ordinale) Nutzenfunktion fr z (B) u(z) s u(x) x B und z B u(z) = max u(x) Nutzenmaximierung x

(ist das selbe wie das Prinzip der rationalen Wahl wenn u(x) existiert)

2. Entscheidung bei Unsicherheit Alternativen a Lotterien (Prospekte) ber der ursprnglichen Menge X

z.B.

a gibt daund das Ergebnis (Preis - prize) mit Wahrscheinlichkeit p s Ergebnis y mit Wahrscheinlichkeit 1 - p

Notation:

1-p

p x

y

x ya

p 1 p =

a

allgemein:

gibt Ergebnis x1 2 n1 2 n

x x ... xa

p p ... p = i

X mit Wahrscheinlichkeit pi

sei A0 die Menge aller solcher (einstufigen) Lotterien

speziell: gibt x mit Wahrscheinlichkeit 1 quivalent zum Ergebnis x selbst x

a1

= X A0

p2a

p1 1

xn

xx2

p3 (p s 0 p + pi 1 2 + ... + pn = 1)

- 34 -


Sommersemester 2004

noch allgemeiner:

seien a1, a2, ..., ak A Lotterien 0

gibt a1 2 n1 2 n

a a ... aa

p p ... p =

mit Wahrscheinlichkeit p i i

zweistufige Lotterie (eine Lotterie, deren Preise selbst wieder Lotterien sind)

sei A Menge aller solchen Lotterien

klar: A0 A a1aa 1 = 1

A0

Annahme: der Entscheidungstrger hat eine Prferenzordnung auf A. Anmerkung: insbesondere hat er eine Prferenzordnung auf X (letztlich Konsequenzen)

nmlich: x y x1

y1

Beispiel

Prferenzen der Studenten

a 3000 a b

0,2

b

0,8 4000

0

1

c d

e f

wenn a b, dann muss auch e f, denn wenn die Sonne nicht scheint sind e und f gleich ( hat keinen Einflu auf die Entscheidung) und wenn die Sonne scheint, ist die Wahl zwischen e und f

gleich der Wahl zwischen a und b.

Rationalittspostulate fr auf A x, y, z Xi; a, b A; p, q, r Wahrscheinlichkeiten

(A.1) sei x y, dann gilt: x yp 1 p

x yq 1 q

p > q

0, 5 0 7

c

25 3000 0,

0,8

0,2 4000

d

0

0, 5

0, a

0 7

e

25

c ~

0, 5

0, b

0

d ~

7

f

25

- 35 -


Sommersemester 2004

x yp 1 p

(A.2) sei x y z. Dann p, sodass y ~ [Stetigkeit]

(A.3) zweistufige Lotterien: sei a = und b = , dann gilt:

wo r = p . p

1 1

x yp 1 p

2 2

x yp 1 p

a b x y

~p 1 p r 1 r

1 + (1 - p)p2

1-p1

a

p1x

y

1-p2

b

p2x

y

1 - p

p

(A.4) sei a ~ b, dann gilt: [Unabhngigkeit] a c b c

~p 1 p p 1 p

U: X R Nutzenfunktion fr , wenn a b ua s ubes sei u: X R eine Funktion definiert fr Konsequenzen

sei eine Lotterie 1 2 n1 2 n

x x ... xa

p p ... p =

Def.: Eu(a) := Erwartungswert von u bei Lotterie a, erwarteter Nutzen von a n ii 1

p u(x )=

i

speziell: a = Eu(a) = 1 . u(x) = u(x) x1

z.B. a = Eu(a) = p . x + (1 - p)y x yp 1 p

verallgemeinert: (zweistufig) Eu(a) = 1 2 k1 2 k

a a ... aa

p p ... p =

ki i

i 1p Eu(a )

=

beachte: U := Eu ist eine Funktion A R a # U(a) := Eu

SATZ (vom erwarteten Nutzen [expected utility])

wenn die Prferenzordnung auf A die Axiome A.1 bis A.4 erfllt, dann eine Funktion u: X R derart, dass der zugehrige erwartete Nutzen U = Eu eine Nutzenfunktion fr auf A darstellt, d.h. fr alle Lotterien a, b A gilt: a b Eu(a) s Eu(b) Die Funktion u heit von NEUMANN-MORGENSTERN Nutzenfunktion (vNM) oder

Risikonutzenfunktion.

- 36 -


Sommersemester 2004

xX Beweis: sei x x x) = 0 def.: u( x

u( ) = 1 x

sei x X beliebig nach A.1, A.2 eine eindeutige Zahl px, 0 c px c 1, sodass

x ~

x

x1 - px

px

Def.: u(x) := px xX

sei 1-p

p x

y

a

, ): zurckfhren auf quivalente Extremlotterie (mit Preisen x x

x ~ b y ~ c

x

x1 - u(x)

u(x) x

x1 - u(y)

u(y)

nach A.4 ist

~ ~ ~ =

b

u(x) x

x

c

u(y) x

x

x

x

p.u(x)+(1-p).u(y)

= Eu(a) = p . u(x) + (1 - p) . u(y)

1-p

p x

y

b

y

a

x

x

Eu(a)

- 37 -


Sommersemester 2004

sei x

x

Eu(a)

~ .......... ~ 1-p

a

p x

y

nach A.1: a a Eu(a) s Eu(a)

Anmerkung: Eu beliebig transformierbar, u eindeutig bestimmt bis auf Nullpunkt und Einheit ( nicht beliebig transformierbar - v(x) = . u(x) + mit > 0 ist erlaubt

konomische Anwendung: Versicherungen, Portfolio - Finanzmrkte

- 38 -

Beispiele fr MatrixspieleGefangenen-DilemmaChicken Game

Documents

Mitschrift Entscheidungs- und Spieltheorie 2004