Vorlesungsskript: Grundlagen des Entscheidens I

Eckhart Arnold

1 Techniken des Entscheidens
2 Zur Theorie der Kollektiven Entscheidungen
3 Wahrscheinlichkeitsrechnung
4 Neumann-Morgensternsche Nutzentheorie
5 Spieltheorie
    5.1 Spieltheorie I: Einführung
    5.2 Spieltheorie II: Vertiefung und Anwendung
        5.2.1 Nicht-Nullsummenspiele
        5.2.2 Wiederholte Spiele
        5.2.3 Evolutionäre Spieltheorie
            5.2.3.1 Evolutionäre Spieltheorie am Beispiel des wiederholten Gefangenendilemmas
            5.2.3.2 Die empirische Unanwendbarkeit spieltheoretischer Evolutionsmodelle
        5.2.4 Ein Anwendungsbeispiel der Spieltheorie, das funktioniert: Vertrauen bei Internetauktionen
        5.2.5 Aufgaben
6 Kritische Reflexion
7 Beispielklausur
Literaturverzeichnis

5.2.3 Evolutionäre Spieltheorie

5.2.3.1 Evolutionäre Spieltheorie am Beispiel des wiederholten Gefangenendilemmas

Das Modell des wiederholten Gefangenendilemmas war für lange Zeit eines der populärsten Modelle der evolutionären Spieltheorie. Besonders duch den auf Computersimulationen gestützten Ansatz von Robert Axelrod (Axelrod 1984) ist es weithin bekannt geworden. Leider hat die Popularität dieses Modells zu einer maßlosen Überschätzung seiner Leistungsfähigkeit geführt. Einer unüberschaubaren Fülle von reinen Modell- und Simulationsstudien steht ein mehr als auffälliger Mangel an empirischen Anwendungen gegenüber. Da das Modell aber ebenso anschaulich wie leicht verständlich ist, werden wir es hier dennoch zur Einführung in einige der Grundgedanken der evolutionären Spieltheorie heranziehen. Auf die Probleme werden wir danach kurz eingehen.

Wie wir gesehen haben, existiert im wiederholten Gefangenendilemma keine dominante Strategie und es gibt eine Vielzahl von Gleichgewichtsstrategien. Können wir trotzdem irgendwelche Strategien als gute oder in irgendeinem anderen Sinne als dem der Dominanz als „beste“ Strategien auszeichnen. Der (aus heutiger Sicht naive) Ansatz, den Axelrod verfolgt hat (Axelrod 1984), bestand darin, einfach eine größere Menge von unterschiedlichen Strategien in einer Art Turnier gegeneinander antreten zu lassen. Jede Strategie spielt gegen jede andere ein paarweise Gefangenendilemma durch. „Gewonnen“ hat am Ende die Strategie, die die höchste Durchschnittspunktzahl über alle Begegnungen erzielt hat. (Wohlbemerkt: Es kommt bei diesem Turnier auf die Durchschnittspunktzahl und nicht auf die Anzahl gewonnenen Begegnunen bzw. der besiegten Gegner an, ganz wie es dem ökonomischen Menschbild des „neidlosen Egoisten“ entspricht.) Da man die Strategien im wiederholten Gefangenendilemma sehr leicht programmieren kann, führt man entsprechende Turniere am besten mit dem Computer durch.[79]

Um das Prinzip zu verdeutlichen, wird an dieser Stelle nur ein sehr einfaches Turnier mit einer sehr kleinen Stratgiemenge von 7 Strategien besprochen. Diese ausgewählten Strategien sind:

Ein „Turnier“ dieser Strategien liefert für die Auszahlungsparameter (siehe Seite ) folgendes Ergebnis:

Rang Stratgie Durchschnittspunkte
1. TitForTat: 2.4631
2. Grim: 2.4270
3. Tester: 2.3565
4. Pavlov: 2.2185
5. Hawk: 2.1486
6. Random: 1.9992
7. Dove: 1.7121

In diesem Fall hat also TitForTat das Turnier gewonnen. Die Durchschnittspunktzahl von liegt zwar deutlich unter der Auszahlung für wechselseitige Kooperation von Punkten, aber das ist nicht verwunderlich, da man gegen eine Strategie wie Hawk, die immer defektiert, bestenfalls eine Durchschnittspunktzahl von erzielen kann. Auffällig ist, dass in diesem Beispiel bösartige Strategien wie Tester, die versuchen naive Strategien wie Dove auszubeuten, nicht die erfolgreichsten sind. Aber das ist erklärlich, wenn auch Strategien wie Grim im Rennen sind, die von „bösartigen“ Strategien wie Tester keine Friedensangebote akzeptieren. So erzielt Tester gegen Grim nur eine Durchschnittspunktzahl von knapp (was der Auszahlung für wechselseitige Defektion entspricht), während TitForTat und Grim kooperieren, so dass TitForTat gegen Grim satte Punkte erhält. Es ist zu betonen, dass das Ergebnis sehr stark von der Ausgansstrategiemenge und von den gewählten Auszahlungsparametern abhängt. Wandelt man das eine oder andere ab, dann kann eine ganz andere Strategie die beste sein. Grundsätzlich sollte man keine voreiligen und verallgemeinernden Schlussfolgerungen aus Computersimulationen mit willkürlich festgesetzten Ausgangsbedingungen und Parameterwerten ziehen.

Bis hierher hat das Computerturnier nur etwas mit wiederholten Spielen, aber noch nichts mit Evolution zu tun. Zu einem evolutionären Modell wird das Computerturnier, wenn man die Durchschnittsauszahlungen als Fitnesswerte interpretiert. Man stellt sich dazu vor, dass wir es mit einer großen Population von Spielern und einer kleinen Menge von Spielertypen zu tun haben. Der Typ eines Spielers ist die Strategie, die er spielt. Um es noch ein wenig anschaulicher zu machen, können wir uns auch eine Population von Tieren vorstellen, die in Gemeinschaft leben, etwa einen Vogelschwarm. Bei der Nahrungssuche unterstützen die Vögel einander, aber es gibt genetisch bedingte Unterschiede. Einige Tiere sind extrem sozial, d.h. sie unterstützen jeden Artgenossen (Strategie: Dove), andere machen die Unterstützung eines Artgenossen davon abhängig, ob sie erwiedert wird (TitForTat), wieder andere verhalten sich völlig egoistisch (Hawk). Der Erfolg bei der Nahrungssuche hängt nun davon ab, wie leistungsfähig jede der Strategien ist. Zugleich kann man davon ausgehen, dass sich der Erfolg bei der Nahrungssuche in Fortpflanzungserfolg umsetzt. Das bedeutet aber wiederum, dass eine erfolgreiche Strategie in der folgenden Generation häufiger auftritt und eine weniger erfolgreiche seltener, sie könnte irgendwann sogar ganz aussterben.

Um nun diese Überlegungen in das Modell zu übertragen, gehen wir der Einfachheit halber davon aus, dass in der ersten Generation auf jede Strategie auf ein gleich großer Anteil der Spielpopulation entfällt. Für die nächste Generation wird der Populationsanteil dann allerdings mit dem Fitnesswert mutlipliziert. Der Fitnesswert entspricht nach der ersten Generation noch genau den Durchschnittsauszahlungen, die auf die (gleichverteilten) Strategien entfallen. In den folgenden Generationen darf man jedoch nicht mehr einfach den Durchschnitt bilden, sondern muss für jede Strategie das mit dem Bevölkerungsanteil der Gegnerstrategien gewichtete Mittel der Ergebnisse der einzelnen Begegnungen berechnen. Das ist durchaus einleuchtend, wenn man sich vor Augen hält, dass der Erfolg einer Strategie wie Tester umso größer ist, je mehr Dove-Spieler in der Population vorkommen, und dass er geringer wird, wenn der Populationsanteil von Dove-Spielern absinkt. Im Laufe von mehreren Generationen ändern sich also sowohl die Populationsanteile der Strategien als auch die Fitnesswerte der Strategien (weil sie von den Populationsanteilen abhängen). Mathematisch werden diese Zusammenhänge folgendermaßen ausgedrückt:

Fitness der -ten Strategie
Auszahlung für die -te Strategie gegen die -te Strategie
Bevölkerungsanteil der -ten Strategie
Anzahl der vorkommenden Strategien
Indizes einzelner Strategien ()

Anstatt mit der absoluten Zahl von Individuen zu rechnen, die eine Strategie angenommen haben, wobei man die Größe der Population willkürlich festlegen müsste, rechnet man der Einfachheit halber immer mit relativen Bevölkerungsanteilen einer gedachten unendlich großen Bevölkerung. (Die Bevölkerungsanteile müssen sich dabei immer zu 1 aufsummieren, weshalb man sie nach jeder Generation renormieren muss.) Neben der Formel, nach der die Fitness berechnet wird, ist noch eine Formel notwendig, um die Bevölkerungsanteile, die in der Folgegeneration auf jede Strategie entfallen, zu berechnen:

Populationsanteil der -ten Strategie in der -ten Generation
Fitness der -ten Strategie in der Generation Nummer
die Nummer der gegenwärtigen Generation
Anzahl der vorkommenden Strategien
Indizes einzelner Strategien ()

Die Formel sieht sehr viel hässlicher aus, als sie ist. Alles Wichtige steht im Zähler des Bruchs. Der Nenner dient lediglich der Renormierung. (Wir teilen einfach den nicht normierten Bevölkerungsanteil jeder Strategie durch die Summe aller nicht normierten Bevölkerungsanteile.)

Übt die evolutionäre Entwicklung einen Einfluss darauf aus, welche Strategien erfolgreich sind? Dazu betrachten wir die Rangfolge nach 50 Generationen:

Rang Stratgie Bevölkerungsanteil Durchschnittspunkte
1. TitForTat 0.7745 3.0000
2. Grim 0.1922 2.9984
3. Dove 0.0325 2.9988
4. Tester 0.0008 2.6461
5. Random 0.0000 1.9727
6. Pavlov 0.0000 1.8125
7. Hawk 0.0000 1.1338

Die Strategie TitForTat steht nach wie vor an der Spitze, aber die Strategie Tester ist vom dritten auf den vierten Platz abgesackt und Hawk befindet sich nunmehr ganz am Ende der Tabelle. Die evolutionäre Entwicklung lässt sich sehr anschaulich in einem kartesischen Koordinatensystem darstellen, wenn man auf der X-Achse die Generation und auf der Y-Achse die Bevölkerungsanteile für jede Strategie einträgt, wie auf der Abbildung 1 auf Seite 1 zu sehen ist.


[image: Einfaches_Beispiel.png]
Abbildung 1. Beispiel einer evolutionären Simulation des wiederholten Gefangenendilemmas

Ganz grob kann man die Entwicklung folgendermaßen charakterisieren. Durch Präsenz ausbeuterischer Strategien (Tester, Hawk und m.E. auch Pavlov und Random) sacken die rein kooperativen Straegien (in dieser Simulation nur Dove) am Anfang stark ab. Dadurch verlieren aber die ausbeuterischen Strategien auf längere Sicht gesehen ihre Basis, so dass sich die reziproken Strategien durchsetzen. Ein hoher Anteil reziproker Strategien (d.h. Strategien, die Wohlverhalten belohnen und Fehlverhalten bestrafen wie TitForTat und besonders Grim) bewirkt schließlich, dass erstens die ausbeuterischen Strategien sich nicht wieder erholen und zweitens ein gewisser Anteil rein kooperativer Strategien „im Windschatten“ der reziproken Strategien überleben kann.

Es ist durchaus charakteristisch, dass evolutionäre Entwicklung am Ende mit einem Mix von Strategien zum Stillstand kommt. TitForTat, Dove und Grim kooperieren immer miteinander, so dass die Unterschiede zwischen diesen Strategien unter Abwesenheit anderer Strategien gar nicht zum tragen kommen und keine Verschiebungen in der Bevölkerungsverteilung mehr bewirken können. Man kann die Situation auch so interpretieren, dass sich am Ende eine gemischte Strategie durchgesetzt hat, die zu ca. 77,5% TitForTat, 19,2% Grim zu und zu 3,3% Dove spielt. Übrigens ist das auch eine übliche Interpretation gemischter Strategien im evolutionären Zusammenhang: Eine gemischte Strategie kann man auch als eine gemischte Population reiner Strategien auffassen.

Bei evolutionären Computersimulationen stellt sich in besonderer Schärfe das Problem der Modellkontingenz (d.h. die Ergebnisse sind abhägig von der Ausgangssituation und den Modellparametern und damit kaum verallgemeinerbar).[80] Bloß auf Grund von Simulationsläufen, seien dies nun einzelne oder eine große Zahl von Simulationsläufen, lässt sich bestenfalls ein subjektiver Eindruck davon gewinnen, welche Strategien vorteilhaft sind und welche nicht.

Aussichtsreicher, da weniger kontingenzbehaftet, erscheint der Versuch einer mathematischen Charakterisierung vorteilhafter Strategien. Ähnlich wie in der gewöhnlichen Spieltheorie der Begriff des Nash-Gleichgewichts entwickelt wurde, um bestimmte Strategien bzw. Strategiekombinationen auszuzeichnen, gibt es auch in der evolutionären Spieltheorie diverse Gleichgewichtsbegriffe, durch die evolutionäre Strategien charakterisiert werden können. Der wichtigste davon ist der Begriff des „evolutionären Gleichgewichts“ bzw. der evolutionär stabilen Strategien (ESS). Als „evolutionär stabil“ charakterisiert man Strategien, die, wenn sie sich einmal in einer Population durchgesetzt haben, vor dem Eindringen von mutierten Strategien geschützt sind. Zur Charakterisierung von Strategien im wiederholten Gefangenendilemma-Spiel bietet sich allerdings eher der etwas schwächere Begriff der kollektiven Stabilität an. Im folgenden wird daher vorwiegend von kollektiver Stabilität die Rede sein.

Eine Strategie gilt als „kollektiv stabil“ wenn kein einzelnes Individuum einer anderen Strategie in eine Population, die nur aus Individuen der der Strategie gebildet wird „eindringen“ kann. Eindringen kann genau dann, wenn die Auszahlung, die der Begegnung mit erhält (formal: , wobei das V für „value“ steht, also den Wert des Spiels für Spieler B wiedergibt) größer ist, als die Auszahlung, die gegen sich selbst erhält (), kurz „Eindringen“ wird durch die Ungleichung beschrieben:



Wenn diese Ungleichung erfüllt ist, dann wird ein einzelner -Spieler nämlich eine höhere Durchschnittsauszahlung erhalten als die -Spieler und sich damit stärker vermehren, so dass sich die -Spieler schließlich in der -Population ausbreiten.

Kollektiv stabil ist eine Strategie nun genau dann, wenn keine andere Strategie exiistiert, die in eindringen kann, d.h. wenn



Man kann nun leicht zeigen, dass die Strategie TitForTat kollektiv stabil ist, denn TitForTat erhält gegen sich selbst als Durchschnittspunktzahl den Kooperationsgewinn von 3 (bzw. ). Keine Strategie, die gegen TitForTat ausschließlich kooperiert, kann mehr als 3 (bzw. ) Punkte erhalten. Damit können aber höchstens noch solche Strategien in eine Population von TitForTat-Spielern eindringen, die gegen TitForTat nicht immer kooperieren. Wenn eine Strategie aber in irgendeiner Runde gegen TitForTat nicht kooperiert, dann wird sie in den folgenden Runden von TitForTat solange bestraft, bis sie eine Bestrafung „hinnimmt“, d.h. bis sie in einer der Runden, in der TitForTat bestraft, ihrerseits nicht defektiert. Dann erhält sie von der Runde, in der sie ausbeutet, zusammen genommen mit der Runde, in der sie die Bestrafung hinnimmt, eine Durchschnittsauszahlung von 5+0 (bzw. +), was kleiner als 3 (bzw. ) ist. (Gibt es dazwischen Runden wechselseitiger Defektion, so ist die Durchschnittsauszahlung von 1 (bzw. ) ohnehin kleiner als 3 (bzw. ).) Damit sinkt aber der Gesamtdurchschnitt unter die Kooperationsauszahlung von . Wegen gilt also . Mit anderen Worten eine Strategie, die gegen TitForTat irgendwann einmal nicht kooperiert, kann erst recht nicht in eine Population von TitForTat-Spielern eindringen. (Dieser Beweis gilt, so wie er geführt wurde, zunächst einmal für ein idealisiertes unendlich oft wiederholtes Gefangenendilemma. Man kann ihn aber auch leicht auf unbestimmt oft wiederholte endliche Spiele übertragen, sofern die Wahrscheinlichkeit, mit der nach jeder Runde das Spiel abgebrochen wird, klein genug (bezogen auf die Auszahlungsparameter in ihrem Verhältnis zueinander) gewählt wird, so dass - grob gesagt - die Chance, dass die Runde, in der defektiert wird, die letzte ist, nicht den zu erwartenden Schaden ausgleicht, falls sie es doch nicht ist.)

Aber ebenso ist auch die Strategie Hawk kollektiv stabil, denn jede andere Strategie kann gegen Hawk höchstens eine Durschnittspunktzahl von 1 (bzw. ) erzielen, was aber nicht mehr ist als Hawk gegen sich selbst erzielt. Wenn Hawk und TitForTat beide gleichermaßen kollektiv stabil sind, kann man dann noch eine dieser beiden Strategien bezüglich der ihrer Stabilität vor der anderen auszeichnen? Man kann: Bei der kollektiven Stabilität wird nur gefragt, ob ein einzelner Eindringling sich in einer Fremdpopulation ausbreiten kann. Aber wie verhält es sich, wenn eine kleine Gruppe von Eindringligen versucht, in eine Fremdpopulation einzudringen? Angenommen eine kleine Gruppe von TitForTat-Spielern versucht in eine Gruppe von Hawk-Spielern einzudringen. Dann ist geringfügig kleiner als , da TFT in der ersten Runde einen Kooperationsversuch wagt. Andererseits erhalten die TFT-Spieler untereinander die Kooperationsauszahlung , die erheblich größer ist als die Defektionsauszahlung , die die Hawk-Spieler untereinander erhalten (). Dementsprechend könnte schon eine Minderheit von TFT Spielern eine höhere Durchschnittsauszahlung erhalten als die Mehrheitspopulation der Hawk-Spieler. Umgekehrt ist das nicht der Fall. Das bedeutet aber, dass eine Population von Hawk-Spielern nur relativ schwach gegen das Eindringen durch eine Gruppe von TitForTat-Spielern geschützt ist.[81] . Dominieren die TitForTat-Spieler aber erst einmal die Population, so hat umgekehrt eine Gruppe von Hawk-Spielern kaum eine Chance in die Population einzudringen. Es besteht also eine Asymmetrie zwischen reziproken und bösartigen Strategien, die sich zugunsten der reziproken Strategien auswirkt.

Der Begriff der kollektiven Stabilität hat die Schwäche, dass kollektiv stabile Strategien nicht unbedingt gegen das Eindringen von Mutationen geschützt sind, die gegen die Vertreter der Stammpopulation genauso gut abschneiden wie diese gegen sich selbst. Damit schließt die kollektive Stabilität einer Strategie z.B. nicht aus, dass ihre Population gegen die Ausbreitung degenerierender Mutationen geschützt ist. So könnte sich innerhalb einer Population von TitForTat-Spielern die Strategie Dove ungehindert ausbreiten, da keinerlei „Erhaltungsselektion“ statt findet, durch die die „schwächeren“ Dove-Spieler in einem Millieu von TitForTat-Spielern an der Ausbreitung gehindert würden. Aus diesem Grund ist insbesondere in der Biologie ein vergleichsweise stärkeres Konzept als das der kollektiven Stabilität üblich, nämlich des der evolutionären Stabilität.

Evolutionäre Stabilität: Eine Strategie ist evolutionär stabil, wenn für jede beliebige Strategie gilt, dass entweder



oder



Für die Analyse des wiederholten Gefangenendilemma-Spiels erscheint dieser vergleichsweise stärkere Begriff jedoch nicht unbedingt geeignet, weil es dann äußerst schwierig wird, überhaupt noch eine Strategie zu konsturieren, die evolutionär stabil ist. Eine reziproke Strategie könnte gegenüber von Dove-Mutanten nur noch dann evolutionär stabil sein, wenn sie einen Mechanismus enthält, der die Abwesenheit des eigenen Bestrafungsmechanismus sanktioniert (wodzu dieser Mechanismus durch zufällige Defektion aber erst einmal ausgelöst werden muss). Aber nicht nur ausbleibende Bestrafungen müssten sanktioniert werden, sondern auch ausbleibende Bestrafungen von ausbleibenden Bestrafungen usf. Ob eine solche Stratgie wenigstens theoretisch denkbar ist, sei hier einmal dahin gestellt.

[79] Wen es interessiert, der kann sich die Software dafür von dieser Web-Seite herunterladen: www.eckhartarnold.de/apppages/coopsim.html

[80] Axelrod glaubte aufgrund der detaillierten Analyse mehrfacher Simulationsläufe die Strategie TitForTat als eine besonders vorteilhafte Strategie auszeichnen zu können (Axelrod 1984, S. 25ff, S. 29ff.). Ken Binmore argumentiert jedoch überzeugend dagegen und zeigt, dass die vermeintliche Überlegenheit von TitForTat als theoretischer Befund nicht haltbar ist (Binmore 1998, S. 313). (Empirisch bestätigt ist sie ohnehin nicht, siehe unten, Kapitel 5.2.3.2). Angesichts der außergewöhnlichen Popularität von Axelrods Ansatz spricht Binmore daher durchaus treffend von der „Tit for Tat Bubble“ (Binmore 1994, S. 194).

[81] Wieviele TFT-Spieler notwendig sind, um in eine Population von Hawk-Spielern einzudringen, hängt von der relativen Größe der Auszahlungsparameter und der durchschnittlichen Spiellänge ab.

t g+ f @