Quelltext der Seite Nash-Gleichgewicht

[[Datei:John f nash 20061102 3.jpg|mini|John F. Nash (2006)]]
Das '''Nash-Gleichgewicht''' (abgekürzt als '''NGG''' oder '''NGGW''') ist ein zentraler Begriff der [[Spieltheorie]]. Es beschreibt in [[Nichtkooperative Spieltheorie|nicht-kooperativen Spielen]] eine Kombination von [[Strategie (Spieltheorie)|Strategien]], wobei jeder Spieler genau eine Strategie wählt, von der aus es für keinen Spieler sinnvoll ist, von seiner gewählten Strategie als einziger abzuweichen. In einem Nash-Gleichgewicht ist daher jeder Spieler auch im Nachhinein mit seiner Strategiewahl einverstanden, er würde sie wieder genauso treffen. Die Strategien der Spieler sind demnach gegenseitig [[beste Antwort]]en. Das Nash-Gleichgewicht ist ein elementares [[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.<ref>John Forbes Nash: ''Non-cooperative games.'' Dissertation, Princeton University 1950 ([http://rbsc.princeton.edu/sites/default/files/Non-Cooperative_Games_Nash.pdf Online-Version]; PDF; 1,2&nbsp;MB).</ref> Das Nash-Gleichgewicht hat u.&nbsp;a. eine zentrale Bedeutung in wirtschaftswissenschaftlichen Bereichen wie der [[Mikroökonomie]], bei der Verteilung von Gütern und der Preisfindung.

== Idee ==
Das wesentliche Ziel der mathematischen Spieltheorie ist es, für Konflikt-, aber auch für Kooperationssituationen 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 ungewiss, wie sich seine konkrete Entscheidung für einen Handlungsplan („Strategie“) auswirken wird. Er kann aber die Situation aus der Sicht der anderen Spieler durchdenken, um eine Erwartung zu bilden, was diese tun werden.

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, weil 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.

== Definition ==
Ein '''Nash-Gleichgewicht''' ist ein Strategienpaar (bzw. bei mehr als zwei Spielern ein Strategien-Tupel), bei dem es sich für keinen Spieler auszahlt, einseitig (alleine) von seiner Strategie abzuweichen. Strategisch aus der Sicht eines Spielers betrachtet bedeutet dies: Ich tue das Beste, was ich kann, unter Berücksichtigung dessen, was du tust; du tust, unter Berücksichtigung dessen, was ich tue, das Beste, was du tun kannst.

Bei der Untersuchung von Nash-Gleichgewichten können drei Arten von Strategien unterschieden werden: ''dominante Strategien, reine Strategien'' und ''gemischte Strategien.'' Es ist zu beachten, dass bei einigen Spielen kein Nash-Gleichgewicht existiert, wenn nur reine Strategien zum Einsatz kommen. Beim Einsatz gemischter Strategien gibt es dagegen stets ein oder mehrere Gleichgewichte, wenn von endlich vielen reinen Strategien ausgegangen wird.

'''Dominante Strategien''': Was ein Spieler tut, ist das Beste für ihn, ganz unabhängig davon, was die anderen tun. Solche dominanten Strategien existieren eher selten, da es meist von den Entscheidungen anderer abhängt, was für einen Spieler das Beste ist. Mitunter – etwa im [[Gefangenendilemma]] – hat aber jeder Spieler eine dominante Strategie, die dann ein sogenanntes Gleichgewicht in dominanten Strategien konstituieren.

'''Reine Strategien''': Der Spieler trifft eine ganz bestimmte Entscheidung.

'''Gemischte Strategien''': Der Spieler trifft eine zufällige Entscheidung zwischen zwei oder mehr möglichen Handlungsmöglichkeiten (den reinen Strategien), aber mit bestimmten Wahrscheinlichkeiten für die reinen Strategien.

== Formale Definition bei unterschiedlichen Strategien ==
=== Nash-Gleichgewicht in reinen Strategien ===
Es bezeichne <math>\Sigma_i</math> die Menge der Strategien (Handlungsalternativen) des <math>i</math>-ten Spielers und <math>\Sigma := \Sigma_1\times\dotsb\times\Sigma_n</math> das [[Kartesisches Produkt|kartesische Produkt]] dieser Strategienmengen.

Unter einem Nash-Gleichgewicht in reinen [[Strategie (Spieltheorie)|Strategien]] versteht man ein Strategieprofil <math>\sigma^* = (\sigma_1^*,\dotsc,\sigma_n^*) \in \Sigma</math>, bei dem die Strategie jedes Spielers <math>i</math> 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 <math>i</math> also kein <math>\sigma_i \neq \sigma_i^*</math> gibt, das dem Spieler <math>i</math> eine höhere Auszahlung verspricht:

:<math>
\forall \sigma_i \in \Sigma_i: u_i(\sigma_1^*,\dotsc,\sigma_i^*,\dotsc, \sigma_n^*) \geq u_i(\sigma_1^*,\dotsc,\sigma_i,\dotsc, \sigma_n^*)
</math>.

Man sagt auch, dass Spieler <math>i</math> 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.
Besteht ein Nash-Gleichgewicht nur aus dominanten Strategien, bezeichnet man es außerdem als [[striktes Gleichgewicht]].

=== Nash-Gleichgewicht in gemischten 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 <math>\sigma_i</math> aus <math>\Sigma_i</math> zufällig gezogen werden. Ist <math>\Sigma_i</math> [[Endliche Menge|endlich]] oder zumindest [[Abzählbare Menge|abzählbar]], so kann die Wahrscheinlichkeitsverteilung durch einen [[Vektor]] <math>s_i</math> beschrieben werden, wobei <math>s_{i,j}</math> die Wahrscheinlichkeit ist, dass die Strategie <math>\sigma_{i,j} \in \Sigma_i</math> gewählt wird.

Die [[gemischte Strategie]] <math>s = (s_1^*,\dotsc,s_n^*)</math> ist genau dann ein Nash-Gleichgewicht, wenn kein Spieler durch alleiniges Abweichen eine bessere Auszahlung erreichen kann, das heißt genau dann, wenn

:<math>
\forall i \in \{1,\dotsc,n\} \;\;\forall s_i \in S_i\;\;u_i(s_1^*,\dotsc,s_{i-1}^*,s_i,s_{i+1}^*,\dotsc, s_n^*) \leq u_i(s_1^*,\dotsc,s_{i-1}^*,s_i^*,s_{i+1}^*,\dotsc, s_n^*)
</math>.

Ein Nash-Gleichgewicht in gemischten Strategien kennzeichnet sich dadurch, dass jede Strategie, die als Teil eines Gleichgewichtes gespielt wird, die gleiche erwartete Auszahlung aufweist.

== Existenz ==
Mit Hilfe des [[Fixpunktsatz von Kakutani|Fixpunktsatzes von Kakutani]] kann man zeigen, dass mindestens ein Nash-Gleichgewicht existieren muss, wenn folgende Voraussetzungen erfüllt sind:

# Die Auszahlungsfunktionen <math>H_i(\sigma_1,\ldots,\sigma_n)</math> sind [[Stetige Funktion|stetig]] und [[Quasikonkave Funktion|quasikonkav]] in <math>\sigma_i</math> .
# Die Strategiemengen <math>\Sigma_1,\ldots,\Sigma_n</math> sind [[Konvexe Menge|konvex]] und [[Kompakter Raum|kompakt]].

Häufig werden Spiele so konstruiert, dass die <math>\Sigma_i</math> endlich sind, endliche Mengen mit mehr als einem Element können jedoch nicht konvex sein. Allerdings ist in diesem Falle die Menge der gemischten Strategien <math>S_i</math> über <math>\Sigma_i</math> kompakt und konvex und die entsprechende Erweiterung von <math>H</math> 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 ''(wenn von endlich vielen reinen Strategien ausgegangen wird).

== 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 <math>i=1,\dotsc,n</math> bei (beliebig) fixierten Strategien aller anderen Spieler: Markiere die unter diesen Umständen erreichbaren höchsten Auszahlungen für Spieler <math>i</math> (die sog. „besten Antworten“ auf die Strategiekombination der anderen Spieler). Wiederhole dies für alle möglichen Strategiekombinationen der anderen Spieler.
# Führe 1. für alle Spieler durch.

Dann sind genau die Strategiekombinationen Nash-Gleichgewichte, bei denen die Auszahlungen für alle Spieler markiert sind. Wenn es keine Strategiekombination gibt, die für alle Spieler markiert ist, hat das Spiel auch kein Nash-Gleichgewicht in reinen Strategien. - Diese Vorgehensweise eignet sich nur für eine geringe Anzahl von Spielern und Strategien.

=== Beispiel ===
Sei folgendes Spiel in [[Normalform eines Spiels|Normalform]] gegeben:

{| class="wikitable" style="margin: 1em; font-size: 95%; text-align: center;"
|- style="color:#990000;"
|
! links
! Mitte
! rechts
|- style="color:#000099;"
! oben
| '''''4''''', <span style="color:#990000">'''''2'''''</span>
| '''''1''''', <span style="color:#990000">1</span>
| '''''2''''', <span style="color:#990000">0</span>
|- style="color:#000099;"
! style="color:#000099"|Mitte
| 2, <span style="color:#990000">3</span>
| '''''1''''', <span style="color:#990000">1</span>
| 1, <span style="color:#990000">'''''4'''''</span>
|- style="color:#000099;"
! style="color:#000099"|unten
| 3, <span style="color:#990000">0</span>
| 0, <span style="color:#990000">2</span>
| 1, <span style="color:#990000">'''''3'''''</span>
|-
| colspan="4"| ''Auszahlung[[bimatrix]] für<br /><span style="color:#000099">Spieler 1</span> und <span style="color:#990000">Spieler 2</span>''
|}

Dann funktioniert der Algorithmus wie folgt (Markierung durch Fetten):

* <math>i = 1:</math>
** 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

* <math>i = 2:</math>
** 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 das Strategiepaar (oben, links), das zur Auszahlung (4, 2) führt.

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. Alternativ lässt sich das Spiel auch mit [[Iterative Eliminierung strikt dominierter Strategien|iterativer Eliminierung strikt dominierter Strategien]] lösen.

== Ein Algorithmus zur Identifizierung von Nash-Gleichgewichten in gemischten Strategien ==

Bei der Identifizierung von Nash-Gleichgewichten in gemischten Strategien ist es hilfreich, diejenigen [[Gemischte Strategie|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.

Für beliebige [[Zwei-Personen-Nullsummenspiel]]e mit endlicher Strategiemenge ([[Matrix-Spiel]]) kann die Bestimmung von Nash-Gleichgewichten in gemischten Strategien als [[Lineare Optimierung (Spieltheorie)|lineares Optimierungsproblem]] dargestellt werden, das sich mit Hilfe des [[Simplex-Algorithmus]] lösen lässt.

=== Beispiel ===

Gegeben sei die folgende [[Bimatrix]]:

{| class="wikitable" style="margin: 1em; font-size: 95%; text-align: center;"
|- style="color:#990000;"
|
! Oper
! Fußball
|- style="color:#000099;"
! scope="row" style="color:#000099"|Oper
| 3, <span style="color:#990000">2</span>
| 2, <span style="color:#990000">3</span>
|- style="color:#000099;"
! scope="row" style="color:#000099"|Fußball
| 1, <span style="color:#990000">3</span>
| 4, <span style="color:#990000">1</span>
|-
|colspan="3"| ''Auszahlungsmatrix für<br /><span style="color:#000099">Spieler 1</span> und <span style="color:#990000">Spieler 2</span>''
|}

Dann funktioniert der Algorithmus wie folgt:

Spielt Spieler 2 mit einer Wahrscheinlichkeit von <math>q</math> Oper und mit der [[Wahrscheinlichkeitstheorie#Folgerungen|Gegenwahrscheinlichkeit]] von <math>(1-q)</math> Fußball, so ergeben sich für Spieler 1 folgende [[Erwartungsnutzen]] (''Expected Utility''):

:<math>\operatorname{E}[U_1(O)] = 3q + 2(1-q)</math>
:<math>\operatorname{E}[U_1(F)]= 1q + 4(1-q)</math>

Spieler 1 ist also indifferent zwischen seinen beiden Strategien, wenn

<math>\begin{array}{cl}
& 3q + 2(1-q) \;=\; 1q + 4(1-q) \\
\Leftrightarrow & 3q + 2 - 2q \;=\;  1q + 4 - 4q \\
\Leftrightarrow  & 1q + 2 \;=\;  4 - 3q \\
\Leftrightarrow & 4q \;=\;  2 \\
\Leftrightarrow & q \;=\;  1/2
\end{array}</math>

Für Spieler 2 lässt sich analog ermitteln, dass er indifferent ist, wenn Spieler 1 mit einer Wahrscheinlichkeit von <math>p = 2/3</math> Oper und mit <math>(1-p) = 1/3</math> 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 <math>[(2/3;1/3),(1/2;1/2)]</math> als Nash-Gleichgewicht in gemischten Strategien identifiziert werden.

== Spezialfälle ==
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 <math>(v,-v)</math>, wobei <math>v</math> der Wert des Spieles heißt.

Für [[Spiel (Spieltheorie)#Nullsummen-Eigenschaft|Zwei-Personen-Nullsummenspiele]] mit [[Spiel (Spieltheorie)#Perfekte Information|perfekter Information]], zu denen Brettspiele wie [[Schach]] und [[Mühlespiel|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.

== Praxisbeispiele ==
=== Marktwirtschaft ===
Strategiefindung basierend auf Nash-Gleichgewichten lassen sich auf '''Preise und Mengen''' gleichermaßen anwenden. In der [[Marktwirtschaft]] ist eine Situation denkbar, bei der mehrere Anbieter in einem Markt die [[Preistheorie|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.

=== Gefangenendilemma ===
{{Hauptartikel|Gefangenendilemma}}
Ein weiteres Beispiel ist das Gefangenendilemma, ein spieltheoretisches Problem, bei dem genau ein Nash-Gleichgewicht existiert.

{| class="wikitable float-right" style="margin: 1em; font-size: 95%; text-align: center;"
|- style="color:#990000;"
|
! gesteht
! gesteht nicht
|- style="color:#000099;"
! gesteht
| −5, <span style="color:#990000">−5</span>
| −1, <span style="color:#990000">−10</span>
|- style="color:#000099;"
! gesteht nicht
| −10, <span style="color:#990000">−1</span>
| −2, <span style="color:#990000">−2</span>
|-
|colspan="3"| ''Auszahlungsmatrix für<br /><span style="color:#000099">Spieler 1</span> und <span style="color:#990000">Spieler 2</span>''
|}

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 10 Jahre Haft. Beiden Gefangenen wird nun ein Handel angeboten, worüber auch beide informiert sind. Wenn einer allein gesteht (Kronzeuge) und somit seinen Partner mitbelastet, bekommt er eine milde Strafe von 1 Jahr Haft – der andere muss die vollen 10 Jahre absitzen. Entscheiden sich beide zu schweigen, bleiben nur Indizienbeweise, die aber ausreichen, um beide für 2 Jahre einzusperren. Gestehen aber beide die Tat, erwartet jeden eine Gefängnisstrafe von 5 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. Anders gesagt: Das Nash-Gleichgewicht im Gefangenendilemma ist nicht [[Pareto-Optimum|Pareto-optimal]], da sich beide Spieler zusammen dagegen verbessern können.

== Siehe auch ==
* Eine Vielzahl verwandter Konzepte finden sich unter [[Gleichgewicht (Spieltheorie)]]

== Weblinks ==
{{Wiktionary}}
* [http://www.bewersdorff-online.de/quaak/quaak.htm Minimax-Strategie in der Praxis: Einfaches Zwei-Personen-Bluffspiel gegen den Computer]

== Einzelnachweise ==
<references />

[[Kategorie:Spieltheorie]]
[[Kategorie:Theoretische Biologie]]