3. Dynamische Spiele mit vollständiger Information · Abb. 3.1: Ein Spielbaum Klaus M. Schmidt (LMU München) 3. Dynamische Spiele mit vollständiger Information Spieltheorie, Wintersemester

3. Dynamische Spiele mit vollständigerInformation

Klaus M. Schmidt

LMU München

Spieltheorie, Wintersemester 2014/15

Klaus M. Schmidt (LMU München) 3. Dynamische Spiele mit vollständiger Information Spieltheorie, Wintersemester 2014/15 1 / 72

Literaturhinweise zu Kapitel 3:

Osborne (2004), Kapitel 5-7

Gibbons (1992), Kapitel 2

MasColell, Whinston, Green (1995), Kapitel 7 und 9A+B

Fudenberg und Tirole (1991), Kapitel 3 und 4

c© 2014 Klaus M. Schmidt


3.1 Dynamische Spiele und Rückwärtsinduktion

Bisher haben wir Situationen betrachtet, in denen beide Parteien simultanüber ihre Strategie entscheiden müssen.

Jetzt betrachten wir etwas kompliziertere zeitliche Strukturen. Dabeibeschränken wir uns zunächst auf Spiele mit vollständiger und perfekterInformation, d.h., alle Spieler spielen sequentiell und jeder Spielerbeobachtet alle vorangegangenen Züge.


Die Zeitstruktur eines Spiels

u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

Spieler 1

Spieler 2Spieler 2

Aktion 1 Aktion 2

Aktion 3 Aktion 4 Aktion 3 Aktion 4

( ab

) ( cd

) ( ef

) ( gh

)Abb. 3.1: Ein Spielbaum


Beispiel 1: IBM vs. Intel

In den frühen 70er Jahren ist Intel der einzige Lieferant von IBM fürbestimmte Computerchips.IBM steht vor der Wahl, entweder Intel als einzigen Lieferanten zubehalten oder einen zweiten Lieferanten (AMD) aufzubauen.Ohne einen zweiten Lieferanten kann Intel seine Monopolmachtausnutzen. Dann würde IBM einen Gewinn von 10 und Intel einenGewinn von 90 erhalten.Intel kündigt jedoch an, auf das Ausnutzen der Monopolstellung zuverzichten und die Gewinne gleichmäßig aufzuteilen (jeder bekommteinen Gewinn von 50).Wenn sich IBM entscheidet, AMD als zweiten Lieferanten aufzubauen,erhält IBM einen Gewinn von 40 und Intel einen Gewinn von 30.

Sollte IBM eine zweite Lieferantenbeziehung aufbauen oder daraufverzichten?


Zeichnen Sie den Spielbaum für dieses Spiel.


Bestimmen Sie die Normalform für dieses Spiel.


Beispiel 2: Marktzutrittsspiel

u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................

Zutreter

Monopolist

N E

k n(

02

)(−1−1

) (21

)Abb. 3.2: Marktzutrittsspiel

Der Marktzutreter entscheidet, ob er eintritt (E) oder nicht (N).Der Monopolist entscheidet, ob er kämpft (k) oder nicht kämpft und sichden Markt teilt (n).


Ein sequentielles Spiel mit endlich vielen Stufen und perfekter Informationwird durch Rückwärtsinduktion gelöst.

Monopolist: Gegeben, dass der Zutreter eingetreten ist, ist es für michoptimal den Markt zu teilen.

Zutreter: Wenn ich zutrete, wird der Monopolist den Markt teilen. Alsosollte ich zutreten.

Das Ergebnis der Rückwärtsinduktion ist also (E ,n).


Rückwärtsinduktion und Nash-Gleichgewicht

Das Ergebnis der Rückwärtsinduktion ist ein Nash-GG:Gegeben, dass der Zutreter E spielt, ist für den Monopolisten n optimal.Gegeben, dass der Monopolist n spielt, ist für den Zutreter E optimal.

@@

@

Z

M

N

E

k n

0, 2 0, 2

-1, -1 2, 1

Abb. 3.3: Normalform des Marktzutrittsspiels


Analyse der Normalform zeigt ein zweites Nash-GG gibt: (N, k).

In diesem Nash-GG ist die Strategie des Monopolisten nicht optimal, wenn derZutreter E spielen sollte. Aber: Im Nash-GG (N, k) tritt der Zutreter nicht ein.

Trotzdem ist das Nash-GG (N, k) nicht überzeugend. Der Monopolist “droht”,zu kämpfen, falls der Zutreter zutritt. Diese Drohung ist unglaubwürd, weil esnicht im Interesse des Monopolisten liegt, sie im Fall des Zutritts tasächlichwahr zu machen.

Die Unglaubwürdigkeit einer Drohung lässt sich aus der Normalform desSpiels nicht erkennen. Darum werden wir bei dynamischen Spielen dieextensive Form des Spiels betrachten, die die Zeit- und Informationsstrukturexplizit macht.

Ziel: Verfeinerung des Nash-Gleichgewichts Wir wollen denGleichgewichtsbegriff so verschärfen, dass Gleichgewichte keineunglaubwürdigen Drohungen enthalten können.

Bevor wir das tun, werden wir aber ein paar weitere Anwendungsbeispiele fürRückwärtsinduktion betrachten.


3.2 Anwendungsbeispiele für Rückwärtsinduktion

3.2.1 Stackelberg-Duopol

Heinrich von Stackelberg (1934)1) Unternehmen 1, der Stackelberg-Führer, wählt seine Menge x1.2) Unternehmen 2, der Stackelberg-Anpasser, beobachtet x1 und wählt

dann seine Menge x2.3) Auf dem Markt ergibt sich der Preis als Funktion der gesamten Menge:

p = p(x1 + x2).Dieses Modell wird oft verwendet, wenn es auf einem Markt einen dominantenAnbieter gibt, an den alle übrigen Anbieter ihr Verhalten anpassen.

Beispiele:Saudi-Arabien als größter Ölproduzent legt seine Menge als erster fest.Andere Ölproduzenten passen sich an.Südafrika: Dominierender Diamantenproduzent De Beers.Andere Marktführer: Microsoft, IBM, Telekom etc., aber hier geht esmeist um Preis- und/oder Qualitätswettbewerb bei heterogenen Gütern.


Das Entscheidungsproblem des Anpassers

Der Anpasser maximiert seinen Gewinn

π2 = p(x1 + x2)x2 − c2(x2)

durch geeignete Wahl von x2. Dabei liegt die Menge x1 bereits fest und istbekannt.

Bedingung erster Ordnung (BEO) für Gewinnmaximum:

p(x1 + x∗2 ) +dp(x1 + x∗2 )

dx2x2 =

dc2(x∗2 )dx2

Diese Bedingung legt die optimale Menge x∗2 als Funktion von x1 fest, d.h.:

x∗2 = R2(x1)

Die Funktion R2(x1) wird Reaktionsfunktion von Unternehmen 2 genannt.


Beispiel:Lineare Nachfrage: p(x1 + x2) = a− b · (x1 + x2) = a− b · x , x = x1 + x2

Konstante Grenzkosten: c1(x1) = c · x1, c2(x2) = c · x2

Gewinnfunktion des Anpassers:

π2 = [a− b(x1 + x2)] · x2 − c · x2

BEO für Gewinnmaximum:

a− b(x1 + x2)− bx2 = c

Gewinnfunktion ist streng konkav:

d2π2

dx22

= −2b < 0

Reaktionsfunktion des Anpassers:

x2 =a− bx1 − c

2b=

a− c2b

− 12

x1


Das Problem des Marktführers

Der Marktführer kennt das Entscheidungsproblem des Anpassers und weiß,dass er die Menge x∗2 = R2(x1) wählen wird. Also ist seinGewinnmaximierungsproblem:

maxx1

p(x1 + R2(x1)) · x1 − c1(x1)


p(x∗1 + R2(x∗1 )) +(

1 +dR2

dx1

)dpdx

x∗1 =dc1

dx1

Der Stackelberg-Führer berücksichtigt nicht nur, wie eine zusätzliche Einheitden Martkpreis direkt senkt, sondern auch, wie sie die Menge seinesKonkurrenten und damit indirekt den Marktpreis beeinflusst.


Fortsetzung des Beispiels:

Gewinnfunktion des Marktführers:

π1 = [a− b(x1 + R2(x1))] · x1 − c · x1

=a− c

2· x1 −

b2· x2

1


a− c2− bx∗1 = 0

x∗1 =a− c

2b


Nachdem wir die optimale Menge des Stackelberg-Führers kennen, könnenwir sie in die Reaktionsfunktion des Anpassers einsetzen, um dessen Menge,die gesamte Menge und den Marktpreis zu bestimmen.

Einsetzen von x∗1 in R2(x1) ergibt:

x∗2 =a− c

4b

Die gesamte Menge ist also:

x1 + x2 =3(a− c)

4b

Der Marktpreis ergibt sich als:

p∗ =a + 3c

4


Vergleich zum Cournot-Duopol

Der Gewinn des Stackelberg-Führers ist immer höher als der Gewinneines Cournot-Duopolisten. Warum?Im Stackelberg-Spiel ist der Anpasser besser informiert als ein Duopolistim Cournot-Spiel. Er kann beobachten, welche Menge derStackelberg-Führer auf den Markt wirft. Trotzdem geht es dem Anpasserschlechter als dem Cournot-Duopolisten. Warum?In Ein-Personen-Entscheidungssituationen ist es unmöglich, dass sichein rationaler Entscheidungsträger schlechter stellt, wenn er zusätzlicheInformationen oder zusätzliche Handlungsmöglichkeiten bekommt.In interpersonellen Entscheidungssituationen ist es dagegen oft besser,weniger Informationen oder weniger Handlungsmöglichkeiten zu haben.Beispiele:

I Cournot- versus Stackelberg-Spiel.I Chicken-Spiel: Angenommen, einer der Fahrer kann sein Lenkrad aus dem

Fenster werfen und sich damit die Möglichkeit zum Ausweichen nehmen.⇒ Gegenspieler wird ausweichen.

I Viele andere Beispiele für Selbstbindung (Commitment).


3.2.2 Löhne und Beschäftigung

Leontief (1946), später in zahlreichen Variationen.

Zweistufiges Spiel:1. Gewerkschaft bestimmt den Lohnsatz, w .2. Unternehmen bestimmt die Beschäftigungsmenge, L.

Auszahlungsfunktionen:Gewerkschaft:

U(w ,L),

streng monoton steigend in w und L, quasikonkav (konvexeIndifferenzkurven)Unternehmen:

π(w ,L) = R(L)− wL,

R(L) steigend und streng konkav, limL→0 R′(L) =∞, limL→∞ R′(L) = 0.


Rückwärtsinduktion

Stufe 2: Unternehmen maximiert

maxL≥0

R(L)− wL

BEO (hier notwendig und hinreichend, warum?):

R′(L)− w = 0

Die optimale Beschäftigungsmenge L∗(w) ist eine fallende Funktion von w .(Warum?)

Isogewinnlinien:

R(L)− wL = c ⇒ w =R(L)− c

L


. ....................................................................................................................................................................................................................................................................................................

............................................................................................................................................................................................................................................................................................................................................ . ................ ...............

................ ................

L

R

...............................

............................

...........................

.........................

..............................................

.........................................

..........................................

...................... ....................... ....................... ........................ ......................... ..........................

.......... ........... ............................

.....................................

..............................................

......................................................

..............................................................

..................................

....................................

. ....................................................................................................................................................................................................................................................................................................

............................................................................................................................................................................................................................................................................................................................................ . ................ ...............

................ ................

L

w

Abb. 3.4: Gewinnmaximum und Isogewinnlinien der Unternehmung


Stufe 2: Gewerkschaft antizipiert L∗(w) und maximiert

maxw≥0

U(w ,L∗(w))

BEO:∂U∂w

+∂U∂L

dL∗(w)

dw= 0


. ....................................................................................................................................................................................................................................................................................................

............................................................................................................................................................................................................................................................................................................................................ . ................ ...............

................ ................

L

w

. ....................................................................................................................................................................................................................................................................................................

............................................................................................................................................................................................................................................................................................................................................ . ................ ...............

................ ................

L

w

Abb. 3.5: Nutzenmaximum der Gewerkschaft, Ineffizienz


Bemerkungen:

1) Gewerkschaft sucht sich den besten Punkt auf der Reaktionsfunktion desUnternehmens.

2) Aber das Ergebnis ist ineffizient: Gewerkschaften und Unternehmenkönnten sich besser stellen, wenn sie den Lohn etwas verringerten unddie Beschäftigung etwas erhöhten.

3) Die Ineffizienz besteht, weil Gewerkschaft und Unternehmen nicht überBeschäftigung und Lohnhöhe gleichzeitig verhandeln. Warum wird dasnicht gemacht?


3.3 Allgemeine Beschreibung eines dynamischen Spiels

3.3.1 Die Extensive Form

Definition 3.1 (Extensive Form)Die extensive Form eines Spiels spezifiziert:

(1) die Menge der Spieler {1, . . . ,n};(2a) zu welchem Zeitpunkt welcher Spieler am Zug ist;(2b) welche Aktionen einem Spieler zur Verfügung stehen, wenn er

am Zug ist;(2c) was ein Spieler weiß, wenn er am Zug ist;(3) die Auszahlung eines jeden Spielers für jede mögliche

Kombination von Zügen.

Die Definition der extensiven Form ist ganz analog zu der der Normalform.Einziger Unterschied: Die Beschreibung der Strategienräume kann sehr vielkomplexer sein.


Spiele in extensiver Form können mit Hilfe eines Spielbaums beschriebenwerden.

Ein Spielbaum besteht aus einer Menge von geordneten und miteinanderverbundenen Knoten:

Entscheidungsknoten: Hier kann genau ein Spieler aus einer Mengevon Aktionen auswählen. Jede Aktion führt zu einem neuenEntscheidungs- oder Endknoten.Endknoten: Hier endet das Spiel, und Auszahlungen werdenzugeordnet.

Der Spielbaum beginnt mit genau einem Anfangs-Entscheidungsknoten.Wir werden immer annehmen, dass ein Spielbaum sich echt verzweigt:

Er wächst nicht in sich selbst zurück (keine Zyklen);Zweige wachsen nicht wieder zusammen (keine gemeinsamenVorgänger).

Gegenbeispiele?


3.3.2 Zufallszüge der Natur

In vielen Spielen gibt es exogene Unsicherheit.

Wir können das modellieren, indem wir einen zusätzlichen Spieler, die“Natur”, einführen, die aus der Menge der möglichen Zustände der Welt einennach einer gegebenen Wahrscheinlichkeitsverteilung auswählt.

u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................

u...................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

.........................

Z

Natur

M M

N E

12

12

k n k n

(02

)

(00

) (33

) (−1−1

) (11

)Abb. 3.6: Marktzutrittsspiel mit exogener Unsicherheit


Nach der Zutrittsentscheidung realisiert sich der Zustand der Welt:

Mit Wahrscheinlichkeit 12 ist die Nachfrage groß, beide können hohe

Gewinne machen.

Mit Wahrscheinlichkeit 12 ist die Nachfrage niedrig, beide machen bei

Wettbewerb Verluste.

Die Natur verhält sich nicht strategisch, sondern folgt einfach dervorgegebenen Wahrscheinlichkeitsverteilung.


3.3.3 Informationsmengen

Definition 3.2 (Informationsmenge)Eine Informationsmenge ist eine Menge von Entscheidungsknoten mit denEigenschaften:

Bei allen Entscheidungsknoten einer Informationsmenge ist derselbeSpieler am Zug.Ein Spieler kann die verschiedenen Knoten einer Informationsmengenicht unterscheiden. Insbesondere hat er an jedem Knoten einerInformationsmenge dieselbe Menge von Aktionen.

Jeder Entscheidungsknoten gehört zu genau einer Informationsmenge.


Beispiele:

u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

1

22

G L

g `g `

(−3−3

) (0−5

) (−50

) (−1−1

)Abb. 3.7: Das Gefangenen-Dilemma


u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

u...................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

.........................

1

2 2

1 1 1 1

Abb. 3.8: Mögliche und unmögliche Informationsmengen

Wenn ein Spiel nur einelementige Informationsmengen enthält, sprechen wirvon einem Spiel mit perfekter Information (nicht zu verwechseln mitvollständiger Information).

Gibt es mehrelementige Informationsmengen, sprechen wir von einem Spielmit imperfekter Information (nicht zu verwechseln mit unvollständigerInformation).


3.3.4 Strategien

Definition 3.3 (Strategie)Eine Strategie ist ein vollständig konditionierter Aktionsplan: Für jedeInformationsmenge, in der der Spieler am Zug ist, spezifiziert die Strategieeine mögliche Aktion, d.h., sie konditioniert die Aktion auf die von Spieler ibeobachtete bisherige Geschichte des Spiels.


Beispiele:

u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

1

22

L R

` r` r

(31

) (12

) (21

) (00

)Abb. 3.9: Strategien in einem Spiel mit perfekter Information

Spieler 1 hat 2 Strategien: L, RSpieler 2 hat 4 Strategien: ``, `r , r`, rr


@@

@

1

2

L

R

`` `r r` rr

3, 1 3, 1 1, 2 1, 2

2, 1 0, 0 2, 1 0, 0

Abb. 3.10: Normalform dieses Spiels


u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

u...................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

.........................

1

2 2

1 1 1 1

L R

` r` r

L′ R′ L′ R′ L′′ R′′ L′′ R′′

Abb. 3.11: Strategien in einem Spiel mit imperfekter Information

Strategien von Spieler 1:

Strategien von Spieler 2:

Jedes Spiel in extensiver Form kann in ein Spiel in Normalform überführtwerden.Aber: Zu einem Spiel in Normalform können mehrere verschiedene Spiele inextensiver Form existieren.


3.4 Teilspielperfekte Gleichgewichte

Definition 3.4 (Teilspiel)Ein Teilspiel eines Spiels in extensiver Forma) beginnt in einem Entscheidungsknoten K einer einelementigen

Informationsmenge,b) beinhaltet alle Entscheidungs- und Endknoten, die K nachfolgen, aber

keine Knoten, die K nicht nachfolgen,c) durchtrennt keine nachfolgenden Informationsmengen.

Intuitiv ist ein Teilspiel einfach ein Teil des gesamten Spiel, der in einemKnoten beginnt und alle nachfolgenden Knoten enthält. An diesem Knotenmuss die gesamte bisherige Geschichte des Spiels dem Spieler, der hier amZug ist, bekannt sein.


u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

u...................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

......................... u.

..................................................................................................

....................................

....................................

.........................

1

2 2

1 1 1 1

L R

` r` r

L′ R′ L′ R′ L′′ R′′ L′′ R′′

Abb. 3.12: Teilspiele

Ein Teilspiel kann isoliert betrachtet und analysiert werden.


Teilspielperfektes Gleichgewicht

Das folgende Gleichgewichtskonzept geht auf Reinhard Selten (1965) zurück.

Definition 3.5 (Teilspielperfektes Gleichgewicht)Ein Nash-Gleichgewicht ist teilspielperfekt, wenn die Strategien der Spieler injedem Teilspiel ein Nash-Gleichgewicht bilden.


u.....................................

........................................................................

........................................................................

...............

........................................................................

........................................................................

..................................................

u......................

..........................................

..........................................

.......

..........................................

..........................................

...........................u.

..........................................

..........................................

............................

..........................................

..........................................

...........................

1

22

L R

` r` r

(31

) (12

) (21

) (00

)Abb. 3.13: Teilspielperfektes Nash-Gleichgewicht


Analyse der Teilspiele:Gegeben, dass Spieler 1 L gewählt hat, sollte 2 r spielen.Gegeben, dass Spieler 1 R gewählt hat, sollte 2 ` spielen.Gegeben das Verhalten von 2 sollte 1 R spielen.

Das teilspielperfekte Nash-Gleichgewicht ist (R, r`).

Beachten Sie:Der Gleichgewichtspfad ist (R, `).Aber: Das Gleichgewicht muss auch angeben, was außerhalb desGleichgewichtspfades passieren würde. Darum ist das Gleichgewicht(R, r`).Es existiert ein zweites Nash-Gleichgewicht: (L, rr). Aber diesesNash-GG ist nicht teilspielperfekt. Es enthält die unglaubwürdigeDrohung, dass Spieler 2 r spielt, sollte Spieler 1 R spielen.Teilspielperfektheit ist nicht nur für Spiele mit perfekter Information,sondern auch für beliebige Spiele mit imperfekter Informationwohldefiniert.


Satz 3.1 (Existenz des TPGGs)Jedes endliche Spiel in extensiver Form hat wenigstens ein teilspielperfektesNash-Gleichgewicht.

Beweis von Satz 3.1:


Satz 3.2 (Eindeutigkeit des TPGGs)(Fast) jedes endliche Spiel in extensiver Form mit perfekter Information hat eineindeutiges teilspielperfektes Nash-Gleichgewicht.



Bemerkungen:

1. Dieser Satz wurde schon von Zermelo (1913) bewiesen.

2. Bei Spielen mit imperfekter Information kann es natürlich mehrereGleichgewichte in einem Teilspiel geben. Die Menge allerteilspielperfekten Gleichgewichte im gesamten Spiel erhält man, wennman die Rückwärtsinduktion mit jeder möglichen Kombination allermöglichen Gleichgewichte durchführt.


Beispiel: Ein Spiel mit imperfekter InformationBetrachten Sie das folgende Spiel mit zwei Perioden, bei dem die Spieler inder ersten Periode ein Gefangenen-Dilemma und in der zweiten Periode einKoordinationsspiel spielen:

@@

@

A

B

Kooperation

Verrat

Kooperation Verrat

2, 2 -1, 3

3, -1 0, 0


@@

@

A

B

L

R

` r

x, x 0, 0

0, 0 y, y

Abb. 3.14: TPGG eines Spiels mit imperfekter Information

Was sind die teilspielperfekten Gleichgewichte dieses Spiels? Unter welcherAnnahme an x und y kann ein teilspielperfektes Gleichgewicht gestütztwerden, bei dem die beiden Spieler in der ersten Periode kooperieren?


3.5 Teilspielperfektheit und Rationalität

Teilspielperfektheit erfordert, dass es “Common Knowledge” ist, dass alleSpieler rational sind. Betrachten Sie das folgende Spiel:

u.

..........................................

..........................................

..........................................

..........................................

..........................................

..........................................

..........................................

.......................................

..........................................

..........................................

...........................

.

..........................................

..........................................

...........................

.

..........................................

..........................................

...........................

uu

1

2

1

L R

` r

L′ R′

(20

)(

11

)(

30

) (02

)Abb. 3.15: Rationalität und Rückwärtsinduktion


Rückwärtsinduktion ergibt, dass Spieler 1 L spielen und das Spiel damitbeenden sollte. Begründung: Wenn Spieler 1 R spielt, sollte Spieler 2 `spielen, denn würde er r spielen, würde Spieler 1 in der letzten Runde L′

spielen.

Angenommen, Spieler 1 spielt dennoch R.

Zeigt er damit nicht, dass er irrational ist?

Wenn Spieler 1 aber irrational ist, sollte Spieler 2 dann nicht vielleichtdoch lieber r spielen, in der Hoffnung, dass Spieler 1 sich in der letztenRunde ebenfalls irrational verhält und R′ spielt?

Wenn Spieler 2 durch diese Argumentation verleitet wird, r zu spielen,sollte dann nicht auch ein rationaler Spieler 1 R in Runde 1 spielen?


Rückwärtsinduktion ist nur solange überzeugend, solange Abweichungenvom Rückwärtsinduktionspfad rational erklärt werden können. Das hat Selten(1975) motiviert, das Konzept des “perfekten Gleichgewichts” einzuführen:1) Es ist common knowledge, dass beide Spieler rational sind.2) Aber: Beide Spieler machen mit sehr kleinen Wahrscheinlichkeiten

Fehler: ihre Hände zittern bei der Auswahl der Strategien. MitWahrscheinlichkeit 1− ε spielt jeder Spieler die intendierte Strategie,aber mit Wahrscheinlichkeit ε macht er einen Fehler und wählt eineandere (zufällig ausgewählte) Strategie. Die Wahl von R kann dann alsnicht intendierter Fehler von 1 interpretiert werden und bedeutet nicht,dass 1 irrational ist.

3) Ein perfektes Gleichgewicht ist der Limes einer Folge vonGleichgewichten, in denen jeder Spieler mit Wahrscheinlichkeit ε einenFehler macht, wenn ε gegen 0 konvergiert.

Beachten Sie: Wenn jeder Spieler nur einmal zieht, tauchen diese Problemenicht auf.


Rosenthals Hundertfüßler

Das folgende Spiel zeigt noch einmal, dass Teilspielperfektheit nicht immerplausibel sein muss.

u u u. ................................................................................................................................................................................................................ . ...................................................................................................................................................................................................................................................................... u u u.

................

................

................

................

................

................

........ .

................

................

................

................

................

................

........ .

................

................

................

................

................

................

........ .

................

................

................

................

................

................

........ .

................

................

................

................

................

................

........ .

................

................

................

................

................

................

........1 2 1 2 1 2

w

s

w

s

w

s

w

s

w

s

w

s

(11

) (03

) (22

) (97100

) (9999

) (98

101

)

(100100

)

Abb. 3.16: Rosenthals Hundertfüßler


Das eindeutige TPGG ist, dass jeder Spieler das Spiel beendet, wenn er zumZug kommt.

Was passiert, wenn Spieler 1 das Spiel in Periode 1 nicht beendet?

Sollte Spieler 2 sich dennoch an das Gleichgewicht halten?

Ob das TPGG überzeugend ist oder nicht, hängt entscheidend davon ab, wiedie Spieler Abweichungen vom Gleichgewichtspfad interpretieren.


3.6 Ein Zermürbungskrieg

Das klassische Beispiel für einen Zermürbungskrieg stammt aus der Biologie(Maynard Smith, 1974): Kampf zweier Tiere um ein Territorium.

Wir betrachten dieses Spiel nur in diskreter Zeit mit unendlichem Horizont:Folge von Zeitpunkten: t = 0,1,2, . . .In jeder Periode entscheiden beide Spieler simultan, ob sie “kämpfen”oder “aufgeben” sollen.Wenn beide kämpfen, verlieren beide eine Nutzeneinheit pro Periode,und das Spiel geht weiter.Wenn einer aufgibt, der andere aber nicht, erhält der Gewinner einenPreis im Wert v , der Verlierer nichts, und das Spiel ist zu Ende.Wenn beide gleichzeitig aufgeben, sind beide Verlierer und erhaltenbeide nichts.


Auszahlungen:

Sei t die Periode, in der der Verlierer aufgegeben hat.

Verlierer:

uv (t) = −(1 + δ + · · ·+ δ t−1) · 1 = − 1− δ t

1− δGewinner:

ug (t) = −(1 + δ + · · ·+ δ t−1) · 1 + δ tv = − 1− δ t

1− δ+ δ tv

Existiert ein symmetrisches, stationäres TPGG?


Angenommen beide Spieler geben in jeder Periode mit Wahrscheinlichkeit pauf und kämpfen mit Wahrscheinlichkeit 1− p.

Diese Strategien sind nur dann ein Gleichgewicht, wenn jeder Spieler in jederPeriode indifferent ist, ob er aufgeben oder weiterkämpfen soll. Also muss injeder Periode t gelten:

0 = p v + (1− p) · [−1 + δ · 0]

Interpretation:Die bisher verlorenen Nutzeneinheiten sind “sunk costs”. Wir brauchenalso nur Auszahlungen zu betrachten, die von der jetzigen Periode anerhalten werden.

0 ist die Auszahlung, wenn ich heute aufgebe.


Wenn ich nicht aufgebe, gibt es zwei Möglichkeiten:I Mit Wahrscheinlichkeit p gibt mein Gegner auf und ich bekomme v .I Mit Wahrscheinlichkeit 1− p gibt er nicht auf, was mich diese Runde eine

Nutzeneinheit kostet. In der nächsten Runde bin ich dann wieder indifferentzwischen Aufgeben und Kämpfen. Also ist der Folge-Payoff ab der nächstenRunde genau 0.

Auflösen ergibt:

p∗ =1

1 + v


Bemerkungen:

1) Je höher der Preis v , umso kleiner ist die Wahrscheinlichkeit desAufgebens.

2) Das Ergebnis ist ineffizient, weil mit positiver Wahrscheinlichkeitgekämpft wird. Mit positiver Wahrscheinlichkeit sind die Kosten desKämpfens sogar höher als der zu gewinnende Preis.

3) Es gibt noch andere TPGG. Beispiel: Spieler 1 wird immer kämpfen,Spieler 2 wird immer aufgeben. Insbesondere sind alle stationärenNash-Gleichgewichte auch teilspielperfekt.

4) Aber: Das Gleichgewicht, dass wir oben charakterisiert haben, ist daseinzige symmetrische Gleichgewicht.


3.7 Das “Einmal-Abweichungsprinzip”

In den bisherigen Beispielen war es relativ einfach zu prüfen, ob einStrategientupel (s∗1 , . . . , s

∗n) ein TPGG ist. In komplizierteren Spielen kann das

jedoch sehr aufwendig sein. Der folgende Satz macht uns das Lebenerheblich leichter:

Satz 3.3 (Einmal-Abweichungsprinzip)Ein Strategientupel s∗ ist teilspielperfekt genau dann, wenn es für keinenSpieler i eine Strategie si gibt, die sich von s∗i nur in einer Periode t und nacheiner Geschichte ht unterscheidet, und die echt besser ist als s∗i , wenn dasTeilspiel nach ht erreicht wird.


Bemerkungen:1) Es ist offensichtlich, dass die Bedingung notwendig für

Teilspielperfektheit ist. Gäbe es eine solche profitableAbweichungsstrategie si , dann kann sicher kein TPGG vorliegen.(Achtung: Es könnte immer noch ein Nash-Gleichgewicht vorliegen, fallsdie Geschichte ht auf dem Gleichgewichtspfad nicht erreicht wird.)

2) Es ist nicht offensichtlich, dass die Bedingung auch hinreichend fürTeilspielperfektheit ist. Angenommen, es gäbe keine profitable Strategiesi , die nur in einer Informationsmenge von s∗i abweicht. Dann könnte esimmer noch eine Strategie si geben, die an mehrerenInformationsmengen gleichzeitig von s∗i abweicht und echt besser als s∗iist.

3) Wenn wir den Satz bewiesen haben, können wir uns das Leben inZukunft sehr viel leichter machen: Wir müssen nur noch prüfen, ob esAbweichungsstrategien gibt, die profitabel an nur einerInformationsmenge abweichen. Das ist besonders nützlich beiwiederholten Spielen.

4) Wir führen den Beweis für Spiele mit endlichem Horizont. Der Beweis fürSpiele mit unendlichem Horizont wird nur skizziert. SieheFudenberg-Tirole, S. 107-110.




3.8 Verhandlungen

Verhandlungsspiele sind in vielen Bereichen der Ökonomie sehr wichtig.Immer wenn zwei oder mehr Parteien gemeinsam einen Überschusserwirtschaften können, stellen sich folgende Fragen:

1. Werden sich die Parteien auf eine effiziente Allokation einigen?

2. Wie werden die Parteien den Überschuss, der gemeinsam erwirtschaftetwird, untereinander aufteilen?


Beispiele:

Tarifverhandlungen zwischen Arbeitgeberverbänden und Gewerkschaften

Bi- oder multilaterale Verhandlungen zum Abbau von Handelsschranken

Verhandlungen zwischen Unternehmer und Investor (Kapitalgeber) überFinanzierung eines Investitionsprojekts

Verhandlungen zwischen Käufer und Verkäufer über den Verkauf einesGutes

etc.

In allen diesen Beispielen haben die Parteien das gemeinsame Interesse, denerreichbaren Überschuss so groß wie möglich zu machen, aber es gibt aucheinen Interessenkonflikt über die Aufteilung des Überschusses.


3.8.1 Das Ultimatumspiel

Die einfachste Version eines nicht-kooperativen Verhandlungsspiels ist diefolgende:

Spieler 1 und 2 können einen gemeinsamen Überschuss erreichen,dessen Maximalgröße auf 1 normiert ist.

In Stufe 1 schlägt Spieler 1 eine Aufteilung dieses Überschusses (s1, s2)vor, wobei s1 + s2 = 1.In Stufe 2 kann Spieler 2 diesen Vorschlag annehmen oder ablehnen:

I wenn er annimmt, bekommt Spieler 1 s1 und Spieler 2 s2;I wenn er ablehnt, bekommen beide Spieler eine Auszahlung von 0 und das

Spiel ist zu Ende.


Analyse des Spiels durch Rückwärtsinduktion:

Stufe 2: Spieler 2 wird jedes Angebot s2 > 0 annehmen. Bei s2 = 0 ist erindifferent zwischen Annehmen und Ablehnen.

Stufe 1:Spieler 1 wird Spieler 2 so wenig wie möglich anbieten und für sich denmaximal möglichen Rest beanspruchen.

Angenommen er schlägt (s1 = 1− ε, s2 = ε) vor, wobei ε > 0. Ist das einGleichgewicht?

Nein: Spieler 1 könnte sich besserstellen, wenn er (s1 = 1− ε2 , s2 = ε

2 )vorschlägt, was Spieler 2 immer noch annehmen wird.

Fazit: Das einzige teilspielperfekte Gleichgewicht in diesem Spiel ist(s1 = 1, s2 = 0). Im Gleichgewicht muss Spieler 2 dieses Angebot annehmen!


Beachten Sie:

1. Wenn es eine kleinste Geldeinheit (z.B. 0,01 EUR) gibt, ist auch(s1 = 0,99, s2 = 0,01) ein TPGG. (Zeigen!)

2. Jede Aufteilung des Überschusses ist ein Nash-GG.

Beispiel: Spieler 1 schlägt (s1 = 0,4; s2 = 0,6) vor. Spieler 2 lehnt jedesAngebot mit s2 < 0,6 ab.

Aber: Die Ablehnungsdrohung ist nicht glaubwürdig.

Das Ultimatumspiel ist allerdings keine sehr realistische Beschreibung einesVerhandlungsprozesses.


3.9 Ein Verhandlungsspiel mit endlichem Zeithorizont: Ståhl (1972)

Spieler 1 und Spieler 2 verhandeln über die Aufteilung eines Kuchens mitWert 1. Sei s ∈ [0,1] der Anteil des Kuchens, der an Spieler 1 geht, 1− s derAnteil von Spieler 2.


Zeitliche Strukturt=1: Spieler 1 macht einen Vorschlag s1 ∈ [0,1].

Wenn Spieler 2 zustimmt, ist das Spiel zu Ende.Ansonsten:

t=2: Spieler 2 macht einen Vorschlag s2.Wenn Spieler 1 zustimmt, ist das Spiel zu Ende.Ansonsten:

t=3: Spieler 1 macht einen Vorschlag s3.Wenn Spieler 2 zustimmt, ist das Spiel zu Ende.Ansonsten:

...t=T: Falls T ungerade ist, macht Spieler 1 den letzten Vorschlag sT .

Wenn Spieler 2 zustimmt, ist das Spiel zu Ende. Wenn erablehnt, ist der Kuchen verloren.Falls T gerade ist, sind die Rollen von 1 und 2 in Periode Tvertauscht.


Auszahlungen

Einigung in Periode t auf (s,1− s) ⇒

u1 = δt−1s,u2 = δt−1(1− s),

Keine Einigung ⇒ beide erhalten 0.


Analyse per Rückwärtsinduktion

Wir nehmen an, T ist ungerade.

t=T:Spieler 2 akzeptiert g.d.w. sT ≤ 1.Spieler 1: sT = 1.Spieler 2 akzeptiert.u1 = δT−1 · 1 = δT−1,u2 = δT−1 · 0 = 0.

t=T-1:Spieler 1 akzeptiert g.d.w. δT−2sT−1 ≥ δT−1.Spieler 2: sT−1 = δ.Spieler 1 akzeptiert.u1 = δT−2δ = δT−1,u2 = δT−2(1− δ).


t=T-2:Spieler 2 akzeptiert g.d.w. δT−3(1− sT−2) ≥ δT−2(1− δ).Spieler 1: sT−2 = 1− δ(1− δ) = 1− δ + δ2.Spieler 2 akzeptiert.u1 = δT−3(1− δ + δ2),u2 = δT−2(1− δ).

t=T-3:Spieler 1 akzeptiert g.d.w. δT−4sT−3 ≥ δT−3(1− δ + δ2).Spieler 2: sT−3 = δ(1− δ + δ2).Spieler 1 akzeptiert.u1 = δT−3(1− δ + δ2),u2 = δT−4(1− δ + δ2 − δ3).


t=T-4:Spieler 2 akzeptiert g.d.w.δT−5(1− sT−4) ≥ δT−4(1− δ + δ2 − δ3).Spieler 1: sT−4 = 1− δ(1− δ + δ2 − δ3).Spieler 2 akzeptiert.u1 = δT−5(1− δ + δ2 − δ3 + δ4),u2 = δT−4 · (1− δ + δ2 − δ3).

t=T-(T-1)=1:Spieler 2 akzeptiert g.d.w.δ(T−T )(1− sT−T+1) = (1− s1) ≥ δ(1− δ + δ2 − . . .− δT−2).Spieler 1: sT−T+1 = 1− δ + δ2 − · · ·+ δT−1.Spieler 2 akzeptiert.


u1 = 1− δ + δ2 − · · ·+ δT−1

= (1− δ)(1 + δ2 + δ4 + · · ·+ δT−3) + δT−1

= (1− δ)(

11− δ2 − δ

T−1 − δT+1 − δT+3 · · ·)+ δT−1

= (1− δ)(

1− δT−1

1− δ2

)+ δT−1 =

1− δT−1

1 + δ+ δT−1.

u2 = δ − δ2 + · · · − δT−1

= δ(1− δ)(1 + δ2 + δ4 + · · ·+ δT−3)

= δ(1− δ)(

1− δT−1

1− δ2

)= δ

1− δT−1

1 + δ.


Beachten Sie:Hier haben wir wiederholt verwendet, dass

1 + δ2 + δ4 + · · · = 11− δ2 .

Dies folgt aus der bekannten Summenformel

1 + q + q2 + · · · = 11− q

.

Die Analyse für gerades T ist analog, nur dass Spieler 2 das letzteAngebot macht.Die Summe der Auszahlungen ist

u1 + u2 =1− δT−1

1 + δ+ δT−1 + δ

1− δT−1

1 + δ

=(1 + δ)(1− δT−1)

1 + δ+ δT−1 = 1 .

Also ist das Ergebnis effizient. (Das muss so sein, weil im Gleichgewichtdas Angebot der ersten Periode bereits angenommen wird.)


Für T →∞ verschwindet der Unterschied in den Payoffs zwischengeradem und ungeradem T .Für T →∞ konvergiert u1 gegen 1

1+δ und u2 gegen δ1+δ .

Wenn Angebote und Gegenangebote sehr schnell erfolgen können, sollteδ sehr nahe bei 1 liegen. In diesem Fall bekommen beide Spielerungefähr 1

2 .Die letzte Periode ist sehr wichtig: Sie zwingt die Spieler, letztendlichzuzustimmen, weil sonst der Kuchen endgültig verloren ist.Die Annahme einer letzten Periode scheint unplausibel. Wer hält dieParteien davon ab, nach Periode T noch ein weiteres Angebot zumachen?Rubinstein (1982) hat dieses Verhandlungsspiel mit einem unendlichenHorizont gelöst. Das ist nicht trivial, weil man dieses Spiel nicht mehrdurch Rückwärtsinduktion lösen kann. Er hat gezeigt, dass das einzigeTPGG in diesem Spiel zu denselben Auszahlungen führt wie der Limesdes endlichen Spiels, wenn T gegen unendlich geht.


Documents

3. Dynamische Spiele mit vollständiger Information · Abb. 3.1: Ein Spielbaum Klaus M. Schmidt (LMU München) 3. Dynamische Spiele mit vollständiger Information Spieltheorie, Wintersemester