Sequentielles Gleichgewicht

Aus Wikiludia
Wechseln zu: Navigation, Suche

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.


Inhaltsverzeichnis

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 si 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 ui 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 E1 und E2 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((E1)) = j((E2)) = 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 E1 bzw. E2 gewählt hat.

Matrix 1


A D
N (0,60) (0,60)
E1 (-10,-10) (30,30)
E2 (-5,-5) (-20,10)

Dieses Spiel hat offensichtlich zwei Nash-Gleichgewichte, (N,A) und (E1,D). Da M keine Information darüber hat, ob K E1 oder E2 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 (E1,D) als einziges sequentielles Gleichgewicht bestehen bleibt.

Matrix 2


A D
N (0,60) (0,60)
E1 (-10,-10) (30,30)
E2 (-5,40) (-20,10)

Ändern wir die Auszahlung von (A,E2) 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 (E1,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 E2 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
Von „http://wikiludia.mathematik.uni-muenchen.de/wiki/index.php?title=Sequentielles_Gleichgewicht
Ansichten
Meine Werkzeuge
Navigation
Werkzeuge