Nash-Gleichgewicht

Das Nash-Gleichgewicht ist ein zentraler Begriff der mathematischen Spieltheorie. Es beschreibt in Spielen einen Zustand eines strategischen Gleichgewichts, von dem ausgehend kein einzelner Spieler für sich einen Vorteil erzielen kann, indem er allein seine Strategie verändert. Definition und Existenzbeweis des Nash-Gleichgewichts gehen auf die 1950 veröffentlichte Dissertation des Mathematikers John Forbes Nash Jr. zurück.

Inhaltsverzeichnis

1 Definition

1.1 Reine Strategien
1.2 Gemischte Strategien

2 Existenz eines Nash-Gleichgewichtes

3 Ein einfacher Algorithmus zur Identifizierung von Nash-Gleichgewichten

4 Beispiel

5 Spezialfälle

Definition

Reine Strategien

Unter einem Nash-Gleichgewicht in reinen Strategien versteht man ein Strategieprofil $\sigma^* = (\sigma_1^*,...,\sigma_n^*) \in \Sigma$ , bei der die Strategie jedes Spielers $i$ die beste Antwort auf die gewählten Strategien der anderen Spieler ist.

Unter der der Voraussetzung, dass alle anderen Spieler an ihren gewählten Strategien festhalten, gibt es für Spieler $i$ also kein $\sigma_i \neq \sigma_i^*$ , das dem Spieler $i$ eine höhere Auszahlung verspricht:

$u_i(\sigma_1^*,\ldots,\sigma_i^*,\ldots, \sigma_n^*) \geq u_i(\sigma_1^*,\ldots,\sigma_i,\ldots, \sigma_n^*)\ \forall \sigma_i \in \Sigma_i$ .

Man sagt auch, dass Spieler $i$ seine Auszahlung durch ein einseitiges Abweichen nicht verbessern kann.

Gemischte Strategien

In manchen Fällen lässt man zu, dass die Spieler sich nicht auf eine bestimmte Strategie festlegen, sondern auf eine Wahrscheinlichkeitsverteilung, mit der die $σ i$ aus $Σ i$ zufällig gezogen werden. Ist $Σ i$ endlich oder zumindest abzählbar, so kann die Wahrscheinlichkeitsverteilung durch einen Vektor $s i$ beschreiben, wobei $s i, j$ die Wahrscheinlichkeit ist, dass die Strategie $\sigma_{i,j} \in \Sigma_i$ gewählt wird.

Ist die gemischte Strategie $s = (s_1^*,...,s_n^*)$ ein Nash-Gleichgewicht, gilt:

$u_i(s_1^*,\ldots,s_i^*,\ldots, s_n^*) \geq u_i(s_1^*,\ldots,s_i,\ldots, s_n^*)\ \forall s_i \in S_i$ .

Existenz eines Nash-Gleichgewichtes

Mit Hilfe des Fixpunktsatzes von Kakutani kann man zeigen, dass unter bestimmten Voraussetzungen mindestens ein Nash-Gleichgewicht existieren muss:

Die Auszahlungsfunktionen $H_i(\sigma_1,\ldots,\sigma_n)$ sind stetig.
Die Strategiemengen $\Sigma_1,\ldots,\Sigma_n$ sind konvex und kompakt.

Häufig werden Spiele so konstruiert, dass die $Σ i$ endlich sind, endliche Mengen können jedoch nicht konvex sein. Allerdings ist die Menge der gemischten Strategien $S i$ über $Σ i$ kompakt und konvex. Während die Existenz eines Nash-Gleichgewichtes in reinen Strategien also nicht garantiert werden kann, existiert in einem Spiel im Allgemeinen mindestens ein Nash-Gleichgewicht in gemischten Strategien.

Ein einfacher Algorithmus zur Identifizierung von Nash-Gleichgewichten

Liegt ein Spiel in strategischer Form vor, so lassen sich alle Nash-Gleichgewichte in reinen Strategien durch folgenden Algorithmus bestimmen:

Optimiere die Entscheidung von Spieler i=1,...,n bei (beliebig) fixierten Strategien aller anderen Spieler: Markiere die unter diesen Umständen erreichbaren höchsten Auszahlungen für Spieler i. Wiederhole dies für alle möglichen Strategiekombinationen der anderen Spieler.
Führe 1. für alle Spieler durch.

Dann sind genau die Strategienkombinationen Nash-Gleichgewichte, bei denen alle Auszahlungen markiert sind.

Diese Vorgehensweise eignet sich nur für eine geringe Anzahl von Spielern und Strategien.

Beispiel

Sei folgendes Spiel in Normalform gegeben:

		Spieler 2
		links	mitte	rechts
Spieler 1	oben	4 , 2	1 , 1	2 , 0
	mitte	2 , 3	1 , 1	1 , 4
	unten	3 , 0	0 , 2	1 , 3

Dann funktioniert der Algorithmus wie folgt:

i=1:
- gegeben Spieler 2 spielt Rechts: Für Spieler 1 ist oben optimal - markiere die 2
- gegeben Spieler 2 spielt Mitte: oben und mitte ist optimal - markiere die beiden 1en
- gegeben Spieler 2 spielt Links: oben ist optimal - markiere die 4
i=2:
- gegeben Spieler 1 spielt oben: Für Spieler 2 ist Links optimal - markiere die 2
- gegeben Spieler 1 spielt mitte: Rechts ist optimal - markiere die 4
- gegeben Spieler 1 spielt unten: Rechts ist optimal - markiere die 3

Das eindeutige Nash-Gleichgewicht ist also die Strategie die zur Auszahlung 4 , 2 führt: (T,R).

Falls zu überprüfen ist, ob ein Tupel von gemischten Strategien ein Nash-Gleichgewicht ist, funktioniert obiger Algorithmus ebenfalls (es müssen nur die reinen Strategien der anderen Spieler in Schritt 1 variiert werden, da beliebige Wahrscheinlichkeitsverteilungen über diese nicht zu höheren Auszahlungen führen können).

Mit dieser Methode lassen sich übrigens auch strikt dominierte Strategien identifizieren: das sind genau die, bei denen keine Auszahlung markiert wurde.

Spezialfälle

Ein Spezialfall des Nash-Gleichgewichts ist der für Zwei-Personen-Nullsummenspiele gültige Minimax-Satz, der 1928 durch John von Neumann bewiesen wurde. Anders als im allgemeinen Fall entspricht dabei jedem Spiel ein eindeutiger Auszahlungsvektor $(v, - v)$ , wobei $v$ der Wert des Spieles heißt.

Für Zwei-Personen-Nullsummenspiele mit perfekter Information, zu denen Brettspiele wie Schach und Mühle gehören, existiert sogar immer ein Minimax-Gleichgewicht in reinen Strategien, das mit dem Minimax-Algorithmus rekursiv bestimmt werden kann. Dieser Satz wurde bereits 1912 von Ernst Zermelo bewiesen.