Spieltheorie - WU · 2016. 4. 19. · Folienskriptum Spieltheorie, Ulrich Berger & Peter Bednarik, Version Nov. 2014 2 Worum geht es? Wir untersuchen Situationen, in denen alle Entscheidungsträger

Folienskriptum Spieltheorie, Ulrich Berger &

Peter Bednarik, Version Nov. 2014

1

Spieltheorie

Teil 1: Statische Spiele mit

vollständiger Information



2

Worum geht es?

Wir untersuchen Situationen, in denen

alle Entscheidungsträger (Agenten, Spieler) rational sind,

jeder Spieler eine genau definierte Menge an Handlungsmöglichkeiten

(Strategien) zur Wahl hat,

und das Ergebnis (die Auszahlungen für die Spieler) von den gewählten

Strategien aller Spieler abhängt – also wo es “strategische Interaktion”

gibt.

Beispiel: Sie gehen mit 5 Freunden in ein Restaurant. Was bestellen Sie?

Jeder bezahlt sein eigenes Essen simples Entscheidungsproblem.

Vor dem Essen wurde vereinbart, dass jeder 1/6 der Gesamtrechnung

bezahlt ein Spiel!



3

Was ist Spieltheorie?

3 kurze Antworten:

Spieltheorie ist ein anderes Wort für “mehr-Personen Entscheidungstheorie".

Spieltheorie ist ein Werkzeug zur Analyse von strategischer Interaktion.

Spieltheorie ist eine formale Methode zur Analyse von strategischem Verhalten in einer Gruppe von rationalen Spielern.

Spieltheorie kommt aus der Mathematik und hat innerwissenschaftliche Anwendungen in

Wirtschaftswissenschaften und Soziologie

Politik- und Rechtswissenschaften

Philosophie und Computerwissenschaften

Biologie



4

Spieltheorie in den Wirtschaftswissenschaften

John von Neumann & Oskar Morgenstern 1944, Theory of Games

and Economic Behavior

Nobelpreise (Wirtschaftswissenschaften) für Spieltheoretiker:

1994: John Nash, John Harsanyi und Reinhard Selten

2005: Robert Aumann und Thomas Schelling

2012: Alvin Roth und Lloyd Shapley



5

Statische Spiele mit vollständiger Information:

Was ist ein Spiel?

I ist eine nichtleere Menge von Spielern.

• Bei uns meistens endlich: I = {1, 2, …, n}

• i I bezeichnet einen Spieler

S = S1 × S2 × … × Sn = Si × S-i

• Si ist eine nichtleere Menge, sie heißt Spieler i's Strategiemenge

• S-i = S1 × ... × Si-1 × Si+1 × … × Sn ist das Produkt der Strategiemengen von i's Gegenspielern.

• s = (s1, ... , sn) = (si, s-i) S ist ein Strategieprofil aller Spieler

• si Si bezeichnet eine Strategie von Spieler i

• s-i = (s1, ... , si-1, si+1, ... , sn) S-i ist das Strategieprofil von i's Gegenspielern

U = (u1, u2, ... , un) ist der Vektor der Auszahlungsfunktionen

• ui: S → ℝ bezeichnet Spieler i's Auszahlungsfunktion

Ein statisches Spiel ist eine Menge G = {I, S, U}, wobei gilt:



6

Nicht-kooperative Spiele: Bindende Verträge sind

ausgeschlossen. Drei Grundannahmen:

Einmaliges Spiel mit simultaner Wahl

Jeder Spieler wählt eine Strategie, ohne die Wahl der anderen Spieler zu kennen. Die Spieler erhalten ihre Auszahlungen und das Spiel endet.

Vollständige Information

Das Spiel, also I, S und U, sind Common Knowledge (CK = "gemeinsames Wissen").

• Eine Tatsache T ist CK, wenn jeder Spieler T weiß, und jeder weiß dass jeder T weiß, und jeder weiß dass jeder weiß dass jeder T weiß, und ... (ad infinitum).

Rationalität

Alle Spieler sind rational, d.h. jeder Spieler maximiert seine Auszahlung, gegeben seinen belief (= Glauben, Einschätzung) über die Strategiewahl der anderen Spieler.

Die Rationalität der Spieler ist CK.



7

Bi-Matrix Spiele

Ein Spiel heißt endlich, wenn I und S endliche Mengen sind.

Ein endliches 2-Personen Spiel kann als Bi-Matrix dargestellt werden, man nennt es daher Bi-Matrix Spiel. Hat Spieler 1 v und Spieler 2 w Strategien, spricht man von einem v×w Bi-Matrix Spiel.

Als Konvention wählt Spieler 1 aus den Zeilen und Spieler 2 aus den Spalten der Bi-Matrix. Die Auszahlungen stehen in der Reihenfolge u1, u2 in den Zellen.

Beispiel: Ein 3×2 Bi-Matrix Spiel mit I = {Spieler 1, Spieler 2} und

S1 = {a, b, c}, S2 = {d, e} Spieler 2

d e

Spieler 1

a u1(a,d), u2(a,d) u1(a,e), u2(a,e)

b u1(b,d), u2(b,d) u1(b,e), u2(b,e)

c u1(c,d), u2(c,d) u1(c,e), u2(c,e)



8

Beispiel: Gefangenen-Dilemma

Zwei Gefangene sind eines gemeinsamen Verbrechens angeklagt. In getrennten Zellen erhält jeder folgendes Angebot: "Wenn ihr beide schweigt, können wir euch nur 1 Jahr festhalten. Wenn ihr beide gesteht, sitzt ihr je 6 Jahre. Aber wenn du gestehst und dein Komplize dichthält, gehst du als Kronzeuge frei, und er bekommt 9 Jahre."

I = {Gefangener 1, Gefangener 2}, S1 = S2 = {Dichthalten, Gestehen}, Auszahlungsfunktionen: u1(D,D) = -1, u1(D,G) = -9, u1(G,D) = 0, u1(G,G) = -6, u2(D,D) = -1, u2(D,G) = 0, u2(G,D) = -9, u2(G,G) = -6

-1 , -1 -9 , 0

0 , -9 -6 , -6 Gefangener 1

Gefangener 2 G

D

G

D Spieler

Strategien

Auszahlungen



9

Beispiel: Dating Game (Verabredungsspiel)

Chris und Pat wollen den Abend zusammen verbringen. Chris möchte gern in die Oper, aber Pat lieber zum Boxen. Am Abend allein zu sein ist gleich unbefriedigend, egal wo man ist.

Menge der Spieler I = {Chris, Pat}

Strategiemengen S1 = S2 = {Oper, Boxen}

Auszahlungsfunktionen: u1(O, O) = 2, u1(O, B) = 0, u1(B, O) = 0, u1(B, B) = 1 u2(O, O) = 1, u2(O, B) = 0, u2(B, O) = 0, u2(B, B) = 2

2 , 1 0 , 0

0 , 0 1 , 2 Chris

Pat

Boxen

Oper

Boxen

Oper



10

Beispiel: Matching Pennies (Kopf oder Zahl)

Zwei Spieler zeigen gleichzeitig eine Seite einer Münze. Wenn die

Seiten verschieden sind, bekommt Spieler 1 die Münze von Spieler 2.

Wenn beide Seiten Kopf oder beide Zahl zeigen, bekommt Spieler 2

die Münze von Spieler 1.

Menge der Spieler I = {Spieler 1, Spieler 2}

Strategiemengen S1 = S2 = {Kopf, Zahl}

Auszahlungsfunktionen:

u1(K, K) = -1, u1(K, Z) = 1, u1(Z, K) = 1, u1(Z, Z) = -1

u2(K, K) = 1, u2(K, Z) = -1, u2(Z, K) = -1, u2(Z, Z) = 1

-1 , 1 1 , -1

1 , -1 -1 , 1

Spieler 1

Spieler 2

Zahl

Kopf

Zahl

Kopf



11

Seien d, h Si. Strategie d wird streng dominiert durch

Strategie h, wenn ui(d, s-i) < ui(h, s-i) für alle s-i S-i.

D.h. Strategie h liefert eine höhere Auszahlung für i als Strategie d,

egal was die Gegenspieler spielen.

Man sagt kurz: Strategie d ist streng dominiert.

Strategie h ist hier die d streng dominierende Strategie.

Zum Nachdenken:

Kann ein rationaler Spieler eine streng dominierte Strategie spielen?

Definition: streng dominierte Strategie



12

Seien d, h Si. Strategie d wird schwach dominiert durch

Strategie h, wenn ui(d, s-i) ≤ ui(h, s-i) für alle s-i S-i und

ui(d, s-i) < ui(h, s-i) für ein s-i S-i.

D.h. Strategie h liefert eine mindestens so hohe Auszahlung wie Strategie d für Spieler i,

und eine echt höhere Auszahlung für mindestens ein gegnerisches Strategieprofil.

Man sagt Strategie h domininiert Strategie d schwach.

Zum Nachdenken:

Kann ein rationaler Spieler eine schwach dominierte Strategie spielen?

Definition: schwach dominierte Strategie



13

Strategie si ist streng dominant, wenn

ui(si, s-i) > ui(si', s-i) für alle s-i S-i und für alle si' Si\{si}

Strategie si ist schwach dominant, wenn für alle si' Si\{si} gilt:

ui(si, s-i) ≥ ui(si', s-i) für alle s-i S-i, und ui(si, s-i) > ui(si', s-i)

für ein s-i S-i.

D.h.: Eine Strategie ist genau dann streng [schwach] dominant, wenn sie alle anderen Strategien des Spielers streng [schwach] dominiert.

Definition: dominante Strategie



14

Strategie si ist eine beste Antwort von Spieler i auf s-i, wenn

ui(si, s-i) ≥ ui(si', s-i) für alle si' Si.

Strategie si ist eine bessere Antwort auf s-i als si', wenn

ui(si, s-i) > ui(si', s-i).

Wir bezeichnen die Menge der besten Antworten von Spieler i auf s-i mit Bi(s-i). Wenn Spieler i den belief s-i hat, dann wird er (weil er rational ist) jedenfalls ein Element dieser Menge, also eine beste Antwort auf s-i, spielen. (aber Achtung: diese Menge kann leer sein!)

Eine Strategie von Spieler i, die auf keinen belief s-i eine beste Antwort ist, wird niemals-beste Antwort genannt.

Definition: beste Antwort



15

IESDS – Iterierte Elimination streng dominierter

Strategien

Ein rationaler Spieler spielt nie eine streng dominierte Strategie. Eine streng

dominierte Strategie kann also eliminiert werden. Hier ist ein Algorithmus

für die IESDS:

1. Prüfen Sie ob irgendein Spieler eine streng dominierte Strategie besitzt.

Wenn nein, sind Sie fertig. Wenn ja, eliminieren Sie diese Strategie aus

dem Spiel.

2. Das Spiel ist jetzt reduziert, es ist "kleiner" und weniger komplex. Gehen

Sie zu Schritt 1.

Übrig bleibt ein Spiel ohne streng dominierte Strategien. Die übrig

gebliebenen Strategien heißen iterativ undominiert. Wenn pro Spieler nur

eine Strategie überlebt, heißt das Spiel Dominanz-lösbar.

Da Rationalität CK ist, wird ein Spieler nie eine iterativ streng dominierte

Strategie Strategie wählen (= eine Strategie, die im Zuge der IESDS

eliminiert wird). Wenn ein Spiel Dominanz-lösbar ist, wird also jeder

Spieler seine einzige überlebende Strategie spielen.



16

IESDS – ein Beispiel (1 von 5)

1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0 Spieler 1

Spieler 2

Middle

Up

Down

Left Right



17


1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0 Spieler 1

Spieler 2

Middle

Up

Down

Left Right

2 > 1 und 1 > 0, daher ist Right streng dominiert (und zwar von Middle).

Right wird von Spieler 2 also nicht gespielt werden, und Spieler 1 weiß das.

Right kann also aus dem Spiel eliminiert werden.



18


1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0 Spieler 1

Spieler 2

Middle

Up

Down

Left Right

1 > 0, daher ist nun Down streng dominiert (und zwar von Up).

Down wird von Spieler 1 also nicht gespielt werden, und Spieler 2 weiß das.

Down kann also aus dem Spiel eliminiert werden.



19


1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0 Spieler 1

Spieler 2

Middle

Up

Down

Left Right

2 > 0, daher ist nun Left streng dominiert (und zwar von Middle).

Left wird von Spieler 2 also nicht gespielt werden, und Spieler 1 weiß das.

Left kann also aus dem Spiel eliminiert werden.



20


1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0 Spieler 1

Spieler 2

Middle

Up

Down

Left Right

Die einzigen überlebenden Strategien sind Up (für Spieler 1) und Middle (für

Spieler 2). Das Spiel ist Dominanz-lösbar. Die Lösung lautet (Up, Middle).



21

Rationalisierbarkeit und IENBA (iterierte

Elimination von niemals-besten Antworten)

Ein rationaler Spieler spielt immer eine beste Antwort auf seinen belief. Eine niemals-beste Antwort kann man also eliminieren. Hier ist ein Algorithmus für die IENBA:

1. Prüfen Sie ob einer der Spieler eine niemals-beste Antwort hat. Wenn nein, sind Sie fertig. Wenn ja, eliminieren Sie diese Strategie aus dem Spiel.

2. Das Spiel ist jetzt reduziert, es ist "kleiner" und weniger komplex. Gehen Sie zu Schritt 1.

Übrig bleibt ein Spiel, in dem jede Strategie eine beste Antwort auf zumindest einen belief ist. Die überlebenden Strategien heißen rationalisierbar.



22

Mehr über Rationalisierbarkeit

Ein rationaler Spieler spielt nur rationalisierbare

Strategien!

In 2-Personen-Spielen sind die Konzepte IESDS und

IENBA identisch: Eine Strategie ist genau dann iterativ

undominiert, wenn sie rationalisierbar ist.

Aber in Spielen mit 3 oder mehr Personen ist

Rationalisierbarkeit ein stärkeres Konzept als IESDS!

D.h. es gibt Spiele mit iterativ undominierten Strategien,

die nicht rationalisierbar sind.



23

Wir wissen, dass ein Spieler immer eine beste Antwort auf seinen belief spielt, und dass dieser belief nur rationalisierbare Strategien beinhaltet. Trotzdem kann sich der belief nach dem Spiel als falsch erweisen.

Auf lange Sicht sollten die beliefs aber entsprechend angepasst werden und sich schließlich als korrekt erweisen. Ist das der Fall, so spielt jeder Spieler sogar eine beste Antwort auf das tatsächlich gewählte Strategieprofil der Gegenspieler. In diesem Fall nennt man das Strategieprofil ein Nash Gleichgewicht.

Ein Strategieprofil s* ist ein Nash Gleichgewicht, wenn

si* Bi(s-i*) für alle i I.

In Worten: Ein Strategieprofil ist ein Nash Gleichgewicht, wenn jeder Spieler eine beste Antwort auf die Wahl seiner Gegenspieler spielt.

Definition: Nash Gleichgewicht (NG)



24

1. Die beliefs können nicht dauerhaft falsch sein. Wenn die beliefs aller Spieler korrekt sind, so spielen sie ein NG.

2. In einem NG spielt jeder Spieler optimal, gegeben die Entscheidungen der Gegenspieler. Wenn also ein NG gespielt wird, bereut kein Spieler seine Strategiewahl nach dem Spiel. Nur NGs haben diese Eigenschaft!

3. Jede "plausible Lösung" eines Spiels muss ein NG sein! (Warum?) Andererseits ist aber nicht jedes NG eine plausible Lösung – dazu später mehr.

Warum NG ein wichtiges Konzept ist



25

NGs müssen nicht existieren, d.h. nicht jedes Spiel besitzt ein NG.

NGs, wenn sie existieren, müssen nicht eindeutig sein, d.h. ein Spiel kann mehrere NGs haben.

Ein NG, wenn es existiert, muss nicht Pareto-optimal (effizient) sein.

Wiederholung: Pareto-Optimalität

Strategieprofil s ist Pareto-besser als Strategieprofil s', wenn

ui(s) ≥ ui(s') für alle i I, und ui(s) > ui(s') für ein i I.

Man nennt dann s auch eine Pareto-Verbesserung gegenüber s'.

Ein Strategieprofil s is Pareto-optimal, wenn es keine Pareto-Verbesserung gegenüber s gibt, d.h. wenn kein anderes Strategieprofil Pareto-besser als s ist.

Welche Strategieprofile im Gefangenendilemma sind Pareto-optimal?

Pareto-Optimalität und mehr über NGs



26

Im allgemeinen ist es nicht einfach, NGs in einem gegebenen Spiel zu

finden. Für Bi-Matrix Spiele gibt es jedoch eine einfache Methode:

In jeder Spalte der Bi-Matrix unterstreichen Sie die höchste(n)

Auszahlung(en) von Spieler 1 (links stehend!).

In jeder Zeile der Bi-Matrix unterstreichen Sie die höchste(n)

Auszahlung(en) von Spieler 2 (rechts stehend!).

Wenn in einer Zelle der Bi-Matrix beide Auszahlungen unterstrichen

sind, so ist das entsprechende Strategieprofil ein Nash Gleichgewicht.

Wie man NGs in Bi-Matrix Spielen findet



27

Eine Anmerkung zu Auszahlungen

In Beispielen sind Auszahlungen oft Geldbeträge, "Punkte" oder ähnliches. Das vereinfacht die Darstellung, aber bedenken Sie dabei immer:

Auszahlungen sind stets von-Neumann-Morgenstern Nutzenwerte. Das bedeutet, dass die Risikoeinstellung der Spieler schon in den Auszahlungen berücksichtigt ist. Wenn also Risiko (Zufall) involviert ist, so maximieren rationale Spieler immer ihre erwartete Auszahlung.

Stellen Sie sich vor, Sie sind Chris im Verabredungsspiel, und Sie wissen, dass Pat würfelt, um ihr Ziel zu bestimmen. Wenn der Würfel 1 oder 2 Augen zeigt, geht sie zum Boxen, andernfalls in die Oper. Was ist Ihre beste Antwort auf diese "gemischte" Strategie?



28

Definition: Gemischte Strategien

Strategien in Si nennt man reine Strategien, um sie von

gemischten Strategien zu unterscheiden.

Die Interpretation einer gemischten Strategie ist, dass der Spieler

nicht eine reine Strategie, sondern nur eine Wahrscheinlichkeits-

verteilung wählt, und die "Auswahl" der tatsächlich gespielten

reinen Strategie (die Realisierung) dem Zufall überlässt.

Eine gemischte Strategie von Spieler i bezeichnen wir mit σi, und

Σi ist die Menge seiner gemischten Strategien. Die Vektoren σ-i

und Σ-i sind analog wie bei reinen Strategien definiert.

Wenn Si endlich ist, z.B. Si = {si1, si

2, ... , sik}, und σi

Wahrschein-lichkeiten (oder Gewichte) pi1, ... , pi

k auf diese

reinen Strategien legt, dann schreibt man: σi = pi1

si1 + pi

2 si

2 + ...

+ pik si

k.

Eine gemischte Strategie von Spieler i ist eine

Wahrscheinlichkeitsverteilung auf der Menge Si.



29

Mehr über gemischte Strategien

Durch die Verwendung von erwarteten Auszahlungen erweitern wir de facto die Auszahlungsfunktion ui zu einer Funktion auf der Menge der gemischten Strategieprofile

Σ = Σi × Σ-i = Σ1 ×...×Σn.

Alle vorangegangenen Definitionen lassen sich auf gemischte Strategien erweitern, wenn man si, Si, s-i, S-i, s, S jeweils durch

σi, Σi, σ-i, Σ-i, σ, Σ ersetzt.

Eine reine Strategie kann man mit jener gemischten Strategie identifizieren, die Gewicht 1 auf sie und Gewicht 0 auf alle anderen reinen Strategien legt. Man kann also die Identifikation si

j ≡ 0si1 + ... + 0si

j-1 + 1sij + 0si

j+1 + ... + 0sik vornehmen.

Zum Nachdenken:

Kann eine reine Strategie, die von keiner anderen reinen Strategie streng dominiert wird, von einer gemischten Strategie streng dominiert werden?



30

Gemischte Strategien als beste Antworten

Der support (“Träger”) einer gemischten Strategie ist die Menge der reinen Strategien, die positives Gewicht erhalten:

supp(σi) = {sij Si: pi

j > 0}.

Fundamentaltheorem oder Indifferenzprinzip:

σi ist genau dann eine beste Antwort auf σ-i , wenn alle reinen Strategien in supp(σi) beste Antworten auf σ-i sind.

Intuition für das Fundamentaltheorem: Wenn eine bestimmte reine Strategie im support keine beste Antwort wäre, dann könnte der Spieler seine erwartete Auszahlung erhöhen, indem er Gewicht von dieser Strategie wegnimmt und zu einer reinen besten Antwort hin verschiebt.



31

Zur Erinnerung: Ein Strategieprofil σ* ist ein Nash

Gleichgewicht (NG), wenn σi* Bi(σ-i*) für alle i I.

1950 bewies John F. Nash:

Jedes endliche Spiel besitzt mindestens ein Nash

Gleichgewicht.

Konstruieren Sie ein Spiel ohne NG!

Nashs Theorem



32

Spieltheorie

Teil 2: Dynamische Spiele mit

vollständiger Information



33

Dynamische Spiele mit vollständiger Information:

Bäume, Knoten und Züge

In einem dynamischen Spiel mit vollständiger Information ziehen die Spieler abwechselnd, es gibt also eine zeitliche Abfolge von Spielzügen. Die exakte Definition ist zu komplex, hier ist eine Beschreibung:

Ein dynamisches Spiel wird durch einen Spielbaum dargestellt. Ein Spielbaum spezifiziert, welcher Spieler wann zieht, welche Information er hat, welche Züge für ihn möglich sind und welche Auszahlungen mit den Zugfolgen verknüpft sind.

Ein Spielbaum startet an der sog. Wurzel. Ein Spieler beginnt dort mit einem von mehreren möglichen Zügen. Jeder Zug führt zu einer neuen Verzweigung, genannt Knoten, des Spielbaumes. Bei jedem Knoten macht entweder einer der Spieler einen Zug (Entscheidungsknoten), oder die "Natur" macht einen Zufallszug, oder das Spiel endet in einem Endknoten. Zu jedem Endknoten gehört ein Auszahlungsvektor mit den jeweiligen Auszahlungen für alle Spieler.



34

Informationsmengen und perfekte Information

Die Entscheidungsknoten eines jeden Spielers sind in

Informationsmengen partitioniert. Eine Informationsmenge

enthält jene Knoten, zwischen denen der Spieler nicht

unterscheiden kann. (Er weiß in welcher Informationsmenge er

sich befindet, aber nicht an welchem Knoten in dieser Menge. Für

jeden Knoten in der Informationsmenge muss die Menge der

möglichen Züge notwendigerweise dieselbe sein.) Eine

Informationsmenge wird durch eine strichlierte Linie zwischen

den jeweiligen Knoten im Spielbaum dargestellt.

Wenn eine Informationsmenge nur einen einzigen Knoten enthält,

nennt man sie ein-elementig. Ein dynamisches Spiel, in dem alle

Informationsmengen ein-elementig sind, nennt man ein Spiel mit

perfekter Information, andernfalls ein Spiel mit imperfekter

Information.



35

Spielverlauf und Strategien in dynamischen

Spielen

Eine Zugfolge, die von der Wurzel eines Spiels bis zu einem

Endknoten verläuft, nennt man einen Spielverlauf.

Wenn ein dynamisches Spiel nur endlich viel Knoten enthält,

heißt es endlich. Wenn es unendlich ist, enthält es entweder

Knoten mit unendlich vielen möglichen Zügen, oder es sind

unendliche Spielverläufe möglich. Wenn alle Spielverläufe

endlich sind, sagt man, das Spiel hat einen endlichen Horizont.

Eine reine Strategie eines Spielers in einem dynamischen Spiel

ist ein vollständiger Verhaltensplan. D.h. sie muss für jede

Informationsmenge des Spielers einen der möglichen Züge

vorschreiben. Dies gilt auch für Informationsmengen, die gar

nicht erreicht werden, wenn diese Strategie gespielt wird!



36

Die strategische Form eines dynamischen Spiels

Durch ein reines Strategieprofil ist der Spielverlauf (bis auf Zufallszüge) eindeutig bestimmt, ebenso der Auszahlungsvektor.

Damit können wir ein dynamisches Spiel in ein statisches Spiel übersetzen. Wir konstruieren einfach aus dem Spielbaum die Menge der reinen Strategien für jeden Spieler und daraus die Auszahlungsfunktionen. Das so konstruierte statische Spiel nennt man die strategische Form des dynamischen Spiels.

Auf diese Weise lassen sich alle Definitionen, inklusive Dominanz, gemischte Strategien, etc., auch auf dynamische Spiele übertragen. Ein wichtiges Beispiel:

Ein Strategieprofil σ* in einem dynamischen Spiel heißt Nash Gleichgewicht, wenn es ein Nash Gleichgewicht in der strategischen Form des Spiels ist.



37

Ein Beispiel

Zum Nachdenken:

Was sind die reinen

Strategien der Spieler?

Wie lautet die

strategische Form

dieses Spiels?

Finden Sie alle reinen

NGs dieses Spiels!

2 N

1

2 1

a b

[0.2]

h i

d c

f g f

4

0

0

2 4

1

8

4

0

3

15

15 -5

10

0

-5

[0.8]

g

e



38

Beispiel: Entry Deterrence

Firma Y ist Monopolist im Markt, wird aber durch den Markteintritt von X bedroht. Wenn X draußen bleibt macht es 0 Gewinn, und Y behält den Monopolgewinn von 8. Wenn X eintritt, kann Y entweder den Markt teilen (Gewinn jeweils 3) oder einen Preiskampf beginnen, der mit einem Verlust von 1 für beide Firmen endet.

Lösen Sie dieses Spiel! Was werden die Firmen tun?

Y

X

in out

share 0

8 fight

-1

-1 3

3



39

Analyse von Entry Deterrence

Jede Firma hat nur einen Entscheidungsknoten, also sind die Strategiemengen {in, out} für X und {share, fight}für Y.

Die strategische Form des Spiels ist:

Y

X

in out

share 0

8 fight

-1

-1 3

3

3 , 3 -1 , -1

0 , 8 0 , 8 X

Y fight

in

out

share

Die NGs sind leicht zu finden, es sind

(in, share) und (out, fight).

Halten Sie (out, fight) für eine

plausible Lösung?



40

Analyse von Entry Deterrence (Forts.)

Wenn der Spielverlauf den

Entscheidungsknoten von Y

erreicht, also wenn X "in" wählt,

dann wird Y nicht kämpfen. Das

NG (out, fight) beruht auf Ys

unglaubwürdiger Drohung, zu

kämpfen falls X eintritt.

Rational ist es für X einzutreten und

für Y den Markt zu teilen. Das NG

(in, share) ist eine plausible Lösung.

Das NG (out, fight) ist unplausibel,

da es in dem Teilspiel, das an Ys

Entscheidungsknoten beginnt, einen

irrationalen Zug vorschreibt.

Y

X

in out

share 0

8 fight

-1

-1 3

3

ein Teilspiel



41

Teilspiele

Ein Teilspiel eines dynamischen Spiels ist ein Teil des Spielbaums, der an einer ein-elementigen Informationsmenge beginnt und alle darauf folgenden Knoten (und nur diese) enthält.

Diese Definition impliziert, dass das ganze Spiel immer ein Teilspiel seiner selbst ist. Alle anderen Teilspiele heißen echte Teilspiele.

Ein Spiel muss kein echtes Teilspiel haben. Geben Sie ein Beispiel!

Ein Strategieprofil in einem Spiel induziert (erzeugt) ein (Teilspiel-) Strategieprofil in jedem Teilspiel.

2 N

1

2 1

Die echten Teilspiele in dem

Beispiel von S. 35.



42

Teilspielperfektes Gleichgewicht (TPG)

Ein Nash Gleichgewicht eines dynamischen Spiels heißt teilspielperfekt, wenn es in jedem Teilspiel ein Nash Gleichgewicht induziert.

Teilspielperfektion schließt alle NGs aus, die auf unglaubwürdigen Drohungen beruhen.

Man kann zeigen, dass jedes endliche dynamische Spiel mit vollständiger Information ein teilspielperfektes Nash Gleichgewicht besitzt.

Y

X

in out

share 0

8 fight

-1

-1 3

3

Dieses Teilspiel ist ein 1-Personen Spiel

mit NG (share). Das NG (out, fight) des

Originalspiels induziert (fight) in diesem

Teilspiel, also ist es nicht teilspielperfekt.

Nur das NG (in, share) ist ein TPG.



43

TPGs in Spielen mit perfekter Information finden:

Rückwärtsinduktion

In einem Spiel mit perfekter Information und endlichem Horizont gibt es eine einfache Methode, um TPGs zu finden, genannt Rückwärtsinduktion.

Sie beginnen am Ende des Spielbaums (bei einem der letzten Entscheidungsknoten) und bestimmen den optimalen Zug des ziehenden Spielers. Gehen Sie dann zum vorletzten Entscheidungsknoten und bestimmen Sie den optimalen Zug des dort ziehenden Spielers, wobei der zuvor bestimmte optimale Zug als gegeben angenommen wird. Arbeiten Sie sich auf diesem Weg bis zur Wurzel zurück.

Y

X

in out

share 0

8 fight

-1

-1 3

3

Falls Y zum Zug kommt, ist sein

optimaler Zug "share". X weiß das,

entscheidet also effektiv zwischen den

Auszahlungsvektoren (3,3) und (0,8).

Optimal für X ist daher "in". Die

Rückwärtsinduktion liefert also das

TPG (in, share).



44

Beispiel: Tausendfüßler

Sie und ein Gegenspieler sitzen in getrennten Räumen vor einer

"Münzmaschine". Die beiden Maschinen sind verbunden und jede

hat einen Münzschlitz und einen Stop-Knopf. Wenn einer von Ihnen

1€ in den Schlitz wirft, kommen beim anderen 2€ heraus. Wenn aber

einer auf Stop drückt, ist das Spiel zu Ende. Die Spieler ziehen

abwechselnd und höchstens je 10 Mal. Sie beginnen.

Wie würden Sie dieses Spiel in der Realität spielen?

Wie würden rationale Spieler dieses Spiel spielen?



45

Beispiel: Wiederholtes Gefangenendilemma mit

fixer Anzahl von Runden

Sie (Spieler 1) und Ihr Gegenspieler (Spieler 2) spielen diese Variante des Gefangenendilemmas. Im einmaligen Spiel ist D(efect) offensichtlich streng dominant. Sie spielen dieses Spiel aber wiederholt, nämlich 5 Mal hintereinander. Nach jeder Runde wird deren Resultat bekannt gegeben.

Wie würden Sie das wiederholte Spiel in der Realität spielen?

Wie würden rationale Spieler das wiederholte Spiel spielen?

3 , 3 0 , 5

5 , 0 1 , 1

Defect

Cooperate

Cooperate

Defect

2

1



46

Beispiel: Wiederholtes Gefangenendilemma mit

unbestimmter Anzahl von Runden (wGD)

Zeigen Sie, dass (immer D, immer D) ein NG für das wGD ist!

Die folgende Strategie T heißt eine Trigger-Strategie für das wGD:

Beginne mit C. In jeder weiteren Runde, spiele C wenn in allen bisherigen Runden (C, C) gespielt wurde, sonst spiele D.

Zeigen Sie, dass das Profil (T, T) zu durchgehender Kooperation führt!

Zeigen Sie, dass (T, T) für kleine Werte von p ein Nash Gleichgewicht des wGD ist!

Zeigen Sie, dass (T, T) dann sogar teilspielperfekt ist!

3 , 3 0 , 5

5 , 0 1 , 1

D

C

C

D

2

1

Sie spielen das GD wiederholt, aber die

Anzahl der Runden ist eine Zufallsvariable.

Nach jeder Runde endet das Spiel mit einer

Wahrsch. von p bzw. wird eine weitere Runde

gespielt mit einer Wahrsch. von 1-p.

Documents

Spieltheorie - WU · 2016. 4. 19. · Folienskriptum Spieltheorie, Ulrich Berger & Peter Bednarik, Version Nov. 2014 2 Worum geht es? Wir untersuchen Situationen, in denen alle Entscheidungsträger