Sequentielles Gleichgewicht

Aus Wikiludia

Das sequentielle Gleichgewicht ist eine Verfeinerung des Nash-Gleichgewichts insbesondere für Spiele mit unvollkommener Information. Das von Kreps und Wilson 1982 entwickelte Konzept verfeinert dabei die Menge der teilspielperfekten Gleichgewichte. Indem es unplausible teilspielperfekte Gleichgewichte ausschließt, bildet die Menge der sequentiellen Gleichgewichte damit eine Teilmenge der teilspielperfekten Gleichgewichte.

Motivation

Um teilspielperfekte Strategien zu entwickeln, müssen Spieler über vollkommene Information verfügen, das heißt, sie müssen über den bisherigen Spielverlauf informiert sein. Ist diese Information nicht gegeben, müssen Spieler eine Wahrscheinlichkeitseinschätzung bilden, welche Strategien bisher gespielt wurden und an welchem Entscheidungsknoten sie sich gerade befinden. Auf der Grundlage dieser Einschätzungen ermitteln die Spieler ihre optimale Strategien. Die sich daraus ergebenden Gleichgewichte werden im Konzept der sequentiellen Gleichgewichte behandelt.

Definitionen und Bemerkungen

Definition: Sequentielles Gleichgewicht

Ein sequentielles Gleichgewicht ist ein Paar $(s,μ)$ mit der Strategiekombination s und der Wahrscheinlichkeitseinschätzung $μ$ , falls gilt:

(a) Jede Handlung eines Spielers ist an jeder Informationsmenge eine optimale Wahl, gegeben das Paar $(s,μ)$ , d.h., gegeben die Strategien $s - i$ der anderen Spieler und gegeben die Wahrscheinlichkeitseinschätzung $μ$ .

(b) Die Wahrscheinlichkeitseinschätzungen über das Verhalten der anderen Spieler sind konsistent mit den im weiteren Spielverlauf optimalen Strategien dieser Spieler.

Definition: Sequentielle Rationalität

Die in Teil a der Definition angeführte optimale Wahl wird auch als sequentiell rationale Einschätzung bezeichnet und wie folgt definiert:

In einem extensiven Spiel mit vollkommener Erinnerung heißt eine Einschätzung (s*,

μ *

) sequentiell rational, wenn für die Auszahlung

u i

jedes Spielers i und für jede seiner Informationsmengen $I_i^j \in \mathfrak I_i$ gilt: $\quad u_i (s^*, \mu^*; I_i^j) \ge u_i (s_i, s_{-i}, \mu^*; I_i^j) \quad \forall s_i.$

Definition: Konsistenz

Die in Teil b der Definition für die Wahrscheinlichkeitseinschätzungen geforderte Konsistenz definieren Kreps und Wilson folgendermaßen:

Seien

s ε

vollständig gemischte Strategiekombinationen, bei denen jede reine Strategie mit mindestens einer echt positiven Wahrscheinlichkeit

ε

gespielt wird und seien

μ ε

die aus der Anwendung der Bayes'schen Regel resultierenden Wahrscheinlichkeitseinschätzungen.

Dann heißt eine Kombination

(s,μ)

konsistent, wenn eine Folge

(s ε,μ ε)

existiert, so dass $\lim_{{\epsilon} \to 0}(s^{\epsilon},\mu ^{\epsilon} ) = (s,\mu )$

Definition: Sequentielles Gleichgewicht (Kurzfassung)

Mit diesen Begriffen ist auch eine Kurzfassung der Definition möglich:

Eine Einschätzung, die sequentiell rational und konsistent ist, heißt sequentielles Gleichgewicht.

Bemerkungen

Ähnlich wie beim teilspielperfekten Gleichgewicht soll also bei jedem erreichten Punkt der folgende Spielverlauf wieder ein sequentielles Gleichgewicht sein, selbst wenn der bisher erreichte Punkt nicht mehr im Nash-Gleichgewichtspfad liegt. In letzterem Fall errechnen die Spieler dann mit Hilfe ihrer Wahrscheinlichkeitseinschätzungen µ bedingt auf den erreichten Entscheidungsknoten nach der Bayes'schen Regel neue Wahrscheinlichkeiten und spielen (bis zum nächsten abweichenden Ereignis) wieder optimale Strategien. Bei einer weiteren Abweichungen wiederholt sich dieser Vorgang.

Zu beachten ist, dass jedes Nash-Gleichgewicht bereits mit einer einzigen konsistenten Wahrscheinlichkeitseinschätzung zu einem sequentiellen Gleichgewicht wird; es ist nicht notwendig, dass alle möglichen konsistenten Wahrscheinlichkeitseinschätzungen berücksichtigt werden.

Sequentielle Gleichgewichte können ihrerseits aber ebenfalls unplausibel sein (vgl. das Beispiel "Variante des Markteintrittspiels"). Es wurden daher weitere Verfeinerungen auch des sequentiellen Gleichgewichts entwickelt. Beispielhaft sei hier nur das Konzept des perfekten Gleichgewichts genannt.

Satz (Existenz)

Satz

Sei G ein endliches extensives Spiel mit perfekter Erinnerung, sei $\hat s*$ ein perfektes Gleichgewicht von G und sei s die daraus abgeleitete Strategie.

Dann gibt es ein $μ *$ , so dass $(s * ,μ * )$ ein sequentielles Gleichgewicht ist.

Beweis

Da $\hat s*$ perfektes Gleichgewicht ist, existiert nach Definition eine gegen $\hat s*$ konvergente Folge $(\hat s*)_k$ gemischter Strategien, deren beste Antwort $\hat s*$ ist. Die Folgen $(s) k$ und $(μ) k$ , die sich daraus ableiten, sind daher offensichtlich ebenfalls konvergent mit $\lim_{{\epsilon} \to 0}(s^{\epsilon},\mu ^{\epsilon} ) = (s,\mu )$ , also konsistent. Zudem gilt, ebenfalls da $\hat s*$ perfektes Gleichgewicht offenbar, dass $(s,μ)$ sequentiell rational sind. Damit folgt die Behauptung.

Folgerung

Da jedes endliche Spiel ein perfektes Gleichgewicht besitzt, folgt aus diesem Satz, dass jedes endliche extensive Spiel auch mindestens ein sequentielles Gleichgewicht besitzt.

Beispiele

Variante des Markteintrittspiels

In einer Version des Markteintrittspiels überlegt ein Konkurrent K eines Monopolisten M, in den Markt des Monopolisten einzutreten. Tritt K ein, so kann er zwischen zwei Alternativen $E 1$ und $E 2$ wählen (etwa zwischen zwei Produktionsmethoden). Tritt K ein, so kann sich M zwischen einer Duldung (D) oder einem aggressiven Verdrängungskampf (A) entscheiden, ohne jedoch zu wissen, ob K die Alternative 1 oder 2 gewählt hat. N sei Nichteintritt von K.

Sei also G = (L, H, j, u) mit

der Spielermenge $L = {K, M}$
der Historie $H = \{\emptyset, (N),(E_1),(E_2), (E_1,A), (E_1,D), (E_2,A), (E_2,D)\}$ , wobei $E = \{\emptyset,(E_1), (E_2)\}$ die Entscheidungsmenge ist und die Endknoten $Z:=H \setminus E = \{(N), (E_1,A), (E_1,D), (E_2,A), (E_2,D)\}$
der Spielerfunktion $j:E \longrightarrow L$ mit $j(\emptyset)= K$ und $j ((E 1)) = j ((E 2)) = M$
der Nutzenfunktion u mit den in Matrix 1 (bzw. 2) angegeben Auszahlungen

und den Wahrscheinlichkeitseinschätzungen $μ 1$ bzw. $μ 2$ = (1 - $μ 1$ ) von M, dass K bei Markteintritt die Strategie $E 1$ bzw. $E 2$ gewählt hat.

Matrix 1

	A	D
N	(0,60)	(0,60)
$E 1$	(-10,-10)	(30,30)
$E 2$	(-5,-5)	(-20,10)

Dieses Spiel hat offensichtlich zwei Nash-Gleichgewichte, (N,A) und ( $E 1$ ,D). Da M keine Information darüber hat, ob K $E 1$ oder $E 2$ gewählt hat, kann das Spiel nicht in einzelne Teilspiele zerlegt werden. Da somit das Gesamtspiel das einzige mögliche Teilspiel ist, sind diese beiden Gleichgewichte natürlich auch die beiden teilspielperfekten Gleichgewichte, obwohl (N,A) wegen der rational nicht zu rechtfertigenden Entscheidung von M für A offenbar unplausibel ist. Ist K in den Markt eingetreten, so bildet M die Wahrscheinlichkeitseinschätzung $μ 1$ , dass K die Alternative 1 gewählt hat, und kann damit seinen Erwartungsnutzen für beide Alternativen berechnen:

wählt M die Strategie D, so beträgt sein Erwartungsnutzen $30μ 1 + 10(1 - μ 1) = 20μ 1 + 10$
wählt M die Strategie A, so beträgt sein Erwartungsnutzen $- 10μ 1 - 5(1 - μ 1) = - 5μ 1 - 5$

Da für jedes $μ 1 > 0$ D offensichtlich besser ist als A, wird M immer D wählen. K antizipiert dies und tritt in den Markt ein, so dass ( $E 1$ ,D) als einziges sequentielles Gleichgewicht bestehen bleibt.

Matrix 2

	A	D
N	(0,60)	(0,60)
$E 1$	(-10,-10)	(30,30)
$E 2$	(-5,40)	(-20,10)

Ändern wir die Auszahlung von (A, $E 2$ ) wie in der zweiten Matrix auf (-5,40) ab, ändert sich die Situation für M grundlegend. Nun hängt seine optimale Strategie ganz wesentlich von der von K gewählten Alternative ab: Hat K 1 gewählt, so ist D die beste Antwort, hat K 2 gewählt, ist A die optimale Strategie. M wird nun A wählen, wenn der Erwartungsnutzen der Strategie A größer als der Erwartungsnutzen von D ist, also wenn gilt:

$- 10μ 1 + 40(1 - μ 1) = - 50μ 1 + 40 > 30μ 1 + 10(1 - μ 1) = 20μ 1 + 10$ .

Das heißt, schätzt M die Wahrscheinlichkeit $μ 1$ < 5/7, so wird er sich für einen aggressiven Kampf (A) entscheiden, schätzt er jedoch $μ 1$ als größer als 5/7, so wird er sich erneut für D entscheiden, schätzt er $μ 1$ als genau 5/7 ein, so ist er indifferent zwischen den beiden Möglichkeiten.

Das sequentielle Gleichgewicht dieses Spiels ist also für $μ 1$ < 5/7 die Strategie (N,A) und für $μ 1$ > 5/7 die Strategie ( $E 1, D$ ). (Für die Situation $μ 1$ = 5/7 muss sich K eine Einschätzung darüber bilden, mit welcher Wahrscheinlichkeit P(D) (bzw. p(A) = 1 - p(D)) M die Option D (bzw. A) spielt, und dies mit seinem Erwartungsnutzen abgleichen. Das sequentielle Gleichgewicht ergibt sich dann analog aus der als rational erkannten Strategie von K.)

An diesem Beispiel ist auch zu beobachten, dass nicht alle sequentiellen Gleichgewichte plausibel sind: Da für K die Strategie $E 2$ von der Strategie N strikt dominiert wird, ist eine Wahrscheinlichkeitseinschätzung von $μ 1$ < 5/7 nicht realitätsnah. Das sequentielle Gleichgewicht (N,A) für diese Einschätzung ist also unplausibel.

Die Abweichung Eingeschaft von Sequentielles Gleichgewicht

Sei $\ (\beta,\mu)$ konsistente Einschätzung in extensivem endlichem Spiel mit vollkommener Erinnerung und sei $\beta_i^'$ Strategie von Spieler $\ i$ . Beziechne $\beta^'=(\beta_{-i},\beta_i^' )$ . $\ I_i^'$ enthält Historien, die Teilhistorien in $\ I_i$ haben. Zeige, falls $\ I_i$ und $\ I_i^'$ Informationsmenge von Spieler $\ i$ sind, dann

$O(\beta^',\mu|I_i )(h)=O(\beta^',\mu|I_i^' )(h)*Pr(\beta^',\mu|I_i )(I_i^')$

für alle Endhistorien, die Teilhistorien in $\ I_i^'$ haben. Wobei $\ Pr(\beta^',\mu|I_i )(I_i^')$ ist die Wahrscheinlichkeit nach $\ (\beta^',\mu)$ , dass $\ I_i^'$ erreicht ist, falls $\ h$ erreicht ist. Benutze diese Voraussetzung um zu beweisen dass $\ (\beta,\mu)$ sequentiell rational ist genau dann wenn keine Spieler $\ i$ eine Informationsmenge $\ I_i$ hat, so dass eine Abweichung in $\ \beta_i(I_i)$ seine erwartete Auszahlung maximiert.

Beweis:

Beachte dass, unter der Voraussetzung von vollkommener Erinnerung, falls die Informationsmenge $\ I_i^'$ von Spieler $\ i$ eine Historie $\ (h,a^1,...,a^k)$ enthält, wobei $\ h \in I_i$ , alle Historien in $\ I_i^'$ von der form $\ (h^',b^1,...,b^m)$ ,für $\ h \in I_i$ sind. Folge von Aktionen von Spieler $\ i$ in $\ (a^1,...,a^k)$ ist die gleiche wie die Folge von Spieler $\ i$ in $\ (b^1,...,b^m )$ .

Wir nehmen an dass $\ (\beta,\mu)$ konsistente Einschätzung ist. Sei $β'$ Strategie von Spieler $\ i$ und $\beta^'=(\beta_{-i},\beta_i^' )$ . Weiter seien $\ I_i$ und $\ I_i^'$ Informationsmenge von Spieler $\ i$ und sei $\ h=(h^*,a^',a^{''} )$ Endhistorie, wobei $\ a^'$ und $\ a^{''}$ folgen von Aktionen sind. $h^* \in I_i$ und $(h^*,a^' ) \in I_i^'$ .

Zuerst zeigen wir dass $O(\beta^',\mu|I_i )(h)=O(\beta^',\mu|I_i^' )(h)*Pr(\beta^',\mu|I_i )(I_i^')$

Für $\ Pr(\beta^',\mu|I_i )(I_i^')=0$ es trivial. Wir nehmen dann an, dass $\ Pr(\beta^',\mu|I_i )(I_i^')>0$ ist. Dann haben wir

$O(\beta^',\mu|I_i )(h)=\mu(I_i)(h^*)*P_{\beta^'}(a^',a^{''})$

und

$O(\beta^',\mu|I_i )(h)=\mu(I_i^')(h^*,a^')*P_{\beta^'}(a^{''})$

Wobei $\ P_{\beta^'}(a)$ Produkt der, von $β'$ zugewiesenen, Wahrscheinlichkeiten von Folgen von Aktionen $\ a$ ist. Sei jetzt $\ \bar h (h^')$ Teilhistorie von $\ h^'$ in $\ I_i$ , für alle $\ h^' \in I_i^'$ . Und sei $\ {\bar h (h^') \over h^'}$ ein Teil von $\ h^'$ . Dann,

$Pr(\beta^',\mu|I_i )(I_i^' )= \sum_{h^' \in I_i^'} \mu(I_i )(\bar h (h^' ) )*P_{\beta^' }(({\bar h (h^' )) \over h^'} )$

Da $\ (\beta,\mu)$ konsistent ist, existiert eine Folge von gemischten Einschätzungen $\ (\beta^n,\mu^n)$ mit $\ \mu^n \to \mu$ und $\ \beta^n \to \beta$ , für $\ n \to \infty$ und für alle $\ n$ die Wahrscheinlichkeitseinschätzung $\ \mu^n$ ist abgeleitet von $\ \beta^n$ mit Hilfe von Bayessche Regel. Für alle $\ n$ haben wir

$\ \mu(I_i^' )(h^*,a^')={\mu^n(I_i )(h^* )*P_{\beta^' }(a^') \over \sum_{h^' \in I_i^'} \mu(I_i)(\bar h (h^'))*P_{\beta^'}({\bar h (h^' )) \over h^' })}$

weil $\ Pr(\beta^',\mu|I_i )(I_i^')>0$ . Für für $\ n \to \infty$ und $\ P_{\beta^'}(a^',a^{''})=P_{\beta^'}(a^')P_{\beta^'}(a^{''})$ wir stellen fest, dass $O(\beta^',\mu|I_i )(h)=O(\beta^',\mu|I_i^' )(h)*Pr(\beta^',\mu|I_i )(I_i^')$ ist.

Um eine Abweichung Eigenschaft zu zeigen, benutzen wir Rückwärtsinduktion. Wir nehmen an: $\ (\beta,\mu)$ ist konsistente Einschätzung mit Eigenschaft, dass kein Spieler eine Informationsmenge hat, mit der er, bei einer Änderung seiner Aktion, die erwartete Auszahlung maximieren kann. Wir nehmen eine Informationsmenge $\ I_i$ und setzen im Voraus dass, um eine von Informationsmengen $\ I_i^'$ von Spieler $\ i$ zu erreichen, $\ \beta_i$ eine optimale Wahl ist. Wir müssen zeigen dass $\ \beta_i$ optimale Wahl ist. Nehmen wir an, dass Spieler $\ i$ Strategie $\ \beta_i^'$ benutzt. Sei $\ \beta^'=(\beta_{-i},\beta_i^')$ und sei $\ F(I_i)$ die Menge von Informationsmengen von Spieler $\ i$ , die nach $\ I_i$ folgt. Weiter sei $\ Z(I_i)$ die Endhistorie, die Teilhistorien in $\ I_i$ hat. Dann erwartete Auszahlung von Spieler $\ i$ , bedingt auf erreichen von $\ I_i$ , ist Summe von seinen Auszahlungen $\ E_i$ von Historien, die nicht anderen Informationsmengen erreichen, und

$\sum_{I_i^' \in F(I_i)} \sum_{h \in Z(I_i^')} O(\beta^',\mu|I_i)(h)*u_i(h)$

Da $O(\beta^',\mu|I_i )(h)=O(\beta^',\mu|I_i^' )(h)*Pr(\beta^',\mu|I_i )(I_i^')$ , folgt dass erwartete Auszahlung von Spieler $\ i$ ist

$E_i + \sum_{I_i^' \in F(I_i)} \sum_{h \in Z(I_i^')} O(\beta^',\mu|I_i^')(h)*Pr(\beta^',\mu|I_i)(I_i^')*u_i(h))$

und dass ist gleich,

$E_i + \sum_{I_i^' \in F(I_i)}Pr(\beta^',\mu|I_i)(I_i^')*E_{(\beta^',\mu)}[u_i|I_i^']$

wobei $\ E_{(\beta^',\mu)}[u_i|I_i^']$ ist erwartete Auszahlung unter $\ (\beta^',\mu)$ und dass ist nach der Induktionsvoraussetzung bestenfalls

$E_i + \sum_{I_i^' \in F(I_i)}Pr(\beta^',\mu|I_i)(I_i^')*E_{(\beta,\mu)}[u_i|I_i^']$

Weiter, nach der Gleichheit in dem ersten Teil des Problems, ist das gleich

$E_{(\beta_{-i},\hat \beta_i),\mu)}[u_i|I_i^']$

Wobei $\ \hat \beta_i$ ist Strategie von Spieler $\ i$ . In diese Strategie Spieler $\ i$ wählt $\ \beta_i^'$ in $\ I_i$ und $\ \beta_i$ sonst. Dann ist $\ \beta_i$ optimale Wahl um $\ I_i$ zu erreichen.

Seltens Pferd

Ein weiteres, sehr bekanntes Beispiel für ein Spiel mit sequentiellem Gleichgewicht ist das Spiel Seltens Pferd.

Quelle

Holler, Manfred J., Illing, G.: Einführung in die Spieltheorie, Springer Verlag Berlin Heidelberg, 7. Aufl. 2009, ISBN 978-3-540-69372-7
Schlee, Walter: Einführung in die Spieltheorie, Vieweg, Wiesbaden, 1. Aufl. 2004, ISBN 3-528-03214-6