Nash-Gleichgewicht

Nash-Gleichgewicht ⓘ
Ein Lösungskonzept in der Spieltheorie
Beziehung
Untermenge von	Rationalisierbarkeit, Epsilon-Gleichgewicht, Korreliertes Gleichgewicht
Obermenge von	Evolutionär stabile Strategie, Perfektes Subgame-Gleichgewicht, Perfektes Bayes'sches Gleichgewicht, Perfektes Gleichgewicht der Zitterhand, Stabiles Nash-Gleichgewicht, Starkes Nash-Gleichgewicht, Cournot-Gleichgewicht
Bedeutung
Vorgeschlagen von	John Forbes Nash Jr.
Verwendet für	Alle nicht-kooperativen Spiele

In der Spieltheorie ist das nach dem Mathematiker John Forbes Nash Jr. benannte Nash-Gleichgewicht die gebräuchlichste Methode, um die Lösung eines nicht-kooperativen Spiels mit zwei oder mehr Spielern zu definieren. Bei einem Nash-Gleichgewicht wird davon ausgegangen, dass jeder Spieler die Gleichgewichtsstrategien der anderen Spieler kennt und dass niemand etwas zu gewinnen hat, wenn er nur seine eigene Strategie ändert. Das Prinzip des Nash-Gleichgewichts geht auf Cournot zurück, der es 1838 auf konkurrierende Unternehmen bei der Auswahl ihrer Produkte anwandte. ⓘ

Wenn jeder Spieler eine Strategie gewählt hat - einen Aktionsplan, der auf den bisherigen Ereignissen im Spiel basiert - und niemand seinen eigenen erwarteten Gewinn durch eine Änderung der eigenen Strategie erhöhen kann, während die anderen Spieler ihre Strategie unverändert lassen, dann stellt die derzeitige Auswahl an Strategien ein Nash-Gleichgewicht dar. ⓘ

Wenn zwei Spieler, Alice und Bob, die Strategien A und B wählen, ist (A, B) ein Nash-Gleichgewicht, wenn Alice keine andere Strategie zur Verfügung hat, die ihre Auszahlung besser maximiert als A, wenn Bob B wählt, und Bob keine andere Strategie zur Verfügung hat, die seine Auszahlung besser maximiert als B, wenn Alice A wählt. In einem Spiel, an dem auch Carol und Dan beteiligt sind, ist (A, B, C, D) ein Nash-Gleichgewicht, wenn A die beste Antwort von Alice auf (B, C, D) ist, B die beste Antwort von Bob auf (A, C, D) ist und so weiter. ⓘ

Nash hat gezeigt, dass es für jedes endliche Spiel ein Nash-Gleichgewicht gibt: siehe auch den Artikel über Strategie. ⓘ

John F. Nash (2006) ⓘ

Anwendungen

Spieltheoretiker verwenden das Nash-Gleichgewicht, um das Ergebnis der strategischen Interaktion zwischen mehreren Entscheidungsträgern zu analysieren. Bei einer strategischen Interaktion hängt das Ergebnis für jeden Entscheidungsträger von den Entscheidungen der anderen sowie von seinen eigenen Entscheidungen ab. Die einfache Erkenntnis, die der Idee von Nash zugrunde liegt, ist, dass man die Entscheidungen mehrerer Entscheidungsträger nicht vorhersagen kann, wenn man diese Entscheidungen isoliert analysiert. Stattdessen muss man sich fragen, was jeder Spieler tun würde, wenn er berücksichtigt, was er von den anderen Spielern erwartet. Ein Nash-Gleichgewicht setzt voraus, dass die eigenen Entscheidungen kohärent sind: Kein Spieler möchte seine Entscheidung rückgängig machen, wenn er weiß, wie sich die anderen entscheiden. ⓘ

Das Konzept wurde verwendet, um feindselige Situationen wie Kriege und Wettrüsten zu analysieren (siehe Gefangenendilemma) und auch um zu untersuchen, wie Konflikte durch wiederholte Interaktion gemildert werden können (siehe Tit-for-Tat). Es wurde auch verwendet, um zu untersuchen, inwieweit Menschen mit unterschiedlichen Präferenzen kooperieren können (siehe Kampf der Geschlechter) und ob sie Risiken eingehen, um ein kooperatives Ergebnis zu erzielen (siehe Hirschjagd). Es wurde verwendet, um die Annahme technischer Standards sowie das Auftreten von Bank-Runs und Währungskrisen zu untersuchen (siehe Koordinationsspiel). Weitere Anwendungsbereiche sind der Verkehrsfluss (siehe Wardrop'sches Prinzip), die Organisation von Auktionen (siehe Auktionstheorie), das Ergebnis der Bemühungen mehrerer Parteien im Bildungsprozess, Rechtsvorschriften wie z. B. Umweltvorschriften (siehe Tragödie der Allmende), die Bewirtschaftung natürlicher Ressourcen, die Analyse von Marketingstrategien, sogar Elfmeterschießen im Fußball (siehe Matching Pennies), Energiesysteme, Verkehrssysteme, Evakuierungsprobleme und drahtlose Kommunikation. ⓘ

Geschichte

Das Nash-Gleichgewicht ist nach dem amerikanischen Mathematiker John Forbes Nash Jr. benannt. Die gleiche Idee wurde 1838 von Antoine Augustin Cournot in seiner Oligopoltheorie in einer speziellen Anwendung verwendet. In Cournots Theorie wählt jedes von mehreren Unternehmen aus, wie viel es produzieren soll, um seinen Gewinn zu maximieren. Die beste Produktionsmenge für ein Unternehmen hängt von der Produktionsmenge der anderen Unternehmen ab. Ein Cournot-Gleichgewicht liegt vor, wenn der Output jedes Unternehmens seinen Gewinn unter Berücksichtigung des Outputs der anderen Unternehmen maximiert, was ein rein strategisches Nash-Gleichgewicht darstellt. Cournot führte auch das Konzept der Best-Response-Dynamik in seine Analyse der Stabilität des Gleichgewichts ein. Cournot verwendete das Konzept jedoch nicht in anderen Anwendungen und definierte es auch nicht allgemein. ⓘ

Das moderne Konzept des Nash-Gleichgewichts wird stattdessen durch gemischte Strategien definiert, bei denen die Spieler eine Wahrscheinlichkeitsverteilung über die möglichen reinen Strategien wählen (wobei die Wahrscheinlichkeit für eine reine Strategie 100 % betragen kann; solche reinen Strategien sind eine Teilmenge der gemischten Strategien). Das Konzept eines Gleichgewichts mit gemischten Strategien wurde von John von Neumann und Oskar Morgenstern in ihrem Buch The Theory of Games and Economic Behavior aus dem Jahr 1944 eingeführt, aber ihre Analyse beschränkte sich auf den Spezialfall der Nullsummenspiele. Sie zeigten, dass es für jedes Nullsummenspiel mit einer endlichen Anzahl von Aktionen ein Nash-Gleichgewicht mit gemischten Strategien gibt. Der Beitrag von Nash in seinem Artikel "Non-Cooperative Games" aus dem Jahr 1951 bestand darin, ein Nash-Gleichgewicht mit gemischten Strategien für jedes Spiel mit einer endlichen Anzahl von Aktionen zu definieren und zu beweisen, dass in einem solchen Spiel mindestens ein Nash-Gleichgewicht (mit gemischten Strategien) existieren muss. Der Schlüssel zu Nashs Fähigkeit, die Existenz weitaus allgemeiner zu beweisen als von Neumann, lag in seiner Definition des Gleichgewichts. Nach Nash ist "ein Gleichgewichtspunkt ein n-Tupel, bei dem die gemischte Strategie eines jeden Spielers seine Auszahlung maximiert, wenn die Strategien der anderen fixiert sind. Somit ist die Strategie jedes Spielers optimal im Vergleich zu den Strategien der anderen." Indem er das Problem in diesen Rahmen stellte, konnte Nash in seiner Arbeit von 1950 das Fixpunkttheorem von Kakutani anwenden, um die Existenz von Gleichgewichten zu beweisen. In seiner Arbeit von 1951 verwendete er das einfachere Brouwersche Fixpunkttheorem für denselben Zweck. ⓘ

Spieltheoretiker haben entdeckt, dass das Nash-Gleichgewicht unter bestimmten Umständen ungültige Vorhersagen macht oder keine eindeutige Vorhersage treffen kann. Sie haben viele Lösungskonzepte ("Verfeinerungen" von Nash-Gleichgewichten) vorgeschlagen, um unplausible Nash-Gleichgewichte auszuschließen. Ein besonders wichtiges Problem ist, dass einige Nash-Gleichgewichte auf Drohungen beruhen können, die nicht "glaubwürdig" sind. Im Jahr 1965 schlug Reinhard Selten das subgame perfect equilibrium als eine Verfeinerung vor, die Gleichgewichte ausschließt, die von nicht glaubwürdigen Drohungen abhängen. Andere Erweiterungen des Konzepts des Nash-Gleichgewichts befassten sich mit der Frage, was passiert, wenn ein Spiel wiederholt wird, oder was passiert, wenn ein Spiel in Abwesenheit vollständiger Informationen gespielt wird. Alle nachfolgenden Verfeinerungen und Erweiterungen des Nash-Gleichgewichts haben jedoch die wichtigste Erkenntnis gemeinsam, auf der das Nash-Konzept beruht: Das Gleichgewicht ist eine Menge von Strategien, bei der die Strategie jedes Spielers angesichts der Entscheidungen der anderen optimal ist. ⓘ

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 $(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. ⓘ

Definitionen

Nash-Gleichgewicht

Ein Strategieprofil ist eine Menge von Strategien, eine für jeden Spieler. Inoffiziell ist ein Strategieprofil ein Nash-Gleichgewicht, wenn kein Spieler durch einseitige Änderung seiner Strategie besser abschneiden kann. Um zu verstehen, was das bedeutet, stellen Sie sich vor, dass jedem Spieler die Strategien der anderen Spieler bekannt sind. Angenommen, jeder Spieler fragt sich nun: "Kann ich in Kenntnis der Strategien der anderen Spieler und unter der Annahme, dass die Strategien der anderen Spieler in Stein gemeißelt sind, von einer Änderung meiner Strategie profitieren?" ⓘ

Wenn jeder Spieler diese Frage mit "Ja" beantworten könnte, dann ist diese Gruppe von Strategien kein Nash-Gleichgewicht. Zieht es jedoch jeder Spieler vor, nicht zu wechseln (oder ist es ihm gleichgültig, ob er wechselt oder nicht), dann ist das Strategieprofil ein Nash-Gleichgewicht. Somit ist jede Strategie in einem Nash-Gleichgewicht die beste Antwort auf die Strategien der anderen Spieler in diesem Gleichgewicht. ⓘ

Formal gesehen, sei $S_{i}$ die Menge aller möglichen Strategien für den Spieler $i$, wobei $i=1,\ldots ,N$. Sei $s^{*}=(s_{i}^{*},s_{-i}^{*})$ sei ein Strategieprofil, eine Menge, die aus einer Strategie für jeden Spieler besteht, wobei $s_{-i}^{*}$ bezeichne die $N-1$ Strategien aller Spieler außer $i$. Sei $u_{i}(s_{i},s_{-i}^{*})$ sei die Auszahlung des Spielers i in Abhängigkeit von den Strategien. Das Strategieprofil $s^{*}$ ist ein Nash-Gleichgewicht, wenn

$u_{i}(s_{i}^{*},s_{-i}^{*})\geq u_{i}(s_{i},s_{-i}^{*})\;\;{\rm {for\;all}}\;\;s_{i}\in S_{i}$ ⓘ

Ein Spiel kann mehr als ein Nash-Gleichgewicht haben. Selbst wenn das Gleichgewicht eindeutig ist, kann es schwach sein: Ein Spieler kann angesichts der Wahl der anderen Spieler zwischen mehreren Strategien indifferent sein. Es ist eindeutig und wird als striktes Nash-Gleichgewicht bezeichnet, wenn die Ungleichheit strikt ist, so dass eine Strategie die einzige beste Antwort ist:

$u_{i}(s_{i}^{*},s_{-i}^{*})>u_{i}(s_{i},s_{-i}^{*})\;\;{\rm {for\;all}}\;\;s_{i}\in S_{i},s_{i}\neq s_{i}^{*}$ ⓘ

Beachten Sie, dass die Strategiemenge $S_{i}$ für verschiedene Spieler unterschiedlich sein kann und ihre Elemente eine Vielzahl von mathematischen Objekten sein können. Am einfachsten ist es, wenn ein Spieler zwischen zwei Strategien wählt, z. B. $S_{i}=\{{\text{Yes}},{\text{No}}\}.$ Oder die Strategiemenge ist eine endliche Menge von bedingten Strategien, die auf andere Spieler reagieren, z. B. $S_{i}=\{{\text{Yes}}|p={\text{Low}},{\text{No}}|p={\text{High}}\}.$ Oder es kann eine unendliche Menge sein, ein Kontinuum oder unbegrenzt, z. B. $S_{i}=\{{\text{Price}}\}$ so dass ${\text{Price}}$ eine nichtnegative reelle Zahl ist. Die Existenzbeweise von Nash gehen von einer endlichen Strategiemenge aus, aber das Konzept des Nash-Gleichgewichts setzt dies nicht voraus. ⓘ

Das Nash-Gleichgewicht kann aus der Perspektive der dritten Person manchmal nicht rational erscheinen. Das liegt daran, dass ein Nash-Gleichgewicht nicht unbedingt pareto-optimal ist. ⓘ

Das Nash-Gleichgewicht kann in sequentiellen Spielen auch nicht-rationale Folgen haben, weil die Spieler einander mit Drohungen "drohen" können, die sie nicht tatsächlich wahr machen würden. Für solche Spiele kann das subgame perfect Nash-Gleichgewicht als Analyseinstrument sinnvoller sein. ⓘ

Strenges/schwaches Gleichgewicht

Nehmen wir an, dass sich im Nash-Gleichgewicht jeder Spieler die Frage stellt: "Würde ich in Kenntnis der Strategien der anderen Spieler und unter der Annahme, dass die Strategien der anderen Spieler in Stein gemeißelt sind, einen Verlust erleiden, wenn ich meine Strategie ändere?" ⓘ

Wenn die Antwort jedes Spielers "Ja" lautet, dann wird das Gleichgewicht als striktes Nash-Gleichgewicht eingestuft. ⓘ

Wenn stattdessen für einen Spieler eine exakte Gleichheit zwischen der Strategie im Nash-Gleichgewicht und einer anderen Strategie besteht, die genau die gleiche Auszahlung bringt (d. h. dieser Spieler ist gleichgültig, ob er seine Strategie ändert oder nicht), dann wird das Gleichgewicht als schwaches Nash-Gleichgewicht eingestuft. ⓘ

Ein Spiel kann ein reines Strategie- oder ein gemischtes Strategie-Nash-Gleichgewicht haben. (In letzterem wird eine reine Strategie stochastisch mit einer festen Wahrscheinlichkeit gewählt). ⓘ

Nashs Existenztheorem

Nash hat bewiesen, dass jedes Spiel mit einer endlichen Anzahl von Spielern, bei dem jeder Spieler aus endlich vielen reinen Strategien wählen kann, mindestens ein Nash-Gleichgewicht hat, wenn gemischte Strategien (bei denen ein Spieler die Wahrscheinlichkeiten für die Verwendung verschiedener reiner Strategien wählt) zulässig sind, wobei es sich um eine reine Strategie für jeden Spieler oder um eine Wahrscheinlichkeitsverteilung über Strategien für jeden Spieler handeln kann. ⓘ

Nash-Gleichgewichte müssen nicht existieren, wenn die Menge der Wahlmöglichkeiten unendlich und nicht kompakt ist. Ein Beispiel ist ein Spiel, bei dem zwei Spieler gleichzeitig eine Zahl nennen und der Spieler, der die größere Zahl nennt, gewinnt. Ein anderes Beispiel ist ein Spiel, bei dem jeder der beiden Spieler eine reelle Zahl streng kleiner als 5 wählt und derjenige gewinnt, der die größte Zahl hat; es gibt keine größte Zahl streng kleiner als 5 (wenn die Zahl gleich 5 sein könnte, würde das Nash-Gleichgewicht darin bestehen, dass beide Spieler 5 wählen und das Spiel unentschieden endet). Ein Nash-Gleichgewicht liegt jedoch vor, wenn die Menge der Wahlmöglichkeiten kompakt ist und die Auszahlung jedes Spielers in den Strategien aller Spieler kontinuierlich ist. ⓘ

Beispiele

Koordinationsspiel

Ein Koordinationsspiel mit Auszahlungen für Spieler 1 (Zeile) \ Spieler 2 (Spalte)

Strategie für Spieler 1	Strategie von Spieler 2 ⓘ
	Spieler 2 wählt die Strategie A	Spieler 2 wählt Strategie B
Spieler 1 wählt Strategie A	4 4	3 1
Spieler 1 wählt Strategie B	1 3	2 2

Das Koordinationsspiel ist ein klassisches Spiel mit zwei Spielern und zwei Strategien, wie in der Auszahlungsmatrix auf der rechten Seite dargestellt. Es gibt zwei Gleichgewichte mit reinen Strategien, (A,A) mit einer Auszahlung von 4 für jeden Spieler und (B,B) mit einer Auszahlung von 2 für jeden. Die Kombination (B,B) ist ein Nash-Gleichgewicht, denn wenn einer der Spieler seine Strategie einseitig von B auf A ändert, sinkt seine Auszahlung von 2 auf 1. ⓘ

Die Hirschjagd

Strategie für Spieler 1	Strategie von Spieler 2 ⓘ
	Hirsch jagen	Jagd auf Kaninchen
Hirsch jagen	2 2	1 0
Jagd auf Kaninchen	0 1	1 1

Ein berühmtes Beispiel für ein Koordinationsspiel ist die Hirschjagd. Zwei Spieler können wählen, ob sie einen Hirsch oder ein Kaninchen jagen wollen, wobei der Hirsch mehr Fleisch liefert (4 Nutzeneinheiten, 2 für jeden Spieler) als das Kaninchen (1 Nutzeneinheit). Wenn also ein Spieler versucht, den Hirsch zu jagen, während der andere das Kaninchen jagt, wird der Hirschjäger völlig scheitern und eine Auszahlung von 0 erhalten, während der Kaninchenjäger erfolgreich sein wird und eine Auszahlung von 1 erhält. Das Spiel hat zwei Gleichgewichte, (Hirsch, Hirsch) und (Kaninchen, Kaninchen), weil die optimale Strategie eines Spielers von seiner Erwartung abhängt, was der andere Spieler tun wird. Wenn ein Jäger darauf vertraut, dass der andere den Hirsch jagen wird, sollte er den Hirsch jagen; wenn er jedoch glaubt, dass der andere den Hasen jagen wird, wird auch er den Hasen jagen. Dieses Spiel wird als Analogie für die soziale Zusammenarbeit verwendet, da ein großer Teil des Nutzens, den die Menschen in der Gesellschaft erzielen, davon abhängt, dass die Menschen zusammenarbeiten und einander implizit vertrauen, dass sie in einer Weise handeln, die der Zusammenarbeit entspricht. ⓘ

Das Fahren auf einer Straße gegen ein entgegenkommendes Auto, bei dem man sich entscheiden muss, ob man nach links oder nach rechts ausweichen will, ist ebenfalls ein Koordinationsspiel. Mit den Auszahlungen 10 für keinen Unfall und 0 für einen Unfall kann das Koordinationsspiel beispielsweise mit der folgenden Auszahlungsmatrix definiert werden:

Das Fahrspiel

Strategie für Spieler 1	Strategie von Spieler 2 ⓘ
	Fahren Sie auf der linken Seite	Rechts fahren
Fahren Sie auf der linken Seite	10 10	0 0
Rechts fahren	0 0	10 10

In diesem Fall gibt es zwei Nash-Gleichgewichte mit reinen Strategien, wenn beide entweder links oder rechts fahren wollen. Wenn wir gemischte Strategien zulassen (bei denen eine reine Strategie nach dem Zufallsprinzip und mit einer festen Wahrscheinlichkeit gewählt wird), dann gibt es drei Nash-Gleichgewichte für denselben Fall: zwei haben wir aus der reinen Strategieform gesehen, bei denen die Wahrscheinlichkeiten (0%, 100%) für Spieler eins, (0%, 100%) für Spieler zwei bzw. (100%, 0%) für Spieler eins, (100%, 0%) für Spieler zwei sind. Wir fügen eine weitere hinzu, bei der die Wahrscheinlichkeiten für jeden Spieler (50%, 50%) sind. ⓘ

Netzwerkverkehr

Beispiel eines Netzgraphen. Die Werte an den Kanten sind die Reisezeit, die ein "Auto" auf dieser Kante benötigt. x ist die Anzahl der Autos, die über diese Kante fahren. ⓘ

Eine Anwendung von Nash-Gleichgewichten ist die Bestimmung des erwarteten Verkehrsflusses in einem Netz. Betrachten Sie das Diagramm auf der rechten Seite. Wenn wir annehmen, dass x "Autos" von A nach D fahren, wie sieht dann die erwartete Verteilung des Verkehrs im Netz aus? ⓘ

Diese Situation kann als "Spiel" modelliert werden, bei dem jeder Reisende die Wahl zwischen 3 Strategien hat, wobei jede Strategie eine Route von A nach D ist (eine von ABD, ABCD oder ACD). Die "Auszahlung" für jede Strategie ist die Reisezeit für jede Strecke. In der Grafik rechts hat ein Auto, das über ABD fährt, eine Fahrzeit von (1+x/100)+2, wobei x die Anzahl der Autos ist, die auf der Kante AB fahren. Die Auszahlungen für eine bestimmte Strategie hängen also, wie üblich, von den Entscheidungen der anderen Spieler ab. In diesem Fall besteht das Ziel jedoch darin, die Reisezeit zu minimieren und nicht zu maximieren. Ein Gleichgewicht tritt ein, wenn die Zeit auf allen Wegen genau gleich lang ist. In diesem Fall hat kein einzelner Fahrer einen Anreiz, die Route zu wechseln, da sich dadurch nur seine Fahrzeit verlängert. Wenn in der Grafik auf der rechten Seite beispielsweise 100 Autos von A nach D fahren, dann tritt Gleichgewicht ein, wenn 25 Fahrer über ABD, 50 über ABCD und 25 über ACD fahren. Jeder Fahrer hat nun eine Gesamtreisezeit von 3,75 (um dies zu sehen, beachten Sie, dass insgesamt 75 Autos die AB-Kante nehmen, und ebenso 75 Autos die CD-Kante). ⓘ

Beachten Sie, dass diese Verteilung nicht wirklich sozial optimal ist. Wenn sich die 100 Autos darauf geeinigt haben, dass 50 über ABD und die anderen 50 über ACD fahren, dann wäre die Fahrzeit für jedes einzelne Auto 3,5, also weniger als 3,75. Dies ist auch das Nash-Gleichgewicht, wenn der Weg zwischen B und C wegfällt, was bedeutet, dass das Hinzufügen eines weiteren möglichen Weges die Effizienz des Systems verringern kann, ein Phänomen, das als Braess'sches Paradoxon bekannt ist. ⓘ

Wettbewerbsspiel

Ein Wettbewerbsspiel

Strategie für Spieler 1	Strategie von Spieler 2 ⓘ
	Wähle "0"	Wähle "1"	Wähle "2"	Wähle "3"
Wähle "0"	0, 0	2, −2	2, −2	2, −2
Wähle "1"	−2, 2	1, 1	3, −1	3, −1
Wähle "2"	−2, 2	−1, 3	2, 2	4, 0
Wähle "3"	−2, 2	−1, 3	0, 4	3, 3

Dies kann durch ein Spiel mit zwei Spielern veranschaulicht werden, bei dem beide Spieler gleichzeitig eine ganze Zahl von 0 bis 3 wählen und beide die kleinere der beiden Zahlen in Punkten gewinnen. Wählt ein Spieler eine größere Zahl als der andere, muss er dem anderen zwei Punkte abtreten. ⓘ

In diesem Spiel gibt es ein einziges Nash-Gleichgewicht mit reiner Strategie: beide Spieler wählen 0 (hellrot hervorgehoben). Jede andere Strategie kann verbessert werden, indem ein Spieler seine Zahl auf eine Zahl weniger als die des anderen Spielers ändert. Wenn in der nebenstehenden Tabelle das Spiel auf dem grünen Feld beginnt, ist es im Interesse von Spieler 1, auf das lila Feld zu ziehen, und im Interesse von Spieler 2, auf das blaue Feld zu ziehen. Obwohl es nicht der Definition eines Wettbewerbsspiels entspricht, gibt es vier Nash-Gleichgewichte: (0,0), (1,1), (2,2) und (3,3), wenn das Spiel so modifiziert wird, dass die beiden Spieler den genannten Betrag gewinnen, wenn sie beide die gleiche Zahl wählen, und ansonsten nichts gewinnen. ⓘ

Nash-Gleichgewichte in einer Auszahlungsmatrix

Es gibt einen einfachen numerischen Weg, um Nash-Gleichgewichte in einer Auszahlungsmatrix zu identifizieren. Dies ist besonders hilfreich bei Zwei-Personen-Spielen, bei denen die Spieler mehr als zwei Strategien haben. In diesem Fall kann die formale Analyse zu lang werden. Diese Regel gilt nicht für den Fall, dass gemischte (stochastische) Strategien von Interesse sind. Die Regel lautet wie folgt: Wenn die erste Auszahlungszahl in dem Auszahlungspaar der Zelle das Maximum der Spalte der Zelle ist und wenn die zweite Zahl das Maximum der Zeile der Zelle ist - dann stellt die Zelle ein Nash-Gleichgewicht dar. ⓘ

Eine Auszahlungsmatrix - Nash-Gleichgewichte in Fettdruck

Strategie für Spieler 1	Strategie von Spieler 2 ⓘ
	Möglichkeit A	Möglichkeit B	Möglichkeit C
Möglichkeit A	0, 0	25, 40	5, 10
Möglichkeit B	40, 25	0, 0	5, 15
Möglichkeit C	10, 5	15, 5	10, 10

Wir können diese Regel auf eine 3×3-Matrix anwenden: Anhand der Regel können wir sehr schnell (viel schneller als mit einer formalen Analyse) erkennen, dass die Zellen für Nash-Gleichgewichte (B,A), (A,B) und (C,C) sind. In der Tat ist für die Zelle (B,A) 40 das Maximum der ersten Spalte und 25 das Maximum der zweiten Zeile. Für (A,B) ist 25 das Maximum der zweiten Spalte und 40 das Maximum der ersten Zeile. Dasselbe gilt für die Zelle (C,C). Bei anderen Zellen sind entweder eines oder beide der Duplettmitglieder nicht das Maximum der entsprechenden Zeilen und Spalten. ⓘ

Die eigentliche Mechanik der Suche nach Gleichgewichtszellen ist jedoch offensichtlich: Man sucht das Maximum einer Spalte und prüft, ob das zweite Mitglied des Paares das Maximum der Zeile ist. Wenn diese Bedingungen erfüllt sind, stellt die Zelle ein Nash-Gleichgewicht dar. Überprüfen Sie alle Spalten auf diese Weise, um alle NE-Zellen zu finden. Eine N×N-Matrix kann zwischen 0 und N×N reine Strategie-Nash-Gleichgewichte aufweisen. ⓘ

Stabilität

Das Konzept der Stabilität, das bei der Analyse vieler Arten von Gleichgewichten nützlich ist, kann auch auf Nash-Gleichgewichte angewendet werden. ⓘ

Ein Nash-Gleichgewicht für ein Spiel mit gemischten Strategien ist stabil, wenn eine kleine Änderung (insbesondere eine infinitesimale Änderung) der Wahrscheinlichkeiten für einen Spieler zu einer Situation führt, in der zwei Bedingungen erfüllt sind:

1. der Spieler, der nicht gewechselt hat, hat unter den neuen Umständen keine bessere Strategie
2. der Spieler, der gewechselt hat, spielt nun mit einer deutlich schlechteren Strategie. ⓘ

Wenn diese beiden Fälle erfüllt sind, kehrt ein Spieler mit der kleinen Änderung in seiner gemischten Strategie sofort zum Nash-Gleichgewicht zurück. Das Gleichgewicht wird als stabil bezeichnet. Wenn die erste Bedingung nicht erfüllt ist, ist das Gleichgewicht instabil. Wenn nur die erste Bedingung erfüllt ist, gibt es wahrscheinlich unendlich viele optimale Strategien für den Spieler, der seine Strategie geändert hat. ⓘ

In dem obigen Beispiel des "Fahrspiels" gibt es sowohl stabile als auch instabile Gleichgewichte. Die Gleichgewichte mit gemischten Strategien mit 100 % Wahrscheinlichkeiten sind stabil. Wenn einer der beiden Spieler seine Wahrscheinlichkeiten geringfügig ändert, sind sie beide im Nachteil, und der Gegner hat keinen Grund, seine Strategie zu ändern. Das (50%,50%)-Gleichgewicht ist instabil. Wenn einer der beiden Spieler seine Wahrscheinlichkeiten ändert (was der Erwartung des Spielers, der die Änderung vorgenommen hat, weder nützt noch schadet, wenn die gemischte Strategie des anderen Spielers immer noch (50 %, 50 %) ist), dann hat der andere Spieler sofort eine bessere Strategie bei entweder (0 %, 100 %) oder (100 %, 0 %). ⓘ

Stabilität ist bei praktischen Anwendungen von Nash-Gleichgewichten von entscheidender Bedeutung, da die gemischte Strategie jedes Spielers nicht genau bekannt ist, sondern aus der statistischen Verteilung ihrer Aktionen im Spiel abgeleitet werden muss. In diesem Fall ist es sehr unwahrscheinlich, dass in der Praxis instabile Gleichgewichte auftreten, da jede winzige Änderung der Anteile jeder gesehenen Strategie zu einer Strategieänderung und zum Zusammenbruch des Gleichgewichts führt. ⓘ

Das Nash-Gleichgewicht definiert die Stabilität nur in Bezug auf einseitige Abweichungen. Bei kooperativen Spielen ist ein solches Konzept nicht überzeugend genug. Das starke Nash-Gleichgewicht lässt Abweichungen durch jede denkbare Koalition zu. Formal gesehen ist ein starkes Nash-Gleichgewicht ein Nash-Gleichgewicht, in dem keine Koalition unter der Annahme, dass die Handlungen ihrer Komplementäre gegeben sind, kooperativ in einer Weise abweichen kann, die allen ihren Mitgliedern zugute kommt. Das Konzept des starken Nash-Gleichgewichts wird jedoch manchmal als zu "stark" empfunden, da das Umfeld eine unbegrenzte private Kommunikation zulässt. In der Tat muss ein starkes Nash-Gleichgewicht pareto-effizient sein. Aufgrund dieser Anforderungen ist ein starkes Nash-Gleichgewicht zu selten, um in vielen Bereichen der Spieltheorie nützlich zu sein. Bei Spielen wie Wahlen, bei denen es viel mehr Spieler als mögliche Ergebnisse gibt, kann es jedoch häufiger vorkommen als ein stabiles Gleichgewicht. ⓘ

Ein verfeinertes Nash-Gleichgewicht, das als koalitionssicheres Nash-Gleichgewicht (CPNE) bekannt ist, tritt auf, wenn die Spieler auch dann nicht besser abschneiden können, wenn sie kommunizieren und eine "selbstverstärkende" Vereinbarung über eine Abweichung treffen dürfen. Jede korrelierte Strategie, die durch iterierte strikte Dominanz unterstützt wird und auf der Pareto-Grenze liegt, ist ein CPNE. Darüber hinaus ist es möglich, dass ein Spiel ein Nash-Gleichgewicht hat, das gegen Koalitionen unter einer bestimmten Größe, k, resistent ist. ⓘ

Schließlich wurden in den achtziger Jahren, aufbauend auf diesen Ideen, Mertens-stabile Gleichgewichte als Lösungskonzept eingeführt. Stabile Mertens-Gleichgewichte erfüllen sowohl die Vorwärtsinduktion als auch die Rückwärtsinduktion. In einem spieltheoretischen Kontext beziehen sich stabile Gleichgewichte nun gewöhnlich auf stabile Gleichgewichte nach Mertens. ⓘ

Ein weiteres Beispiel ist das Gefangenendilemma, ein spieltheoretisches Problem, bei dem genau ein Nash-Gleichgewicht existiert. ⓘ

	gesteht	gesteht nicht ⓘ
gesteht	-5, -5	-1, -10
gesteht nicht	-10, -1	-2, -2
Auszahlungsmatrix für Spieler 1 und Spieler 2

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-optimal, da sich beide Spieler zusammen dagegen verbessern können. ⓘ

Vorkommen

Wenn ein Spiel ein eindeutiges Nash-Gleichgewicht hat und unter bestimmten Bedingungen zwischen den Spielern gespielt wird, dann wird die NE-Strategie gewählt. Hinreichende Bedingungen, die garantieren, dass das Nash-Gleichgewicht gespielt wird, sind:

1. Alle Spieler tun ihr Bestes, um ihren erwarteten Gewinn zu maximieren, wie es das Spiel vorgibt.
2. Die Spieler sind fehlerfrei in der Ausführung.
3. Die Spieler verfügen über ausreichende Intelligenz, um die Lösung abzuleiten.
4. Die Spieler kennen die geplante Gleichgewichtsstrategie aller anderen Spieler.
5. Die Spieler glauben, dass eine Abweichung in ihrer eigenen Strategie keine Abweichungen bei anderen Spielern verursachen wird.
6. Es ist allgemein bekannt, dass alle Spieler diese Bedingungen erfüllen, einschließlich dieses einen Spielers. Jeder Spieler muss also nicht nur wissen, dass die anderen Spieler die Bedingungen erfüllen, sondern auch, dass sie alle wissen, dass sie sie erfüllen, und wissen, dass sie wissen, dass sie wissen, dass sie sie erfüllen, und so weiter. ⓘ

Wenn die Bedingungen nicht erfüllt sind

Beispiele für spieltheoretische Probleme, bei denen diese Bedingungen nicht erfüllt sind:

1. Die erste Bedingung ist nicht erfüllt, wenn das Spiel die Mengen, die ein Spieler maximieren möchte, nicht korrekt beschreibt. In diesem Fall gibt es keinen besonderen Grund für diesen Spieler, eine Gleichgewichtsstrategie zu wählen. So ist beispielsweise das Gefangenendilemma kein Dilemma, wenn einer der beiden Spieler damit zufrieden ist, auf unbestimmte Zeit im Gefängnis zu sitzen.
2. Beabsichtigte oder zufällige Unvollkommenheit in der Ausführung. Wenn zum Beispiel ein Computer, der zu einem fehlerfreien logischen Spiel fähig ist, einem zweiten fehlerfreien Computer gegenübersteht, wird sich ein Gleichgewicht einstellen. Die Einführung einer Unvollkommenheit führt zu einer Störung des Gleichgewichts, entweder durch den Verlust des Spielers, der den Fehler macht, oder durch die Negation des Kriteriums des gemeinsamen Wissens, was zu einem möglichen Sieg des Spielers führt. (Ein Beispiel dafür wäre, wenn ein Spieler beim Hühner-Spiel plötzlich den Rückwärtsgang einlegt und so dafür sorgt, dass er nicht verliert und nicht gewinnt).
3. In vielen Fällen ist die dritte Bedingung nicht erfüllt, weil das Gleichgewicht zwar existieren muss, aber aufgrund der Komplexität des Spiels nicht bekannt ist, z. B. beim chinesischen Schach. Oder, wenn es bekannt ist, ist es vielleicht nicht allen Spielern bekannt, wie beim Tic-Tac-Toe-Spiel mit einem kleinen Kind, das unbedingt gewinnen will (was die anderen Kriterien erfüllt).
4. Das Kriterium des Allgemeinwissens kann auch dann nicht erfüllt sein, wenn alle Spieler tatsächlich alle anderen Kriterien erfüllen. Spieler, die der Rationalität des anderen fälschlicherweise misstrauen, können Gegenstrategien anwenden, um ein irrationales Spiel ihrer Gegner zu erwarten. Dies ist z. B. ein wichtiger Aspekt bei "Chicken" oder einem Wettrüsten. ⓘ

Wenn die Bedingungen erfüllt sind

In seiner Dissertation schlug John Nash zwei Interpretationen seines Gleichgewichtskonzepts vor, um zu zeigen, wie Gleichgewichtspunkte mit beobachtbaren Phänomenen in Verbindung gebracht werden können. ⓘ

(...) Die eine Interpretation ist rationalistisch: Wenn wir davon ausgehen, dass die Spieler rational sind, die vollständige Struktur des Spiels kennen, das Spiel nur einmal gespielt wird und es nur ein Nash-Gleichgewicht gibt, dann werden die Spieler nach diesem Gleichgewicht spielen. ⓘ

Diese Idee wurde formalisiert von R. Aumann und A. Brandenburger, 1995, Epistemic Conditions for Nash Equilibrium, Econometrica, 63, 1161-1180, die die gemischte Strategie jedes Spielers als Vermutung über das Verhalten der anderen Spieler interpretierten und zeigten, dass, wenn das Spiel und die Rationalität der Spieler gegenseitig bekannt sind und diese Vermutungen allgemein bekannt sind, die Vermutungen ein Nash-Gleichgewicht sein müssen (eine gemeinsame Vorannahme ist für dieses Ergebnis im Allgemeinen erforderlich, aber nicht im Fall von zwei Spielern. In diesem Fall müssen die Vermutungen nur gegenseitig bekannt sein). ⓘ

Eine zweite Interpretation, die von Nash als Massenaktionsinterpretation bezeichnet wird, stellt weniger hohe Anforderungen an die Spieler:

[Es wird nicht vorausgesetzt, dass die Teilnehmer die Gesamtstruktur des Spiels vollständig kennen oder die Fähigkeit und Neigung haben, komplexe Überlegungen anzustellen. Es wird davon ausgegangen, dass es für jede Position im Spiel eine Population von Teilnehmern gibt, die im Laufe der Zeit von Teilnehmern gespielt wird, die zufällig aus den verschiedenen Populationen gezogen werden. Wenn es eine stabile durchschnittliche Häufigkeit gibt, mit der jede reine Strategie von dem durchschnittlichen Mitglied der entsprechenden Population eingesetzt wird, dann stellt diese stabile durchschnittliche Häufigkeit ein Nash-Gleichgewicht mit gemischten Strategien dar. ⓘ

Für ein formales Ergebnis in diesem Sinne siehe Kuhn, H. und et al., 1996, "The Work of John Nash in Game Theory", Journal of Economic Theory, 69, 153-185. ⓘ

Aufgrund der begrenzten Bedingungen, unter denen NE tatsächlich beobachtet werden können, werden sie nur selten als Leitfaden für das alltägliche Verhalten behandelt oder in der Praxis bei menschlichen Verhandlungen beobachtet. Als theoretisches Konzept in den Wirtschaftswissenschaften und der Evolutionsbiologie haben die NE jedoch Erklärungskraft. In der Ökonomie ist der Nutzen (oder manchmal auch das Geld) und in der Evolutionsbiologie die Weitergabe von Genen das ausschlaggebende Kriterium für das Überleben. Forscher, die die Spieltheorie in diesen Bereichen anwenden, behaupten, dass Strategien, die diese aus welchen Gründen auch immer nicht maximieren, aus dem Markt oder der Umwelt verdrängt werden, denen die Fähigkeit zugeschrieben wird, alle Strategien zu testen. Diese Schlussfolgerung ergibt sich aus der oben erwähnten "Stabilitätstheorie". In diesen Situationen hat sich die Annahme, dass es sich bei der beobachteten Strategie tatsächlich um eine NE handelt, in der Forschung häufig bestätigt. ⓘ

NE und nicht glaubwürdige Bedrohungen

Illustrationen in extensiver und normaler Form, die den Unterschied zwischen SPNE und anderen NE zeigen. Das blaue Gleichgewicht ist nicht subgame perfect, weil Spieler zwei eine nicht glaubwürdige Drohung bei 2(2) macht, unfreundlich zu sein (U). ⓘ

Das Nash-Gleichgewicht ist eine Obermenge des subgame perfect Nash-Gleichgewichts. Das subgame perfect equilibrium erfordert zusätzlich zum Nash-Gleichgewicht, dass die Strategie auch ein Nash-Gleichgewicht in jedem Unterspiel des Spiels ist. Dadurch werden alle nicht glaubwürdigen Drohungen eliminiert, d. h. Strategien, die nicht-rationale Züge enthalten, um den Gegenspieler dazu zu bringen, seine Strategie zu ändern. ⓘ

Das Bild auf der rechten Seite zeigt ein einfaches sequentielles Spiel, das das Problem der unvollkommenen Nash-Gleichgewichte in Unterspielen veranschaulicht. In diesem Spiel wählt Spieler eins links (L) oder rechts (R), woraufhin Spieler zwei aufgefordert wird, freundlich (K) oder unfreundlich (U) zu Spieler eins zu sein, wobei Spieler zwei jedoch nur davon profitiert, unfreundlich zu sein, wenn Spieler eins links geht. Wenn Spieler eins nach rechts geht, würde der rationale Spieler zwei in diesem Unterspiel de facto freundlich zu ihm sein. Die nicht glaubwürdige Drohung, bei 2(2) unfreundlich zu sein, ist jedoch immer noch Teil des blauen (L, (U,U)) Nash-Gleichgewichtes. Wenn also von beiden Parteien rationales Verhalten erwartet werden kann, kann das subgame perfect Nash equilibrium ein sinnvolleres Lösungskonzept sein, wenn solche dynamischen Inkonsistenzen auftreten. ⓘ

Beweis der Existenz

Beweis mit Hilfe des Fixpunkttheorems von Kakutani

Der ursprüngliche Beweis von Nash (in seiner Dissertation) verwendet das Brouwersche Fixpunkttheorem (siehe z. B. unten für eine Variante). Wir geben einen einfacheren Beweis über den Fixpunktsatz von Kakutani, in Anlehnung an Nashs Arbeit von 1950 (er schreibt David Gale die Beobachtung zu, dass eine solche Vereinfachung möglich ist). ⓘ

Um die Existenz eines Nash-Gleichgewichts zu beweisen, sei $r_{i}(\sigma _{-i})$ die beste Antwort des Spielers i auf die Strategien aller anderen Spieler sein.

$r_{i}(\sigma _{-i})=\mathop {\underset {\sigma _{i}}{\operatorname {arg\,max} }} u_{i}(\sigma _{i},\sigma _{-i})$ ⓘ

Hier, $\sigma \in \Sigma$, wobei $\Sigma =\Sigma _{i}\times \Sigma _{-i}$ein gemischtes Strategieprofil in der Menge aller gemischten Strategien und $u_{i}$ ist die Auszahlungsfunktion für Spieler i. Definieren Sie eine mengenwertige Funktion $r\colon \Sigma \rightarrow 2^{\Sigma }$ so dass $r=r_{i}(\sigma _{-i})\times r_{-i}(\sigma _{i})$. Die Existenz eines Nash-Gleichgewichts ist äquivalent zu $r$ einen Fixpunkt zu haben. ⓘ

Das Fixpunkttheorem von Kakutani garantiert die Existenz eines Fixpunktes, wenn die folgenden vier Bedingungen erfüllt sind.

1. $\Sigma$ ist kompakt, konvex und nichtleer.
2. $r(\sigma )$ ist nicht-leer.
3. $r(\sigma )$ ist oberhalb der Hemikontinuität
4. $r(\sigma )$ ist konvex. ⓘ

Bedingung 1. ist erfüllt, wenn man bedenkt, dass $\Sigma$ ein Simplex und damit kompakt ist. Die Konvexität folgt aus der Fähigkeit der Spieler, Strategien zu mischen. $\Sigma$ ist nichtleer, solange die Spieler Strategien haben. ⓘ

Die Bedingungen 2. und 3. sind mit Hilfe des Berge'schen Maximalsatzes erfüllt. Da $u_{i}$ kontinuierlich und kompakt ist, $r(\sigma _{i})$ nichtleer und oben halbkontinuierlich ist. ⓘ

Bedingung 4. ist durch gemischte Strategien erfüllt. Angenommen, $\sigma _{i},\sigma '_{i}\in r(\sigma _{-i})$, dann $\lambda \sigma _{i}+(1-\lambda )\sigma '_{i}\in r(\sigma _{-i})$. d.h. wenn zwei Strategien die Auszahlungen maximieren, dann wird eine Mischung zwischen den beiden Strategien die gleiche Auszahlung ergeben. ⓘ

Daher gibt es einen Fixpunkt in $r$ und ein Nash-Gleichgewicht. ⓘ

Als Nash 1949 John von Neumann auf diesen Punkt hinwies, wies von Neumann ihn bekanntlich mit den Worten zurück: "Das ist trivial, wissen Sie. Das ist nur ein Fixpunkt-Theorem." (Siehe Nasar, 1998, S. 94.) ⓘ

Alternativer Beweis unter Verwendung des Brouwerschen Fixpunktsatzes

Wir haben ein Spiel $G=(N,A,u)$ wobei $N$ die Anzahl der Spieler ist und $A=A_{1}\times \cdots \times A_{N}$ die Aktionsmenge für die Spieler ist. Alle Aktionsmengen $A_{i}$ sind endlich. Mit $\Delta =\Delta _{1}\times \cdots \times \Delta _{N}$ die Menge der gemischten Strategien für die Spieler bezeichnen. Die Endlichkeit der $A_{i}$s gewährleistet die Kompaktheit von $\Delta$. ⓘ

Wir können nun die Gewinnfunktionen definieren. Für eine gemischte Strategie $\sigma \in \Delta$lassen wir den Gewinn für den Spieler $i$ bei der Aktion $a\in A_{i}$ sein. ⓘ

${\text{Gain}}_{i}(\sigma ,a)=\max\{0,u_{i}(a,\sigma _{-i})-u_{i}(\sigma _{i},\sigma _{-i})\}.$ ⓘ

Die Gewinnfunktion stellt den Nutzen dar, den ein Spieler durch eine einseitige Änderung seiner Strategie erhält. Wir definieren nun $g=(g_{1},\dotsc ,g_{N})$ wobei ⓘ

$g_{i}(\sigma )(a)=\sigma _{i}(a)+{\text{Gain}}_{i}(\sigma ,a)$ ⓘ

für $\sigma \in \Delta ,a\in A_{i}$. Wir sehen, dass ⓘ

$\sum _{a\in A_{i}}g_{i}(\sigma )(a)=\sum _{a\in A_{i}}\sigma _{i}(a)+{\text{Gain}}_{i}(\sigma ,a)=1+\sum _{a\in A_{i}}{\text{Gain}}_{i}(\sigma ,a)>0.$ ⓘ

Als nächstes definieren wir:

${\begin{cases}f=(f_{1},\cdots ,f_{N}):\Delta \to \Delta \\f_{i}(\sigma )(a)={\frac {g_{i}(\sigma )(a)}{\sum _{b\in A_{i}}g_{i}(\sigma )(b)}}&a\in A_{i}\end{cases}}$ ⓘ

Es ist leicht zu sehen, dass jede $f_{i}$ eine gültige gemischte Strategie ist in $\Delta _{i}$. Es ist auch leicht zu überprüfen, dass jede $f_{i}$ eine stetige Funktion von $\sigma$ist, und daher $f$ eine stetige Funktion ist. Als Kreuzprodukt einer endlichen Anzahl von kompakten konvexen Mengen, $\Delta$ ebenfalls kompakt und konvex. Die Anwendung des Brouwerschen Fixpunktsatzes auf $f$ und $\Delta$ ergibt sich, dass $f$ einen Fixpunkt hat in $\Delta$hat, nennen wir ihn $\sigma ^{*}$. Wir behaupten, dass $\sigma ^{*}$ ein Nash-Gleichgewicht ist in $G$. Zu diesem Zweck genügt es zu zeigen, dass ⓘ

$\forall i\in \{1,\cdots ,N\},\forall a\in A_{i}:\quad {\text{Gain}}_{i}(\sigma ^{*},a)=0.$ ⓘ

Dies besagt einfach, dass jeder Spieler keinen Nutzen aus einer einseitigen Änderung seiner Strategie zieht, was genau die notwendige Bedingung für ein Nash-Gleichgewicht ist. ⓘ

Nehmen wir nun an, dass die Gewinne nicht alle gleich Null sind. Deshalb, $\exists i\in \{1,\cdots ,N\},$ und $a\in A_{i}$ so dass ${\text{Gain}}_{i}(\sigma ^{*},a)>0$. Beachten Sie dann, dass ⓘ

$\sum _{a\in A_{i}}g_{i}(\sigma ^{*},a)=1+\sum _{a\in A_{i}}{\text{Gain}}_{i}(\sigma ^{*},a)>1.$ ⓘ

Also sei ⓘ

$C=\sum _{a\in A_{i}}g_{i}(\sigma ^{*},a).$ ⓘ

Wir bezeichnen auch ${\text{Gain}}(i,\cdot )$ als den Verstärkungsvektor bezeichnen, der durch die Aktionen in $A_{i}$. Da $\sigma ^{*}$ der Fixpunkt ist, haben wir:

${\begin{aligned}\sigma ^{*}=f(\sigma ^{*})&\Rightarrow \sigma _{i}^{*}=f_{i}(\sigma ^{*})\\&\Rightarrow \sigma _{i}^{*}={\frac {g_{i}(\sigma ^{*})}{\sum _{a\in A_{i}}g_{i}(\sigma ^{*})(a)}}\\[6pt]&\Rightarrow \sigma _{i}^{*}={\frac {1}{C}}\left(\sigma _{i}^{*}+{\text{Gain}}_{i}(\sigma ^{*},\cdot )\right)\\[6pt]&\Rightarrow C\sigma _{i}^{*}=\sigma _{i}^{*}+{\text{Gain}}_{i}(\sigma ^{*},\cdot )\\&\Rightarrow \left(C-1\right)\sigma _{i}^{*}={\text{Gain}}_{i}(\sigma ^{*},\cdot )\\&\Rightarrow \sigma _{i}^{*}=\left({\frac {1}{C-1}}\right){\text{Gain}}_{i}(\sigma ^{*},\cdot ).\end{aligned}}$ ⓘ

Da $C>1$ haben wir, dass $\sigma _{i}^{*}$ eine positive Skalierung des Vektors ${\text{Gain}}_{i}(\sigma ^{*},\cdot )$. Wir behaupten nun, dass ⓘ

$\forall a\in A_{i}:\quad \sigma _{i}^{*}(a)(u_{i}(a_{i},\sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*}))=\sigma _{i}^{*}(a){\text{Gain}}_{i}(\sigma ^{*},a)$ ⓘ

Um dies zu sehen, stellen wir zunächst fest, dass wenn ${\text{Gain}}_{i}(\sigma ^{*},a)>0$ dann ist dies durch die Definition der Verstärkungsfunktion wahr. Nehmen wir nun an, dass ${\text{Gain}}_{i}(\sigma ^{*},a)=0$. Aus unseren vorherigen Aussagen ergibt sich, dass ⓘ

$\sigma _{i}^{*}(a)=\left({\frac {1}{C-1}}\right){\text{Gain}}_{i}(\sigma ^{*},a)=0$ ⓘ

und somit ist der linke Term Null, was bedeutet, dass der gesamte Ausdruck $0$ wie erforderlich. ⓘ

Wir haben also schließlich, dass ⓘ

${\begin{aligned}0&=u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*})\\&=\left(\sum _{a\in A_{i}}\sigma _{i}^{*}(a)u_{i}(a_{i},\sigma _{-i}^{*})\right)-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*})\\&=\sum _{a\in A_{i}}\sigma _{i}^{*}(a)(u_{i}(a_{i},\sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*}))\\&=\sum _{a\in A_{i}}\sigma _{i}^{*}(a){\text{Gain}}_{i}(\sigma ^{*},a)&&{\text{ by the previous statements }}\\&=\sum _{a\in A_{i}}\left(C-1\right)\sigma _{i}^{*}(a)^{2}>0\end{aligned}}$ ⓘ

wobei die letzte Ungleichung folgt, da $\sigma _{i}^{*}$ ein Nicht-Null-Vektor ist. Dies ist jedoch ein klarer Widerspruch, so dass alle Gewinne tatsächlich Null sein müssen. Daher $\sigma ^{*}$ ein Nash-Gleichgewicht für $G$ wie erforderlich. ⓘ

Berechnung von Nash-Gleichgewichten

Wenn ein Spieler A eine dominante Strategie hat $s_{A}$ dann gibt es ein Nash-Gleichgewicht, in dem A spielt $s_{A}$. Bei zwei Spielern A und B gibt es ein Nash-Gleichgewicht, bei dem A spielt $s_{A}$ spielt und B eine beste Antwort auf $s_{A}$. Wenn $s_{A}$ eine streng dominante Strategie ist, spielt A $s_{A}$ in allen Nash-Gleichgewichten. Wenn sowohl A als auch B streng dominante Strategien haben, gibt es ein einziges Nash-Gleichgewicht, in dem jeder seine streng dominante Strategie spielt. ⓘ

Bei Spielen mit Nash-Gleichgewichten mit gemischten Strategien kann die Wahrscheinlichkeit, dass ein Spieler eine bestimmte (also reine) Strategie wählt, berechnet werden, indem jeder Strategie eine Variable zugewiesen wird, die eine feste Wahrscheinlichkeit für die Wahl dieser Strategie darstellt. Damit ein Spieler bereit ist, zu randomisieren, sollte seine erwartete Auszahlung für jede (reine) Strategie gleich sein. Darüber hinaus sollte die Summe der Wahrscheinlichkeiten für jede Strategie eines bestimmten Spielers gleich 1 sein. Daraus ergibt sich ein Gleichungssystem, aus dem die Wahrscheinlichkeiten für die Wahl jeder Strategie abgeleitet werden können. ⓘ

Beispiele

Zusammenpassen von Pfennigen

Strategie	Spieler B spielt H	Spieler B spielt T ⓘ
Spieler A spielt H	−1, +1	+1, −1
Spieler A spielt T	+1, −1	−1, +1

Im Matching-Pennies-Spiel verliert Spieler A einen Punkt an B, wenn A und B die gleiche Strategie spielen, und gewinnt einen Punkt von B, wenn sie unterschiedliche Strategien spielen. Um das Nash-Gleichgewicht mit gemischten Strategien zu berechnen, weist man A die Wahrscheinlichkeit p zu, H zu spielen und (1-p), T zu spielen, und weist B die Wahrscheinlichkeit q zu, H zu spielen und (1-q), T zu spielen. ⓘ

$${\begin{aligned}&\mathbb {E} [{\text{payoff for A playing H}}]=(-1)q+(+1)(1-q)=1-2q\\&\mathbb {E} [{\text{payoff for A playing T}}]=(+1)q+(-1)(1-q)=2q-1\\&\mathbb {E} [{\text{payoff for A playing H}}]=\mathbb {E} [{\text{payoff for A playing T}}]\implies 1-2q=2q-1\implies q=1/2\\&\mathbb {E} [{\text{payoff for B playing H}}]=(+1)p+(-1)(1-p)=2p-1\\&\mathbb {E} [{\text{payoff for B playing T}}]=(-1)p+(+1)(1-p)=1-2p\\&\mathbb {E} [{\text{payoff for B playing H}}]=\mathbb {E} [{\text{payoff for B playing T}}]\implies 2p-1=1-2p\implies p=1/2\\\end{aligned}}$$

ⓘ

Ein Nash-Gleichgewicht mit gemischten Strategien besteht in diesem Spiel also darin, dass jeder Spieler zufällig H oder T mit p = 1/2 und q = 1/2 wählt. ⓘ

Unregelmäßigkeit der Gleichgewichtspunkte

1971 stellte Robert Wilson das Ungeradheitstheorem auf, das besagt, dass "fast alle" endlichen Spiele eine endliche und ungerade Anzahl von Nash-Gleichgewichten haben. Im Jahr 1993 veröffentlichte Harsanyi einen alternativen Beweis für dieses Ergebnis. "Fast alle" bedeutet hier, dass jedes Spiel mit einer unendlichen oder geraden Anzahl von Gleichgewichten in dem Sinne etwas Besonderes ist, dass es, wenn seine Auszahlungen auch nur geringfügig zufällig gestört werden, mit Wahrscheinlichkeit 1 stattdessen eine ungerade Anzahl von Gleichgewichten aufweisen würde. ⓘ

Spiel um freies Geld

Strategie	Spieler B stimmt mit Ja	Spieler B stimmt mit Nein ⓘ
Spieler A stimmt mit Ja	1, 1	0, 0
Spieler A stimmt mit Nein	0, 0	0, 0

Beim Gefangenendilemma gibt es beispielsweise nur ein Gleichgewicht, während es beim Kampf der Geschlechter drei Gleichgewichte gibt - zwei reine und ein gemischtes, und das bleibt auch dann so, wenn sich die Auszahlungen leicht ändern. Das Freigeldspiel ist ein Beispiel für ein "spezielles" Spiel mit einer geraden Anzahl von Gleichgewichten. Bei diesem Spiel müssen zwei Spieler beide mit "Ja" statt mit "Nein" stimmen, um eine Belohnung zu erhalten, und die Abstimmungen erfolgen gleichzeitig. Es gibt zwei Nash-Gleichgewichte mit reinen Strategien, (ja, ja) und (nein, nein), und keine Gleichgewichte mit gemischten Strategien, weil die Strategie "ja" die Strategie "nein" schwach dominiert. "Ja" ist so gut wie "Nein", unabhängig von der Aktion des anderen Spielers, aber wenn die Möglichkeit besteht, dass der andere Spieler "Ja" wählt, ist "Ja" die beste Antwort. Bei einer kleinen zufälligen Störung der Auszahlungen ist die Wahrscheinlichkeit, dass zwei Auszahlungen gleich bleiben, sei es bei 0 oder einer anderen Zahl, verschwindend gering, und das Spiel würde stattdessen ein oder drei Gleichgewichte aufweisen. ⓘ

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