Nash-Gleichgewicht
aus Wikipedia, der freien Enzyklopädie
Das Nash-Gleichgewicht, teils auch (wie im englischen) Nash-Equilibrium genannt, ist ein zentraler Begriff der mathematischen Spieltheorie. Es beschreibt in nicht-kooperativen Spielen einen Zustand eines strategischen Gleichgewichts, von dem ausgehend kein einzelner Spieler für sich einen Vorteil erzielen kann, indem er einseitig von seiner Strategie abweicht. Es ist ein grundlegendes Lösungskonzept der Spieltheorie. Definition und Existenzbeweis des Nash-Gleichgewichts gehen auf die 1950 veröffentlichte Dissertation des Mathematikers John Forbes Nash Jr. zurück.
Inhaltsverzeichnis |
[Bearbeiten] Definition
[Bearbeiten] Reine Strategien
Unter einem Nash-Gleichgewicht in reinen Strategien versteht man ein Strategieprofil 
, bei dem die Strategie jedes Spielers i die beste Antwort auf die gewählten Strategien der anderen Spieler ist.
Unter der Voraussetzung, dass alle anderen Spieler an ihren gewählten Strategien festhalten, gibt es für Spieler i also kein 
, das dem Spieler i eine höhere Auszahlung verspricht:
.
Man sagt auch, dass Spieler i seine Auszahlung durch ein einseitiges Abweichen nicht verbessern kann. Ein Nash-Gleichgewicht zeichnet sich damit dadurch aus, dass sich kein Spieler durch eine einseitige Änderung seiner Strategie verbessern kann.
[Bearbeiten] 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 si beschrieben werden, wobei si,j die Wahrscheinlichkeit ist, dass die Strategie 
gewählt wird.
Ist die gemischte Strategie 
ein Nash-Gleichgewicht, gilt:
.
[Bearbeiten] Existenz eines Nash-Gleichgewichtes
Mit Hilfe des Fixpunktsatzes von Kakutani kann man zeigen, dass mindestens ein Nash-Gleichgewicht existieren muss, wenn folgende Voraussetzungen erfüllt sind:
sind 
sind 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 Si ü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.
[Bearbeiten] 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.
[Bearbeiten] 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 ("Oben ist beste Antwort auf Rechts")
- 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 einzige Nash-Gleichgewicht ist also die Strategie die zur Auszahlung 4, 2 führt: (oben,links).
Falls zu überprüfen ist, ob ein Tupel von gemischten Strategien ein Nash-Gleichgewicht ist, funktioniert obiger Algorithmus nur bedingt, da eine unendliche Anzahl an gemischten Strategien überprüft werden müsste.
Mit dieser Methode lassen sich übrigens auch strikt dominierte Strategien identifizieren: das sind genau die, bei denen keine Auszahlung markiert wurde.
[Bearbeiten] Ein Algorithmus zur Identifizierung von Nash-Gleichgewichten in gemischten Strategien
Bei der Identifizierung von Nash-Gleichgewichten in gemischten Strategien ist es hilfreich, diejenigen gemischten Strategien zu identifizieren, die den Gegenspieler indifferent zwischen seinen Handlungsalternativen machen. Ist solch eine Strategie gefunden, sind alle Handlungen des Gegners beste Antworten. Treffen solche gemischten Strategien aufeinander, so sind sie folglich wechselseitig beste Antworten, es besteht kein Grund zum einseitigen Abweichen, und die gemischten Strategien bilden ein Nash-Gleichgewicht.
[Bearbeiten] Beispiel
Sei der Kampf der Geschlechter mit folgenden Auszahlungen versehen:
| Spieler 2 | |||
| Oper | Fußball | ||
|---|---|---|---|
| Spieler 1 | Oper | 2 , 5 | 0 , 0 |
| Fußball | 0, 0 | 5, 2 | |
Dann funktioniert der Algorithmus wie folgt:
Spielt Spieler 2 mit einer Wahrscheinlichkeit von q Oper und mit der Gegenwahrscheinlichkeit von (1-q) Fußball, so ergeben sich für Spieler 1 folgende Erwartungsnutzen:
- EU1(O) = 2q
- EU2(F) = 5-5q
Spieler 1 ist also indifferent zwischen seinen beiden Strategien, wenn 2q = 5-5q, also wenn 7q = 5 und somit q = 5/7 gilt.
Für Spieler 2 lässt sich analog ermitteln, dass er indifferent ist, wenn Spieler 1 mit einer Wahrscheinlichkeit von p=2/7 Oper und mit (1-p)=5/7 Fußball spielt.
Da auf diese beiden Strategien alle Antworten des Gegenspielers beste Antworten sind, sind sie speziell jeweils auch wechselseitig beste Antworten. Somit kann [(2/7;5/7),(5/7;2/7)] als Nash-Gleichgewicht in gemischten Strategien identifiziert werden.
[Bearbeiten] 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.
[Bearbeiten] Praxisbeispiel
Denkbar ist eine Situation, bei der mehrere Anbieter in einem Markt die Preise ihrer konkurrierenden Produkte so weit gesenkt haben, dass sie gerade noch wirtschaftlich arbeiten. Für den einzelnen Anbieter wäre eine ausweichende Strategie nicht möglich: Senkt er seinen Preis, um seinen Absatz zu erhöhen, fällt er unter die Wirtschaftlichkeit; erhöht er ihn, werden die Käufer auf die Konkurrenzprodukte ausweichen. Ein Ausweg kann nun etwa darin bestehen, (beinahe) gleichzeitig mit einem Konkurrenten eine Produktinnovation einzuführen, um damit einen höheren Preis zu begründen. Unter dem Begriff Coopetition wurden derartige Szenarien mitte der 1990er breiter diskutiert, wobei vor allem die Auseinandersetzung zwischen den US-amerikanischen Fluglinien als markantes Beispiel zitiert wurde.
