Perfektes Gleichgewicht

Aus Wikiludia
(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
Zeile 34: Zeile 34:
 
|
 
|
 
|}
 
|}
 +
 +
 +
=== Nash-Gleichgewicht eines gestörten Spiels ===
 +
==== Satz ====
 +
Eine Strategiekombination <math>\hat s</math> aus <math>\hat S_\epsilon </math> ist genau dann [[Nash-Gleichgewicht]] des gestörten Spiels <math> \hat \Gamma_\epsilon</math>, wenn für alle Spieler i = 1, ... , m und alle reinen Strategien j = 1, .... , <math>n_i</math> gilt: <math>\{u_i(s^j_i, s_{-i}) < u_i(s_i, s_{-i})\} \Rightarrow \hat s^j_i = \hat \epsilon^j_i </math>.
 +
 +
==== Beweis ====
 +
Für [[gemischte Strategie]]n gilt <math> \hat s^* = (\hat s^*_i, \hat s^*_{-i}) </math> ist [[Nash-Gleichgewicht]], wenn für alle reinen Strategien <math> s^j_i </math> der Spieler i = 1, ... , m gilt: <math> \hat u_i(s^j_i, \hat s^*_{-i}) \leq \hat u_i(\hat s^*) </math> mit j = 1, ... , <math>n_i</math>
 +
d.h. für <math> s^j_i \notin \Tau(\hat s) </math> (<math> \Tau(\hat s) </math> Träger) bzgl. dem ungestörten Spiel <math> \hat \Gamma </math> gilt <math> u_i(s^j_i, \hat s_{-i}) < u_i(\hat s_i, \hat s_{-i}) </math>. Im gestörten Spiel muss dann <math> s^j_i </math> möglichst klein sein, d.h. <math> s^j_i = \epsilon^j_i </math>.
 +
 +
 +
=== Definition 2: Perfektes Gleichgewicht ===
 +
{|
 +
|width="5%" style="vertical-align:top" |
 +
|width="95%" style="vertical-align:top"|
 +
<div style="margin: 0; margin-right:10px; padding: 0 1em 1em 1em; background-color:#DDFFFF; align:right;">
 +
<br>
 +
Ein [[Nash-Gleichgewicht]] <math> \hat s </math> eines Spiels <math> \hat \Gamma = (A, \hat S, \hat U) </math> ist ein perfektes Gleichgewicht, wenn <math> \hat s </math> Häufungspunkt einer Folge <math> (s_\epsilon) \epsilon \searrow 0 </math> ist, bei der jedes Folgenglied ein [[Nash-Gleichgewicht]] des zugeordneten <math> \epsilon </math>-gestörten Spiels ist.
 +
|
 +
|}
 +
 +
 +
=== Äquivalente Aussagen zum perfekten Gleichgewicht ===
 +
==== Satz ====
 +
Sei <math>\hat \Gamma_\epsilon = (A, \hat S, \hat U)</math> ein Spiel mit einer ausgezeichneten Strategiekombination <math>\hat s \in \hat S</math>. Dann sind äquivalent:
 +
# <math> \hat s </math> ist ein perfektes Gleichgewicht
 +
# <math> \hat s </math> ist der Grenzwert einer Folge <math> (\hat s_\epsilon) \epsilon \searrow 0 </math>, deren Folgenglieder <math>\hat s_\epsilon</math>  <math>\epsilon</math>-perfekte Gleichgewichte von <math>\hat \Gamma</math> für alle <math>\epsilon</math> > 0 sind.
 +
# <math> \hat s </math> ist der Grenzwert einer Folge, deren Folgenglieder <math>\hat s_\epsilon</math> Kombinationen von stark [[gemischte Strategie|gemischten Strategien]] sind mit der zusätzlichen Eigenschaft, dass <math> \hat s </math> die [[beste Antwort]] für jedes Folgenglied ist.
 +
 +
==== Beweis ====
 +
: (1) <math>\Rightarrow</math> (2): Sei <math> \hat s </math> Häufungspunkt einer Folge <math> (\hat s_\epsilon) \epsilon \searrow 0 </math> nach Definition 2. Wähle <math>\epsilon = max_{j, i}</math> <math>\epsilon^j_i</math>, dann ist <math> \hat s </math> ein <math>\epsilon</math>-perfektes Gleichgewicht von <math>\hat \Gamma</math>.
 +
: (2) <math>\Rightarrow</math> (3): Sei <math> (\hat s_\epsilon) \epsilon \searrow 0 </math> eine Folge von <math>\epsilon</math>-perfekten Gleichgewichten des Spiels <math>\hat \Gamma</math>, die gegen <math> \hat s </math> konvergiert. Seien die <math>\epsilon</math> ausreichend klein. Dann ist nach Definition 1 und dem Satz über die [[Nash-Gleichgewicht]]e des gestörten Spiels jedes Element des Trägers <math>\Tau(\hat s)</math> eine beste Antwort für jedes <math>(\hat s_\epsilon)</math> und damit auch <math> \hat s </math> eine beste Antwort für alle Folgenglieder.
 +
: (3) <math>\Rightarrow</math> (1): Konvergiere die Folge <math> (\hat s_\eta) \eta \searrow 0 </math> gegen <math> \hat s </math>. Wähle <math>\epsilon^j_i(\eta) = s^{\eta,j}_i</math>, falls <math>s^j_i \notin \Tau(s_i)</math> und <math>\eta </math> sonst. Dann konvergiert <math>\epsilon(\eta)</math> mit <math>\eta </math> gegen 0. Nach dem Satz über die [[Nash-Gleichgewicht]]e des gestörten Spiels ist <math> \hat s_\epsilon \in \hat S(\epsilon(\eta))</math> [[Nash-Gleichgewicht]] von <math>\Gamma_{\epsilon(\eta)}</math>. Nach Definition 2 ist <math>\hat s</math> dann perfektes Gleichgewicht.
 +
 +
 +
== Beispiele ==
 +
 +
 +
== Quellen ==
 +
* 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

Version vom 11. Januar 2009, 22:31 Uhr

Dieser Artikel wird gerade bearbeitet und in Kürze vervollständigt!


Das perfekte Nash-Gleichgewicht, oft auch als trembling-hand-perfektes Gleichgewicht bezeichnet, ist ein von Selten entwickeltes Konzept zur Verfeinerung des Nash-Gleichgewichts. Die Menge der perfekten Gleichgewichte bildet eine Teilmenge der sequentiellen Gleichgewichte und damit auch eine Teilmenge der teilspielperfekten Nash-Gleichgewichte.


Inhaltsverzeichnis

Motivation:

Das perfekte Gleichgewicht berücksichtigt, dass Spieler bei ihrer Strategiewahl mit einer bestimmten, kleinen Wahrscheinlichkeit Fehler begehen, das heißt, jeder Spieler spielt jede Strategie mit einer positiven, wenn auch kleinen Wahrscheinlichkeit. Perfekte Gleichgewichte sollen auch unter einer geringfügigen Änderung des Spiels stabil bleiben.


Definitionen und Sätze

Definition 1: Perfektes Gleichgewicht


Sei ε > 0, sei  \hat \Gamma = (A, \hat S, \hat U) ein Spiel mit einer ausgezeichneten Strategiekombination  \hat s \in \hat S . Dann ist  \hat s ein ε-perfektes Gleichgewicht von  \hat \Gamma , wenn  \hat s vollkommen gemischt ist und für alle Spieler i = 1, ... , m und alle reinen Strategien j = 1, ... , ni gilt: \{u_i (s^j_i, \hat s_{-i}) < u_i (\hat s_i, \hat s_{-i}) \} \Rightarrow \hat s^j_i \leq \epsilon


Definition: Gestörtes Spiel


Ein Spiel  \hat \Gamma_\epsilon = (A, \hat S(\epsilon), \hat U) heißt das dem Spiel  \hat \Gamma = (A, \hat S, \hat U) zugeordnete ε-gestörte Spiel, wenn gilt:  \hat S_i(\epsilon_i) = \{\hat s_i| \hat s^j_i \geq \epsilon^j_i > 0, \sum_{j=1}^{n^i} \hat s^j_i = 1 \} und  \hat S(\epsilon) = \prod_{i=1}^m \hat S_i(\epsilon_i) .


Nash-Gleichgewicht eines gestörten Spiels

Satz

Eine Strategiekombination \hat s aus \hat S_\epsilon ist genau dann Nash-Gleichgewicht des gestörten Spiels  \hat \Gamma_\epsilon, wenn für alle Spieler i = 1, ... , m und alle reinen Strategien j = 1, .... , ni gilt: \{u_i(s^j_i, s_{-i}) < u_i(s_i, s_{-i})\} \Rightarrow \hat s^j_i = \hat \epsilon^j_i .

Beweis

Für gemischte Strategien gilt  \hat s^* = (\hat s^*_i, \hat s^*_{-i}) ist Nash-Gleichgewicht, wenn für alle reinen Strategien  s^j_i der Spieler i = 1, ... , m gilt:  \hat u_i(s^j_i, \hat s^*_{-i}) \leq \hat u_i(\hat s^*) mit j = 1, ... , ni d.h. für  s^j_i \notin \Tau(\hat s) ( \Tau(\hat s) Träger) bzgl. dem ungestörten Spiel  \hat \Gamma gilt  u_i(s^j_i, \hat s_{-i}) < u_i(\hat s_i, \hat s_{-i}) . Im gestörten Spiel muss dann  s^j_i möglichst klein sein, d.h.  s^j_i = \epsilon^j_i .


Definition 2: Perfektes Gleichgewicht


Ein Nash-Gleichgewicht  \hat s eines Spiels  \hat \Gamma = (A, \hat S, \hat U) ist ein perfektes Gleichgewicht, wenn  \hat s Häufungspunkt einer Folge  (s_\epsilon) \epsilon \searrow 0 ist, bei der jedes Folgenglied ein Nash-Gleichgewicht des zugeordneten ε-gestörten Spiels ist.


Äquivalente Aussagen zum perfekten Gleichgewicht

Satz

Sei \hat \Gamma_\epsilon = (A, \hat S, \hat U) ein Spiel mit einer ausgezeichneten Strategiekombination \hat s \in \hat S. Dann sind äquivalent:

  1.  \hat s ist ein perfektes Gleichgewicht
  2.  \hat s ist der Grenzwert einer Folge  (\hat s_\epsilon) \epsilon \searrow 0 , deren Folgenglieder \hat s_\epsilon ε-perfekte Gleichgewichte von \hat \Gamma für alle ε > 0 sind.
  3.  \hat s ist der Grenzwert einer Folge, deren Folgenglieder \hat s_\epsilon Kombinationen von stark gemischten Strategien sind mit der zusätzlichen Eigenschaft, dass  \hat s die beste Antwort für jedes Folgenglied ist.

Beweis

(1) \Rightarrow (2): Sei  \hat s Häufungspunkt einer Folge  (\hat s_\epsilon) \epsilon \searrow 0 nach Definition 2. Wähle ε = maxj,i \epsilon^j_i, dann ist  \hat s ein ε-perfektes Gleichgewicht von \hat \Gamma.
(2) \Rightarrow (3): Sei  (\hat s_\epsilon) \epsilon \searrow 0 eine Folge von ε-perfekten Gleichgewichten des Spiels \hat \Gamma, die gegen  \hat s konvergiert. Seien die ε ausreichend klein. Dann ist nach Definition 1 und dem Satz über die Nash-Gleichgewichte des gestörten Spiels jedes Element des Trägers \Tau(\hat s) eine beste Antwort für jedes (\hat s_\epsilon) und damit auch  \hat s eine beste Antwort für alle Folgenglieder.
(3) \Rightarrow (1): Konvergiere die Folge  (\hat s_\eta) \eta \searrow 0 gegen  \hat s . Wähle \epsilon^j_i(\eta) = s^{\eta,j}_i, falls s^j_i \notin \Tau(s_i) und η sonst. Dann konvergiert ε(η) mit η gegen 0. Nach dem Satz über die Nash-Gleichgewichte des gestörten Spiels ist  \hat s_\epsilon \in \hat S(\epsilon(\eta)) Nash-Gleichgewicht von Γε(η). Nach Definition 2 ist \hat s dann perfektes Gleichgewicht.


Beispiele

Quellen

  • 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.math.lmu.de/wiki/index.php?title=Perfektes_Gleichgewicht
Ansichten
Meine Werkzeuge
Navigation
Werkzeuge