Algorithmen zur Nash-Gleichgewichtsberechnung.

10

Ich habe das Forum durchsucht, um zu sehen, ob dies zuvor gefragt wurde, und während die algorithmische Spieltheorie diskutiert wird, konnte ich dieses spezielle Problem nicht finden. Ich versuche herauszufinden, was der bekannteste Algorithmus ist, um ungefähre (gemischte Strategie) Nash-Gleichgewichte in einem endlichen N-Personen-Spiel zu berechnen. Natürlich wäre dieser Algorithmus PPAD. Ich interessiere mich mehr für Geschwindigkeit / Effizienz als für die perfekte Genauigkeit des Algorithmus.

Danke, Philip

ds.algorithms gt.game-theory Philip White
quelle
Wir können Ihnen besser helfen, wenn Sie weitere Details angeben. Welchen Wert von haben Sie zum Beispiel im Sinn? Haben Sie eine spezielle Struktur der Auszahlungsfunktion im Auge? Benötigen Sie wirklich ein Nash-Gleichgewicht oder würde ein korreliertes Gleichgewicht ausreichen? Suchen Sie etwas mit guten nachweisbaren Grenzen oder etwas mit guter praktischer Leistung? n
Warren Schudy

Antworten:

7

Die kurze Antwort lautet: Obwohl es einige polynomielle Zeitalgorithmen gibt, mit denen nachweislich ungefähre Nash-Gleichgewichte ermittelt werden können, finden alle relativ schlechte Näherungen - wahrscheinlich nicht gut genug, wenn Sie tatsächlich versuchen, einen Algorithmus zum Spielen eines Spiels zu finden. Für 2-Spieler-Spiele ist mehr bekannt als für N-Spieler-Spiele.

Wenn Sie tatsächlich versuchen, ein (ungefähres) Nash-Gleichgewicht zu finden, können Sie leicht versuchen, das Spiel zu simulieren, wobei jeder Spieler den Algorithmus der randomisierten gewichteten Mehrheit verwendet (http://en.wikipedia.org/). wiki / Randomized_weighted_majority_algorithm). Dies funktioniert nicht garantiert, wird aber in vielen Fällen funktionieren (und wird in bestimmten Spielklassen wie Nullsummenspielen garantiert). Insbesondere wenn dieser Prozess überhaupt konvergiert, wird garantiert, dass er zu einem Nash-Gleichgewicht konvergiert. Die Gefahr besteht darin, dass es nicht konvergiert und für immer zyklisiert - aber selbst in diesem Fall konvergiert die empirische Geschichte des Spiels gegen die Menge der grob korrelierten Gleichgewichte.

Aaron Roth
quelle
Ich fing an, mir das in der obigen Antwort erwähnte Papier anzusehen. Ich habe nicht alles verstanden (oder viel davon auf den ersten Blick) ... können Sie erklären, warum die Annäherung "relativ schlecht" ist? Können Sie auch kurz erklären, was ein "grob korreliertes Gleichgewicht" ist? Ich weiß, was ein korreliertes Gleichgewicht ist, aber was es für eine solche Gleichung bedeutet. grob sein. Was meinst du schließlich mit "die empirische Geschichte des Spielens wird konvergieren ... [etc.]"? Wie kann etwas, das niemals konvergiert, zu einer Reihe von CCEs konvergieren? Vielen Dank für Ihre Antwort. Ich schaue jetzt im Wikipedia-Artikel nach.
Philip White
Für einige Hintergrundinformationen zu Algorithmen, die Verteilungen erzeugen, die zu grob korrelierten Gleichgewichten oder korrelierten Gleichgewichten konvergieren, würde ich hier beginnen: cs.cmu.edu/~avrim/Papers/regret-chapter.pdf
Aaron Roth
Wenn Sie ein korreliertes Gleichgewicht anstelle eines grob korrelierten Gleichgewichts wünschen, können Sie einen Lernenden ohne internes Bedauern verwenden. Zum Beispiel (schamloser Stecker) cs.brown.edu/~ws/papers/regret.pdf . Es gibt auch Algorithmen zur Berechnung korrelierter Gleichgewichte direkt in der Polynomzeit.
Warren Schudy
10

n

Joseph O'Rourke
quelle
4

Wenn Sie an Algorithmen interessiert sind, die tatsächlich in Software implementiert sind, gibt es einige, die mir bekannt sind:

  1. Das GAMBIT-Paket (http://www.gambit-project.org/doc/index.html) implementiert mehrere Nash-Gleichgewichtsalgorithmen für die normale Form von 2 Spielern und n Spielern und in einigen Fällen für umfangreiche Formspiele.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) implementiert die GNM- und IPA-Algorithmen von Govindan & Wilson für N-Player-Spiele in normaler Form.

  3. Bei großen Spielen ist die normale Formendarstellung problematisch, da die Anzahl der Spieler exponentiell zunimmt. Wenn die Utility-Funktion Ihres Spiels bestimmte Strukturen aufweist, können Sie stattdessen eine "übersichtliche Darstellung" (z. B. grafische Spiele, symmetrische Spiele, Action-Graph-Spiele) verwenden, um sie mit viel weniger Platz auszudrücken. und außerdem kann die Struktur oft für Rechenbeschleunigungen ausgenutzt werden. In Bezug auf die Software passt der AGG Solver (http://agg.cs.ubc.ca) den GNM-Algorithmus von GameTracer und den simpdiv-Algorithmus von GAMBIT an die Darstellung des Action-Graph-Spiels (AGG) an. (Haftungsausschluss: Ich bin an der Entwicklung dieses Softwarepakets beteiligt.)

albert
quelle