Wiederholte Spiele

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

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]

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]

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:

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 ${\displaystyle 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 ${\displaystyle \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).[10]

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. ${\displaystyle u_{i}(s^{*})}$ steht für die Auszahlung, wenn in einer Runde die vereinbarte Strategie ${\displaystyle s^{*}}$ gespielt wird. ${\displaystyle u_{i}(\sigma ^{*})}$ steht für die Auszahlung, wenn sich alle Spieler über t Runden an die vereinbarte Strategie ${\displaystyle s^{*}}$ halten. Weicht allerdings einer der beiden Spieler von der Kooperation ab, weil einseitiges Defektieren kurzfristig eine höhere Auszahlung ${\displaystyle u_{i}(r_{i}(s^{*}))}$ einbringen kann, wird in den Folgerunden nicht mehr kooperiert und folglich nur noch eine Auszahlung von ${\displaystyle u_{i}(s^{c})}$ erreicht, wobei ${\displaystyle 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 ${\displaystyle 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:

${\displaystyle 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:

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

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

${\displaystyle {\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.[12]

• 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]

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]

In einem unendlich oft wiederholten Spiel diskontieren die Spieler ihre Auszahlung mit dem Faktor ${\displaystyle \delta }$, wobei ${\displaystyle 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 ${\displaystyle \delta }$. Demzufolge beträgt die Wahrscheinlichkeit, dass das Spiel nach der aktuellen Runde endet 1-${\displaystyle \delta }$. Die Wahrscheinlichkeit, dass in Runde t noch gespielt wird, ist gleich ${\displaystyle \delta ^{t}}$. Wenn ${\displaystyle \delta }$ hinreichend groß ist, existiert im unendlich oft wiederholten Gefangenendilemma ein teilspielperfektes Gleichgewicht, in dem beide Spieler entlang des Gleichgewichtspfades in allen Runden kooperieren.

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 ${\displaystyle \operatorname {E} [\pi (D_{N},Grim)]\ {\text{und}}\ \operatorname {E} [\pi (C,C)]}$ miteinander vergleichen. ${\displaystyle \operatorname {E} [\pi (D_{N},Grim)]}$ bezeichnet dabei den Erwartungswert der Auszahlung bei Abweichung und ${\displaystyle \operatorname {E} [\pi (C,C)]}$ den Erwartungswert der Auszahlung bei unendlicher Kooperation.[11]

Abweichen lohnt, falls:

${\displaystyle {\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:

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

• ${\displaystyle \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:

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

Im Gefangenendilemma durch gemischte Strategien erreichbare Auszahlungen

Anhand des vorangegangenen Beispiels (Gefangenendilemma)

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 ${\displaystyle G(\infty )}$ bilden kann, wenn der Diskontfaktor ${\displaystyle \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.[16]

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

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

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