Das Nash-Gleichgewicht, teils auch (wie im Englischen) Nash-Equilibrium genannt, ist ein zentraler Begriff der mathematischen Spieltheorie. Es beschreibt in nicht-kooperativen Spielen eine Kombination von Strategien, eine für jeden Spieler, von der ausgehend kein einzelner Spieler für sich einen Vorteil erzielen kann, indem er einseitig von seiner Strategie abweicht. In einem Nash-Gleichgewicht bereut daher kein Spieler seine Strategiewahl. Die Strategien der Spieler sind wechselseitig beste Antworten. 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[1].
Das wesentliche Ziel der mathematischen Spieltheorie ist es, für Konfliktsituationen rationale Entscheidungen zu charakterisieren und zu bestimmen. Die Schwierigkeit dabei ist, dass keiner der Entscheider („Spieler“) weiß, welche Pläne die anderen Spieler verfolgen und wie sie sich dementsprechend entscheiden werden. Damit ist es für einen einzelnen Spieler völlig ungewiss, wie sich seine konkrete Entscheidung für einen Handlungsplan („Strategie“) auswirken wird.
Dem Nash-Gleichgewicht liegt nun die folgende Idee zugrunde: Man geht von allen möglichen Kombinationen aus, die für jeden Spieler eine Strategie beinhalten. Eine solche Strategie-Kombination heißt Nash-Gleichgewicht, wenn ihr eine gewisse Stabilität unterstellt werden kann aufgrund der Tatsache, dass kein einzelner Spieler einen Anreiz besitzt, von seiner Strategie abzuweichen. Formal bedeutet dies, dass sich die Auszahlung an denjenigen Spieler, der seine Strategie als Einzelner ändert, aufgrund dieser Änderung nicht erhöhen darf.
Es bezeichne 
die Menge der Strategien (Handlungsalternativen) des i-ten Spielers und 
das kartesische Produkt dieser Strategienmengen.
Unter einem Nash-Gleichgewicht in reinen Strategien versteht man ein Strategieprofil 
, bei dem die Strategie jedes Spielers 
eine beste Antwort auf die gewählten Strategien der anderen Spieler ist. Wenn alle anderen Spieler an ihren gewählten Strategien festhalten, so ist das Nash-Gleichgewicht bei reinen Strategien formal dadurch gekennzeichnet, dass es für Spieler also kein 
gibt, das dem Spieler eine höhere Auszahlung verspricht:
.Man sagt auch, dass Spieler 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.
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 
aus zufällig gezogen werden. Ist endlich oder zumindest abzählbar, so kann die Wahrscheinlichkeitsverteilung durch einen Vektor 
beschrieben werden, wobei 
die Wahrscheinlichkeit ist, dass die Strategie 
gewählt wird.
Die gemischte Strategie 
ist genau dann ein Nash-Gleichgewicht, wenn kein Spieler durch alleiniges Abweichen eine bessere Auszahlung erreichen kann, das heißt genau dann, wenn
.Mit Hilfe des Fixpunktsatzes von Kakutani kann man zeigen, dass mindestens ein Nash-Gleichgewicht existieren muss, wenn folgende Voraussetzungen erfüllt sind:
sind stetig und quasikonkav in .
sind konvex und kompakt.Häufig werden Spiele so konstruiert, dass die endlich sind, endliche Mengen können jedoch nicht konvex sein. Allerdings ist die Menge der gemischten Strategien 
über kompakt und konvex und die entsprechende Erweiterung von 
multilinear. Während die Existenz eines Nash-Gleichgewichtes in reinen Strategien also nicht garantiert werden kann, existiert mindestens ein Nash-Gleichgewicht bei einem Spiel in gemischten Strategien.
Liegt ein Spiel in strategischer Form vor, so lassen sich alle Nash-Gleichgewichte in reinen Strategien durch folgenden Algorithmus bestimmen:
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.
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:
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.
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.
Betrachten Sie die folgende Bi-Matrix:
| Spieler 2 | |||
| Oper | Fußball | ||
|---|---|---|---|
| Spieler 1 | Oper | 3, 2 | 2, 3 |
| Fußball | 1, 3 | 4, 1 | |
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:
Spieler 1 ist also indifferent zwischen seinen beiden Strategien, wenn
Für Spieler 2 lässt sich analog ermitteln, dass er indifferent ist, wenn Spieler 1 mit einer Wahrscheinlichkeit von p = 2/3 Oper und mit (1-p) = 1/3 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/3;1/3),(1/2;1/2)] als Nash-Gleichgewicht in gemischten Strategien identifiziert werden.
Ein Spezialfall von Nashs Existenzsatz für Gleichgewichte ist das für Zwei-Personen-Nullsummenspiele gültige Min-Max-Theorem, das 1928 durch John von Neumann bewiesen wurde. Anders als im allgemeinen Fall entspricht dabei jedem Spiel ein eindeutiger Auszahlungsvektor 
, wobei 
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.
In der Marktwirtschaft ist eine Situation denkbar, 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 und sein Gewinn sinkt ebenfalls. 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.
Ein weiteres Beispiel ist das Gefangenendilemma, ein spieltheoretisches Problem, bei dem genau ein Nash-Gleichgewicht existiert.
Hierzu stelle man sich folgende Situation vor: Zwei Gefangene werden verdächtigt, gemeinsam eine Straftat begangen zu haben. Die Höchststrafe für das Verbrechen beträgt fünf Jahre Haft. Beiden Gefangenen wird nun ein Handel angeboten, worüber auch beide informiert sind. Wenn einer allein gesteht und somit seinen Partner mitbelastet, kommt er ohne Strafe davon – der andere muss die vollen fünf Jahre absitzen. Entscheiden sich beide zu schweigen, bleiben nur Indizienbeweise, die aber ausreichen, um beide für zwei Jahre einzusperren. Gestehen aber beide die Tat, erwartet jeden eine Gefängnisstrafe von vier Jahren. Nun werden die Gefangenen unabhängig voneinander befragt. Weder vor noch während der Befragung haben die beiden die Möglichkeit, sich untereinander abzusprechen.
Zwar ist es optimal für die beiden Gefangenen, wenn sie beide schweigen. Diese Strategie-Kombination ist aber nicht stabil, weil sich ein einzelner Gefangener durch ein Geständnis einen Vorteil für sich verschaffen kann. Stabil im Sinne eines Nash-Gleichgewichtes ist die Strategie-Kombination, bei der beide Gefangene gestehen: Dann kann sich kein einzelner durch ein Schweigen einen Vorteil verschaffen, so dass ein Nash-Gleichgewicht vorliegt. Dieses Nash-Gleichgewicht liefert aber für beide Gefangene schlechtere Ergebnisse als das beidseitige Schweigen, das nur durch Kooperation fixierbar ist.
Dieser Artikel basiert auf dem Artikel Nash-Gleichgewicht aus der freien Enzyklopädie Wikipedia und ist unter der Lizenz Creative Commons Attribution/Share Alike verfügbar. Zusätzliche Bedingungen können anwendbar sein. In der Wikipedia ist eine Liste der Autoren verfügbar. |
Wetter
