Benutzer:STHD6/Sandbox

aus Wikipedia, der freien Enzyklopädie

Wiederholte Spiele sind ein Spezialfall dynamischer Spiele in der Spieltheorie. Sie werden verwendet, um wiederholte Interaktionen zwischen Akteuren darzustellen. In einem solchen Spiel treffen die Akteure in der gleichen Entscheidungssituation in unbestimmter Anzahl von Perioden (Runden) aufeinander. Der Spielausgang unterscheidet sich deutlich von den statischen Spielen (One-Shot-Game), bei denen die Spieler nur einmalig interagieren. Dies ist darauf zurückzuführen, dass zukünftiges Verhalten der Spieler nur nach Wiederholung des Spiels auf ihr vergangenes Verhalten konditioniert werden kann. Von daher ist es möglich sich in den Folgerunden gegenseitig zu „bestrafen“ oder zu „belohnen“.[1] [2] Ein Großteil der Analyse wiederholter Spiele wurde von Robert Aumann (Nobelpreis 2005) angetrieben. Sein wissenschaftlicher Schwerpunkt lag auf der Untersuchung langfristiger Interaktion und kooperativem Verhalten basierend auf dem Modell der "egoistischen" Nutzenmaximierung. [3]

Beispiele für wiederholte Interaktionen: Konkurrenz auf Märkten (Anbieter auf einem Oligopolmarkt), Versicherungsverträge, Auktionen, Handeln innerhalb von Unternehmen oder Gruppen (Arbeitgeber und Arbeitnehmer, Familienmitglieder).[4]

Struktur wiederholter Spiele

Wiederholte Interaktionen werden als dynamisches Spiel dargestellt, in dem die Spieler in jeder Runde das gleiche statische Spiel (Stufenspiel) spielen. Wird dieses Stufenspiel unendlich oft wiederholt, spricht man von einem Superspiel . Gegeben sei ein statisches Spiel mit vollständiger Information, wobei Spieler aus der Strategiemenge simultan eine Strategie wählen und die Auszahlung erhalten. Die in einer Runde erhaltenen Auszahlungen der Spieler hängen nur von den in der jeweiligen Runde gewählten Handlungen ab. Für alle einzelnen Runden bleibt der funktionale Zusammenhang gleich. Unmittelbar nach jeder Runde können die Strategien aller Spieler beobachtet werden. Entscheidungen in vorhergehenden Runden beeinflussen somit die Strategien der Spieler und die daraus resultierenden Auszahlungen in nachfolgenden Runden. Die Zeitpräferenz der Spieler wird durch einen Diskontfaktor 0 1 dargestellt. Die Spieler versuchen ihre Auszahlungen über alle Runden hinweg zu maximieren: . Je näher der Diskontfaktor bei Eins liegt, desto gleichgültiger sind die Spieler bezüglich des Auszahlungszeitpunkts. Liegt der Diskontfaktor nahe Null, ist die Zeitpräferenz sehr hoch und die Zukunft spielt keine Rolle. Dies kann mit einem statischen (one-shot) Spiel verglichen werden. [5]

Relevant für den Ausgang eines wiederholten Spiels ist,

  • ob es endlich oder unendlich oft wiederholt wird,
  • ob das zugrunde liegende Stufenspiel nur ein Nash-Gleichgewicht oder mehrere Gleichgewichte besitzt und
  • ob Auszahlungen diskontiert werden oder nicht.[6]

Endliche Wiederholung

Eindeutiges Nash-Gleichgewicht

Angenommen, das zugrunde liegende Stufenspiel (Gefangenendilemma), mit dem eindeutigen Nash-Gleichgewicht (D,d), wird zweimal hintereinander gespielt:[1]

Spieler 1/Spieler 2 Defektieren (d) Kooperieren (c)
Defektieren (D) (1, 1) (5, 0)
Kooperieren (C) (0, 5) (4, 4)

In der ersten Runde bestimmen die Spieler gleichzeitig, ob sie „kooperieren“ oder „defektieren“. Nach Ende der ersten Runde werden die Entscheidungen der Spieler bekanntgegeben. Daraufhin wird das Stufenspiel wiederholt.[7]

Die Auszahlung ergibt sich nach dem Ausgang der zweiten Runde aus der Summe der Gleichgewichtsauszahlungen der einzelnen Runden:[1]

Spieler 1/Spieler 2 Defektieren (d) Kooperieren (c)
Defektieren (D) (2, 2) (6, 1)
Kooperieren (C) (1, 6) (5, 5)
2x wiederholtes Gefangenendilemma in Extensivform

Analyse des Spiels durch Rückwärtsinduktion:

Das vorliegende Spiel enthält 4 echte Teilspiele, die jeweils ab der zweiten Runde beginnen (siehe Grafik-Spielbaum).

2. Runde: Unabhängig von dem Spielausgang der ersten Runde wird in allen vier Teilspielen immer das Nash-Gleichgewicht (D, d) gespielt.

1. Runde: Die Auszahlung der zweiten Runde (1,1) wird zur Auszahlung der ersten Runde hinzu addiert, da die Entscheidung der ersten Runde keinen Einfluss auf den Spielausgang hat.

Das einzige Nash-Gleichgewicht entsteht, wenn beide Spieler in jeder Runde defektieren. Deshalb sollte auch in der ersten Runde nicht kooperiert werden. Dies resultiert daraus, dass in der zweiten Runde abweichendes Verhalten nicht sanktioniert werden kann. Kooperation kann in einem 2x2 Gefangenendilemma aus rationaler Sicht nicht erreicht werden.

Definition (Reinhard Selten 1965): Ein Nash-Gleichgewicht ist teilspielperfekt, wenn die Strategien der Spieler in jedem Teilspiel ein Nash-Gleichgewicht bilden.[8]

Das einzige teilspielperfekte Gleichgewicht (grün) entsteht, wenn beide Spieler in jeder Runde „defektieren“:

Strategie Sp. 1: (D1, D2D2D2D2),

Strategie Sp. 2: (d1, d2d2d2d2),

wobei (D1,d1) die Strategienkombination der 1. Runde und (D2D2D2D2, d2d2d2d2) die Strategienkombination an jedem Teilspiel der 2. Runde bezeichnet.

Resultat: Wenn das Stufenspiel ein eindeutiges Nash-Gleichgewicht besitzt, dann hat das wiederholte Spiel G(T), für T endlich, ein eindeutiges teilspielperfektes Gleichgewicht, nämlich die Wiederholung des Nash-Gleichgewichts des Stufenspiels in jeder Runde.[9]

Multiple Nash-Gleichgewichte

Das ursprüngliche Gefangenendilemma wird im folgenden um eine Zusatzstrategie erweitert, wobei ein weiteres Nash-Gleichtgewicht entsteht. Angenommen, das Stufenspiel (erweitertes Gefangenendilemma) mit zwei reinen Nash-Gleichgewichten (D,d) und (E,e) wird zweimal hintereinander gespielt:

Spieler 1/Spieler 2 Defektieren (d) Kooperieren (c) Zusatzstrategie (e)
Defektieren (D) (1, 1) (5, 0) (0, 0)
Kooperieren (C) (0, 5) (4, 4) (0, 0)
Zusatzstrategie (E) (0, 0) (0, 0) (3, 3)

In der ersten Runde bestimmen die Spieler gleichzeitig ihre Strategie. Im Anschluss werden die Entscheidungen der Spieler bekanntgegeben. Daraufhin wird das Stufenspiel wiederholt. Auch im erweiterten Spiel G(2) existiert Teilspielperfektheit, wenn unabhängig vom Spielverlauf in jeder Runde das Nash-Gleichgewicht (D,d) gewählt wird (siehe eindeutiges Gleichgewicht). Es gibt allerdings noch weitere teilspielperfekte Gleichgewichte in G(2), welche mit Hilfe von Rückwärtsinduktion ermittelt werden können:

2. Runde: Unabhängig vom Spielausgang der ersten Runde wird in allen neun Teilspielen immer ein Nash-Gleichgewicht gespielt. Da im vorliegenden Spiel zwei Gleichgewichte existieren, wovon eines eine höhere Auszahlung ergibt (E,e) und eines eine niedrigere (D,d), kann in dieser Runde die Entscheidung der ersten Runde sanktioniert oder belohnt werden.

1. Runde: In der ersten Runde antizipieren die Spieler, dass in der 2. Runde ein Nash-Gleichgewicht des Teilspiels gespielt wird. Da zwei Nash-Gleichgewichte existieren, ist es für die Spieler möglich durch die Wahl der Strategie in dieser Runde den Spielausgang zu beeinflussen. Dies ist abhängig vom Diskontfaktor 0 1. Je näher der Wert bei 1 liegt, desto eher kooperieren die Spieler, da Auszahlungen in weiteren Runden höher gewichtet werden. Für gegen 0, verhält es sich genau entgegengesetzt.

Kooperation wird hier ermöglicht, aufgrund von glaubwürdiger Androhung das „schlechtere“ Nash-Gleichgewicht (D,d) in der zweiten Runde zu spielen, falls in der ersten Runde abgewichen wurde. Eine Abweichung von der Strategie (C,c) bringt zwar in der 1. Runde eine höhere Auszahlung für den abweichenden Spieler, jedoch insgesamt eine geringere: (C,c)+(E,e)=(7,7) bei Kooperation und (D,c)+(D,d)=(6,1) bzw. (C,d)+(D,d)=(1,6) bei einseitigem Abweichen. Auch wenn in beiden Runden die Zusatzstrategie (E,e) gespielt wird, fällt die Auszahlung geringer aus (6,6)<(7,7).

Resultat: Bei einem endlich wiederholten Spiel mit mehreren Nash-Gleichgewichten können Gleichgewichte bestehen, in denen Strategien gewählt werden, die im Stufenspiel keine Nash-Gleichgewichte bilden, wie zum Beispiel die pareto-optimale Strategienkombination (C,c).[10]

Unendliche Wiederholung

Im Gegensatz zu endlich häufigen Wiederholungen, kann es bei unendlich oft bzw. unbestimmt oft wiederholten Spielen profitabel sein mit seinem Gegenspieler zu kooperieren. Es ist nicht mehr sinnvoll anzunehmen, dass die Spieler die Summe ihrer Auszahlungen maximieren. Jeder Spieler maximiert bei unendlichem Zeithorizont den Gegenwartswert seiner diskontierten Auszahlungen mit 0 1. Eine Analyse des Spiels mit Hilfe der Rückwärtsinduktion ist nun auf Grund des Fehlens einer definitiv letzten Runde nicht mehr möglich. Das entstehende Spiel komplett zu analysieren ist wegen der sehr hohen Zahl an möglichen Strategien sehr aufwendig. Man muss sich deswegen auf die Formulierung einiger expliziter Strategien beschränken.[11]

Trigger-Strategie

Trigger-Strategien sind die bekanntesten Strategien bei unendlichen Spielen. Sie sind durch folgende Merkmale gekennzeichnet:

  1. Das Spiel beginnt mit gegenseitiger Kooperation.
  2. Es wird solange kooperiert, bis mindestens einer der Spieler defektiert.
  3. Daraus folgt als Bestrafung Defektion in den nachfolgenden Runden.[12]

Relevant für den Spielausgang ist, neben der Auswahl einer Strategie, die Reputation der Spieler. Durch wiederholte Interaktion ist es möglich zu kooperieren und einen pareto-optimalen Zustand zu erreichen. Weicht allerdings einer der beiden Spieler von der Kooperation ab, weil einseitiges Defektieren kurzfristig eine höhere Auszahlung einbringen kann, wird in den Folgerunden nicht mehr kooperiert. Bei einem unendlich andauernden Spiel ist eine langfristige Betrachtung von Bedeutung. Die Spieler diskontieren ihre Auszahlung mit einem Faktor . Für den Fall, dass der diskontierte Wert zukünftiger Rundengewinne bei Kooperation den Wert der einmaligen Abweichung und anschließend fortdauernder Defektion übertrifft, wird bei rationalem Verhalten der Spieler kooperiert. Folglich kann es für die Spieler sinnvoll sein, von einem kurzfristig höheren Gewinn abzusehen, um langfristig höhere Auszahlungen zu erzielen.

Auszahlung, wenn sich alle Spieler an die Vereinbarungen halten:

Auszahlung für den Abweichler:

Eine Abweichung auf ist folglich nicht vorteilhaft, falls gilt:


Man unterscheidet folgende Abwandlungen der Trigger Strategien:

  • Grim-Trigger ist die schärfste Form der Sanktion von unkooperativem Verhalten, da nach einmaliger Abweichung bis zum Ende des Spiels defektiert wird.[12]
Zug 1 Zug 2 Zug 3 Zug 4 Zug 5 Zug 6 Zug 7 Zug 8 ...
Spieler A C C C D D D D D
Spieler B C C C C D D D D
  • Tit for Tat (Wie du mir, so ich dir) ist eine abgeschwächte Form der Trigger-Strategie. Die vorangegangene Strategie des Gegenspielers wird in der aktuellen Runde imitiert. Das Spiel beginnt mit kooperativem Verhalten, bis einer der Spieler abweicht. Anders als bei Grim-Trigger kann hier, bei einmaliger Abweichung, Kooperation wieder erreicht werden:[13]
Zug 1 Zug 2 Zug 3 Zug 4 Zug 5 Zug 6 Zug 7 Zug 8 ...
Spieler A C C D C C D D C
Spieler B C C C D C C D D

Evidenz durch Experimente (Axelrod)

Um erfolgreiche Strategien in einem unendlich wiederholten Gefangenendilemma zu ermitteln, entwickelte Robert Axelrod ein Computer-Programm, bei dem verschiedene Strategien gegeneinander antraten. Das Ergebnis des Experiments: Über den gesamten Spielverlauf hinweg erzielt die Tit-for-Tat-Strategie das beste Ergebnis, obwohl diese im Einzelvergleich anderen Strategien unterlegen ist. Gründe dafür sind:

1. Freundlichkeit (nice): Es wird stets mit Kooperation begonnen und Defektion kommt nicht zustande, falls keiner von der Kooperation abweicht.

2. Vergeltung (retaliatory): Kontinuierliche Defektion bringt keinen Vorteil, da mit gegenseitiger Defektion fortgefahren wird.

3. Nachsicht (forgiveness): Sobald einer der Spieler wieder kooperiert, zieht der zweite Spieler nach. Fehler werden somit „verziehen“.

4. Einfachheit der Strategie: sie wird von Spielern sehr leicht erkannt, weshalb eine langfristige Kooperation ermöglicht werden kann.

Fazit: Tit-for-Tat kombiniert die Eigenschaften, dass sich einerseits Freundlichkeit durch langfristige Kooperation auszahlt und andererseits abweichendes Verhalten sanktioniert werden kann. Sie schneidet bei unendlicher Wiederholung des Gefangenendilemmas am besten ab, da sie die Gesamtauszahlung der Spieler maximiert.[13][14]

Beispiel

In einem unendlich oft wiederholten Spiel diskontieren die Spieler ihre Auszahlung mit dem Faktor , wobei 0 1. Dieser Faktor kann auch als Fortsetzungswahrscheinlichkeit interpretiert werden, da die Spieler nicht wissen, ob das Spiel mit Sicherheit fortgeführt wird oder nicht. Für das vorliegende Beispiel sollen folgende Annahmen gelten: Ob eine weitere Runde des wiederholten Spiels folgen wird, ist unsicher. Die Wahrscheinlichkeit, dass auf eine Runde eine weitere Runde folgen wird, beträgt . Demzufolge beträgt die Wahrscheinlichkeit, dass das Spiel nach der aktuellen Runde endet 1-. Die Wahrscheinlichkeit, dass in Runde t noch gespielt wird, ist gleich ^t. Wenn hinreichend groß ist, existiert im unendlich oft wiederholten Gefangenendilemma ein teilspielperfektes Gleichgewicht, in dem beide Spieler entlang des Gleichgewichtspfades in allen Runden kooperieren.

Spieler 1/Spieler 2 Defektieren (d) Kooperieren (c)
Defektieren (D) (1, 1) (5, 0)
Kooperieren (C) (0, 5) (4, 4)

Mit den gegebenen Annahmen kann man eine bestimmte dynamische Strategie untersuchen. Mit der Grim-Trigger Strategie kooperiert man so lange bis der Gegenspieler defektiert, um dann seinerseits auch in jeder Runde zu defektieren. Wird Grim-Trigger von beiden Spielern angewandt, so wird in jeder Runde kooperiert und die Spieler erhalten eine Auszahlung von 4.

Anders verhält sich die Auszahlung, wenn ein Spieler die Kooperation nicht einhält und ab Runde N defektiert. Daraus folgt, dass der Spieler mit der Grim-Strategie bis Runde N kooperiert und in den nachfolgenden Runden ausschließlich defektiert. In den ersten N-1 Runden erhält der Spieler, welcher die Kooperation ab Runde N verweigert, eine Auszahlung von 4. In Runde N erhält er 5 und in den nachfolgenden Runden nur noch eine Auszahlung von 1.

Um festzustellen, ob es profitabel ist bei einem Grim-Spieler von der Kooperation abzuweichen, muss man die Auszahlungen von miteinander vergleichen. bezeichnet dabei den Erwartungswert der Auszahlung bei Abweichung und den Erwartungswert der Auszahlung bei unendlicher Kooperation.[11]

Abweichen lohnt, falls:



Mit Hilfe der Grenzwertsätze für unendliche geometrische Reihen lässt sich der erste Teil vereinfachen:


Sodass sich für das vorliegende Gefangenendilemma ergibt:



Kooperation ist nur dann profitabel, wenn auf die jetzige Runde mit hinreichend hoher Wahrscheinlichkeit eine weitere folgt. In diesem Beispiel des unbestimmt oft wiederholten Gefangenendilemmas liegt der kritische Punkt bei *=1/4. Auf Dauer lässt sich durch Kooperation eine höhere Auszahlung als bei Defektion erwarten, wenn * größer als 1/4 beträgt. Für bildet Kooperation ein teilspielperfektes Nash-Gleichgewicht.[15]

Folk Theorem

Im Gefangenendilemma durch gemischte Strategien erreichbare Auszahlungen

Folk-Theoreme besagen, dass jeder erreichbare und individuell rationale Auszahlungsvektor eines Stufenspiels eine teilspielperfekte Gleichgewichtsauszahlung im unendlich oft wiederholten Spiel bilden kann, wenn der Diskontfaktor nahe genug bei 1 liegt. Erreichbarkeit und individuelle Rationalität gelten sowohl als notwendige, als auch (fast immer) als hinreichende Bedingung, damit der Auszahlungsvektor eine Gleichgewichtsauszahlung darstellt.[16]

Anhand des vorangegangenen Beispiels (Gefangenendilemma)

Spieler 1/Spieler 2 Defektieren (d) Kooperieren (c)
Defektieren (D) (1, 1) (5, 0)
Kooperieren (C) (0, 5) (4, 4)

kann der erreichbare Auszahlungsvektor grafisch veranschaulicht werden (siehe Grafik). Bei unendlicher Wiederholung dieses Gefangenendilemmas ist es möglich teilspielperfekte Gleichgewichte zu erreichen, die von dem statischen Nash-Gleichgewicht (D,d) abweichen und langfristig eine höhere Auszahlung ergeben.

One Deviation Principle

Das 'One Deviation'-Prinzip dient zur Vereinfachung der Identifizierung von teilspielperfekten Nash-Gleichgewichten in sowohl endlich, als auch unendlich wiederholten Spielen. Das Prinzip besagt, dass kein Spieler seine Auszahlung erhöhen kann, indem er in einem Teilspiel eine Strategie wählt, die von der Gleichgewichtsstrategie abweicht.

Resultat: Ein Strategienprofil eines wiederholten Spiels ist nur dann ein teilspielperfektes Nash-Gleichgewicht, wenn es die One-Deviation Eigenschaft erfüllt.[17][18]

Siehe auch

Literatur

Drew Fudenberg, David Levine: Subgame-perfect equilibria of finite- and infinite-horizon games, Journal of Economic Theory, Volume 31, Issue 2, December 1983, Pages 251-268

Drew Fudenberg, Jean Tirole: Game Theory, The MIT Press, Cambridge, Massachusetts 1991

Dilip Abreu, Prajit K. Dutta and Lones Smith: The Folk Theorem for Repeated Games: A Neu Condition, Econometrica, Vol. 62, No. 4, July 1994

Ebbe Hendon, Hans Jørgen Jacobsen, Birgitte Sloth: The One-Shot-Deviation Principle for Sequential Rationality, Games and Economic Behavior, Volume 12, Issue 2, February 1996, Pages 274-282

Gernot Sieg: Spieltheorie, 3. Auflage, Oldenbourg, München 2010

Joachim Zentes: Kooperationen, Allianzen und Netzwerke: Grundlagen - Ansätze - Perspektiven, 2. Auflage, Gabler, Wiesbaden 2005

Manfred J. Holler, Gerhard Illing: Einführung in die Spieltheorie, 7. Auflage, Springer, Berlin 2009

Robert Axelrod and William D. Hamilton: The Evolution of Cooperation, Science, Vol. 211, 27 March 1981

Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow 1992

Sergiu Hart: Robert Aumann’s Game and Economic Theory, Scandinavian Journal of Economics, Vol. 108(2), March 2006, Pages 185-211

Siegfried Berninghaus, Siegfried K. Berninghaus, Karl-Martin Ehrhart: Strategische Spiele: Eine Einführung in die Spieltheorie, 3. Auflage, Springer, Berlin 2010

Sylvain Sorin: Repeated Games with Incomplete Information. Robert J. Aumann and Michael B. Maschler, with the collaboration of Richard E. Stearns, Games and Economic Behavior, Volume 16, Issue 2, October 1996, Pages 347-352

Thomas Riechmann: Spieltheorie, 3. Auflage, Vahlen, München 2010

Weblinks

Einzelnachweise

  1. a b c Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow 1992, Seite 82
  2. Thomas Riechmann: Spieltheorie, 3. Auflage, Vahlen, München 2010, Seite 141
  3. Sergiu Hart: Robert Aumann’s Game and Economic Theory, Scand. J. of Economics 108(2), Israel 2006, Seite 185
  4. Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, Seite 145
  5. Manfred J. Holler, Gerhard Illing: Einführung in die Spieltheorie, 7. Auflage, Springer, Berlin 2009, Seite 129-132
  6. Siegfried Berninghaus, Siegfried K Berninghaus, Karl-Martin Ehrhart: Strategische Spiele: Eine Einführung in die Spieltheorie, 3. Auflage, Springer, Berlin 2010, Seite 348
  7. Gernot Sieg: Spieltheorie, 3. Auflage, Oldenbourg, München 2010, Seite 56
  8. Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow 1992, Seite 95
  9. Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow 1992, Seite 84
  10. Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow 1992, Seite 84-88
  11. a b Thomas Riechmann: Spieltheorie, 3. Auflage, Vahlen, München 2010, Seite 146-148
  12. a b Joachim Zentes: Kooperationen, Allianzen und Netzwerke: Grundlagen - Ansätze - Perspektiven, 2. Auflage, Gabler, Wiesbaden 2005, Seite 129
  13. a b Joachim Zentes: Kooperationen, Allianzen und Netzwerke: Grundlagen - Ansätze - Perspektiven, 2. Auflage, Gabler, Wiesbaden 2005, Seite 130
  14. Gernot Sieg: Spieltheorie, 3. Auflage, Oldenbourg, München 2010, Seite 57 ff.
  15. Thomas Riechmann: Spieltheorie, 3. Auflage, Vahlen, München 2010, Seite 153-155
  16. Dilip Abreu, Prajit K. Dutta and Lones Smith: The Folk Theorem for Repeated Games: A Neu Condition, Econometrica, Vol. 62, No. 4 (July, 1994), Seite 939
  17. Ebbe Hendon, Hans Jørgen Jacobsen, Birgitte Sloth: The One-Shot-Deviation Principle for Sequential Rationality, Games and Economic Behavior, Volume 12, Issue 2, February 1996, Seite 274-282
  18. Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, Seite 109