Existenz von Nash-Gleichgewichten

Aus Wikiludia
Wechseln zu: Navigation, Suche
Der folgende Satz formuliert sehr allgemeine Voraussetzungen, unter denen ein Nash-Gleichgewicht existiert.

Formulierung des Satzes:


Satz von Nash (1. Version): Gegeben sei ein Spiel L mit folgenden Eigenschaften:

  • für alle Spieler i ist die Strategiemenge Si eine kompakte (beschränkt und abgeschlossen) und konvexe (jede Verbindungslinie zwischen zwei Elementen der Menge liegt in der Menge) Teilmenge in einem geeigneten  \mathbb R^{k_i} .
  • für alle Spieler i ist ui stetig (und damit beschränkt) und quasi-konkav in si

Dann existiert ein Nash-Gleichgewicht für L.

Hierbei kann der Strategieraum z.B. ein Intervall oder ein ki-dimensionaler abgeschlosser Quader sein.

Im Spezialfall für endliche Spiele in Normalform mit Auszahlungsfunktion wie in der Vorlesung, kann der Satz auch folgendermaßen formuliert werden:


Satz von Nash (2. Version):In jedem endlichen Spiel in Normalform gibt es ein Nash-Gleichgewicht (in gemischten Strategien).


Beweis der 2. Version:

Seien S_i=\{s_1,\ldots s_{m_i}\} bzw. Δi die Mengen der reinen bzw. gemischten Strategien des Spielers i, und S=S_1\times \ldots \times S_N und \Delta=\Delta_1\times\ldots\times\Delta_N.
Ein Nash-Gleichgewicht \sigma^*=(\sigma_1^*,\ldots \sigma_N^*) ist dadurch festgelegt, dass die Strategie \sigma_i^* eine beste Antwort auf \sigma_{-i}^* für alle Spieler i ist.
Wir definieren also für jeden Spieler i die Abbildung:
b_i:\ \Delta\rightarrow \mathcal{P}(\Delta_{i}), \sigma \mapsto \{ \tau \in \Delta_{i}: \tau ist beste Antwort auf σi}
Da Δi abgeschlossen ist, existiert zu jeder stetigen Funktion auf Δ ein Maximum, also insbes. zu jeder Strategie eine beste Antwort. Somit ist b_i(\Delta)\neq \emptyset.
Wir erhalten damit eine Korrespondenz b=(b_1,\ldots,b_N):\ \Delta\rightarrow \Delta.

Behauptung 1: Fixpunkte von b sind Nash-Gleichgewichte.
Sei x\in b(x), dann ist für alle i x_i\in b_i(x), also xi eine beste Antwort auf xi. Da das für alle Spieler i gilt, ist x ein Nash-Gleichgewicht.

Behauptung 2: Die Voraussetzungen des Satzes von Kakutani sind erfüllt.
Es gilt nämlich:

  • Δ ist kompakt und konvex (klar ist jede Linearkombination (mit positiven Gewichten deren Summe 1 ist) wieder eine gemischte Strategie, und, da die Gewichte der Strategien auch =1 sein können, ist die Menge abgeschlossen. Beschränktheit ist klar.)
  • Die Korrespondenz b ist abgeschlossen:
    Seien (x^{(n)})_{n\in\mathbb{N}} und (y^{(n)})_{n\in\mathbb{N}} Folgen in Δ mit x^{(n)}\rightarrow x und y^{(n)}\rightarrow y so dass für alle n gilt: x^{(n)}\in b(y^{(n)}). Wir m"ussen zeigen: x\in b(y), d.h. für alle i ist xi beste Antwort auf yi.
    Für alle t\in\Delta_igilt:
    u_i(x_i^{(n)}, y_{-i}^{(n)})\geq u_i(t, y_{-i}^{(n)})
    ui ist stetig auf Δ, denn in einer konvergenten Folge von Strategie, konvergieren die Gewichte und ui hängt linear von den Gewichten ab. Demnach können wir die Limesbildung mit der Funktion vertauschen und erhalten:
    u_i(x_i, y_{-i})\geq u_i(t, y_{-i})
    Dies wiederum bedeutet, dass xi beste Antwort auf yi, also x\in b(y)
  • Für alle x\in\Delta ist b(x) konvex:
    Seien also t_1, t_2\in b_(x), und \delta\in (0,1). Für y = δt1 + (1 − δ)t2 gilt dann:
    u_i(y_i,x_{-i})=\delta u_i((t_1)_i,x_{-i})+(1-\delta) u_i((t_2)_i,x_{-i})\geq \delta u_i(z_i,x_{-i})+(1-\delta)u_i(z_i,x_{-i})=u_i(z_i,x_{-i})\ \ \ \forall z_i\in \Delta_i
    Da dies für alle i gilt, ist y\in b(x) und damit ist die Menge konvex.

Damit folgt aus dem Fixpunktsatz von Kakutani, dass die Korrespondenz mind. einen Fixpunkt besitzt und dieser ist nach Behauptung 1 das gesuchte Nash-Gleichgewicht.


Historisches:

John Nash bewies 1950 für endliche Spiele (endliche Spielerzahl und endliche Menge von reinen Strategien) die Existenz von Nash-Gleichgewichten in gemischten Strategien. Sein Beweis verwendet den Fixpunktsatz von Kakutani. Ein Jahr später erscheint Nashs zweiter Beweis der Existenz von Nash-Gleichgewichten. Dieser Beweis verwendet lediglich den Brouwerschen Fixpunktsatz und wurde daher von Nash als erhebliche Verbesserung angesehen.

Eine ausführliche Darstellung von Nashs zweitem Beweis und dessen Hintergründen findet sich hier:

Nashs zweiter Beweis der Existenz von Nash-Gleichgewichten



Link:

Projekt: Computerprogramm zur Berechnung von Nash-Gleichgewichten
Ansichten
Meine Werkzeuge
Navigation
Werkzeuge