Fictitious Play

Fictitious Play (engl., wörtlich: fiktives Spiel, sinngemäß: Spielzüge im Geiste), auch Brown-Robinson learning process genannt, ist eine Analyse aus der Spieltheorie. Genauer gesagt ist Fictitious Play ein konvergentes Verfahren zur Bestimmung von Wert und optimaler Strategie. Dieses Verfahren wurde 1951 von G.W. Brown (1951) als ein Algorithmus eingeführt, der den optimalen Wert in Nullsummenspielen finden soll.

Fictitious Play gehört zum Teilbereich der evolutionären Spieltheorie. Die Grundidee dieser Theorien basieren auf der Annahme, dass die Spieler auf der Suche nach optimierenden Lösungen nicht (voll) rational handeln.

Geschichte

Brown bezeichnete 1951 in seinem Review, Fictitious Play als eine Strategie, bei der die Spieler den fiktiven Spielablauf in ihrem Kopf durchgehen, diesen in jeder Runde aktualisieren und an die Strategie anpassen, welche von ihren Gegenspielern bereits im Vorfeld gewählt wurde. Daher kommt auch die Namensgebung dieser Strategie, wobei die Strategien nicht ausschließlich im Kopf stattfinden, sondern alle gespielt werden können.

In der modernen Spieltheorie wird den Ideen Browns nicht mehr der Stellenwert entgegengebracht, den diese Theorie früher innehatte. Die neuen Darstellungen unterscheiden sich gegenüber der ursprünglichen Veröffentlichung, im Ablauf der Aktualisierung der neuen Beliefs vor jeder Spielrunde. Brown geht davon aus, dass die Beliefs der einzelnen Spieler abwechselnd, in Bezug auf die empirischen Verteilungsfunktion des Gegners, angepasst und aktualisiert werden. Im Gegensatz dazu sind moderne Spieltheoretiker der Auffassung, dass die Beliefs gleichzeitig von den Spielern aktualisiert werden.

Nach 1951 wurden Beliefs ausschließlich simultan aktualisiert, was u. a. auf die symmetrische Behandlung von Entscheidungen zurückzuführen ist.

Des Weiteren wurde Fictitious Play damals zur Approximation genutzt um die optimale Strategie zu errechnen. Dies ist ebenfalls sehr veraltet und in der heutigen Zeit findet nur noch der Algorithmus des Nash-Gleichgewicht praktische Anwendung. Somit werden die optimalen Strategien nicht mehr approximiert, sondern durch den folgenden Algorithmus ermittelt:

1. Optimiere die Entscheidung von Spieler i=1,…,n bei (beliebig) fixierten Strategien aller anderen Spieler: Markiere die unter diesen Umständen erreichbaren höchsten Auszahlungen für Spieler i. Wiederhole dies für alle möglichen Strategiekombinationen der anderen Spieler.
2. Führe 1. für alle Spieler durch.

Heute wird Fictitious Play wegen der enormen Komplexität, fast ausschließlich nur noch in der Informatik angewendet. Dort werden sehr komplexe, spieltheoretische Probleme mit zwei Personen, wie z. B. Schach oder Backgammon, mit Fictitious Play analysiert.

Evolutorische Spieltheorie

Fictitious Play stützt die Annahmen der evolutorischen, auch evolutionäre Spieltheorie genannt. Ihr Ansatz unterscheidet sich von der „herkömmlichen“ Spieltheorie darin, dass sie sich von den Rationalitätsargumenten der Spieler abwendet. Stattdessen wird angenommen, dass jedem Spieler genau eine mögliche Strategie zugeordnet ist, die auf Grund einer irrationalen Annahme die Auszahlung der Spieler nicht optimiert. Außerdem ist sich der Spieler in solchen Spielen nicht bewusst, dass er sich in einem Spiel befindet. Diese Strategie ist nicht auf die klaren Regeln eines Spiels beschränkt, sondern stellt eine evolutionsbiologische Entwicklung dar, in der die Spieler eine „Spezies“ symbolisieren.

Im Modell der evolutorischen Spieltheorie treffen die Spieler immer paarweise aufeinander. Die Wahrscheinlichkeit auf einen speziellen Strategietypen zu stoßen, hängt dabei vom Anteil dieser Strategie an der Gesamtheit aller möglichen Strategien ab. In diesem Modell spricht man nicht mehr von einer Gesamtheit an Strategien, sondern von einer „Population“.

Praktische Anwendung in der Ökonomik finden die Theorien der evolutorischen Spieltheorie vor allem in Feldern von Steuer- und Wahlsystemen, Verhaltensstandards und Eigentumsstrukturen.

Learning Strategies

Fictitious Play wird diesem Teilbereich der Spieltheorie zugeordnet. Diese Strategien werden nur auf sich wiederholende Spiele angewendet, da ihre besten Antworten auf Entscheidungen beruhen, die in der Vergangenheit getroffen wurden. An diese Entscheidungen in der Vergangenheit werden die Beliefs angepasst, was auch als Belief Learning bezeichnet wird.

Reinforcement Learning ist eine Verstärkung der Learning Strategies, da hierbei davon ausgegangen wird, dass Spieler Strategien häufiger spielen, die ihnen in der Vergangenheit Gewinne eingebracht haben.

Modell Fictitious Play

Fictitious Play wurde entwickelt, um Agenten in die Lage zu versetzen, innerhalb kürzester Zeit optimale Lösungen zu approximieren. In jeder Runde spielt jeder Spieler die beste Antwort, die sich an den vergangenen, gegnerischen Spielzügen orientiert und die höchste Gewinnwahrscheinlichkeit generiert. Bei Fictitious Play nimmt jeder Spieler an, dass die anderen Spieler eine stationäre Strategie verfolgen. Eine stationäre Strategie ist durch Einzelentscheidungen, die unabhängig vom Entscheidungszeitpunkt getroffen werden, charakterisiert.

In der ersten Runde bei Fictitious Play sollte eine beliebige Strategie gewählt werden, da man auf keine historischen Strategien der anderen Spieler zurückgreifen kann.

Ab der zweiten Runde nehmen die Spieler den Durchschnitt der historischen Strategien des Kontrahenten als Grundlage für dessen Handlungsprognose im nächsten Spiel. Dies geschieht aufgrund der Annahme, dass die Kontrahenten nach ihrer historischen Strategie-Frequenz auch im kommenden Spiel spielen werden. Mithilfe dieser Analyse der vergangenen Strategien spielt der Spieler die beste Strategie gegen diese.

Fictitious Play ist lediglich dann erfolgreich, wenn die Gegner tatsächlich eine stationäre Strategie verfolgen. Verfolgen die Gegner hingegen eine Strategie, die auf einer anderen Grundlage beruht (beispielsweise wenn sich der Gegenspieler jeweils nur an der zuletzt gespielten Strategie orientiert), ist Fictious Play keine erfolgreiche Strategie.

Annahmen des Modells

Es wird von einem sich wiederholenden Spiel mit zwei fixen Personen ausgegangen, wobei diese ihre Entscheidungen simultan treffen. Die Beliefs der Spieler werden auf Grund der in der Vergangenheit gespielten Strategien des Gegners gebildet. Beide Spieler spielen stationäre Strategien.

Mathematische Definitionen

Es wird im Folgenden die symmetrische Bildung der Beliefs eines Spiels mit zwei Spielern betrachtet.

$S$ ist der reine Strategieraum der beiden Spieler mit $m=\left|S\right|$

$h_{T}=\left\{i_{t}\right\}_{t=1}^{T}$, sei ein historischer Spielverlauf.

$f_{T}^{i}=\left|\left\{s:i_{s}=i,1\leq s\leq T\right\}\right|$ sei die Anzahl mit der $i\in S$ in $h_{T}$ auftritt. Also ist $\sum _{i=1}^{m}f_{T}^{i}=T$ und ${\bar {f}}_{T}^{i}={\frac {f_{T}^{i}}{T}}$

Nun werden die Startbedingungen für $T=1$ ermittelt. Für $i\in S$ sei $x_{0}^{i}\geq 0,\sum _{i=1}^{m}x_{0}^{i}>0$

Mit diesen Bedingungen werden nun die Durchschnitte berechnet als ${\bar {x}}_{T}^{i}={\frac {f_{T}^{i}+x_{0}^{i}}{\sum _{k=1}^{m}\left(f_{T}^{k}+x_{0}^{k}\right)}}$

Da wiederum $\sum _{k=1}^{m}f_{T}^{i}=T$, entspricht dies ${\bar {x}}_{T}^{i}={\frac {{\bar {f}}_{T}^{i}+\left({\frac {1}{T}}\right)x_{0}^{i}}{1+\left({\frac {1}{T}}\right)\sum _{k=1}^{m}x_{0}^{k}}}\approx {\bar {f}}_{T}^{i}$

Browns Definition von 1951

Eine beste Antwort $x$ eines Spielers auf die Strategie $y$ des Gegenspielers mit $x\in B\left(y\right)$.

Gegeben ist $\left\{x_{0}^{i}\right\}_{i=1}^{m}$ und $\left\{y_{0}^{j}\right\}_{j=1}^{m}$, heißt ein Paar von Funktionen

$x:\triangle \left(S\right)\rightarrow$ $\triangle \left(S\right)$, $y:\triangle \left(S\right)\rightarrow$ $\triangle \left(S\right)$ Fictitious Play, wenn in jeder Periode $t\geq 1$ gilt,

dass $x\left({\bar {x}}_{T}\right)\in B\left({\bar {y}}_{T}\right)$ und $y\left({\bar {y}}_{T}\right)\in B\left({\bar {x}}_{T}\right)$ und ${\bar {x}}_{T},{\bar {y}}_{T}$ rekursiv von $\left({\bar {x}}_{0},{\bar {y}}_{0}\right)$ und $\left(x,y\right)$ bestimmt sind.

Das bedeutet, dass sich ein Spieler nur dann optimal verhält, wenn sein Gegner tatsächlich ${\bar {x}}_{T}$ oder ${\bar {y}}_{T}$ spielt – sonst nicht!

Konvergenzeigenschaften von Fictitious Play

Langfristig führt Fictitious Play nur unter speziellen Annahmen zu einem Nash-Gleichgewicht. Im Fictitious Play sind Nash-Gleichgewichte absorbierend, was bedeutet falls in einer beliebigen Runde des Spiels von allen Spielern ein Nash-Gleichgewicht gespielt wird, folgt daraus, dass für jedes nachfolgende Spiel ebenfalls das Nash-Gleichgewicht gespielt wird. Des Weiteren kann gezeigt werden, dass sich eine Korrelation zwischen Nash-Gleichgewicht und den Wahrscheinlichkeiten bildet, wenn Fictitious Play zu einer Verteilung konvergiert.

Da Fictitious Play nicht immer zu Verteilungen konvergiert, werden andere Aktualisierungs-Dynamiken angewandt um Beliefs für die kommende Runde zu bilden wie z. B. Replicator Dynamics. Diese Methode ist komplizierter als Fictitious Play, dafür kann mit Sicherheit davon ausgegangen werden, dass die Ergebnisse konvergieren.

Fictitious Play konvergiert mit Sicherheit in den folgenden Fällen:

1. Nullsummenspiele mit zwei Spielern (Robinson 1951)
2. Allgemein alle 2x2 Spiele (Miyasawa 1961; Monderer und Shapley 1996)
3. Spiele, die mit iterativer strikt dominanter Strategie lösbar sind (Nachbar 1990)
4. Spiele mit gewichtetem Potenzial (Monderer und Shapley 1996)

Fictitious Play gilt zwar weiterhin nicht als allgemeines Lösungskonzept (Shapley 1964), allerdings konvergiert es prinzipiell gegen die Hälfte von approximierten Gleichgewichten (Conitzer 2009; Goldberg, Savani, Sorensen, Ventre 2011).

Wenn alle Spieler ihre Strategien nach Fictitious Play wählen, wird die Strategie durch die entstehenden Nash-Gleichgewichte abgeschwächt. Ein typisches Ergebnis dafür ist das limit-cycle Verhalten, welches mit steigender Anzahl der Spiele steigt. In manchen bestimmten Fällen konvergiert das Produkt der empirischen Verteilung gegen das Nash-Gleichgewicht, obwohl in Zyklen gespielt wird, wie bei Matching Pennies.

Praktische Anwendung

Poker Spielbaum mit einer Karte und einer Runde

Den größten Zuspruch findet Fictitious Play heutzutage nur noch im Poker. Vorreiter in der Anwendung von Fictitious Play bei Poker (hierbei sprechen wir nur über die Pokervariante Texas Hold’em) war Duziak 2006. Durch Fictitious Play wird die Komplexität der Spielzustände stark vereinfacht.

Es gibt bei Poker 10^18 mögliche Spielzustände, welche mit Fictitious Play auf 10^7 reduziert werden. Diese Abstraktion kann verschiedene Algorithmen zu Grunde haben. Bei Poker wird hierbei hauptsächlich auf das sogenannte „Bucketing“ (engl., Eimer) zurückgegriffen, da hierbei die Größe des Algorithmus reduziert wird, ohne die zugrundeliegende Ursache zu abstrahieren. Dies geschieht dadurch, dass Hände (Poker) mit ähnlichem Wert in verschiedene „Buckets“ gruppiert werden. Wenn man nun das Spiel abstrahiert hat, ist es nun essentiell, wenn man Fictitious Play seine Strategie optimieren will, einen gut definierten Spielbaum zu entwickeln. Dieser Baum nimmt schnell gigantische Maße an, sodass man geringere Gewinnwahrscheinlichkeiten aussortiert und diese Pfade des Baumes abschneidet. So wird der Spielbaum immer kleiner und die pseudo-optimale Strategie lässt sich während des Spiels errechnen. Die Pseudooptimalität kommt deswegen zustande, da die Spielzustände stark vereinfacht werden und dadurch die Gewinnchancen sinken.

Kritik an Fictitious Play

In der Praxis ist Fictious Play, außer im Poker, nur kaum anzutreffen, da es für Spiele mit mehreren Personen nicht geeignet ist und keine optimalen Strategien spielt. Schon simple Spiele mit mehr als zwei Personen können auf Grund der zu hohen Anzahl an Termen nicht mehr errechnet werden, sodass dies lediglich für Computer in absehbarer Zeit möglich ist.

Für komplexere Spiele gibt es eine effizienteren Algorithmus namens Joint Strategy Fictitious Play. Dieser vereinfacht die Komplexität von Fictitious Play, da er die historischen Entscheidungen betrachtet und somit die kommenden Strategien der Kontrahenten approximiert wird. Die Vereinfachung liegt darin, dass die eigene Strategie zufällig gewählt wird und nicht an alle Spieler angepasst wird. Somit ist der Rechenaufwand wesentlich geringer, zur Lasten der Optimalität. Im Fall des 2-Personen-Spiels entspricht die Strategie von Joint Strategy Fictitious Play dem ursprünglichen Fictitious Play. Joint Strategy Fictitious Play ist jedoch im Gegensatz zu Fictitious Play bei Spielen mit einer Personenanzahl > 2 praktikabel. Neben dem hohen Rechenaufwand von Fictitious Play, ist der Beobachtungsaufwand der vorherigen Strategien ein weiterer Aspekt, der diese Strategie in der Praxis kaum möglich macht.

Siehe auch

• Beliefs
• Nash-Gleichgewicht
• Konvergenz
• Matching Pennies
• Texas Hold’em

Weblinks

http://www.gambit-project.org/

Literatur

• Original paper: G.W. Brown: Iterative solution of games by Fictitious Play, in Activity Analysis of Production and Allocation, ed. T.C. Koopmans, New York, Wiley (1951), 374–376

• Berger, U. (2004). Two more classes of games with the Fictitious Play property. Mimeo, Vienna University of Economics.

• Berger, U. (2005) „Fictitious Play in 2xN Games“, Journal of Economic Theory 120, 139–154.

• Berger, U. (2007) „Brown’s original Fictitious Play“, Journal of Economic Theory 135:572-578
• Danskin, J. M. (1954), Fictitious play for continuous games. Naval Research Logistics Quarterly, 1: 313–320
• Duziak, W. (2006). Using Fictitious Play to find pseudo-optimal solutions for full-scale poker. In Proceedings of the 2006 International Conference on Artificial Intelligence(ICAI-2006).
• J. R. Marden, G. Arslan, J. S. Shamma, “Joint strategy fictitious play with inertia for potential games,” in Proceedings of the 44th IEEE Conference on Decision and Control, December 2005, pp. 6692–6697
• D. Monderer, L. Shapley: Fictitious Play property for games with identical interests, J. Econ. Theory 68 (1996), 258–265
• von Neumann and Morgenstern (1944), Theory of Games and Economic Behavior, Princeton and Woodstock: Princeton University Press.
• Samuelson, L. (1998) Evolutionary Games and Equilibrium Selection, MITP.
• Shapley L. (1964) „Some Topics in Two-Person Games“ In Advances in Game Theory M. Dresher, L.S. Shapley, and A.W. Tucker (Eds.), Princeton: Princeton University Press.
• Weibull, J. (1995) Evolutionary Game Theory, MITP. Fudenberg, D. & David K. Levine, D. (1998) The Theory of Learning in Games, MITP.
• M. Zinkevich, M. Bowling, M. J., & Piccione, C. (2007). Regret minimization in games with incomplete information. Advances in Neural Information Processing Systems (NIPS 2007), 374–380.