Wiederholte Spiele
# Wiederholte Spiele

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 mehreren 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. Deshalb ist es möglich, sich in den Folgerunden gegenseitig zu „bestrafen“ oder zu „belohnen“.

Ein Großteil der Analyse wiederholter Spiele wurde von Robert Aumann angetrieben.

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).

## Struktur wiederholter Spiele

Wiederholte Interaktionen werden als dynamisches Spiel dargestellt, in dem die Spieler in jeder Runde das gleiche statische Spiel (Stufenspiel) $G$ spielen. Wird dieses Stufenspiel unendlich oft wiederholt, spricht man von einem Superspiel $G(\infty )$. Gegeben sei $G=\lbrace S_{1},\dotsc ,S_{n};\ u_{1},\dotsc ,u_{n}\rbrace$ ein statisches Spiel mit vollständiger Information, wobei Spieler $1{\text{ bis }}n$ aus der Strategiemenge $S_{1}{\text{ bis }}S_{n}$ simultan eine Strategie $s_{1}{\text{ bis }}s_{n}$ wählen und die Auszahlung $u_{1}(s_{1},\dotsc ,s_{n}){\text{ bis }}u_{n}(s_{1},\dotsc ,s_{n})$ erhalten. Die in einer Runde erhaltenen Auszahlungen der Spieler $u_{t}\ ({\text{wobei}}\ t=1,\dotsc ,n)$ hängen nur von den in der jeweiligen Runde gewählten Handlungen $s_{t}$ ab. Für alle einzelnen Runden bleibt der funktionale Zusammenhang $u_{t}\ (s_{t})$ gleich. Unmittelbar nach jeder Runde können die Strategien aller Spieler beobachtet werden. Der Spielverlauf bis zum Zeitpunkt t wird als $h_{t}$ bezeichnet. 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\leq \delta \leq 1$ dargestellt. Die Spieler versuchen ihre Auszahlungen über alle Runden hinweg zu maximieren: $\max \sum \nolimits _{t=0}^{n}\delta ^{t}{u_{i}}_{t}({s_{i}}_{t}(h_{t}))$. Je näher der Diskontfaktor bei Eins liegt, desto gleichgültiger sind die Spieler bezüglich des Auszahlungszeitpunkts. Liegt der Diskontfaktor $\delta$ nahe Null, ist die Zeitpräferenz sehr hoch und die Zukunft spielt keine Rolle. Dies kann mit einem statischen (one-shot) Spiel verglichen werden.

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.

## Endliche Wiederholung

Wird ein statisches Spiel, z. B. das Gefangenendilemma, mit absehbarem Ende mehrmals hintereinander von den gleichen Spielern wiederholt, spricht man von einem endlich oft wiederholten Spiel. Dabei ist die Unterscheidung von eindeutigem und multiplen Nash-Gleichgewichten von großer Bedeutung für den Spielausgang. Dies wird im Folgenden anhand von 2 Beispielen verdeutlicht:

### Eindeutiges Nash-Gleichgewicht

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

| 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.

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

| Spieler 1/Spieler 2 | Defektieren (d) | Kooperieren (c) |
| - | - | - |
| Defektieren (D) | (2, 2) | (6, 1) |
| Kooperieren (C) | (1, 6) | (5, 5) |

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.

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.

### Multiple Nash-Gleichgewichte

Das ursprüngliche Gefangenendilemma wird im Folgenden um eine Zusatzstrategie erweitert, wobei ein weiteres Nash-Gleichgewicht 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\leq \delta \leq 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 $\delta$ 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).

## 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. Jeder Spieler maximiert bei unendlichem Zeithorizont den Gegenwartswert seiner diskontierten Auszahlungen mit $0\leq \delta \leq 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.

### Trigger-Strategie

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

* 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.

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. $u_{i}(s^{*})$ steht für die Auszahlung, wenn in einer Runde die vereinbarte Strategie $s^{*}$ gespielt wird. $u_{i}(\sigma ^{*})$ steht für die Auszahlung, wenn sich alle Spieler über t Runden an die vereinbarte Strategie $s^{*}$ halten. Weicht allerdings einer der beiden Spieler von der Kooperation ab, weil einseitiges Defektieren kurzfristig eine höhere Auszahlung $u_{i}(r_{i}(s^{*}))$ einbringen kann, wird in den Folgerunden nicht mehr kooperiert und folglich nur noch eine Auszahlung von $u_{i}(s^{c})$ erreicht, wobei $s^{c}$ für die Strategie steht, in der das Nashgleichgewicht des Stufenspiels gespielt wird. Bei einem unendlich andauernden Spiel ist eine langfristige Betrachtung von Bedeutung. Die Spieler diskontieren ihre Auszahlung mit einem Faktor $0\leqq \delta \leqq 1$. 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:

    $u_{i}(\sigma ^{*})=u_{i}(s^{*})[1+\delta _{i}+\delta _{i}^{2}+\dotsc ]=u_{i}(s^{*})\sum \nolimits _{t=0}^{\infty }\delta _{i}^{t}={\dfrac {u_{i}(s^{*})}{(1-\delta _{i})}}$

Auszahlung für den Abweichler:

    $u_{i}(r_{i}(s^{*}))+u_{i}(s^{c}){\dfrac {\delta _{i}}{1-\delta _{i}}}$

Eine Abweichung auf $r_{i}(s^{*})$ ist folglich nicht vorteilhaft, falls gilt:

    ${\begin{aligned}u_{i}(r_{i}(s^{*}))+u_{i}(s^{c}){\dfrac {\delta _{i}}{1-\delta _{i}}}&<{\dfrac {u_{i}(s^{*})}{1-\delta _{i}}}\\u_{i}(r_{i}(s^{*}))+u_{i}(s^{*})&<[u_{i}(s^{*})-u_{i}(s^{c})]{\dfrac {\delta _{i}}{1-\delta _{i}}}\\\delta _{i}&>{\dfrac {u_{i}(r_{i}(s^{*}))-u_{i}(s^{*})}{u_{i}(r_{i}(s^{*}))-u_{i}(s^{c})}}\\\end{aligned}}$

Es gibt unter anderem 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.

| | 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 |
| Grim-Spieler | 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:

| | 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 |
| TfT-Spieler | 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:

* Freundlichkeit (nice): Es wird stets mit Kooperation begonnen und Defektion kommt nicht zustande, falls keiner von der Kooperation abweicht.
* Vergeltung (retaliatory): Kontinuierliche Defektion bringt keinen Vorteil, da mit gegenseitiger Defektion fortgefahren wird.
* Nachsicht (forgiveness): Sobald einer der Spieler wieder kooperiert, zieht der zweite Spieler nach. Fehler werden somit „verziehen“.
* 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.

### Beispiel

In einem unendlich oft wiederholten Spiel diskontieren die Spieler ihre Auszahlung mit dem Faktor $\delta$, wobei $0\leq \delta \leq 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 $\delta$. Demzufolge beträgt die Wahrscheinlichkeit, dass das Spiel nach der aktuellen Runde endet 1-$\delta$. Die Wahrscheinlichkeit, dass in Runde t noch gespielt wird, ist gleich $\delta ^{t}$. Wenn $\delta$ 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 $\operatorname {E} [\pi (D_{N},Grim)]\ {\text{und}}\ \operatorname {E} [\pi (C,C)]$ miteinander vergleichen. $\operatorname {E} [\pi (D_{N},Grim)]$ bezeichnet dabei den Erwartungswert der Auszahlung bei Abweichung und $\operatorname {E} [\pi (C,C)]$ den Erwartungswert der Auszahlung bei unendlicher Kooperation.

Abweichen lohnt, falls:

    ${\begin{aligned}\operatorname {E} [\pi (D_{N},Grim)]&\geqq \operatorname {E} [\pi (C,C)]\\5+\sum \nolimits _{t=1}^{\infty }\delta ^{t}*1&\geqq \sum \nolimits _{t=0}^{\infty }\delta ^{t}*4\\\end{aligned}}$

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

* ${\begin{aligned}\sum \nolimits _{t=0}^{\infty }\delta ^{t}={\dfrac {1}{1-\delta }}\qquad {\text{für}}\left|\delta \right|<1\\\end{aligned}}$
* $\sum \nolimits _{t=1}^{\infty }\delta ^{t}={\dfrac {\delta }{1-\delta }}\qquad {\text{für}}\left|\delta \right|<1\,$

Sodass sich für das vorliegende Gefangenendilemma ergibt:

    ${\begin{aligned}5+{\dfrac {\delta }{1-\delta }}&\geqq {\dfrac {4}{1-\delta }}\\5\cdot (1-\delta )+\delta &\geqq 4\\1&\geqq 4\cdot \delta \\{\dfrac {1}{4}}&\geqq \delta \\\end{aligned}}$

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 $\delta$*=1/4. Auf Dauer lässt sich durch Kooperation eine höhere Auszahlung als bei Defektion erwarten, wenn $\delta$* größer als 1/4 beträgt. Für $\delta \geq {\dfrac {1}{4}}$ bildet Kooperation ein teilspielperfektes Nash-Gleichgewicht.

### Folk Theorem

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 (falls Diskontfaktor nahe genug 1) eine höhere Auszahlung ergeben.

Diese Erkenntnis wird im sogenannten Folk-Theorem (allgemein bekannte „Geschichte“) festgehalten, welches besagt, dass jeder erreichbare und individuell rationale Auszahlungsvektor eines Stufenspiels eine teilspielperfekte Gleichgewichtsauszahlung im unendlich oft wiederholten Spiel $G(\infty )$ bilden kann, wenn der Diskontfaktor $\delta$ 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.

### One Deviation Principle

Das 'One-Deviation'-Prinzip dient zur Vereinfachung der Identifizierung von teilspielperfekten Nash-Gleichgewichten in sowohl endlich, als auch unendlich wiederholten Spielen.

Satz: Eine Strategie $s_{t}$ in einem endlich oder unendlich wiederholten Spiel, ist teilspielperfekt genau dann, wenn es keine Strategie $s'_{t}$ gibt, die bis auf eine Entscheidung identisch ist zum $s_{t}$ und eine höhere Auszahlung ergibt, falls diese Stufe erreicht wird.

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

