Das Nash-Gleichgewicht

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, wobei jeder Spieler genau eine Strategie wählt, von der aus es für keinen Spieler sinnvoll ist, von seiner gewählten Strategie 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 Antworten. 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.[1] Das Nash-Gleichgewicht findet u. a. eine zentrale Bedeutung in wirtschaftswissenschaftlichen Bereichen wie der Mikroökonomie, bei der Verteilung von Gütern und Preisfindung.


John F. Nash auf einem Symposium zu Spieltheorie und experimenteller Wirtschaftsforschung an der Universität Köln, 2006.

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 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.
Definition

Ein Nash-Gleichgewicht ist ein Strategienpaar (bzw. bei mehr als zwei Spielern ein Strategien-N-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.” und “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 ich tue, ist ganz unabhängig davon, was Du tust, für mich das Beste.” Solche dominanten Strategien existieren eher selten, da es meist von den Entscheidungen anderer abhängt, was "für mich 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: “Ich (der Spieler) treffe eine ganz bestimmte Entscheidung.”

Gemischte Strategien: “Ich (der Spieler) treffe 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 bei reinen Strategien

Es bezeichne \Sigma_i die Menge der Strategien (Handlungsalternativen) des i-ten Spielers und \Sigma := \Sigma_1\times\dotsb\times\Sigma_n das kartesische Produkt dieser Strategienmengen.

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

\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^*) .

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

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

\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^*) .

Existenz

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

Die Auszahlungsfunktionen H_i(\sigma_1,\ldots,\sigma_n) sind stetig und quasikonkav in \sigma_i .
Die Strategiemengen \Sigma_1,\ldots,\Sigma_n sind konvex und kompakt.

Häufig werden Spiele so konstruiert, dass die \Sigma_i endlich sind, endliche Mengen können jedoch nicht konvex sein. Allerdings ist in diesem Falle die Menge der gemischten Strategien S_i über \Sigma_i kompakt und konvex und die entsprechende Erweiterung von H 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 i=1,\dotsc,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 Strategiekombinationen 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:
Auszahlungsmatrix für Spieler 1 und Spieler 2 links mitte rechts
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 (Markierung durch Fetten):

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

Weiteres dazu om Link:

https://de.wikipedia.org/wiki/Nash-Gleichgewicht