Nash-Gleichgewicht

Aus Wikiludia
Wechseln zu: Navigation, Suche

Das Nash-Gleichgewicht ist ein wichtiger und zentraler Begriff der Spieltheorie. Bei nahezu allen Spielen ist er Untersuchungsgegenstand sowie wichtiges Hilfsmittel zum Finden einer Lösung des jeweiligen Spiels.

Inhaltsverzeichnis

Definitionen

Nash-Gleichgewicht in reinen Strategien

Definition: Unter einem Nash-Gleichgewicht eines Spiels in Normalform, Γ = (M,S,u), versteht man ein Strategieprofil s^* = (s_1^*,...,s_n^*) \in S , bei dem jeder Spieler i \in M eine Strategie s_i^* gewählt hat, die insofern optimal ist, als es unter der Voraussetzung, dass die anderen Spieler an ihrer Strategie festhalten, für ihn keine bessere Strategie gibt. Für die Auszahlungsfunktionen gilt also

\forall i \in M \;  \forall s_i \in S: \quad u_i(s_i^*,s_{-i}^*) \geq u_i(s_i,s_{-i}^*).

Zur Existenz von Nash-Gleichgewichten und zur Eindeutigkeit von Nash-Gleichgewichten gibt es allgemeine Sätze.

Nash-Gleichgewicht in gemischten Strategien

Lässt man im Falle von endlichen Strategiemengen Si auch zu, dass die Spieler über ihre Strategien randomisieren, d.h. nicht nur eine (sogenannte reine) Strategie aus Si wählen, sondern beliebige (diskrete) Wahrscheinlichkeitsverteilungen σi über ihre Strategiemenge Si spielen können, so kommt man zu dem Begriff der gemischten Erweiterung des vorgegebenen Normalformenspiels.

Definition: Ein Nash-Gleichgewicht in gemischten Strategien \sigma = (\sigma_1^*,...,\sigma_n^*) ist dann ein Nash-Gleichgewicht der gemischten Erweiterung. Das bedeutet:

\forall i \in M \; \forall \sigma_i \in \Delta S_i: \quad u_i(\sigma_i^*, \sigma_{-i}^*)   \geq u_i(\sigma_i,\sigma_{-i}^*)

Dazu äquivalent:

\forall i \in M \; \forall s_i \in S_i: \quad u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(s_i,\sigma_{-i}^*)

Bestimmung von Nash-Gleichgewichten

Ein einfacher Algorithmus zur Identifizierung von Nash-Gleichgewichten

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

  1. 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.
  2. Führe 1. für alle Spieler durch.

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

Beweis: Der vorgestellte Algorithmus zeichnet jeweils die besten Antworten auf eine (Gegen-) Strategie aus. Diejenigen Strategiekombinationen, in denen alle Auszahlungen markiert sind, sind dann genau die Strategiekombinationen, die beste Antwort auf sich selbst sind, und das sind gerade die Nash-Gleichgewichte.

Bemerkung: Dies ist kein Existenzbeweis, es wird lediglich bewiesen, dass in endlichen Spielen in Normalform die Nashgleichgewichte in reinen Strategien mit diesem Algorithmus gefunden werden können. Er funktioniert also nur dann mit einem positiven Resultat, wenn es überhaupt ein Nash-Gleichgewicht in reinen Strategien gibt. Er liefert allerdings auch das Resultat, dass es kein Nash-Gleichgewicht in reinen Strategien gibt, falls das zutrifft.

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

Beispiel:

Sei folgendes Spiel in Normalform gegeben:

Spieler 2
Rechts Mitte Links
Spieler 1 oben (2,0) (1,1) (4,2)
mitte (1,4) (1,1) (2,3)
unten (1,3) (0,2) (3,0)

Dann funktioniert der Algorithmus wie folgt:

  1. i=1, gegeben Spieler 2 spielt Rechts ist oben optimal: markiere die 2; gegeben Spieler 2 spielt Mitte ist oben und mitte optimal: markiere die beiden 1en; gegeben Spieler 2 spielt Links ist oben optimal: markiere die 4;
  2. i=2, gegeben Spieler 1 spielt oben ist Links optimal: markiere die 2; gegeben Spieler 1 spielt mitte ist Rechts optimal: markiere die 4; gegeben Spieler 1 spielt unten ist Rechts 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.

Verfahren zur Berechnung von Nash-Gleichgewichten in gemischten Strategien

Um Nash-Gleichgewichte in gemischten Strategien zu finden ist ein etwas höherer rechnerischer Aufwand nötig. Algorithmen zum finden von Nash-Gleichgewichten in gemischten Strategien findet man in Nash-Gleichgewicht:Berechnung in gemischten Strategien

Berechnung von symmetrischen Nash-Gleichgewichten in symmetrischen Spielen

Symmetrische Spiele sind die Basispiele der evolutorischen Spieltheorie. Ein sehr einfaches Berechnungsverfahren zur Bestimmung von voll gemischten und symmetrischen Nash-Gleichgewichten findet man in Nash-Gleichgewicht:Berechnung bei symmetrischen Spielen.

Interpretationen des Nash-Gleichgewichts

In der Literatur werden mehrere Erklärungen geliefert, wie das Nash-Gleichgewicht interpretiert werden könnte (s. bspw. Dutta (2000) oder Mas-Colell et al. (1995)):

1. Spielvorhersage

Ein Nash-Gleichgewicht kann insofern als Spielvorhersage betrachtet werden, dass es ein Strategienprofil darstellt, von dem kein Spieler einen Anreiz hat abzuweichen, wenn es vorgeschlagen wurde.

Diese Interpretation führt zu Problemen, die in Übung 1 thematisiert sind.

2. Kommunikation vor dem Spiel

Falls die Spieler vor dem Spiel kommunizieren könnten, ist es natürlich anzunehmen, dass sie sich auf ein Nash-Gleichgewicht koordinieren. Auf Strategien, die kein Nash-Gleichgewicht sind, können sich die Spieler nicht glaubhaft koordinieren, weil (mind.) ein Spieler durch Abweichen eine höhere Auszahlung erhalten könnte.

3. Focal Point (Schelling, 1960, s. Literaturdatenbank)

Ein Nash-Gleichgewicht als Strategientupel ist durch seine Definition von anderen Strategientupeln ausgezeichnet.

4. Versuch und Irrtum

Falls ein Spieler wahrnimmt, dass er keine beste-Antwort gespielt hat, wird er im nächsten Spiel eventuell seine Strategie ändern. Dieser Prozess würde nur in einem Nash-Gleichgewicht nicht fortgesetzt. (Achtung: hier wird nicht behauptet, dass durch Versuch und Irrtum letztendlich ein Nash-Gleichgewicht erreicht wird; der Prozess muss nicht konvergieren).

Verfeinerungen des Nashgleichgewichts

Siehe dazu den Hauptartikel: Verfeinerungen des Nash-Gleichgewichts

Links

Wikipedia-Artikel "Nash-Gleichgewicht"

Meine Werkzeuge