1.2 Dynamische Spiele Flashcards
Was ist ein dynamisches Spiel?
Die Spieler können sequentiell und auch mehr als
einmal entscheiden
dynamische Spiele - Strategie
vollständiger Verhaltensplan, der für jeden Spieler
und jede Möglichkeit, bei der dieser Spieler zum Zug kommen könnte, eine mögliche Aktion vorschreibt
Dynamische Spiele mit vollständiger und vollkommener
Information:
· Es gibt einen Entscheidungsablauf
· Alle vorhergehenden Entscheidungen werden beobachtet, bevor die nächste Aktion gewählt wird
· Die Auszahlungen aller Spieler bei allen möglichen
Kombinationen von Aktionen sind allgemein bekannt
Rückwärtsinduktion
• Lösung der Spiele dieser Klasse: Rückwärtsinduktion
• Zweite Stufe: Spieler 2
· beobachtet die Aktion von Spieler 1 a1
· wählt seine beste Antwort (Reaktion) auf die Aktion von
Spieler 1 a1, R2(a1),
d.h., Spieler 2 löst das Maximierungsproblem max a2∈A2 u2(a1, a2)
• Die beste Antwort kann eine Funktion oder eine
Korrespondenz sein
• Erste Stufe: Spieler 1
· antizipiert die Reaktion von Spieler 2 auf jede Aktion a1
· wählt seine beste Antwort (auf die beste Antwort von Spieler 2), d.h., Spieler 1 löst das Maximierungsproblem
max a1∈A1 u1(a1, R(a1))
• Das Rückwärtsinduktionsergebnis des Spiels ist (a∗1, R(a∗1))
• Das Ergebnis bei Rückwärtsinduktion schließt unglaubwürdige Drohungen aus
Dynamische Spiele mit vollständiger und unvollkommener Information
- Es gibt einen Zugablauf
- Nicht alle vorhergehenden Züge werden beobachtet, bevor der nächste Zug gewählt wird (d.h., innerhalb einer Stufe kann es simultane Entscheidungen)
· Die Auszahlungen aller Spieler bei allen möglichen
Kombinationen von Zügen sind allgemein bekannt
Das teilspielperfekte Ergebnis ist das Analogon zu dem….
…Rückwärtsinduktionsergebnis bei Spielen mit vollkommener Information
Informationsbezirk
Ein Informationsbezirk ist eine Menge von
Entscheidungsknoten, für die gilt:
(1) Der Spieler muss an jedem Knoten in dem
Informationsbezirk eine Entscheidung treen
(2) Wenn beim Spielen des Spiels einen Entscheidungsknoten
in einem Informationsbezirk erreicht wird, weiß der Spieler, der am Zug ist, nicht welchen Knoten in dem
Informationsbezirk erreicht (bzw. nicht erreicht) wurde
⇒ Für jeden Spieler muss die gleiche Menge von Aktionen an jedem Entscheidungsknoten in einem Informationsbezirk verfügbar sein
Forderung der sequentiellen Rationalität:
In jedem Entscheidungsknoten muss die Aktion des Spielers, der am Zug ist, optimal sein, gegeben die Folgestrategien der anderen Spieler
Wiederholte Spiele
Spiele, die darin bestehen, dass ein Spiel (Basisspiel)
wiederholt gespielt wird
• Alle Spieler werden über das Ergebnis der letzten Runde (Stufe) informiert, bevor die nächste Runde (Stufe) beginnt
• Frage: Können Drohungen oder Versprechen über das
Verhalten in der Zukunft, gegenwärtiges Verhalten
beeinflussen?
Notation:
- G Spiel in Normalform (Basisspiel des wdh. Spiels G(T))
- G(T) bezeichnet (T-mal) wiederholte Spiel G
Eine Strategie in einem Spiel in extensiver Form
ist ein…
…vollständiger Verhaltensplan, der für jeden Spieler und
jede Möglichkeit, bei der dieser Spieler zum Zug kommen könnte, eine mögliche Aktion vorschreibt
Extensive Form (Spielbaumdarstellung)
-> jedes Spiel in extensiver Form kann als Normalform-Spiel dargestellt werden
Theorem von Zermelo
Jedes endliche Spiel (endliche Menge von Spielern, endlich vielen Strategien) in extensiver Form mit vollkommener Information hat ein Nash-GG in reinen Strategien, das durch Rückwärtsinduktion
abgeleitet werden kann.
Falls keiner der Spieler an je zwei Endknoten, dieselbe
Auszahlung erhält, so ist das so gefundene Nash-GG eindeutig
Alternative Definitionen von (un)vollkommenen Information mit Hilfe von Informationsbezirken
· Spiel mit vollkommener Information: alle Informationsbezirke aller Spieler bestehen nur aus einem Entscheidungsknoten
· Spiel mit unvollkommener Information: mindestens ein Spieler hat einen Informationsbezirk, der mehr als einen
Entscheidungsknoten enthält
Ein Teilspiel eines Spiels in extensiver Form ist
eine Teilmenge des Spiels mit folgenden Eigenschaften:
(1) Es beginnt an einem Informationsbezirk, der nur einen
Entscheidungsknoten enthält
(2) Es enthält alle Nachfolger (unmittelbare und spätere)
dieses Entscheidungsknotens; Es enthält nur diese Knoten
(3) Es gibt keine durchgetrennten Informationsbezirke (falls der Entscheidungsknoten X zum Teilspiel gehört, so gehört jeder Entscheidungsknoten aus dem Informationsbezirk von X
auch zum Teilspiel)
(Selten, 1965): Ein Nash-Gleichgewicht in einem
Spiel in extensiver Form ist teilspielperfekt, falls es …
… in jedem Teilspiel dieses Spiels ein Nash-Gleichgewicht induziert.
• Jedes teilspielperfektes Gleichgewicht ist ein Nash-GG, aber nicht jedes Nash-GG ist teilspielperfekt
Gleichgewicht im extensiven Spiel:
Sammlung von Strategien (vollständigen Verhaltensplänen)
Ergebnis im extensiven Spiel:
Beschreibung, was passiert, wenn sich die Spieler an
den GG-Strategien halten
• Wenn das Basispiel G ein eindeutiges Nash-GG hat, so hat das endlich oft wiederholte Spiel G(T) …
… ein eindeutiges teilspielperfektes GG: das Nash-GG des Basisspiels wird auf jeder Stufe gespielt
Wenn das Basisspiel G mehr als ein Nash-GG hat, so kann das …
…. endlich oft wiederholte Spiel ein TSP-GG besitzen, in dem auf einer Stufe t < T kein Nash-GG des Basisspiels gespielt wird
Definition unendlich oft wiederholtes Spiel
- G ist ein Spiel in Normalform
- Dann bezeichnet G(∞, δ) das unendlich oft wiederholte
Spiel G, bei dem das Spiel G andauernd gespielt wird, und alle Spieler den Diskontfaktor δ mit 0 < δ < 1 haben
(Auszahlungen aus späteren Stufen werden mit dem Faktor δ per Stufe abdiskontiert).
[ δ ist quasi das 1/(1+i) aus I&F] - Seien π1, π2, … die Auszahlungen auf jeder Stufe. Die
Auszahlung für das Gesamtspiel für jeden Spieler ist der
Gegenwartswert des Auszahlungsstroms π1, π2, …
Gegenwartswert der unendlichen Auszahlungen, wenn diese in jeder Stufe gleich sind
π/(1-δ)
Bzw. Allgemein: Summe {von t=1 bis ∞} (δ^(t-1)*πt
Teilspiele in endlich oft wiederholten Spielen:
Ein Teilspiel im endlich oft wiederholten Spiel G(T), das in der Stufe t + 1 beginnt, ist das…
…T − t-mal wiederholte Spiel G.
Das Teilspiel wird mit G(T − t) bezeichnet.
Es gibt viele Teilspiele, die in der Stufe t + 1 beginnen, ein für jede mögliche “Historie” des Spiels bis zur Stufe t
Teilspiele in unendlich oft wiederholten Spielen:
Ein Teilspiel im unendlich oft wiederholten Spiel G(∞, δ), das in der Stufe t + 1 beginnt, ist ….
… identisch mit dem Originalspiel G(∞, δ).
Es gibt so viele Teilspiele, die in der Stufe t + 1 beginnen, wie es verschiedene mögliche “Historien” des Spiels bis zur Stufe t gibt
Eine Strategie im unendlich oft wiederholten Spiel G(∞, δ) spezifiziert…
… eine Aktion für den Spieler in jeder Stufe und für
jede mögliche Historie des Spiels bis zur vorhergehenden Stufe
Trigger Strategie
- Das Spiel beginnt mit gegenseitiger Kooperation.
- Es wird solange kooperiert, bis mindestens einer der Spieler defektiert.
- Daraus folgt als Bestrafung Defektion in den nachfolgenden Runden.
grim Trigger
Bestrafung bis zum Ende des Spiels
Tit for Tat
(Wie du mir, so ich dir)
Bestrafung nur in der nächsten Runde
Für einen gegebenen Diskontfaktor δ ist die
Durchschnittsauszahlung des unendlichen
Auszahlungsstroms π1, π2, π3, …
(1 − δ)Summe{von t=1 bis ∞} (δ^(t−1)πt)
Durchnittsauszahlung und Gegenwartswert
Die Durchschnittsauszahlung ist lediglich eine Reskalierung des Gegenwartswerts: Die Maximierung der Durchschnittsauszahlung ist äquivalent zur Maximierung des Gegenwartswerts
• Vorteil der Durchschnittsauszahlung im Vergleich zum
Gegenwartswert: die Durchschnittsauszahlung ist direkt mit den Auszahlungen aus dem Basisspiel vergleichbar
Folk-Theorem (Friedman, 1971)
Sei G ein endliches, statisches Spiel mit vollständiger Information. Seien (e1, . . . , en) die Auszahlungen eines Nash-Gleichgewichts von G. Seien (x1, . . . , xn) beliebige realisierbare Auszahlungen in G. Falls xi > ei für alle i = 1, …, n und falls δ hinreichend nahe bei 1 ist, so gibt es ein teilspielperfektes Nash-Gleichgewicht des unendlich oft wiederholten Spiels von G, in dem (x1, . . . , xn) als Durchschnittsauszahlungen erreicht werden
Ein unendlich oft wiederholtes Spiel verfügt über
… eine unendliche Vielfalt von teilspielperfekten Gleichgewichten mit extrem unterschiedlichen Spielergebnissen
⇒ Das Folk-Theorem hat einen geringen Vorhersagewert
• “Fast alle” Auszahlungen können als teilspielperfektes Ergebniserreicht werden, wenn die Spieler ausreichend geduldig sind
