Folk-Theorem

Aus Wikiludia
Wechseln zu: Navigation, Suche

Das Folk-Theorem macht eine Aussage über mögliche Gleichgewichte in wiederholten Spielen. Seinen Namen hat es dem Umstand zu verdanken, dass seine Aussage vielen Spieltheoretikern als evident gilt und seine ursprüngliche Formulierung keinem Einzelnen zugeordnet werden kann.

Formulierung des Satzes: ==Satz (Folk-Theorem)==: In einem wiederholten Spiel können alle möglichen, individuell rationalen Auszahlungen als Gleichgewicht gestützt werden.


Im Folgenden wird ein Spezialfall des Satz, auch Theorem von Friedman genannt, formuliert und bewiesen:

Wir betrachten ein endliches Basisspiel G = (M,S,u) mit M=\{1,\ldots,N\}, das ein Nash-Gleichgewicht s^*=(s_1^*,\ldots s_N^*) besitze. Weiter sei ki,n die Strategie des Spieles i in der n-ten Runde. Damit ergibt sich als Auszahlung des unendliche wiederholten Spiels: u_i^{\infty}(k)=\sum_{n=1}^{\infty}\delta^{n-1}u_i(k_{1,n},\ldots ,k_{N,n})

Das Folk-Theorem kann dann wie folgt formuliert werden:
==Satz (Friedman's Theorem)==: Sei G das oben beschriebene Spiel und es existiere außerdem eine Strategie t=(t_1,\ldots t_N) mit  u_i(t)>u_i(s^*)\ \forall i.
Für alle δ hinreichend nahe bei 1, existiert ein für das iterierte Spiel teilspielperfektes Nash-Gleichgewicht K=(K_n)_{n\in\mathbb{N}} mit (1-\delta)u_i^{\infty}(K)=u_i(t)\ \forall i. ===Beweis===: Definiere eine Strategie Ki für den Spieler i durch: Ki,1 = ti und  K_{i,n}=\begin{cases} t_i \mbox{ falls in allen vorgehenden n-1 Spielen alle Spieler t gespielt haben}\\s^*_i \mbox{ sonst}\end{cases}

1.) Behauptung: K ist ein Nash-Gleichgewicht im iterierten Spiel, zumindest für hinreichend großes δ.
Es Spielen also alle Spieler die Strategie K_i, und wir wollen herausfinden, ob es sich für den Spieler i lohnt, von der Strategie abzuweichen. Tut er das nicht, wird in jeder Runde t gespielt und als Auszahlung ergibt sich:
u_i^{\infty}(K)=\sum_{j=1}^{\infty} u_i(t)\delta^{j-1}=\frac {u_i(t)} {1-\delta}
Weicht er jedoch in der m-ten Runde ab, werden die anderen in jeder folgenden Runde s^* Spielen. Spieler i erält also die höchsten Auszahlungen, wenn er in in der m-ten Runde die beste Antwort \hat{t_i} auf ti spielt und anschließend die beste Antwort auf s^*_{-i} - und das ist s^*_i, weil es sich um ein Nash-Gleichgweicht handelt. F"ur dies Strategie \tilde K_i ergibt sich als Auszahlung: u_i^{\infty}(\tilde K)=\frac {1-\delta^{m-1}}{1-\delta}u_i(t)+\delta^{m-1} u_i(\hat t)+\frac {\delta^m}{1-\delta}u_i(s^*)
Damit lohnt eine Abweichung von der Strategie genau dann, wenn:
u_i^{\infty}(\tilde K)>u_i^{\infty}(K) \Leftrightarrow \frac{u_i(t)}{1-\delta}>u_i(\hat t)+\frac{\delta}{1-\delta}u_i(s^*) \Leftrightarrow \delta>\frac{u_i(\hat t)-u_i(t)}{u_i(\hat t)-u_i(s^*)}
Nach Wahl der Strategien ist die Grenze echt kleiner als 1. Damit lohnt es sich also für keinen Spieler von der Strategie K abzuweichen, wenn: \delta>\max_{i}\frac{u_i(\hat t)-u_i(t)}{u_i(\hat t)-u_i(s^*)}

In diesem Fall handelt es sich bei K um ein Nash-Gleichgewicht und die Behauptung ist gezeigt.

2.) Es bleibt also zu Zeigen, dass K teilspielperfekt ist.
Da das Spiel unendlich oft wiederholt wird, ist jedes Teilspiel von der Gestalt von G_{\infty}(\delta). Wir betrachten nun das Teilspiel Gm(δ) das in der m-ten Runde beginnt. Falls bis dahin immer t gespielt wurde, ist die Strategie nach dem vorher gezeigten ein Nash-Gleichgewicht. Falls einmal abgewichen wurde, ist spielen die anderen immer s^*_{-i} und auch Spieler i spielt mit der Strategie K immer s^*_i, was also wiederum ein Nash-Gleichgewicht ist (wiederholtes spielen des Nash-Gleichgewichts des Basisspiels ist ein Nash-Gleichgewicht).
Damit ist also die Strategie in jedem Teilspiel ein Nash-Gleichgewicht, also teilspielperfekt.

Insgesamt liefert K also das gewünschte, und der Satz ist bewiesen.

Inhaltsverzeichnis

Folk Theoreme für wiederholte Gefangenendilemmas

In wiederholten Gefangenendilemmas kann man sehr effektiv mit der Nash Strategie drohen. Dies vereinfacht die Formulierung teilspielperfekter Gleichgewichte enorm.
Im Allgemeinen (später) sind die Nash–Strategien nicht die effizienten Drohpunkte (bzw. Bestrafungsstrategien).

Das Basisspiel sei folgendes Gefangenendilemma:

C D
C 3, 3 0, 4
D 4, 0 1, 1



Die folgende Analyse läßt sich auf alle Spiele verallgemeinern, in denen die Nash–Strategien sinvolle Drohpunkte sind.

Die Grundidee

Unendliche Wiederholungen von (C, C) können sich in einem TSP–Ggw. ergeben, wenn nach jeder Defektion beide Spieler eine Runde (D,D) spielen würden.
 \triangleright Gewinn durch Defektion: 4 − 3 = 1
 \triangleright Verlust durch Strafe: 3 − 1 = 2
Angenommen, ein Spieler erwägt eine einmalige Abweichung. Die zu vergleichenden Auszahlungsströme sind

(4, 1, 3, 3, . . . ) vs. (3, 3, 3, 3, . . . )

Egal, ob Mittelwert–, Overtaking–, oder Diskontierungskriterium (für δ  \rightarrow 1), der erste Auszahlungsstrom ist nicht vorzuziehen.

Analog, es lohnt sich auch nicht, mehrfach abzuweichen. Aber:

 \triangleright Wie sieht die Strategie genau aus?
 \triangleright Ist es wirklich teilspielperfekt, denn Gegner zu bestrafen? (Auch der Bestrafende leidet darunter.)

Die Strategie

Es gibt zwei Phasen. Die Phase in Runde t ist gespeichert in mt.

m_t=\begin{cases} 0 & \mbox{Standardphase } \\ 1 & \mbox{Bestrafungsphase } \end{cases}

Die Phase kann als Stimmung in einer Beziehung interpretiert werden: gut oder schlecht.

Nach einer Abweichung wechselt das Spiel in die Bestrafungsphase, nach der Bestrafung wieder in die Standardphase.

m1 = 0,   m_{t+1}=\begin{cases} 1, & \mbox{falls }S_t\ne(C,C)\mbox{ und }m_t=0 \\ 0, & \mbox{sonst } \end{cases}

Dies sind die Stimmungswechsel in der Beziehung. Die Strategie ist:

  \hat S_b(S_{1...t})=\begin{cases} C, & \mbox{falls }m_t=0 \\ D, & \mbox{falls }m_t=1 \end{cases}

Teilspielperfektheit der Strategie

Angenommen, ein Spieler erwägt in irgendeiner der (potentiellen) Bestrafungsphasen, abzuweichen.

 \triangleright Dies hätte keine Auswirkungen auf die Fortsetzung des Spiels. (Nach einer Bestrafungsrunde geht es in jedem Fall normal weiter.)
 \triangleright In der Bestrafungsphase macht er Verlust.

Gemäß schwacher Separierbarkeit kann sich das Abweichen insgesamt also nicht lohnen.

 \triangleright Nach jeder Abweichung wird die Bestrafung durchgeführt.
 \triangleright In der Standardphase hat niemand einen Anreiz abzuweichen.

Die Strategie ist damit ein TSP–Ggw.

Sie ist ein schwaches Gleichgewicht laut Mittelwert–Kriterium (denn einmalige Abweichungen schaden auch nicht), sonst ein striktes Gleichgewicht.

Verallgemeinerung des Ergebnisses zum Folk Theorem

Nicht nur (C, C) kann sich in einem TSP–Ggw. ergeben, sondern auch folgender Zyklus:

(C,D), (D, C), (D, C), (C,D), . . .

Oder auch:

Die Durchschnittsauszahlungen wären dann zwar nur (2, 2) bzw. (1.75, 2.75), aber Gleichgewichte k¨onnen es trotzdem sein. Denn beide Spieler erhalten mehr als im Nash–Gleichgewicht, d.h. mehr als (1, 1).

Wenn nach jeder Abweichung einmal (D,D) folgt, kann sich keine Abweichung von einem Zyklus lohnen, der mehr als (2, 2) bringt. Bei weniger profitablen Gleichgewichten müssen die Bestrafungsphasen verlängert werden.

Eine Strategie für Kooperationszyklen


Sei Z^T \in \bar{S}^T ein beliebiger T–Runden–Zyklus, wo die Durchschnittsauszahlung jedes Spielers größer als 2 ist (i.a. reicht sogar > 1).

\qquad \forall {b} : {1 \over T}  \sum_{t\leq T} \hat P_b(Z_t^T) >2

Die Spielphase (nach der Historie St) sei nun: m1 = 1 und

  m_{t+1}=\begin{cases} (m_t  mod T)+1, & \mbox{falls }m_t>0 \mbox{ und }S_t=Z^T_{m_t} \\ -m_t, & \mbox{sonst } \end{cases}

Die Strategie ist:

  \hat S_b(S_{1...t})=\begin{cases} Z^T_{m_t,b}, & \mbox{falls }m_t>0 \\ D, & \mbox{falls }m_t<0 \end{cases}

Allgemeine Folk Theoreme

Im Allgemeinen ist die optimale Strategie zur Bestrafung von b die sogenannte Minimax–Strategie. Die Minimax–Auszahlung ist

 P^*_b=\min_{S_{-b}\in \bar{S}_{-b}}\max_{{S_b}\in \bar{S}_b} \hat{P}_b(S_b,S_{-b})

die Auszahlung, die b unter allen Umst¨anden garantieren kann. Wenn b’s Gegner ihn minimaxen, spielen sie

 M^b_{-b} \in arg\min_{S_{-b}}\max_{{S_b}}\hat{P}_b(S_b,S_{-b})

Zur Verteidigung spielt b die Strategie M^b_b\in \widehat{BA}_b(M^b_{-b}).

Das Minimax–b–Strategieprofil (M^b_b,M^b_{-b})=:M^b ist i.A. kein Nash–Gleichgewicht. Daher können einige Spieler Anreize haben, während des Bestrafens abzuweichen. Außerdem reicht es i.A. nicht, den Abweichler nur eine Runde zu bestrafen.

Ein Folk Theorem für das Mittelwert–Kriterium

Zur Vereinfachung konzentrieren uns auf Zyklen der L¨ange 1, d.h. es wird erwartet, daß die Spieler in jeder Runde S * spielen.

Wenn Spieler b von S * abweicht, weicht er idealerweise zu \widehat{BA}_b(S^*_{-b}). ab, und gewinnt höchstens

\hat{P}_b(\widehat{BA}_b(S^*_{-b}),S^*_{-b})-\hat{P}_b(S^*).

In der Bestrafungsphase verliert er pro Runde

\hat{P}_b(S^*)-\hat{P}_b(M^b).

Also reicht es, b nach Abweichungen rb Runden zu bestrafen, mit

r_b=\left\lfloor {\hat{P}_b(\widehat{BA}_b(S^*_{-b},S^*_{-b})-\hat{P}_b(S^*))\over \hat{P}_b(S^*)-\hat{P}_b(M^b) } \right\rfloor +1

Ein Folk–Theorem für das Overtaking–Kriterium

y1 y2
x1 3, \underline{2} \underline{1}, 0
x2 \underline{5},\underline{1} \underline{1}, 0



Nash: (5,1) \qquad Minimax: (1,1)



Ein Mittelwert–Folk–Theorem–Ggw. für (x1,y1)

Spiel (x1,y1),
nach Abw. von 1: 3 Runden (x2,y2)


nach Abw. von 2: keine Strafe



Eine alternative Strategie von 2 ist: . . . nach Abw. von 1: 3 Runden y1 . . . , d.h. 2 bestraft 1 nicht (kein Ggw.)

Auszahlungsströme nach Abweichung von 1:
(0, 0, 0, 2, 2, . . . )
(1, 1, 1, 2, 2, . . . )

Die Abweichung lohnt sich damit nach Overtaking und Diskontierung. Die obige Strategie ist also nicht teilspielperfekt.

Die Grundidee

Spieler, die nicht bestrafen, werden bestraft. D.h. Abweichungen in der Bestrafungsphase werden ähnlich behandelt wie Abweichungen in der Standardphase.

Abweichungen in der Standardphase werden bestraft wie zuvor.

r_{b}>{\hat{P}_b(\widehat{BA}_b(S^*_{-b},S^*_{-b})-\hat{P}_b(S^*))\over \hat{P}_b(S^*)-\hat{P}_b(M^b)}

Abweichungen in der Bestrafungsphase: angenommen, c sollte r Runden bestraft werden, b weicht ab und wird dann r' Runden bestraft. Dann lohnen sich b’s Abweichungen nicht, wenn

 r*\hat{P}_b(M^c)+(r'-r+1)\hat{P}_b(S^*)>\hat{P}_b(\widehat{BA}_b(M^c_{-b})+r'*\hat{P}_b(M^b)

bzw.

 r*\hat{P}_b(M^c)-\hat{P}_b(S^*)-\hat{P}_b(S^*)-\hat{P}_b(\widehat{BA}_b(M^c_{-b})>r'\underbrace{(\hat{P}_b(M^b)-\hat{P}_b(S^*))}_{<0}

Bemerkung

Für alle individuell rationalen S * existiert ein TSP–Ggw. nach dem Overtaking–Kriterium, so daß im Gleichgewicht niemand von S * abweicht.

Auch dieses Theorem läßt sich auf beliebige Zyklen verallgemeinern, vorausgesetzt die Durchschnittsauszahlung ist größer als die Minimax–Auszahlung.

Ein Folk Theorem bei Diskontierung

Das Diskontierungs–Kriterium ist noch etwas anspruchsvoller, daher werden die Strategien noch etwas komplizierter.

Das Problem: Spieler, die nicht bestrafen, müssen bestraft werden. Dadurch kann sich die Bestrafungsdauer verlängern. Wenn dann wieder einer abweicht, kann sie sich noch weiter verlängern, usw. Dabei kann die Bestrafungsphase beliebig lang werden.

In einer Bestrafungsphase kann es sein, daß einige der bestrafenden Spieler weniger als ihre Minimax–Auszahlung erhalten. Egal wie groß δ ist, die Bestrafungsphase kann zu lang werden, um die entstehenden Verluste später kompensieren zu können. Dann lohnt es sich für manche Spieler, vom Bestrafen abzuweichen und die Minimax–Auszahlung zu realisieren.

Die Lösung: Abweichler in der Bestrafungsphase werden bestraft, und Nicht–Abweichler werden belohnt. Dadurch gibt es stärkere Anreize, nicht abzuweichen, und die Bestrafungsphasen werden nicht beliebig lang.

Diskontierung bei zwei Spielern

Falls nur zwei Spieler beteiligt sind, gibt es einfachere Lösung: gegenseitiges Minimaxen. D.h. beide Spieler werden bestraft (minimaxed), egal wer abgewichen ist.

Auf diese Art und Weise muß die Bestrafungsdauer nicht sukzessive aufgestockt werden. Die Strategie ist:

1.Spiele S^*_b . Nach irgendwelchen Abweichungen gehe zu 2.
2. Spiele Minimax–Strategie gegen den Gegner für v Runden und gehe zurück zu 1. Wenn ein Spieler abweicht, starte 2 neu.

Die Bestrafungsdauer v muß lang genug sein, so daß es sich für keinen Spieler lohnt, irgendwann abzuweichen.

Wenn δ groß genug ist, ist das kein Problem. D.h. für δ nahe bei 1 gibt es immer passende v.

Zusammenfassung

Es gibt mehrere Erkenntnisse: \trianglerightEs gibt viele Gleichgewichte mit vielen verschiedenen Ergebnissen.
\trianglerightBestimmte Verhaltensstrukturen bilden Gleichgewichte (und sind daher rationalisierbar).
\trianglerightJe ungeduldiger die Spieler, desto komplexer sind die n¨otigen Strategien.

Die Verhaltensmuster sind:

\trianglerightBei unendlich geduldigen Spielern: es reicht, wenn die Bestrafung endlich ist.
\trianglerightBei ziemlich geduldigen Spielern: Nicht–Bestrafer müssen auch bestraft werden.
\trianglerightBei leicht ungeduldigen Spielern: Bestrafer müssen zusätzlich belohnt werden.

Zur Interpretation der Folk Theoreme

Die Folk Theoreme sagen nicht, was sich ergeben wird, sondern nur, was sich wie ergeben kann.

Wiederholte Spiele sind ein Modell f¨ur langfristige Interaktionen im Allgemeinen. Die aufeinanderfolgenden Spiele m¨ussen nicht unbedingt identisch sein, dies vereinfacht nur die Analyse.

Die Unterscheidung von verschiedenen Stimmungsphasen und die Phasenübergänge wirken recht realistisch: das Beziehungsklima kann sich recht schnell verschlechtern, aber nur langsam wieder normalisieren.

Bei solchen Akteuren können sich auch soziale Normen etablieren.
\trianglerightAbweichler werden (vorübergehend) ausgeschlossen.
\trianglerightNicht–Ausschließer werden auch ausgeschlossen.
\trianglerightNach Wiederaufnahme in die Gruppe haben die vormals Ausgeschlossenen schlechtere Positionen.

Zur Interpretation, 2

Beispiele:

\trianglerightStraftaten, Gefängnisstrafen, Bewährungsstrafen, Resozialierung
\trianglerightNeidgefühle, Ärger und Wut, Mißtrauen und Unverzeilichkeiten
\trianglerightNachbarschaftshilfe, Sportvereine

Je nach Komplexität der genutzten Strategien kann man auf die Ungeduld der Akteure schließen.

Familienmitglieder sind wohl geduldiger als Fremde, daher sind Familiennormen leichter zu unterstützen als soziale Normen.




Hinweise zum Folk-Theorem:
-Die Aussage des Folk-Theorems ist eine Existenzaussage: Es werden Bedingungen formuliert, unter denen (Trigger-) Strategien existieren, mit deren Hilfe sich beide Spieler besser stellen können, als bei einer permanenten Wiederholung der Nash-Lösung des Stufenspiels.
-Das Folk-Theorem gilt auch in dem Fall, dass die Nash-Lösung des Basisspiels eindeutig ist.


Folk-Theorem für das Overtaking-Kriterium und Interpretation der Folk-Theoreme folgen noch!

Meine Werkzeuge