Unter einem Nash-Gleichgewicht in reinen Strategien versteht man ein Strategieprofil s* = (s1*,...,sn*) ∈ S, bei dem jeder Spieler i eine Strategie si* gewählt hat, die insofern die beste ist, als es unter der Voraussetzung, dass die anderen Spieler an ihrer Strategie festhalten, für ihn keine bessere Strategie gibt. Für die Auszahlungsfunktion gilt also
ui(si*,s-i*) ≥ ui(si,s-i*) ∀ si ∈ Si.
Zur Existenz von Nash-Gleichgewichten und Eindeutigkeit von Nash-Gleichgewichten gibt es allgemeine Sätze.
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 wählen, sondern beliebige (diskrete) Wahrscheinlichkeitsverteilungen σi über ihre Strategiemenge Si spielen können, so ist ein Nash-Gleichgewicht in gemischten Strategien σ = (σ1*,...,σn*) gefunden, wenn für alle Spieler i die folgenden Ungleichungen gelten:
ui( σi*,σ-i*) ≥ ui( si,σ-i*) ∀ si ∈ Si
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: 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 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
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 4; 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 deinen keine Auszahlung markiert wurde.