8. Wiederholte Spiele in:

Thomas Riechmann

Spieltheorie, page 152 - 166

4. Edition 2013, ISBN print: 978-3-8006-4750-7, ISBN online: 978-3-8006-4751-4, https://doi.org/10.15358/9783800647514_152

Series: Vahlens Kurzlehrbücher

Bibliographic information
8. Wiederholte Spiele Spielt man dasselbe statische oder sequentielle Spiel mehrmals hintereinander, spricht man von einem wiederholten Spiel (repeated game). Jede „Runde“ des wiederholten Spiels heißt Stufenspiel (stage game). Wird also das einfache Stufenspiel G insgesamt T –mal nacheinander gespielt, so heißt das resultierende Spiel wiederholtes Spiel GT . Relativ einfach zu untersuchen sind die Wiederholungen solcher Spiele, die als Stufenspiel ein eindeutiges (und damit dominantes) Gleichgewicht besitzen, denn bei diesen Spielen gibt es zumindest theoretisch keinen Zweifel darüber, was in der einstufigen Version des Spiels gespielt würde. Hat dagegen schon das Stufenspiel mehrere Gleichgewichte, wird die Analyse einer wiederholten Version des Spiels sehr kompliziert. 8.1 Wiederholtes Gefangenendilemma Als Beispiel soll das Gefangenendilemma (Spiel G, Abschnitt 3.6.1) betrachtet werden. Das Gefangenendilemma hat in seiner Grundversion als Stufenspiel ein eindeutiges Gleichgewicht und ist deshalb ein relativ einfacher Gegenstand der Analyse wiederholter Spiele. Die Auszahlungen des statischen Gefangenendilemmas sind in Tab. 8.1 gegeben. Die extensive Form ist in Abb. 8.1 dargestellt. B Gestehen g Leugnen l Gestehen g -3, -3 0, -6A Leugnen l -6, 0 -1, -1 Tabelle 8.1: Gefangenendilemma G 8.1.1 Zweistufiges Spiel Nun soll das Gefangenendilemma betrachtet werden, wenn es zweimal hintereinander gespielt wird, also das Spiel G2. Die Auszahlungen ergeben sich jeweils als Summe der Auszahlung aus dem Spiel der ersten Stufe und der Auszahlung aus dem Spiel der zweiten Stufe. Das zweistufige Gefangenendilemma ist in extensiver Form in Abb. 8.2 dargestellt. 142 8. Wiederholte Spiele −3, −3 0, −6 A g g gl l l −6, 0 −1, −1 B B Abbildung 8.1: Gefangenendilemma. Extensive Form. Auszahlungen an (A, B) A B l B l g g l g A B l B l g g l g A B l B l g g l g A B l B l g g l g A B B l l l g g g −6, −6 −3, −9 −9, −3 −4, −4 −3, −9 0, −12 −6, −6 −1, −7 −9, −3 −6, −6 −12, 0 −7, −1 −4, −4 −1, −7 −7, −1 −2, −2 Abbildung 8.2: Zweistufiges Gefangenendilemma G2. Extensive Form. Auszahlungen an (A, B) 8.1 Wiederholtes Gefangenendilemma 143 Die Darstellung der Normalform von G2 ist schon sehr aufwendig: Strategien für A müssen jeweils eine Aktion (von jeweils zwei verfügbaren) pro relevanter Entscheidungssituation spezifizieren. Insgesamt existieren für A fünf relevante Entscheidungssituationen: Die Entscheidung im Wurzelknoten sowie Entscheidungen nach A:g, B:g, nach A:g, B:l, nach A:l, B:g und nach A:l, B:l. Die Aktionsmenge ist jeweils {l, g}, hat also zwei Elemente. Damit resultieren für A 25 = 32 Strategien im Spiel G2. Die Strategien sollen so notiert werden, dass der erste Buchstabe die Aktion im Wurzelknoten angibt, die folgenden Buchstaben die Aktionen nach A:g, B:g, nach A:g, B:l, nach A:l, B:g und nach A:l, B:l, also den Baum aus Abb. 8.2 abwärts. Ähnliches gilt für die Strategien für B. Strategien für B müssen jeweils eine Aktion von B pro distinkter Informationsmenge spezifizieren, also insgesamt fünf Aktionen. Damit gibt es auch für B 32 verschiedene Strategien. Die Notation für B geschieht analog zum Muster für A. Die strategische Form wird angesichts der vielen Strategien etwas unhandlich, wie die Darstellung in den Tabellen 8.2 und 8.3 zeigt. Zwar lässt sich die strategische Form leicht reduzieren, um dies zu können, muss man sie aber erst einmal erstellt haben. Das jedoch ist kein Kindergeburtstag! Glücklicherweise gibt es andere Wege, Stufenspiele mit endlich vielen Stufen zu analysieren. Und diese anderen Wege sind doch etwas weniger umfangreich. Man bedient sich einfach wieder der Rückwärtsanalyse: In der letzten, d.h. der zweiten Stufe ist sicher, dass beide Spieler „gestehen“ werden. Dies ist im einstufigen Spiel die dominante Verhaltensweise. Etwaige Vergeltungsaktionen des Gegenspielers in der Zukunft hat keiner zu erwarten: In der letzten Periode gibt es keine Zukunft. Damit sind die Auszahlungen aus dem zweiten Stufenspiel klar: Jeder Spieler erhält −3. Somit lässt sich die Auszahlungstabelle Tab. 8.1 so modifizieren, dass sie die Auszahlungen beider Perioden enthält (Tab. 8.4), indem man zu den Auszahlungen aus Tab. 8.1 für jedes Aktionsprofil die Auszahlungen (−3,−3) aus der letzten Periode addiert. Es lässt sich leicht erkennen, dass immer noch (g, g) ein dominantes Gleichgewicht ist. Der Grund dafür ist die Tatsache, dass zu allen Auszahlungen dieselbe Auszahlung, (−3,−3) addiert wird. Hierdurch bleibt das ordinale Verhältnis („die Rangfolge“) der Auszahlungen für jeden Spieler unverändert. Beste Antworten, Nash–Strategien und dominante Strategien werden durch diese Auszahlungstransformation nicht verändert. Im zweistufigen Gefangenendilemma wird also genau wie im einstufigen von beiden Spielern „gestehen“ gespielt. 8.1.2 Endlich oft wiederholtes Spiel Dieselbe Überlegung wie beim zweistufigen Gefangenendilemma lässt sich für jede endliche Wiederholung des Spiels, also für GT mit T < ∞ anstellen: In der letzten Stufe, in Stufe T wird in jedem Fall (g, g) gespielt. Da dies 144 8. W iederholte Spiele B g,gggg g,gggl g,gglg g,ggll g,glgg g,glgl g,gllg g,glll g,lggg g,lggl g,lglg g,lgll g,llgg g,llgl g,lllg g,llll A g,gggg -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,gggl -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,gglg -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,ggll -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,glgg -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,glgl -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,gllg -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,glll -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -6, -6 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 -3, -9 g,lggg -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,lggl -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,lglg -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,lgll -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,llgg -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,llgl -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,lllg -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 g,llll -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 -9, -3 -9, -3 -9, -3 -9, -3 -4, -4 -4, -4 -4, -4 -4, -4 l,gggg -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,gggl -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,gglg -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,ggll -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,glgg -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,glgl -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,gllg -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,glll -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,lggg -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,lggl -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,lglg -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,lgll -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,llgg -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,llgl -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 -9, -3 -9, -3 -6, -6 -6, -6 l,lllg -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 l,llll -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 -12, 0 -12, 0 -7, -7 -7, -1 Tabelle 8.2: Zweistufiges Gefangenendilemma G2. Normalform. Erster Teil 8.1 W iederholtes G efangenendilem m a 145 B l,gggg l,gggl l,gglg l,ggll l,glgg l,glgl l,gllg l,glll l,lggg l,lggl l,lglg l,lgll l,llgg l,llgl l,lllg l,llll A g,gggg -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,gggl -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,gglg -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,ggll -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,glgg -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,glgl -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,gllg -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,glll -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,lggg -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,lggl -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,lglg -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,lgll -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 -3, -9 -3, -9 -3, -9 -3, -9 0, -12 0, -12 0, -12 0, -12 g,llgg -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,llgl -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,lllg -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 g,llll -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 -6, -6 -6, -6 -6, -6 -6, -6 -1, -7 -1, -7 -1, -7 -1, -7 l,gggg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,gggl -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,gglg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,ggll -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,glgg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,glgl -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,gllg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,glll -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,lggg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,lggl -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,lglg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,lgll -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,llgg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,llgl -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 l,lllg -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 -4, -4 -1, -7 l,llll -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 -7, -1 -2, -2 Tabelle 8.3: Zweistufiges Gefangenendilemma G2. Normalform. Zweiter Teil 146 8. Wiederholte Spiele B Gestehen g Leugnen l Gestehen g -3 + (-3), -3 + (-3) 0 + (-3), -6 + (-3)A Leugnen l -6 + (-3), 0 + (-3) -1 + (-3), -1 + (-3) Tabelle 8.4: Gefangenendilemma G2. Auszahlungen gewiss ist, können beide Spieler auch in Stufe T − 1 (g, g) spielen. Dies ist so sicher, dass auch in Stufe T − 2 (g, g) das Aktionsprofil der Wahl ist, u.s.w. Diese Argumentation lässt sich wieder in Auszahlungstabellen umsetzen: In Stufe T gilt die Auszahlungstabelle 8.1. Aus dieser Tabelle folgt, dass (g, g) als dominantes Gleichgewicht des Spiels sicher gespielt werden wird. Hieraus folgt, dass in Stufe T −1 Tab. 8.4 die relevante Auszahlungstabelle ist. Aus dieser Tabelle folgt, dass auch in T −1 (g, g) gespielt werden wird. Hieraus lässt sich die Auszahlungstabelle für T − 2 errechnen, die aus der Tabelle für T (Tab. 8.1) dadurch entsteht, dass zu allen Auszahlungen 2 ·(−3) addiert wird. Tab. 8.5 ist eine allgemeine Auszahlungstabelle für jede Stufe T − t des Spiels Gt : B g l g (−3+ t · (−3)), (−3+ t · (−3)) (t · (−3)), (−6+ t · (−3))A l (−6+ t · (−3)), (t · (−3)) (−1+ t · (−3)), (−1+ t · (−3)) Tabelle 8.5: Gefangenendilemma GT−t . Auszahlungen In jeder Stufe T − t des endlich wiederholten Gefangenendilemmas ist (g, g) dominant und wird gespielt. Dies ist das Hauptergebnis der Überlegungen: Egal, wie oft das Gefangenendilemma wiederholt wird — wenn beide Spieler sicher wissen, welche Periode die letzte ist, werden sie immer beide „gestehen“. Zu einer Kooperation im Sinne beidseitigen „Leugnens“ wird es bei endlicher Wiederholung nicht kommen. 8.1.3 Unbestimmt oft wiederholtes Spiel Wird das Gefangenendilemma unendlich oft oder unbestimmt oft wiederholt, kann es — im Gegensatz zur endlich häufigen Wiederholung — sinnvoll sein, zu kooperieren. Durch das Fehlen einer definitiv letzten Runde des Spiels ist eine Analyse mit Hilfe der Rückwärtsinduktion nicht mehr möglich. Angesichts der extrem hohen Zahl möglicher Strategien und Strategieprofile ist es in der arg begrenzten Lebenszeit theoretischer Ökonomen 8.1 Wiederholtes Gefangenendilemma 147 kaum möglich, das entstehende Spiel komplett zu analysieren. Stattdessen muss eine Beschränkung auf einige explizit formulierte Strategien ausreichen. Für die folgende Untersuchung soll zunächst folgende Annahme getroffen werden: In jeder Runde des wiederholten Spiels ist unsicher, ob eine weitere Runde folgen wird. Die Wahrscheinlichkeit, dass sich an eine Runde eine weitere anschließt, betrage p. Entsprechend ist die Wahrscheinlichkeit des Spielendes nach der aktuellen Runde gleich 1− p. Folglich ist die Wahrscheinlichkeit, dass Runde Nummer t überhaupt erreicht wird, gleich pt . Unter diesen Bedingungen soll eine bestimmte (dynamische) Strategie untersucht werden, die häufig Grim genannt wird. Grim fordert, so lange zu kooperieren (zu „leugnen“), bis der Gegner defektiert („gesteht“), dann aber immer selbst zu defektieren. Falls beide Spieler Grim spielen, wird keiner der beiden jemals defektieren. Es wird also in allen Runden kooperiert, die Auszahlung für jeden der Spieler in jeder Runde beträgt also −1. Die erwartete Auszahlung aus dem kompletten Spiel, E [π(C,C)], lautet E [π(C,C)] = −1+ p · (−1)+ p2 · (−1)+ . . . . Verweigert dagegen einer der Spieler die Kooperation und defektiert ab Runde Nummer N, so wird sein Grim–spielender Gegner bis einschließlich Runde N kooperieren, danach aber defektieren. Der Kooperations– Verweigerer erhält damit in den ersten N − 1 Runden jeweils eine Auszahlung von −1 (Beide kooperieren.), in Runde N eine Auszahlung von 0 (Er defektiert, der Gegner kooperiert.) und in allen restlichen Runden jeweils eine Auszahlung von −3 (beidseitige Defektion). Die erwartete Auszahlung über alle Runden, E [π (DN , Grim)], lautet somit E [π (DN , Grim)] = −1+ p · (−1)+ p2 · (−1)+ . . .+ pN−1 · (−1) +pN ·0+ pN+1 · (−3)+ pN+2 · (−3)+ . . . . Um nun festzustellen, ob es sich lohnt, mit einem Grim–spielenden Gegner zu kooperieren, müssen die beiden Auszahlungen E [π(C,C)] und E [π (DN , Grim)] verglichen werden: Es gilt1 E [π(C,C)] ⋚ E [π (DN , Grim)] ⇔ −1− p− p2 − . . .⋚−1− p− p2 − . . .− pN−1 −3 pN+1 −3 pN+2 − . . . ⇔ −pN − pN+1 − . . .⋚ 3 ( −pN+1 − pN+2 − . . . ) ⇔ pN R 2 ( pN+1 + pN+2 + . . . ) ⇔ 1 2 R p 1− p ⇔ p ⋚ 1 3 1 Die komplette Herleitung findet sich in Anhang 8.4. 148 8. Wiederholte Spiele Kooperation ist also dann sinnvoll, wenn sich mit einer hinreichend hohen Wahrscheinlichkeit auf die jeweils aktuelle Spielrunde eine weitere folgt. Im Fall des hier beschriebenen unbestimmt häufig wiederholten Gefangenendilemmas beträgt dieser kritische Wert p⋆ = 13 : Ist die Wahrscheinlichkeit einer weiteren Runde höher als p⋆, so lässt dauernde Kooperation auf Dauer eine höhere Auszahlung erwarten als Defektion. 8.1.4 Endliche Automaten Eine Klasse von (dynamischen) Strategien lässt sich durch endliche Automaten darstellen. Endliche Automaten sind Teile von Computerprogrammen, die in der Lage sind, durch formalisierte Regeln Inputs, hier die jeweilige Aktion des Gegners, in Outputs zu verwandeln, die hier aus der jeweiligen eigenen Strategie bestehen. Abbildung 8.3 zeigt einige recht einfache endliche Automaten für das wiederholte Gefangenendilemma. In jedem endlichen Automaten symbolisiert ein Kreis den aktuellen Zustand des Automaten. Im Kreis ist der Output in diesem Zustand dargestellt, d.h. die Aktion, die der Automat spielen wird, falls er sich im entsprechenden Zustand befindet. Im Gefangenendilemma gibt es lediglich zwei Outputs, g (Gestehen) und l (Leugnen). Die Pfeile symbolisieren die Übergangsfunktion. Je nach Input, der über den Pfeilen notiert ist, geht der Automat zu einem neuen Zustand über. Befindet sich beispielsweise der Automat Tit for Tat (Teilabbildung 8.3(d)) im Zustand l und erhält den Input l, so geht er wiederum zu l über. Erhält er dagegen einen Input von g, so geht er in den Zustand g über. Als Spielzüge ausgedrückt: Hat Tit for Tat in der aktuellen Runde l gespielt und der Gegner antwortet ebenfalls mit l, so wird Tit for Tat auch in der nächsten Runde l spielen. Antwortet der Gegner jedoch mit g, so spielt Tit for Tat in der nächsten Runde g. Der letzte wichtige Bestandteil endlicher Automaten ist der initiale Zustand, d.h. der Zustand, in dem sich der Automat zu Beginn des Spiels befindet. Dieser initiale Zustand ist durch den Pfeil markiert, der „aus dem Nichts kommt“. So unterscheiden sich beispielsweise die Automaten Tit for Tat und Tat for Tit nur durch ihren initialen Zustand. Das Verhalten endlicher Automaten in unendlich oft wiederholten Spielen lässt sich vergleichsweise einfach analysieren: Spielen Strategien gegeneinander, die sich durch endliche Automaten modellieren lassen, so kommt es grundsätzlich früher oder später zu zyklischem Verhalten. Diese Tatsache lässt sich nutzen, um den Nutzen der jeweiligen Strategien beim Aufeinandertreffen in unendlich wiederholten Spielen zu ermitteln. Beispielhaft ist in Tabelle 8.6 der Verlauf eines wiederholten Spiels dargestellt, in dem Gertrud gegen Tit For Two Tat spielt. Es ist zu erkennen, dass es alle sieben Runden zu einer Wiederholung der Aktionsprofile und damit zu Zyklen in den Auszahlungen kommt. 8.1 Wiederholtes Gefangenendilemma 149 g g, l (a) Hawk g, l l (b) Dove g, l g l l g (c) Grim g g l l g l (d) Tit For Tat g g l l g l (e) Tat For Tit g g l l g g, l g l (f) Tit For Two Tat g l l l g g g g l (g) Gertrud Abbildung 8.3: Endliche Automaten für das Gefangenendilemma Stufe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . Periode t 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 . . . Gertrud g g g l g g l g g g l g g l g . . . π 0 -3 -3 -6 -3 -3 -6 0 -3 -3 -6 -3 -3 -6 0 . . . Tit42Tat l g g g g g g l g g g g g g l . . . π -6 -3 -3 0 -3 -3 0 -6 -3 -3 0 -3 -3 0 -6 . . . Tabelle 8.6: Gertrud (Spieler A) gegen Tit for two Tat (Spieler B) 150 8. Wiederholte Spiele Auszahlungen und Nutzen. Um festzustellen, welche Strategie „besser“ ist, kann man zunächst einmal pragmatisch vorgehen und die durchschnittliche Auszahlung pro Periode errechnen. Dabei kann man sich zu Nutze machen, dass sich Zyklen ergeben. Die durchschnittliche Periodeauszahlung von A, der Gertrud gegen den Tit42Tat–spielenden B spielt, ist gleich der Summe seiner Auszahlung eines Zyklus geteilt durch die Zykluslänge in Perioden: πA (Gertrud, Tit42Tat) = (0−3−3−6−3−3−6)/7 ≈−3.34 . Die entsprechende Auszahlung an B beträgt folglich πB (Tit42Tat, Gertrud) = (−6−3−3+0−3−3+0)/7 ≈−4.29 . Der völlig korrekte, aber etwas umständliche Weg zur Berechnung von Auszahlungen (Nutzen) über die Zeit ist der folgende. Der Nutzen der Auszahlungen an A, der Gertrud gegen B spielt, der seinerseits Tit42Tat benutzt, muss über die Zeit diskontiert werden. Angenommen, A diskontiert seinen Nutzen über die Zeit mit dem Parameter σ mit 0 < σ ≤ 1, so beträgt der Nutzen aus den Auszahlungen im ersten Zyklus UA(π, Z1) = −3σ −3σ 2 −6σ 3 −3σ 4 −3σ 5 −6σ 6 = −3σ ( 1+σ +2σ 2 +σ 3 +σ 4 +2σ 5 ) . Die Auszahlungen aus dem zweiten Zyklus sind gleich denen im ersten Zyklus, der Nutzen ist aber verändert, da die Diskontierung jeder Auszahlung um sieben Perioden verschoben ist, also UA(π, Z2) = −3σ 8 −3σ 9 −6σ 10 −3σ 11 −3σ 12 −6σ 13 = σ 7UA(π, Z1) . Der gesamte Nutzen über das komplette, unendliche Spiel beträgt damit2 UA(π) = UA(π, Z1)+σ 7UA(π, Z1)+σ 14UA(π, Z1)+ . . . (8.1) = UA(π, Z1) ( 1+σ 7 +σ 14 + . . . ) = UA(π, Z1) 1 1−σ 7 . (8.2) Nun gilt es, den Betrag des Gesamtnutzen zu errechnen. Dies ist nicht ohne weiteres möglich, denn die Transformation von (8.1) in (8.2) gilt nur für σ < 1. Für den interessanten Fall, dass keine Zeitpräferenzen vorliegen, 2 Die Berechnung stützt sich auf die Regel ∑∞k=0 x k = 11−x für |x|< 1, wobei x := σ7 gesetzt wird. 8.1 Wiederholtes Gefangenendilemma 151 also σ = 1, divergiert die Summe (8.1). Ein Trick, der sich anwenden lässt, ist es, die Nutzenfunktion UA(·) in eine andere zu transformieren. Dies ist zumindest für affine Transformationen zulässig und verändert nicht die ordinalen Nutzenbeziehungen und somit auch nicht die strategische Situation des Spiels. Es soll also eine neue Nutzenfunktion erzeugt werden, die aus der Transformation (1−σ)UA(·) entsteht. Für diese neue Nutzenfunktion lässt sich zumindest der Nutzen errechnen, wenn σ → 1:3 lim σ→1 ((1−σ)UA(π)) = lim σ→1 (1−σ) ( 1 1−σ 7 UA(π, Z1) ) = lim σ→1 ( 1−σ 1−σ 7 ) lim σ→1 ( −3σ ( 1+σ +2σ 2 +σ 3 +σ 4 +2σ 5 )) = lim σ→1 −1 −7σ 6 limσ→1 ( −3σ ( 1+σ +2σ 2 +σ 3 +σ 4 +2σ 5 )) = 1 7 (−24) = −24 7 =∼−3.43 Analog lässt sich mit allen Strategien verfahren, deren endliche Automaten in Abb. 8.3 dargestellt sind. Es resultiert eine Normalform des Spiels wie in Tab. 8.7 dargestellt. Hawk Dove Grim Ti4Ta Ta4Ti Ti42Ta Gertrud Hawk −3,−3 0, -6 -3, -3 -3, -3 -3, -3 -3, -3 -2, -4 Dove -6, 0 -1, -1 -1, -1 -1, -1 -1, -1 -1, -1 -6, 0 Grim -3, -3 -1, -1 −1,−1 −1,−1 -3, -3 −1,−1 -2, -4 Ti4Ta -3, -3 -1, -1 −1,−1 −1,−1 -3, -3 −1,−1 -3, -3 Ta4Ti -3, -3 -1, -1 -3, -3 -3, -3 -3, -3 -3, -3 -3, -3 Ti42Ta -3, -3 -1, -1 −1,−1 −1,−1 -3, -3 −1,−1 -4.29, -3.43 Gertrud -4, -2 0, -6 -4, -2 -3, -3 -3, -3 -3.43, -4.29 -3, -3 Tabelle 8.7: Unendlich oft wiederholtes Gefangenendilemma. Normalform für ausgewählte Strategien Es ist zu erkennen, dass in den gegebenen Strategien insgesamt zehn Nash–Gleichgewichte existieren (in der Tabelle markiert). Hierbei ist oft wichtig, ob solche Strategien beste Antworten auf sich selbst sind, also auch dann gut wären, wenn beide Spieler sie benutzten. Dies ist bei Hawk, Grim, 3 Die Berechnung stützt sich auf die Regel von L’Hôpital, derzufolge gilt, dass limx→a f (x) g(x) = limx→a f ′(x) g′(x) . 152 8. Wiederholte Spiele Tit For Tat und Tit For Two Tat der Fall. Bemerkenswert ist, dass die immer– nette Strategie Dove ebensowenig eine beste Antwort auf sich selbst ist wie Tat For Tit, das sich auf den ersten Blick nur marginal von Tit For Tat unterscheidet. Insgesamt ist das nie verzeihende Grim eine beste Antwort auf fünf der insgesamt sieben Strategien. Tat For Tit und Gertrud sind jeweils nur auf eine Strategie beste Antworten. 8.2 Das Chainstore Paradox Ein spieltheoretisches Resultat, das (zu seiner Zeit) große Verwunderung auslöste, ist das Chainstore Paradox (Selten, 1978). Das Chainstore4 Paradox ist das Ergebnis einer endlich häufigen Wiederholung des Markteintritts– Spiels aus Abschnitt 4.4. Wie auch beim endlich oft wiederholten Gefangenendilemma ändert sich im Grunde nichts. Auch wenn sich die Möglichkeit des Eindringens auf einen Monopolmarkt und die Drohung mit einem Preiskampf endlich oft wiederholt, wird der Monopolist nie kämpfen, der Eindringling immer eindringen. Diese Erkenntnis erscheint auf den ersten Blick nicht einleuchtend. Sie folgt aber einfach aus Anwendung der Rückwärtsinduktion: In den (zeitlich) letzten Markt wird der Eindringling in jedem Fall eindringen, denn dieses letzte Teilspiel entspricht genau dem Spiel aus Abschnitt 4.4. Da das Ergebnis des letzten Marktes somit feststeht, kann unabhängig hiervon das Resultat für den vorletzten Markt ermittelt werden. Auch hier lautet es: Markteintritt. Dieses Verfahren lässt sich bis zum ersten Markt wiederholen, wobei resultiert, dass der Eindringling jeden Markt betreten wird. 8.3 Kollusion im Cournot–Duopol Ähnlich wie in Abschnitt 8.1.3 kann die Frage behandelt werden, ob Kartellbildung im Cournot–Duopol (S. 123) sinnvoll ist, wenn das Duopol–Spiel unbestimmt häufig wiederholt wird. Für diese Untersuchung soll das (statische) Cournot–Spiel grob vereinfacht werden. Es sei angenommen, jede Firma habe nur zwei Aktionen: Kooperation C, d.h. Einhalten einer Kartell–Absprache, und Defektion D, d.h. Brechen einer solchen Absprache. Die Auszahlungen sind so gestaltet, dass das gemeinsame Einhalten der Absprache einen höheren Profit bringt als das gemeinsame Brechen der Absprache. Bricht jedoch nur eine Firma die 4 Ein „Chainstore“ ist ein Geschäft, das zu einer Ladenkette gehört, und nicht etwa, wie ein Kollege schreibt, ein „Kettenladen“. Obwohl für das spieltheoretische Resultat eher von geringer Bedeutung, wäre es wohl allgemein wohlfahrtssteigernd, würde sich diese Erkenntnis auch außerhalb von S/M–Kreisen weiter ausbreiten. 8.4 Anhang: Herleitung zu Abschnitt 8.1.3 153 Absprache, so erhält sie die höchstmögliche Auszahlung, während der „ehrliche“ Gegner die geringstmögliche Auszahlung erhält. Tabelle 8.8 gibt die Auszahlungen an. Dabei gilt, dass a > b > c > d.5 Firma 2 C D Firma 1 C b, b d, a D a, d c, c Tabelle 8.8: Auszahlungen im Cournot–Spiel; a > b > c > d. Es sei wieder angenommen, in einem wiederholten Cournot–Spiel sei p die Wahrscheinlichkeit, mit der jeweils eine neue Runde gespielt wird. Spielen beide Spieler immer C, so beträgt die Auszahlung an jeden der Spieler πC = b+b p+b p2 + . . . . Spielt ein Spieler bis zur Periode N −1 Strategie C, danach aber, also ab Periode N, Strategie D, und spielt sein Gegner Grim, hat der erste Spieler eine Auszahlung von πD = b+b p+b p2 + . . .+b pN−1 +a pN + c pN+1 + c pN+2 + . . . . Einhalten der Kartell–Vereinbarung lohnt sich, falls πC −πD ≥ 0, d.h. πC −πD ≥ 0 ⇔ pN [ (b−a)+(b− c) p 1− p ] ≥ 0 ⇔ p ≥ a−b a− c . Im Gegensatz zum statischen Cournot–Spiel kann es im wiederholten Cournot–Spiel also durchaus sinnvoll sein, zu kooperieren. Voraussetzung hierfür ist aber eine hinreichend hohe Wahrscheinlichkeit dafür, dass sich an eine Runde des Spiels eine weitere anschließt. 8.4 Anhang: Herleitung der kritischen Grenze aus Abschnitt 8.1.3 Die Berechnung, wann sich Kooperation lohnt bzw. wann nicht, stützt sich auf Summenformeln für geometrische Reihen, die in der Herleitung auf 5 Im Grunde gibt Tabelle 8.8 die allgemeine Struktur eines Gefangenendilemmas wieder. Dies bedeutet, dass in diesem Abschnitt nichts weiter geschieht als eine verallgemeinerte Analyse der Inhalte des Abschnitts 8.1.3. 154 8. Wiederholte Spiele S. 147 nicht explizit erwähnt sind. Dies soll an dieser Stelle nachgeholt werden. Beim Vergleich der erwarteten Auszahlung ergibt sich zunächst: E [π(C,C)] ⋚ E [π (DN , Grim)] ⇔ −1− p− p2 − . . .⋚−1− p− p2 − . . .− pN−1 −3 pN+1 −3 pN+2 − . . . ⇔ −pN − pN+1 − . . .⋚ 3 ( −pN+1 − pN+2 − . . . ) ⇔ pN R 2 ( pN+1 + pN+2 + . . . ) . An dieser Stelle hilft es zu erkennen, dass sich die Summe auf der rechten Seite der Gleichung zerlegen lässt: pN+1 + pN+2 + . . . = ∞ ∑ k=N+1 pk = ∞ ∑ k=0 pk − N ∑ k=0 pk . Der erste Teil vereinfacht sich aus dem Grenzwertsatz für unendliche geometrische Reihen, demzufolge gilt, dass ∞ ∑ k=0 pk = 1 1− p für |p|< 1 . Auf den zweiten Teil lässt sich die Summenformel für endliche geometrische Reihen anwenden, so dass N ∑ k=0 pk = 1− pN+1 1− p . Damit ergibt sich insgesamt pN+1 + pN+2 + . . . = ∞ ∑ k=N+1 pk = ∞ ∑ k=0 pk − N ∑ k=0 pk = 1 1− p − 1− pN+1 1− p = pN+1 1− p . Damit vereinfacht sich das Ausgangsproblem zu 8.4 Anhang: Herleitung zu Abschnitt 8.1.3 155 E [π(C,C)] ⋚ E [π (DN , Grim)] ⇔ pN R 2 p N+1 1− p ∣ ∣·p−N ⇔ 1 R 2 p 1− p ⇔ 1 2 R p 1− p ⇔ p ⋚ 1 3 .

Chapter Preview

References

Zusammenfassung

Vorteile

- Alle wichtigen Konzepte der modernen Spieltheorie

- Ein Klassiker in Neuauflage

Stimmen zum Werk

"(…) Wer eine kompakte und verständliche Einführung in die moderne Spieltheorie sucht, ist mit dem "Riechmann" hervorragend bedient. Das Buch enthält nicht nur alles Wissenswerte zu diesem Thema, es überzeugt auch durch eine sehr eingängige Stoffvermittlung, durch die selbst komplizierte Zusammenhänge verständlich werden. (…)"

in: Studium, 20.04.2008, 2. Auflage 2008

Zum Werk

Spieltheorie intuitiv - das muss nicht bedeuten: Spieltheorie ohne Mathematik. Dieses Lehrbuch gibt eine Einführung in alle wichtigen Konzepte der modernen Spieltheorie, indem es die "Idee" in den Mittelpunkt stellt, ohne dabei die notwendigen Formalia zu vernachlässigen.

Der Inhalt des Buches erstreckt sich von den Grundlagen der Spieltheorie über fortgeschrittene Themen wie Lernen in Spielen oder dynamische Gleichgewichtskonzepte in der evolutionären Spieltheorie.

Die Einbeziehung von Resultaten ökonomischer Laborexperimente erweitert die Perspektive des Buches über den Horizont herkömmlicher Werke zur Spieltheorie hinaus.

Insofern ist das Buch sowohl für Anfänger als auch für fortgeschrittene Spieltheoretiker gleichermaßen geeignet und nützlich.

Autor

Prof. Dr. Thomas Riechmann, Kaiserslautern.

Zielgruppe

Studierende der Wirtschaftswissenschaften.