In der Spieltheorie ist Gleichgewicht von Nash (genannt nach John Forbes Nash, der es vorgeschlagen hat) ein Lösungskonzept eines Spiels, das mit zwei oder mehr Spielern verbunden ist, in denen, wie man annimmt, jeder Spieler die Gleichgewicht-Strategien der anderen Spieler weiß, und kein Spieler irgendetwas hat, um zu gewinnen, indem er nur seine eigene Strategie einseitig ändert. Wenn jeder Spieler eine Strategie gewählt hat und kein Spieler Vorteil haben kann, indem er seine oder ihre Strategie ändert, während die anderen Spieler ihrige unverändert halten, dann setzt der aktuelle Satz von Strategie-Wahlen und den entsprechenden Belohnungen ein Gleichgewicht von Nash ein. Die praktische und allgemeine Implikation ist, dass, wenn Spieler auch in den Interessen der Gruppe dann handeln, sie aus besser sind, als wenn sie in ihren individuellen Interessen allein gehandelt haben.

Festgesetzt einfach sind Amy und Phil im Gleichgewicht von Nash, wenn Amy die beste Entscheidung trifft, kann sie, die Entscheidung von Phil in Betracht ziehend, und Phil trifft die beste Entscheidung er kann, die Entscheidung von Amy in Betracht ziehend. Ebenfalls, eine Gruppe von Spielern sind im Gleichgewicht von Nash, wenn jeder die beste Entscheidung trifft, dass er oder sie kann, die Entscheidungen von anderen in Betracht ziehend. Jedoch bedeutet Gleichgewicht von Nash nicht notwendigerweise, dass die beste Belohnung für alle Spieler eingeschlossen hat; in vielen Fällen könnten alle Spieler ihre Belohnungen verbessern, wenn sie sich irgendwie über vom Gleichgewicht von Nash verschiedene Strategien einigen konnten: Z.B, konkurrierende Geschäfte, die ein Kartell bilden, um ihre Gewinne zu vergrößern.

Anwendungen

Spieltheoretiker verwenden das Gleichgewicht-Konzept von Nash, um das Ergebnis der strategischen Wechselwirkung von mehreren Entscheidungsträgern zu analysieren. Mit anderen Worten stellt es eine Weise zur Verfügung vorauszusagen, was geschehen wird, wenn mehrere Menschen oder mehrere Einrichtungen Entscheidungen zur gleichen Zeit treffen, und wenn das Ergebnis von den Entscheidungen von anderen abhängt. Die einfache Scharfsinnigkeit, die der Idee von John Nash unterliegt, ist, dass wir das Ergebnis der Wahlen von vielfachen Entscheidungsträgern nicht voraussagen können, wenn wir jene Entscheidungen in der Isolierung analysieren. Statt dessen müssen wir fragen, was jeder Spieler tun würde, die Beschlussfassung von anderen in Betracht ziehend.

Gleichgewicht von Nash ist verwendet worden, um feindliche Situationen wie Kriegs- und Wettrüsten zu analysieren (sieh das Dilemma des Gefangenen), und auch wie Konflikt durch die wiederholte Wechselwirkung gelindert werden kann (sieh Mit gleicher Münze). Es ist auch verwendet worden, um zu studieren, inwieweit Leute mit verschiedenen Einstellungen zusammenarbeiten können (sieh Kampf der Geschlechter), und ob sie Risikos eingehen werden, um ein kooperatives Ergebnis zu erreichen (sieh Herrenjagd). Es ist verwendet worden, um die Adoption von technischen Standards und auch das Ereignis von Bankläufen und Währungskrisen zu studieren (sieh Koordinationsspiel). Andere Anwendungen schließen Verkehrsfluss ein (sieh den Grundsatz von Wardrop), wie man Versteigerungen organisiert (sieh Versteigerungstheorie), das Ergebnis von Anstrengungen, die von vielfachen Parteien im Ausbildungsprozess und sogar den Elfmetern im Fußball ausgeübt sind (sieh das Zusammenbringen von Pennies).

Geschichte

Eine Version des Gleichgewicht-Konzepts von Nash wurde zuerst von Antoine Augustin Cournot in seiner Theorie von oligopoly (1838) verwendet. In der Theorie von Cournot wählen Unternehmen wie viel Produktion, um zu erzeugen, um ihren eigenen Gewinn zu maximieren. Jedoch hängt die beste Produktion für ein Unternehmen von den Produktionen von anderen ab. Ein Gleichgewicht von Cournot kommt vor, wenn die Produktion jedes Unternehmens seine Gewinne gegeben die Produktion der anderen Unternehmen maximiert, die eine reine Strategie Nash Equilibrium ist.

Das moderne spieltheoretische Konzept von Nash Equilibrium wird stattdessen in Bezug auf Mischstrategien definiert, wo Spieler einen Wahrscheinlichkeitsvertrieb über mögliche Handlungen wählen. Das Konzept der Mischstrategie Nash Equilibrium wurde von John von Neumann und Oskar Morgenstern ihren 1944 vorgestellt, bestellt Die Theorie von Spielen und Wirtschaftsverhalten vor. Jedoch wurde ihre Analyse auf den speziellen Fall von Nullsumme-Spielen eingeschränkt. Sie haben gezeigt, dass eine Mischstrategie Nash Equilibrium für jedes Nullsumme-Spiel mit einem begrenzten Satz von Handlungen bestehen wird. Der Beitrag von John Forbes Nash in seinem 1951-Artikel Non-Cooperative Games sollte eine Mischstrategie Nash Equilibrium für jedes Spiel mit einem begrenzten Satz von Handlungen definieren und beweisen, dass mindestens ein (Mischstrategie) Nash Equilibrium in solch einem Spiel bestehen müssen.

Seit der Entwicklung des Gleichgewicht-Konzepts von Nash haben Spieltheoretiker entdeckt, dass es irreführende Vorhersagen macht (oder scheitert, eine einzigartige Vorhersage zu machen), in bestimmten Fällen. Deshalb haben sie vorgeschlagen, dass viele zusammenhängende Lösungskonzepte (auch genannt 'Verbesserungen' des Gleichgewichts von Nash) vorgehabt haben, wahrgenommene Fehler im Konzept von Nash zu überwinden. Ein besonders wichtiges Problem ist, dass etwas Gleichgewicht von Nash auf Drohungen basieren kann, die nicht 'glaubwürdig' sind. Deshalb 1965 hat Reinhard Selten Subspiel vollkommenes Gleichgewicht als eine Verbesserung vorgeschlagen, die Gleichgewicht beseitigt, das von nichtglaubwürdigen Drohungen abhängt. Andere Erweiterungen des Gleichgewicht-Konzepts von Nash haben gerichtet, was geschieht, wenn ein Spiel wiederholt wird, oder was geschieht, wenn ein Spiel ohne vollkommene Information gespielt wird. Jedoch teilen nachfolgende Verbesserungen und Erweiterungen des Gleichgewicht-Konzepts von Nash die Hauptscharfsinnigkeit, auf der sich das Konzept von Nash ausruht: alle Gleichgewicht-Konzepte analysieren, was Wahlen gemacht werden, wenn jeder Spieler die Beschlussfassung von anderen in Betracht zieht.

Definitionen

Informelle Definition

Informell, eine Reihe von Strategien ist ein Gleichgewicht von Nash, wenn kein Spieler besser tun kann, indem er seine oder ihre Strategie einseitig ändert. Um zu sehen, was das bedeutet, stellen Sie sich vor, dass jedem Spieler die Strategien von anderen erzählt werden. Nehmen Sie dann an, dass jeder Spieler sich oder sie fragt: Wenn ich die Strategien der anderen Spieler weiß, und die Strategien der anderen Spieler, wie gesetzt, im Stein behandelt, kann ich Vorteil haben, indem ich meine Strategie ändere?"

Wenn ein Spieler auf "Ja" antworten würde, dann ist dieser Satz von Strategien nicht ein Gleichgewicht von Nash. Aber wenn jeder Spieler es vorzieht nicht umzuschalten (oder zwischen der Schaltung und gleichgültig ist nicht) dann, ist der Satz von Strategien ein Gleichgewicht von Nash. So ist jede Strategie in einem Gleichgewicht von Nash eine beste Antwort auf alle anderen Strategien in diesem Gleichgewicht.

Das Gleichgewicht von Nash kann manchmal nichtvernünftig in einer Perspektive der dritten Person scheinen. Das ist, weil es geschehen kann, dass ein Gleichgewicht von Nash nicht optimaler Pareto ist.

Das Gleichgewicht von Nash kann auch nichtvernünftige Folgen in folgenden Spielen haben, weil Spieler einander mit nichtvernünftigen Bewegungen "drohen" können. Für solche Spiele das Subspiel kann vollkommenes Gleichgewicht von Nash als ein Werkzeug der Analyse bedeutungsvoller sein.

Formelle Definition

Let (S, f), ein Spiel mit n Spielern sein, wo S der Strategie-Satz für den Spieler i, S=S &times ist; S... × S ist der Satz von Strategie-Profilen, und f = (f (x)..., f (x)) ist die Belohnungsfunktion für x S. Let x, ein Strategie-Profil des Spielers i und x sein, ein Strategie-Profil aller Spieler abgesehen vom Spieler i sein. Wenn jeder Spieler i Strategie x wählt, die auf Strategie-Profil x = (x..., x) dann hinausläuft, erhält Spieler i Belohnung f (x). Bemerken Sie, dass die Belohnung vom Strategie-Profil gewählt, d. h. auf der Strategie abhängt, die vom Spieler i sowie den von allen anderen Spielern gewählten Strategien gewählt ist. Ein Strategie-Profil x S ist ein Gleichgewicht von Nash (NE), wenn keine einseitige Abweichung in der Strategie von einem einzelnem Spieler für diesen Spieler gewinnbringend ist, der ist

:

Ein Spiel kann entweder eine reine Strategie oder einen Nash Mischequilibrium haben, (in den Letzteren eine reine Strategie wird stochastisch mit einer festen Frequenz gewählt). Nash hat bewiesen, dass, wenn wir gemischte Strategien dann erlauben, jedes Spiel mit einer begrenzten Zahl von Spielern, in denen jeder Spieler aus begrenzt vielen reinen Strategien wählen kann, mindestens ein Gleichgewicht von Nash hat.

Wenn die Ungleichheit oben ausschließlich (mit statt) für alle Spieler und alle ausführbaren alternativen Strategien hält, dann wird das Gleichgewicht als ein strenges Gleichgewicht von Nash klassifiziert. Wenn statt dessen für einen Spieler es genaue Gleichheit zwischen und eine andere Strategie im Satz gibt, dann wird das Gleichgewicht als ein schwaches Gleichgewicht von Nash klassifiziert.

Beispiele

Koordinationsspiel

Das Koordinationsspiel ist ein klassischer (symmetrischer) zwei Spieler, zwei Strategie-Spiel, mit einer Beispiel-Belohnungsmatrix gezeigt nach rechts. Die Spieler sollten so, beide Übernehmen-Strategie A koordinieren, um die höchste Belohnung zu erhalten; d. h., 4. Wenn beide Spieler Strategie B obwohl gewählt haben, gibt es noch ein Gleichgewicht von Nash. Obwohl jeder Spieler weniger zuerkannt wird als optimale Belohnung, hat kein Spieler Ansporn, Strategie wegen der Verminderung der unmittelbaren Belohnung (von 2 bis 1) zu ändern.

Ein berühmtes Beispiel dieses Typs des Spiels wurde die Herrenjagd genannt; im Spiel können zwei Spieler beschließen, einen Hirsch oder ein Kaninchen, der erstere zu jagen, mehr Fleisch (4 Dienstprogramm-Einheiten) zur Verfügung stellend, als die Letzteren (1 Dienstprogramm-Einheit). Die Verwahrung besteht darin, dass der Hirsch so kooperativ gejagt werden muss, wenn ein Spieler versucht, den Hirsch zu jagen, während die anderen Jagden das Kaninchen, er in der Jagd scheitern wird (0 Dienstprogramm-Einheiten), wohingegen, wenn sie beide es jagen, sie die Nutzlast (2, 2) spalten werden. Das Spiel stellt folglich zwei Gleichgewicht an (Hirsch, Hirsch) aus und (Kaninchen, Kaninchen), und folglich hängt die optimale Strategie der Spieler von ihrer Erwartung davon ab, was der andere Spieler tun kann. Wenn ein Jäger glaubt, dass der andere den Hirsch jagen wird, sollte er den Hirsch jagen; jedoch, wenn er vermutet, dass der andere das Kaninchen jagen wird, sollte er das Kaninchen jagen. Dieses Spiel wurde als eine Analogie für die soziale Zusammenarbeit verwendet, da viel vom Vorteil, den Leute in der Gesellschaft gewinnen, von Leuten abhängt, die zusammenarbeiten und implizit einander vertrauen, um gewissermaßen entsprechend mit der Zusammenarbeit zu handeln.

Ein anderes Beispiel eines Koordinationsspiels ist die Einstellung, wo zwei Technologien für zwei Unternehmen mit vereinbaren Produkten verfügbar sind, und sie eine Strategie wählen müssen, der Marktstandard zu werden. Wenn sich beide Unternehmen über die gewählte Technologie einigen, werden hohe Verkäufe für beide Unternehmen erwartet. Wenn sich die Unternehmen über die Standardtechnologie, weniges Verkaufsergebnis nicht einigen. Beide Strategien sind Gleichgewicht von Nash des Spiels.

Das Vorantreiben einer Straße und die Notwendigkeit zu beschließen, entweder links zu fahren oder rechts von der Straße zu fahren, sind auch ein Koordinationsspiel. Zum Beispiel, mit Belohnungen 100 Bedeutung kein Unfall und 0 Bedeutung ein Unfall, kann das Koordinationsspiel mit der folgenden Belohnungsmatrix definiert werden:

In diesem Fall gibt es zwei reine Strategie Gleichgewicht von Nash, wenn beide beschließen, links oder rechts entweder zu fahren. Wenn wir gemischte Strategien zulassen (wo eine reine Strategie aufs Geratewohl, Thema etwas fester Wahrscheinlichkeit gewählt wird), dann gibt es drei Gleichgewicht von Nash für denselben Fall: Zwei haben wir von der Form der reinen Strategie gesehen, wo die Wahrscheinlichkeiten (0 %, 100 %) für den Spieler ein, (0 %, 100 %) für den Spieler zwei sind; und (100 %, 0 %) für den Spieler ein, (100 %, 0 %) für den Spieler zwei beziehungsweise. Wir fügen einen anderen hinzu, wo die Wahrscheinlichkeiten für jeden Spieler (50 %, 50 %) sind.

Das Dilemma des Gefangenen

(bemerken Sie Unterschiede in der Orientierung der Belohnungsmatrix)

Das Dilemma des Gefangenen hat dieselbe Belohnungsmatrix, wie gezeichnet, für das Koordinationsspiel, aber jetzt C> A> D> B. Weil C> A und D> B, jeder Spieler seine Situation verbessert, indem er aus der Strategie #1 zur Strategie #2 umschaltet, egal was der andere Spieler entscheidet. Das Dilemma des Gefangenen hat so einen einzelnen Nash Equilibrium: Beide Spieler, die Strategie #2 ("Defekt") wählen. Was lange das gemacht hat, ist ein interessanter Fall, um zu studieren, die Tatsache, dass D die Zahl von Autos ist, die über diesen Rand reisen.]]

Eine Anwendung des Gleichgewichts von Nash ist in der Bestimmung des erwarteten Verkehrsstroms in einem Netz. Denken Sie den Graphen rechts. Wenn wir annehmen, dass dort reisen "Autos" von bis D, wie ist der erwartete Vertrieb des Verkehrs im Netz?

Diese Situation kann als ein "Spiel" modelliert werden, wo jeder Reisende eine Wahl von 3 Strategien hat, wo jede Strategie ein Weg von bis D (entweder, oder) ist. Die "Belohnung" jeder Strategie ist die Fahrzeit jedes Wegs. Im Graphen rechts, ein Auto, das über die Erfahrungsfahrzeit dessen reist, wo die Zahl von Autos ist, die am Rand reisen. So hängen Belohnungen für jede gegebene Strategie von den Wahlen der anderen Spieler ab, wie üblich ist. Jedoch ist die Absicht in diesem Fall, Fahrzeit zu minimieren, sie nicht zu maximieren. Gleichgewicht wird vorkommen, wenn die Zeit auf allen Pfaden genau dasselbe ist. Wenn das geschieht, hat kein einzelner Fahrer jeden Ansporn, Wege zu schalten, da er nur zu seiner/ihrer Fahrzeit beitragen kann. Für den Graphen rechts, wenn, zum Beispiel, 100 Autos von bis D reisen, dann wird Gleichgewicht vorkommen, wenn 25 Fahrer über, 50 über, und 25 darüber reisen. Jeder Fahrer hat jetzt eine Gesamtfahrzeit 3.75.

Bemerken Sie, dass dieser Vertrieb wirklich nicht, sozial optimal ist. Wenn die 100 Autos zugäben, dass 50 Reisen über und die anderen 50 durch, dann würde die Fahrzeit für jedes einzelne Auto wirklich 3.5 sein, der weniger als 3.75 ist. Das ist auch das Gleichgewicht von Nash, wenn der Pfad zwischen B und C entfernt wird, was bedeutet, dass das Hinzufügen eines zusätzlichen möglichen Wegs die Leistungsfähigkeit des Systems, ein als das Paradox von Braess bekanntes Phänomen vermindern kann.

Konkurrenz-Spiel

Das kann durch ein Zwei-Spieler-Spiel illustriert werden, in dem beide Spieler gleichzeitig eine ganze Zahl von 0 bis 3 wählen und sie beide die kleineren von den zwei Zahlen in Punkten gewinnen. Außerdem, wenn ein Spieler eine größere Zahl wählt als der andere, dann muss er/sie zwei Punkte zum anderen aufgeben.

Dieses Spiel hat eine einzigartige reine Strategie Gleichgewicht von Nash: Beide Spieler, die 0 (hervorgehoben im Hellrot) wählen. Jede andere Wahl von Strategien kann verbessert werden, wenn einer der Spieler seine Zahl zu einer weniger senkt als die Zahl des anderen Spielers. Im Tisch nach rechts, zum Beispiel, wenn es am grünen Quadrat anfängt, ist es im Spieler 1 interessieren, sich zum purpurroten Quadrat durch die Auswahl einer kleineren Zahl zu bewegen, und es ist im Spieler 2 interessieren, sich zum blauen Quadrat durch die Auswahl einer kleineren Zahl zu bewegen. Wenn das Spiel modifiziert wird, so dass die zwei Spieler den genannten Betrag gewinnen, wenn sie beide dieselbe Zahl wählen, und sonst nichts gewinnen, dann gibt es 4 Gleichgewicht von Nash (0,0... 1,1... 2,2... und 3,3).

Gleichgewicht von Nash in einer Belohnungsmatrix

Es gibt eine leichte numerische Weise, Gleichgewicht von Nash auf einer Belohnungsmatrix zu identifizieren. Es ist in Zwei-Personen-Spielen besonders nützlich, wo Spieler mehr als zwei Strategien haben. In diesem Fall kann formelle Analyse zu lang werden. Diese Regel gilt für den Fall, wo gemischt, nicht (stochastische) Strategien sind von Interesse. Die Regel geht wie folgt: Wenn die erste Belohnungszahl, im duplet der Zelle, das Maximum der Säule der Zelle ist, und wenn die zweite Zahl das Maximum der Reihe der Zelle - dann ist, vertritt die Zelle ein Gleichgewicht von Nash.

Wir können diese Regel auf 3×3 Matrix anwenden:

Mit der Regel können wir sehr schnell (viel schneller als mit der formellen Analyse) sehen, dass die Zellen von Nash Equilibria (B, A), (A, B), und (C, C) sind. Tatsächlich, für die Zelle (B, A) 40 ist das Maximum der ersten Säule, und 25 ist das Maximum der zweiten Reihe. Für (A, B) 25 ist das Maximum der zweiten Säule, und 40 ist das Maximum der ersten Reihe. Dasselbe für die Zelle (C, C). Für andere Zellen, entweder ein oder beide der duplet Mitglieder sind nicht das Maximum der entsprechenden Reihen und Säulen.

Das, hat die wirkliche Mechanik gesagt zu finden, dass Gleichgewicht-Zellen offensichtlich sind: Finden Sie das Maximum einer Säule und Kontrolle, wenn das zweite Mitglied des Paares das Maximum der Reihe ist. Wenn diese Bedingungen entsprochen werden, vertritt die Zelle ein Gleichgewicht von Nash. Überprüfen Sie alle Säulen diese Weise, alle NE Zellen zu finden. Eine N×N Matrix kann zwischen 0 und N×N reine Strategie Gleichgewicht von Nash haben.

Stabilität

Das Konzept der Stabilität, die in der Analyse von vielen Arten des Gleichgewichts nützlich ist, kann auch auf das Gleichgewicht von Nash angewandt werden.

Ein Gleichgewicht von Nash für ein Mischstrategie-Spiel ist stabil, wenn ein Kleingeld (spezifisch, eine unendlich kleine Änderung) in Wahrscheinlichkeiten für einen Spieler zu einer Situation führt, wo zwei Bedingungen halten:

1. der Spieler, der sich nicht geändert hat, hat keine bessere Strategie im neuen Umstand
2. der Spieler, der sich wirklich geändert hat, spielt jetzt mit einer ausschließlich schlechteren Strategie.

Wenn diese Fälle beide entsprochen werden, dann wird ein Spieler mit dem Kleingeld in seiner Mischstrategie sofort zum Gleichgewicht von Nash zurückkehren. Wie man sagt, ist das Gleichgewicht stabil. Wenn Bedingung man hält dann das Gleichgewicht nicht, nicht stabil ist. Wenn nur Bedingung, die man dann hält, es wahrscheinlich eine unendliche Zahl von optimalen Strategien für den Spieler geben wird, der sich geändert hat. John Nash hat gezeigt, dass die letzte Situation in einer Reihe von bestimmten Spielen nicht entstehen konnte.

Im "" Fahrspielbeispiel oben gibt es sowohl stabiles als auch nicht stabiles Gleichgewicht. Das Gleichgewicht, das Mischstrategien mit 100-%-Wahrscheinlichkeiten einschließt, ist stabil. Wenn jeder Spieler seine Wahrscheinlichkeiten ein bisschen ändert, werden sie sowohl an einem Nachteil sein, als auch sein Gegner wird keinen Grund haben, seine Strategie der Reihe nach zu ändern. (50 %, 50 %) Gleichgewicht ist nicht stabil. Wenn jeder Spieler seine Wahrscheinlichkeiten ändert, dann hat der andere Spieler sofort eine bessere Strategie an irgendeinem (0 %, 100 %) oder (100 %, 0 %).

Stabilität ist in praktischen Anwendungen des Gleichgewichts von Nash entscheidend, da die Mischstrategie jedes Spielers nicht vollkommen bekannt ist, aber aus dem statistischen Vertrieb seiner Handlungen im Spiel abgeleitet werden muss. In diesem Fall wird nicht stabiles Gleichgewicht kaum in der Praxis entstehen, da jede Minutenänderung in den Verhältnissen jeder gesehenen Strategie zu einer Änderung in der Strategie und der Depression des Gleichgewichts führen wird.

Das Gleichgewicht von Nash definiert Stabilität nur in Bezug auf einseitige Abweichungen. In kooperativen Spielen überzeugt solch ein Konzept genug nicht. Starkes Gleichgewicht von Nash berücksichtigt Abweichungen durch jede denkbare Koalition. Formell ist ein Starkes Gleichgewicht von Nash ein Gleichgewicht von Nash, in dem keine Koalition, die Handlungen seiner Ergänzungen, wie gegeben, nehmend, in einem Weg der Vorteile alle seine Mitglieder kooperativ abgehen kann. Jedoch wird das Starke Konzept von Nash manchmal als "zu stark" darin wahrgenommen die Umgebung berücksichtigt unbegrenzte private Kommunikation. Tatsächlich muss Starkes Gleichgewicht von Nash effizienter Pareto sein. Infolge dieser Voraussetzungen ist Starker Nash zu selten, um in vielen Zweigen der Spieltheorie nützlich zu sein. Jedoch, in Spielen wie Wahlen mit noch vielen Spielern als mögliche Ergebnisse, kann es üblicher sein als ein stabiles Gleichgewicht.

Ein raffiniertes als Koalitionsbeweis Gleichgewicht von Nash (CPNE) bekanntes Gleichgewicht von Nash kommt vor, wenn Spieler besser nicht tun können, selbst wenn ihnen erlaubt wird, "Selbsterzwingen"-Abmachung zu kommunizieren und zu machen, abzugehen. Jede aufeinander bezogene Strategie, die durch die wiederholte strenge Überlegenheit und an der Grenze von Pareto unterstützt ist, ist ein CPNE. Weiter ist es für ein Spiel möglich, ein Gleichgewicht von Nash zu haben, das gegen Koalitionen weniger als eine angegebene Größe, k elastisch ist. CPNE ist mit der Theorie des Kerns verbunden.

Schließlich in den achtziger Jahren mit der großen Tiefe auf solchen Ideen bauend, wurde Mertens-stabiles Gleichgewicht als ein Lösungskonzept eingeführt. Mertens stabiles Gleichgewicht befriedigen sowohl Vorwärtsinduktion als auch rückwärts gerichtete Induktion. In einem Spieltheorie-Zusammenhang verweist stabiles Gleichgewicht jetzt gewöhnlich auf Mertens stabiles Gleichgewicht.

Ereignis

Wenn ein Spiel ein einzigartiges Gleichgewicht von Nash hat und unter Spielern unter bestimmten Bedingungen gespielt wird, dann wird der NE Strategie-Satz angenommen. Genügend Bedingungen zu versichern, dass das Gleichgewicht von Nash gespielt wird, sind:

1. Die Spieler werden alle ihr Äußerstes tun, um ihre erwartete Belohnung, wie beschrieben, durch das Spiel zu maximieren.
2. Die Spieler sind in der Ausführung fehlerfrei.
3. Die Spieler haben genügend Intelligenz, um die Lösung abzuleiten.
4. Die Spieler wissen die geplante Gleichgewicht-Strategie von allen anderen Spielern.
5. Die Spieler glauben, dass eine Abweichung in ihrer eigenen Strategie Abweichungen durch keine anderen Spieler verursachen wird.
6. Dort ist allgemein bekannt, dass alle Spieler diese Bedingungen, einschließlich dieses entsprechen. Also, nicht nur muss jeder Spieler wissen, dass die anderen Spieler die Bedingungen entsprechen, sondern auch sie müssen wissen, dass sie alle wissen, dass sie sie treffen und wissen, dass sie wissen, dass sie wissen, dass sie sie und so weiter treffen.

Wo die Bedingungen nicht entsprochen werden

Beispiele von Spieltheorie-Problemen, in denen diese Bedingungen nicht entsprochen werden:

1. Die erste Bedingung wird nicht entsprochen, wenn das Spiel die Mengen nicht richtig beschreibt, möchte ein Spieler maximieren. In diesem Fall gibt es keinen besonderen Grund für diesen Spieler, eine Gleichgewicht-Strategie anzunehmen. Zum Beispiel ist das Dilemma des Gefangenen nicht ein Dilemma, wenn jeder Spieler glücklich ist, unbestimmt eingesperrt zu werden.
2. Absichtlicher oder zufälliger Schönheitsfehler in der Ausführung. Zum Beispiel wird ein Computer, der zum fehlerfreien logischen Spiel fähig ist, das einem zweiten fehlerfreien Computer gegenübersteht, auf Gleichgewicht hinauslaufen. Die Einführung des Schönheitsfehlers wird zu seiner Störung entweder durch den Verlust gegen den Spieler führen, der den Fehler, oder durch die Ablehnung des Kriteriums der Binsenweisheit macht, das zu möglichem Sieg für den Spieler führt. (Ein Beispiel würde ein Spieler sein, der plötzlich das Auto in die Rückseite im Spiel des Huhnes stellt, ein Drehbuch ohne Verluste ohne Gewinne sichernd).
3. In vielen Fällen wird die dritte Bedingung nicht entsprochen, weil, wenn auch das Gleichgewicht bestehen muss, es wegen der Kompliziertheit des Spiels zum Beispiel im chinesischen Schach unbekannt ist. Oder, wenn bekannt, darf es nicht allen Spielern, als bekannt sein, wenn man tic-tac-toe mit einem kleinen Kind spielt, das verzweifelt (das Entsprechen den anderen Kriterien) gewinnen will.
4. Dem Kriterium der Binsenweisheit darf nicht entsprochen werden, selbst wenn alle Spieler wirklich tatsächlich allen anderen Kriterien entsprechen. Spieler, die falsch jeder Vernunft eines anderen misstrauen, können Gegenstrategien zum erwarteten vernunftwidrigen Spiel im Interesse ihrer Gegner annehmen. Das ist eine Hauptrücksicht im "Huhn" oder ein Wettrüsten zum Beispiel.

Wo die Bedingungen entsprochen werden

Wegen der beschränkten Bedingungen, in denen NE wirklich beobachtet werden kann, werden sie als ein Handbuch zum täglichen Verhalten selten behandelt, oder in der Praxis in menschlichen Verhandlungen beobachtet. Jedoch, als ein theoretisches Konzept in der Volkswirtschaft und Entwicklungsbiologie hat der NE erklärende Macht. Die Belohnung in der Volkswirtschaft ist Dienstprogramm (oder manchmal Geld), und in der Entwicklungsbiologie-Genübertragung, beide sind das grundsätzliche Endergebnis des Überlebens. Forscher, die Spieltheorie in diesen Feldern anwenden, behaupten, dass Strategien, die scheitern, diese aus beliebigem Grund zu maximieren, aus dem Markt oder der Umgebung beworben werden, die die Fähigkeit zugeschrieben werden, alle Strategien zu prüfen. Dieser Schluss wird aus der "Stabilitäts"-Theorie oben gezogen. In diesen Situationen ist die Annahme, dass die beobachtete Strategie wirklich ein NE ist, häufig durch die Forschung unterstützt worden.

NE und nichtglaubwürdige Drohungen

Das Gleichgewicht von Nash ist eine Obermenge des Subspiels vollkommenes Gleichgewicht von Nash. Das vollkommene Gleichgewicht des Subspiels zusätzlich zum Gleichgewicht von Nash verlangt, dass die Strategie auch ein Gleichgewicht von Nash in jedem Subspiel dieses Spiels ist. Das beseitigt alle nichtglaubwürdigen Drohungen, d. h. Strategien, die nichtvernünftige Bewegungen enthalten, um die Gegenspieler-Änderung seine Strategie vorzunehmen.

Das Image zum Recht zeigt ein einfaches folgendes Spiel, das das Problem mit dem Subspielimperfekt Gleichgewicht von Nash illustriert. In diesem Spielspieler wählt man verlassen (L) oder Recht (R), dem vom Spieler zwei gefolgt wird besucht werden (K) freundlich oder (U) dem Spieler ein, Jedoch unfreundlich zu sein, gewinnt Spieler zwei nur davon mit Sicherheit, unfreundlich zu sein, wenn Spieler man verlassen geht. Wenn Spieler man geht Recht der vernünftige Spieler zwei, de facto zu ihm in diesem Subspiel freundlich sein würde. Jedoch ist Die nichtglaubwürdige Drohung, an 2 (2) unfreundlich zu sein, noch ein Teil des Blaus (L, (U, U)) Gleichgewicht von Nash. Deshalb, wenn vernünftiges Verhalten von beiden Parteien das Subspiel erwartet werden kann, kann vollkommenes Gleichgewicht von Nash ein bedeutungsvolleres Lösungskonzept sein, wenn solche dynamischen Widersprüchlichkeiten entstehen.

Beweis der Existenz

Der Beweis mit Kakutani hat Punkt-Lehrsatz befestigt

Der ursprüngliche Beweis von Nash (in seiner These) hat den festen Punkt-Lehrsatz von Brouwer verwendet (z.B, sieh unten für eine Variante). Wir geben einen einfacheren Beweis über Kakutani befestigter Punkt-Lehrsatz, im Anschluss an das 1950-Papier von Nash (er schreibt David Gale die Beobachtung zu, dass solch eine Vereinfachung möglich ist).

Um die Existenz eines Gleichgewichts von Nash zu beweisen, lassen Sie, die beste Antwort des Spielers i zu den Strategien aller anderen Spieler zu sein.

:

Hier, wo, ein Mischstrategie-Profil im Satz aller Mischstrategien ist und die Belohnungsfunktion für den Spieler i ist. Definieren Sie eine Satz-geschätzte solche Funktion dass. Die Existenz eines Gleichgewichts von Nash ist dazu gleichwertig, einen festen Punkt zu haben.

Der feste Punkt-Lehrsatz von Kakutani versichert die Existenz eines festen Punkts, wenn die folgenden vier Bedingungen zufrieden sind.

ist

1. kompakt, konvex, und nichtleer.

ist

1. nichtleer.

ist

1. konvex.
2. ist oberer hemicontinuous

Bedingung 1. ist von der Tatsache zufrieden, die ein Simplex und so kompakt ist. Konvexität folgt aus der Fähigkeit von Spielern, Strategien zu mischen. ist nichtleer, so lange Spieler Strategien haben.

Bedingung 2. ist zufrieden, weil Spieler erwartete Belohnungen maximieren, der dauernde Funktion über einen Kompaktsatz ist. Der Weierstrass Äußerste Wertlehrsatz versichert, dass es immer einen maximalen Wert gibt.

Bedingung 3. ist infolge Mischstrategien zufrieden. Denken Sie dann. d. h. wenn zwei Strategien Belohnungen maximieren, dann wird eine Mischung zwischen den zwei Strategien dieselbe Belohnung nachgeben.

Bedingung 4. ist über den maximalen Lehrsatz von Berge zufrieden. Weil dauernd und kompakt ist, ist oberer hemicontinuous.

Deshalb, dort besteht ein fester Punkt in und ein Gleichgewicht von Nash.

Als Nash dieses Argument John von Neumann 1949 angebracht hat, hat von Neumann es berühmt mit den Wörtern abgewiesen, "Es ist trivial, wissen Sie. Es ist gerade ein fester Punkt-Lehrsatz." (Sieh Nasar, 1998, p. 94.)

Abwechselnder Beweis mit dem Fixpunktsatz von Brouwer

Wir haben ein Spiel, wo die Zahl von Spielern und ist

ist der

Handlung ist für die Spieler untergegangen. Alle Handlungssätze sind begrenzt. Lassen Sie

zeigen Sie den Satz von Mischstrategien an

für die Spieler. Die Endlichkeit des s sichert die Kompaktheit dessen.

Wir können jetzt die Gewinn-Funktionen definieren. Für eine Mischstrategie lassen wir

der Gewinn für den Spieler auf der Handlung, sein

:

Die Gewinn-Funktion vertritt den Vorteil ein Spieler geht das einseitige Ändern seiner Strategie vorbei.

Wir definieren jetzt wo

:

dafür. Wir sehen das

:

1 + \sum_ {ein \in A_i} \text {Gewinn} _i (\sigma, a)> 0.\</Mathematik>

Wir verwenden jetzt, um wie folgt zu definieren.

Lassen Sie

:

f_i (\sigma) (a) = \frac {g_i (\sigma) (a)} {\\sum_ {b \in A_i} g_i (\sigma) (b) }\

</Mathematik>

dafür. Es ist leicht zu sehen, dass jeder eine gültige Mischstrategie darin ist. Es ist auch leicht zu überprüfen, dass jeder eine dauernde Funktion dessen ist, und folglich eine dauernde Funktion ist. Jetzt ist das Kreuzprodukt einer begrenzten Zahl von konvexen Kompaktsätzen, und so kommen wir, der auch kompakt und konvex ist. Deshalb können wir Brouwer befestigter Punkt-Lehrsatz darauf anwenden. So ein fester Punkt darin, nennen Sie es.

Ich behaupte, dass das ein Gleichgewicht von Nash darin ist. Für diesen Zweck genügt es, um dem zu zeigen

:

\forall 1 \leq i \leq N, ~ \forall ein \in A_i, ~ \text {Gewinn} _i (\sigma^ *, a) = 0 \text {. }\

</Mathematik>

Das stellt einfach fest, dass jeder Spieler keinen Vorteil gewinnt, indem er seine Strategie einseitig ändert, die genau der ist

notwendige Bedingung, um ein Gleichgewicht von Nash zu sein.

Nehmen Sie jetzt an, dass die Gewinne nicht die ganze Null sind. Deshalb, und

solch dass. Bemerken Sie dann das

:

\sum_ {ein \in A_i} g_i (\sigma^ *, a) = 1 + \sum_ {ein \in A_i} Gain_i (\sigma^ *, a)> 1.

</Mathematik>

So lassen Sie. Auch wir werden als der durch mit einem Inhaltsverzeichnis versehene Gewinn-Vektor anzeigen

Handlungen darin. Da wir klar das haben. Deshalb sehen wir das

:

\sigma^ * _ ich = \frac {g_i (\sigma^ *)} {\\sum_ {ein \in A_i} g_i (\sigma^ *) (a) }\

\Rightarrow

\sigma^ * _ ich = \frac {\\sigma^ * _ ich + \text {Gewinn} _i (\sigma^ *,\cdot)} {C }\

\Rightarrow

C\sigma^ * _ ich = \sigma^ * _ ich + \text {Gewinn} _i (\sigma^ *,\cdot)

</Mathematik>:

\left (C-1\right) \sigma^ * _ ich = \text {Gewinn} _i (\sigma^ *,\cdot)

\Rightarrow

\sigma^ * _ ich = \left (\frac {1} {c-1 }\\Recht) \text {Gewinn} _i (\sigma^ *,\cdot).

</Mathematik>

Da wir haben, der etwas positives Schuppen des Vektoren ist.

Jetzt fordere ich das

:

\sigma^ * _ ich (a) (u_i (a_i, \sigma^ *_ {-i}) - u_i (\sigma^ * _ ich, \sigma^ *_ {-i}))

\sigma^ * _ ich (a) \text {Gewinn} _i (\sigma^ *,)

</Mathematik>

. Um das zu sehen, bemerken wir zuerst das, wenn dann das definitionsgemäß des wahr

ist

Gewinn-Funktion. Nehmen Sie jetzt das an. Durch unsere vorherigen Behauptungen haben wir das

:

\sigma^ * _ ich (a) = \left (\frac {1} {c-1 }\\Recht) \text {Gewinn} _i (\sigma^ *, a) = 0

</Mathematik>

und so der linke Begriff Null ist, uns gebend, dass der komplette Ausdruck so erforderlich ist.

So haben wir schließlich das

:

0 = u_i (\sigma^ * _ ich, \sigma^ *_ {-i}) - u_i (\sigma^ * _ ich, \sigma^ *_ {-i})

</Mathematik>:

= \left (\sum_ {ein \in A_i} \sigma^ * _ ich (a) u_i (a_i, \sigma^ *_ {-i}) \right) - u_i (\sigma^ * _ ich, \sigma^ *_ {-i})

</Mathematik>:

= \sum_ {ein \in A_i} \sigma^ * _ ich (a) (u_i (a_i, \sigma^ *_ {-i}) - u_i (\sigma^ * _ ich, \sigma^ *_ {-i}))

</Mathematik>:

= \sum_ {ein \in A_i} \sigma^ * _ ich (a) \text {Gewinn} _i (\sigma^ *, a) \quad \text {durch die vorherigen Behauptungen }\

</Mathematik>:

= \sum_ {ein \in A_i} \left (C-1 \right) \sigma^ * _ ich (a) ^2> 0

</Mathematik>

wo die letzte Ungleichheit folgt, seitdem ist ein Nichtnullvektor. Aber das ist ein klarer Widerspruch,

so müssen alle Gewinne tatsächlich Null sein. Deshalb ist ein Gleichgewicht von Nash für, wie erforderlich.

Computerwissenschaft des Gleichgewichts von Nash

Wenn ein Spieler A eine dominierende Strategie dann hat, dort besteht ein Gleichgewicht von Nash in der Spiele. Im Fall von zwei Spielern A und B, dort besteht ein Gleichgewicht von Nash, in dem Spiele und B eine beste Antwort darauf spielt. Wenn eine ausschließlich dominierende Strategie, Spiele im ganzen Gleichgewicht von Nash ist. Wenn sowohl A als auch B ausschließlich dominierende Strategien haben, dort besteht ein einzigartiges Gleichgewicht von Nash, in dem jeder seine ausschließlich dominierende Strategie spielt.

In Spielen mit der Mischstrategie können Gleichgewicht von Nash, die Wahrscheinlichkeit eines Spielers, der jede besondere Strategie wählt, durch das Zuweisen einer Variable jeder Strategie geschätzt werden, die eine feste Wahrscheinlichkeit vertritt, um diese Strategie zu wählen. In der Größenordnung von einem Spieler, um zu randomize bereit zu sein, sollte seine erwartete Belohnung für jede Strategie dasselbe sein. Außerdem sollte die Summe der Wahrscheinlichkeiten für jede Strategie eines besonderen Spielers 1 sein. Das schafft ein Gleichungssystem, von dem die Wahrscheinlichkeiten, jede Strategie zu wählen, abgeleitet werden können.

Beispiele

Im zusammenpassenden Penny-Spiel verliert Spieler A einen Punkt zu B, wenn A und B dieselbe Strategie spielen und einen Punkt von B gewinnt, wenn sie verschiedene Strategien spielen. Um die Mischstrategie Gleichgewicht von Nash zu schätzen, teilen Sie die Wahrscheinlichkeit p zu, H und (1p) zu spielen, T zu spielen, und teilen Sie B die Wahrscheinlichkeit q zu, H und (1q) zu spielen, T zu spielen.

:E [Belohnung für Ein Spielen H] = (1) q + (+1) (1q) = 12q

:E [Belohnung für Ein Spielen T] = (+1) q + (1) (1q) = 2q1

:E [Belohnung für Ein Spielen H] = E [Belohnung für Ein Spielen T]  12q = 2q1  q = 1/2

:E [Belohnung für B, der H] = (+1) p + (1) (1p) = 2p1 spielt

:E [Belohnung für B, der T] = (1) p + (+1) (1p) = 12p spielt

:E [Belohnung für B, der H] = E [Belohnung für B spielt, der T]  2p1 = 12p  p = 1/2 spielt

So ist eine Mischstrategie Gleichgewicht von Nash in diesem Spiel für jeden Spieler, um H oder T mit der gleichen Wahrscheinlichkeit zufällig zu wählen.

Siehe auch

• Angepasstes Sieger-Verfahren
• Beste Antwort
• Das Paradox von Braess
• Theorie von Complementarity
• Konfliktentschlossenheitsforschung
• Zusammenarbeit
• Evolutionär stabile Strategie
• Spieltheorie
• Wörterverzeichnis der Spieltheorie
• Das Gesetz von Hotelling
• Mexikanischer toter Punkt
• Lehrsatz von Minimax
• Optimaler Vertrag und Durchschnitt ziehen zusammen
• Das Dilemma des Gefangenen
• Beziehungen zwischen Gleichgewicht-Konzepten
• Das Selbstbestätigen des Gleichgewichts
• Lösungskonzept
• Gleichgewicht-Auswahl
• Konkurrenz von Stackelberg
• Subspiel vollkommenes Gleichgewicht von Nash
• Der Grundsatz von Wardrop

Zeichen

Spieltheorie-Lehrbücher

• Dixit, Avinash und Susan Skeath. Strategische Spiele. W.W. Norton & Company. (Die zweite Ausgabe 2004)
• . Passend für Studenten- und Geschäftsstudenten.
• Fudenberg, Drew und Jean Tirole (1991) Spieltheorie MIT Presse.
• . Eine 88-seitige mathematische Einführung; sieh Kapitel 2. Gratis online an vielen Universitäten.
• Morgenstern, Oskar und John von Neumann (1947) Die Theorie von Spielen und Wirtschaftsverhalten Universität von Princeton Presse
• . Eine moderne Einführung am Absolventenniveau.
• . Eine umfassende Verweisung von einer rechenbetonten Perspektive; sieh Kapitel 3. Herunterladbar gratis online.
• . Klare und ausführliche Einführung in die Spieltheorie in einem ausführlich wirtschaftlichen Zusammenhang.
• . Einführung ins Gleichgewicht von Nash.

Ursprüngliche Papiere von Nash

• Nash, John (1950) "Gleichgewicht weist in N-Person" Spielverhandlungen der Nationalen Akademie von Wissenschaften 36 (1):48-49 hin.
• Nash, John (1951) "Nichtkooperative Spiele" Die Annalen der Mathematik 54 (2):286-295.

Andere Verweisungen

• Mehlmann, A. Das Spiel zu Fuß! Spieltheorie im Mythos und dem Paradox, der amerikanischen mathematischen Gesellschaft (2000).
• Nasar, Sylvia (1998), "eine schöne Meinung", Simon and Schuster, Inc.

Außenverbindungen

• Ganzer Beweis der Existenz des Gleichgewichts von Nash