Eigenschaften guter Strategien

Robert Axelrod hat 1981 zwei Computerturniere durchgeführt, um gute, oder gar die beste Strategie zu finden. Für das erste Turnier hat er professionelle Spieltheoretiker aufgefordert, ihre Strategien zu implementieren und einzusenden. Als Modus wurde ein round-robin-Turnier veranstaltet, in dem jede Strategie einzeln jeweils 200 Züge gegen alle anderen, sich selbst und random angetreten ist. Das Turnier wurde fünf mal wiederholt, um eventuelle Einflüsse von Zufallsentscheidungen zu minimieren. Die Ergebnisse sind in Axelrod (1988) beschrieben. Die Anzahl der Züge war den Autoren der Strategien vorher nicht bekannt.

Unter den 14 Einsendungen befand sich als einfachstes Programm tit-for-tat, das Sieger des Turniers wurde. Diese Strategie war vorher bekannt und hatte in zwei vorbereitenden Turnieren sehr gut abgeschnitten, was die meisten Teilnehmern wußten. Viele der eingereichten Strategien basierten auf tit-for-tat und versuchten, die Strategie zu verbessern, was allerding keiner der Strategien gelungen ist. Dieses überraschende Ergebnis hat Axelrod veranlaßt, das Turnier in größerem Rahmen zu wiederholen. Allen Teilnehmern wurden die Ergebnisse des ersten Turniers zugänglich gemacht und es stand jedem frei, eine beliebige Strategie einzusenden, also insbesondere auch solche, die beim ersten Turnier teilgenommen haben. Unter den 62 Einsendunden der zweiten Runde befand sich aber nur einmal tit-for-tat, vom gleichen Teilnehmer wie in der ersten Runde eingereicht. Auch hier traten wieder alle Strategien gegeneinander an, die Rundenzahl wurde jedoch zufällig festgelegt und betrug im Schnitt 151 Runden. Wiederum hat tit-for-tat gewonnen. Es ist aber nicht so, daß tit-for-tat unter allen Umständen die höchste Punktzahl erringen kann, das Umfeld, d.h. die Menge der andere Strategien bestimmt den Erfolg.

Tit-for-tat muß eine Reihe von Eigenschaften besitzen, die es zu einer guten Strategie machen, die gegen verschiedenste Gegner erfolgreich ist.

Zunächst war auffällig, daß freundliche Strategien generell besser abgeschnitten haben, als unfreundliche. Freundliche Strategien sind solche, die zu Beginn kooperieren und sich allgemein kooperativ verhalten. Sie erreichen untereinander im Schnitt R=3 Punkte, unfreundliche Strategien können nur dann besser sein, wenn sie häufig T=5 Punkte erreichen. Das ist aber, wie oben argumentiert, nur gegen sehr naive Strategien möglich. Die Reihenfolge unter den freundlichen Strategien wird dadurch bestimmt, wie sie gegen unfreundliche abschneiden. Unter den unfreundlichen Strategien muß zwischen den agressiven und kooperativen unterschieden werden: Bei einer agressiven Strategie gibt es nur die Möglichkeit, ebenfalls zu defektieren, um nicht ausgebeutet zu werden, oder aus Sicht des eigenen Ergebnisses gesehen, wenigstens die Punkte für P zu bekommen. Dafür ist die Eigenschaft wichtig, zurückzuschlagen, d.h. eine Defektion nicht unbeantwortet zu lassen. Komplizierter ist die Situation bei einer unfreundlichen kooperativen Strategie als Gegner: Es ist möglich, die Strategie zum Kooperieren zu bewegen, und so R=3 Punkte zu bekommen statt P=1. Entweder versucht die Strategie selbst die Initiative zu ergreifen, und eine erneute Kooperation anzuregen und läuft dabei Gefahr, S=0 Punkte zu bekommen, oder sie wartet auf die Initiative des Gegners und entscheidet dann, ob sie sich auf einer Kooperation einlassen will, oder nicht. Tit-for-tat hat die Eigenschaft, nachgiebig zu sein, d.h. nach dem Zurückschlagen Kooperation wieder zuzulassen. Eine Strategie wie spite hat diese Eigenschaft nicht. Letztendlich gibt es noch komplexere Strategien als Gegner, die versuchen die Strategie des Gegners zu analysieren und daraufhin zu versuchen, Kooperation zu etablieren. Die Analyse der Strategie kann aber nur gelingen, wenn die Strategie einfach, d.h. ihr Verhalten für den Gegner durchschaubar ist.

Im ersten von Axelrod durchgeführten Turnier wurde die Reihenfolge unter den acht freundlichen Strategien von zwei Eigenschaften entschieden. Die erste zeigte sich im Kontakt mit einer komplexen Strategie, die die bedingten Wahrscheinlichkeiten zu berechnen versuchte, wie die gegnerische Strategie auf Defektion bzw. Kooperation reagiert. Das gelang nur bei einfachen Strategien, die damit einen Vorteil gegenüber den weniger einfach zu durchschauenden hatten. Die zweite entscheidende Eigenschaft war Nachsichtigkeit. Die am wenigsten nachsichtige Regel (äquivalent zu spite) schnitt unter den freundlichen Strategien am schlechtesten ab, die am meisten nachsichtigen, darunter tit-for-tat, am besten. Eine noch nachsichtigere Regel als tit-for-tat, tit-for-two-tats, die erst nach zwei aufeinanderfolgenden Defektionen selbst defektiert, hätte übrigens das erste Turnier gewonnen. Die vier Eigenschaften einer guten Strategie sind zusammenfassend:

Mathieu und Delahaye (a) stellen die Frage, ob eine allgemein bessere Strategie als tit-for-tat möglich ist und haben aus ihren Überlegungen heraus gradual entwickelt, eine Strategie, die beim ersten Zug kooperiert, das erste Defektieren des Gegners mit einem Defektieren und anschließend zwei Kooperationen, schließlich das n-te Defektieren des Gegners mit n Defektionen und zwei Kooperationen beantwortet. Dabei ist die von Axelrod aufgestellte Forderung nach Einfachheit verletzt, den die Strategie benötigt Wissen über das gesamte Spiel seit Beginn, tit-for-tat kommt mit dem Wissen über den letzten Zug des Gegners aus. Die Autoren identifizieren zwei herausragende Merkmale an gradual, die tit-fot-tat nicht hat, die aber in besonderer Weise natürlich seien, d.h. dem Verhalten von Menschen, Märkten, usw. näher kommen. Gradual ist sehr offensiv, indem es den Gegner zur Kooperation zwingt: Nichtkooperation zahlt sich für ihn immer weniger aus, denn sie wird mit einer immer größeren Anzahl von Defektionen beantwortet. Gleichzeitig ist die Strategie sehr defensiv und möchte nicht ausgebeutet werden, deshalb wählt sie nach Ausbeutungsversuchen immer seltener die risikoreiche Kooperation, sondern beschränkt sich häufiger auf die rationale Wahl des einfachen Gefangenendilemmas, nicht zu kooperieren. Tabelle 6 zeigt die Ergebnisse eines von Mathieu und Delahaye durchgeführten round-robin Turniers mit den oben beschriebenen Strategien und gradual.

Strategie

gradual

tit-for-tat

soft_majo

spite

prober

pavlov

mistrust

cooperate

per_kind

defect

per_nasty

random

Punkte

33416

31411

31210

30013

29177

28910

25921

25484

24796

24363

23835

22965

Tabelle : Ergebnis eines round-robin Turniers

In den Übungen zu "Programmieren für CL/KI I: Lisp" wurden von mir zweimal round-robin Turniere mit den von den Studenten entwickelten Strategien druchgeführt. Die Ergebnisse decken sich prinzipiell mit den hier vorgestellten, tit-for-tat und Varianten waren realtiv häufig vertreten und konnten gewinnen. Bei den abgegebenen Lösungen war häufig die Tendenz festzustellen, daß die Strategien den Gegner irgendwie "überlisten" sollten, und dadurch mehr als R=3 Punkte im Schnitt erreicht werden sollten. Es hat sich aber gezeigt, daß agressive Strategien keine besonders guten Ergebnisse erreichen. Die bei den Turnieren verwendeten Strategien finden sich bei der Experimentierumgebung in Lisp.