Zum Inhalt springen
Zurück zu den Suchergebnissen

Nash-Gleichgewicht

Eingeführt von
John Nash
Jahr
1950
Typ
algorithm
Familie
Game-theoretic

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Das Nash-Gleichgewicht ist ein spieltheoretisches Lösungs-Konzept, bei dem kein Spieler unilateral abweichen kann, um seinen Ertrag zu verbessern.

Formalisiert von John Nash im Jahr 1950, findet der Lemke-Howson-Algorithmus rechnerisch Gleichgewichte in Bimatrix-Spielen, indem er vollständig beschriftete Eckpunkt-Paare in den Strategie-Polyedern identifiziert.

Die Intuition hinter der Methode

In einem Nash-Gleichgewicht ist die Strategie jedes Spielers eine beste Antwort auf die Strategie jedes anderen Spielers. Stellen Sie sich eine Situation vor, in der beide Spieler die Strategie des anderen kennen: keiner würde seine Strategie ändern wollen, da dies ihn nur schlechter stellen würde. Der Lemke-Howson-Algorithmus nutzt die Geometrie von Spiel-Polyedern, verfolgt Beschriftungen (unerfüllte Nebenbedingungen) und führt Pivot-Operationen durch die Eckpunkte durch, bis ein vollständig beschriftetes Paar gefunden ist – eine Konfiguration, in der beide Spieler keine profitablen Abweichungen haben.

Geschichte

John Nash bewies in seiner Dissertation von 1950, dass jedes endliche Spiel mindestens ein Nash-Gleichgewicht mit gemischten Strategien besitzt. 1964 veröffentlichten Lemke und Howson den ersten konstruktiven Algorithmus zur Ermittlung dieser Gleichgewichte und verwandelten Nashs Existenzbeweis in eine praktische rechnerische Methode. Ihre Arbeit wurde zur Grundlage der rechnerischen Spieltheorie und der algorithmischen Ökonomie.

Wann wird sie eingesetzt?

Verwenden Sie die Nash-Gleichgewichts-Analyse bei der Untersuchung von Spielen mit zwei Spielern und diskreten Strategieräumen oder bei der Suche nach vollständig gemischten Gleichgewichten. Geeignet für die Modellierung von Wettbewerb, Verhandlungen und Koordinationsproblemen, bei denen strategische Interaktion von größter Bedeutung ist. Die Lemke-Howson-Methode funktioniert am besten für nicht-entartete Bimatrix-Spiele; entartete Fälle können symbolische Berechnung oder Perturbation erfordern.

Grenzen und Hinweise

  • Beschränkt auf Bimatrix-Spiele (Zwei-Spieler-Spiele); die Erweiterung auf n-Spieler-Spiele ist NP-schwer
  • Versagt oder wird ineffizient bei entarteten Spielen, bei denen mehrere eintretende Pivot-Operationen möglich sind
  • Findet möglicherweise nur ein Gleichgewicht; in Nicht-Nullsummen-Spielen existieren oft mehrere Gleichgewichte
  • Behandelt dynamische Spiele oder Spiele in extensiver Form nicht direkt ohne Umformulierung

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Rechnerisch effizient für die Ermittlung von Nash-Gleichgewichten in endlichen Bimatrix-Spielen
  • Garantiert die Konvergenz zu einem vollständig beschrifteten Eckpunkt-Paar für nicht-entartete Spiele
  • Bietet eine theoretische Grundlage, die kombinatorische Geometrie mit Spieltheorie verbindet
  • Anwendbar auf gemischte Strategie-Gleichgewichte, die oft realistischer sind als reine Strategie-Ergebnisse

Anwendungen

  • Ökonomie: Modellierung von oligopolistischer Konkurrenz und Preisbildungsstrategien in Märkten
  • Auktionen und Mechanismus-Design: Analyse von Gebotsstrategien in First-Price- und Sealed-Bid-Auktionen
  • Cybersicherheit: Vorhersage von Angreifer-Verteidiger-Gleichgewichten in Netzwerk-Sicherheitsspielen
  • Wildbiologie: Analyse evolutionär stabiler Strategien in Räuber-Beute-Interaktionen

So funktioniert es

So funktioniert es

1

Wandeln Sie das Bimatrix-Spiel in zwei Probleme der linearen Komplementarität (LCP) um, eines für jeden Spieler, die ihre Best-Response-Bedingungen darstellen.

2

Weisen Sie Kanten und Eckpunkten der Strategie-Polyeder Beschriftungen zu, basierend darauf, welche Anreiz-Nebenbedingungen des Spielers verletzt werden.

3

Beginnen Sie am Eckpunkt mit allen Einsen (vollständig beschriftet), führen Sie Simplex-ähnliche Pivot-Operationen durch, um das Polyeder zu durchlaufen, Beschriftungen zu entfernen und hinzuzufügen, bis ein vollständig beschriftetes Paar entdeckt wird.

4

Bestätigen Sie, dass die Strategien beider Spieler gegenseitige beste Antworten bilden, indem Sie überprüfen, ob keiner seinen Ertrag angesichts der Strategie des anderen verbessern kann.

Häufige Fallstricke

  • Unter der Annahme, dass ein eindeutiges Gleichgewicht existiert; viele Spiele haben mehrere Nash-Gleichgewichte mit unterschiedlichen Ertrags-Implikationen
  • Verwechslung von gemischten Strategie-Gleichgewichten (probabilistisches Spiel) mit reinen Strategie-Gleichgewichten, was zu Fehlinterpretationen des Agentenverhaltens führt
  • Übersehen der Unterscheidung zwischen notwendigen und hinreichenden Bedingungen für ein Gleichgewicht; ein vollständig beschriftetes Paar erfüllt die Optimalität, wird aber möglicherweise nicht realisiert, wenn die Spieler nicht koordinieren können

Häufig gestellte Fragen

Kann ein Spiel kein Nash-Gleichgewicht haben?

Reine Strategie-Nash-Gleichgewichte existieren möglicherweise nicht (z. B. Stein-Schere-Papier), aber jedes endliche Spiel hat mindestens ein gemischtes Strategie-Gleichgewicht, bei dem die Spieler mit bestimmten Wahrscheinlichkeiten über Aktionen randomisieren.

Wie unterscheidet sich ein gemischtes Strategie-Gleichgewicht von einem reinen Strategie-Gleichgewicht?

In einem reinen Strategie-Gleichgewicht legt jeder Spieler mit Sicherheit eine bestimmte Aktion fest. In einem gemischten Strategie-Gleichgewicht verwendet jeder Spieler eine Wahrscheinlichkeitsverteilung über Aktionen. Gemischte Gleichgewichte sind oft allgemeiner und existieren, wenn reine nicht existieren.

Warum wird der Lemke-Howson-Algorithmus dem Brute-Force-Suchverfahren vorgezogen?

Der Algorithmus nutzt die Polyederstruktur von Strategieräumen, reduziert den Suchraum exponentiell und erreicht für nicht-entartete Spiele eine Konvergenz in polynomieller Zeit, während die Brute-Force-Aufzählung mit wachsendem Strategieraum unerschwinglich wird.

Verwandte Methoden

Quellen

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    DOI-Referenz öffnen
    Kopiert.
  2. Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.

    DOI-Referenz öffnen
    Kopiert.