Perfektes Gleichgewicht

Aus Wikiludia
Wechseln zu: Navigation, Suche

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 Wahrscheinlichkeit. Perfekte Gleichgewichte sollen auch unter einer geringfügigen Änderung des Spiels stabil bleiben.


Definitionen

Im Folgenden beschränken wir uns auf endliche Spiele in Normalform.

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


Typischerweise ist ε hier die fälschliche Abweichung von einer Strategie, d.h. ε liegt üblicherweise nahe 0. Um zu verdeutlichen, dass es sich hier um Abweichungen handelt, spricht man auch von einem gestörten Spiel:

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) .


Die Abweichung der einzelnen Strategien werden dagegen mit dem Begriff der Perturbation umschrieben:

Definition: Perturbation


Werden verschiedene Strategien mit "zitternder Hand" zu unterschiedlichen, geringen Wahrscheinlichkeiten (also "fälschlich") gespielt, spricht man von einer Perturbation; werden sie zu mit einer gleichen, geringen Wahrscheinlichkeit gespielt, von einer uniformen Perturbation.


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 .


Diese Eigenschaft erlaubt eine weitere, einfachere Definition des perfekten Gleichgewichts:

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.

Eigenschaften perfekter Gleichgewichte

Ä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.


Satz: Existenz

Satz

Jede gemischte Erweiterung eines endlichen Spieles besitzt ein perfektes Gleichgewicht.

Beweis

Da (\hat s_\epsilon)_{\epsilon \searrow 0} eine Folge in der kompakten Menge S ist, hat sie mindestens einen Häufungspunkt  \hat s \in \hat S . Dann existiert zu einem ausgewählten Häufungspunkt  \hat s* eine Teilfolge t * der Folge (\hat s_\epsilon)_{\epsilon \searrow 0} , die gegen  \hat s* konvergiert. Dann gilt  u_i(t^*_i, t^*_{-i}) \geq u_i(\hat s_i, t^*_{-i}) \forall \hat s_i \in \hat S_i(t_{\epsilon}), i = 1, ... , m . Mit  t \rightarrow \infty folgt wegen der Stetigkeit der Auszahlung  u_i: u_i(\hat s^*_i, \hat s^*_{-i}) \geq u_i(\hat s_i, \hat s^*_{-i}) \forall \hat s_i \in \hat S_i(t_{\epsilon}), i = 1, ... , m , d.h.  \hat s^*_i ist Nash-Gleichgewicht des Spiels  \hat \Gamma .


Beispiel

Sei folgendes Spiel gegeben:


A B C
1 (1,1) (0,0) (-6,-4)
2 (0,0) (0,0) (-4,-4)
3 (-4,-6) (-4,-4) (-4,-4)

Offensichtlich hat dieses Spiel die drei Nash-Gleichgewichte (1,A), (2,B) und (3,C). Welche dieser Gleichgewichte sind auch perfekte Gleichgewichte?

Betrachten wir das Nash-Gleichgewicht (3,C): Angenommen, Spieler 2 spielt die Strategien A und B mit einer Fehlerwahrscheinlichkeit von εA und εB, so verbleibt für die Option C die Wahrscheinlichkeit 1 − εA − εB. Dann ist es für Spieler 1 günstiger, die Startegie 2 statt 3 zu spielen, denn sein Erwartungsnutzen ist dann für die Option 2 größer als für Option 3: u1(2) = − 4 * (1 − εA − εB) > − 4 = u1(3) für εi > 0, i = {A,B}. Analog ergibt sich für Spieler 2 u2(B) = − 4 * (1 − ε1 − ε2) > − 4 = u2(C) für εi > 0 für die Strategie i von Spieler 1, i = {1,2}. Damit ist das Nash-Gleichgewicht (3,C) offensichtlich nicht perfekt.

Das Nash-Gleichgewicht (1,A) dagegen ist ein perfektes Gleichgewicht: Nehmen wir hier wiederum eine Perturbation der Strategien von Spieler 2 mit Fehlerwahrscheinlichkeiten εB und εC für das fälschliche Spiel von B bzw. C. Dann ergibt sich für Spieler 1 u1(2) = − 4 * εC < (1 − εB − εC) − 6 = 1 − εB − 7 * εC = u1(1) für εi nahe 0, i = {B,C}. Damit erfüllt (1,A) die Bedingung der Perfektheit.

Für das Nash-Gleichgewicht (2,B) ergibt sich folgende Situation: Spieler 2 spiele A mit Fehlerwahrscheinlichkeit εA und C mit Wahrscheinlichkeit εC. Daraus folgt:  u_1(1) = \epsilon_A - 6*\epsilon_B) \leq 0 - 4*\epsilon_C = u_1(2) , das heißt  \epsilon_A \leq 2*\epsilon_C (\epsilon_i > 0 , i = {A,C}). Damit wäre (2,B) ein perfektes Gleichgewicht, wenn die Fehlerwahrscheinlichkeit für die Option A doppelt so groß ist wie für Option C. Da die Fehler bliebig klein werden können, finden sich immer entsprechende Fehlerwahrscheinlichkeiten. Um diese Problematik zu umgehen, greift man in der Regel auf uniforme Perturbationen zurück, bei denen die Fehlerwahrscheinlichkeiten stets gleich groß sind. Unter einer uniformen Perturbation ist (2,B) also nicht perfekt.


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