Wann konvergieren

Nash-Gleichgewichte sind im Allgemeinen nicht berechenbar. Ein $\epsilon$ Nash-Gleichgewicht ist eine Reihe von Strategien, bei denen jeder Spieler angesichts der Strategien des Gegners innerhalb von $\epsilon$ der maximal möglichen erwarteten Auszahlung erhält . Das Finden eines $\epsilon$ Nash-Gleichgewichts bei gegebenem $\epsilon$ und einem Spiel ist $\mathsf{PPAD}$ -vollendet.

Wenn man sich streng an die Definitionen hält, scheint es keinen besonderen Grund zu geben zu glauben, dass die Strategien eines gegebenen $\epsilon$ Nash-Gleichgewichts irgendwo in der Nähe der Strategien eines Nash-Gleichgewichts liegen. Wir sehen jedoch oft, dass in der Literatur ein Ausdruck wie "ungefähr ein Nash-Gleichgewicht berechnen" etwas schlampig verwendet wird, wenn es bedeutet, "ein ungefähres Nash-Gleichgewicht berechnen" zu sagen.

Ich frage mich also, wann der zweite den ersten impliziert. Das heißt, für welche Spiele können wir erwarten, dass $\epsilon$ Nash-Gleichgewichte "nahe" an Nash-Gleichgewichten liegen?

Angenommen, ich habe ein Spiel mit $n$ Spielern und eine Folge von Strategieprofilen $(s_1^{(1)},\dots,s_n^{(1)}), (s_1^{(2)},\dots,s_n^{(2)}), (s_1^{(3)},\dots,s_n^{(3)}), \dots$ .

Jedes ist ein ϵ i- Nash-Gleichgewicht, und die Folge ϵ 1 , ϵ 2 , ϵ 3 , … konvergiert gegen Null.$(s_1^{(i)},\dots,s_n^{(i)})$$\epsilon_i$$\epsilon_1,\epsilon_2,\epsilon_3,\dots$

Meine Fragen:

1. Wann (unter welchen Bedingungen / Annahmen) konvergieren alle Strategien? Das heißt, für jeden Spieler , s ( 1 ) j , s ( 2 ) , j , s ( 3 ) j , ... notwendigerweise konvergiert.$j$$s_j^{(1)},s_j^{(2)},s_j^{(3)},\dots$

2. Unter welchen weiteren Bedingungen ist die Grenze dieser Sequenz tatsächlich ein Nash-Gleichgewicht des Spiels? (Es scheint mir, dass keine weiteren Annahmen erforderlich sein sollten, dh wenn alle Strategien konvergieren, sollte die Grenze ein NE sein.)

3. Wann impliziert ein Algorithmus zur Berechnung von Nash-Gleichgewichten notwendigerweise einen Algorithmus zur ungefähren Berechnung von Strategien eines Nash-Gleichgewichts? Sind die oben genannten Bedingungen ausreichend?$\epsilon$

Vielen Dank!

Bearbeiten 2014-03-19

Nach dem Lesen der Referenz in Rahuls Antwort erscheint es vernünftiger, in Abständen zwischen Verteilungen zu denken, als in konvergenten Sequenzen. Also werde ich versuchen, die Fragen neu zu formulieren und auch einige aktuelle Gedanken zu formulieren.$\ell_1$

1. (Nun, dies ist zu algorithmisch abhängig, um wirklich eine Antwort zu haben. Ohne Einschränkungen des Algorithmus könnten Sie zwei unterschiedliche Nash-Gleichgewichte haben und dann, wenn Sie immer kleinere in den Algorithmus einfügen , den Abstand ℓ 1 zwischen aufeinanderfolgenden Ausgaben könnte immer noch groß sein, da die Ausgänge zwischen den Gleichgewichten schwingen.)$\epsilon$$\ell_1$

2. Angenommen, ist ein Strategieprofil, dh die Produktverteilung über die Strategien der Spieler. Für welche Spiele können wir sagen, dass p ein ϵ- Nash-Gleichgewicht ist, was ‖ p - q ‖ 1 ≤ δ für ein Nash-Gleichgewicht q impliziert , wobei δ → 0 als ϵ → 0 ist ? (Beachten Sie, dass das Gegenteil gilt, wenn die Auszahlungen durch 1 begrenzt sind .)$p$$p$$\epsilon$$\|p - q\|_1 \leq \delta$$q$$\delta \to 0$$\epsilon \to 0$$1$

   Dies ist tatsächlich schwierig, da wir in der Komplexitätseinstellung, die wir als "Spiel" bezeichnen, tatsächlich eine Folge von Spielen sind, die durch , die Anzahl der reinen Strategien ("Aktionen"), parametrisiert werden . Also n → ∞ als ϵ → 0 , und die relativen Raten sind wichtig. Hier ist ein einfaches Gegenbeispiel, um zu zeigen, dass die Antwort nicht "alle Spiele" ist. Angenommen, wir legen eine Folge von abnehmenden ϵ 1 , ϵ 2 , … fest . Konstruieren Sie dann für jedes ϵ n das Zwei-Spieler-Spiel aus n Aktionen, bei denen ein Spieler, wenn er die erste Aktion spielt, eine Auszahlung von 1 erhält$n$$n \to \infty$$\epsilon \to 0$$\epsilon_1,\epsilon_2,\dots$$\epsilon_n$$n$$1$unabhängig davon, was der andere Spieler spielt; Wenn ein Spieler die zweite Aktion spielt, erhält er eine Auszahlung von unabhängig davon, was der andere Spieler spielt. und wenn ein Spieler eine andere Aktion spielt, erhält er eine Auszahlung von 0, unabhängig davon, was der andere Spieler spielt.$1-\epsilon_n$$0$

   Somit hat jedes Spiel ein ϵ n- Gleichgewicht (beide spielen die zweite Aktion), das maximal in ℓ 1 Entfernung von seinem einzigen Nash-Gleichgewicht liegt (beide spielen die erste Aktion).$n$$\epsilon_n$$\ell_1$

   Also zwei interessante Unterfragen:

   1. Für ein festes Spiel und festes , ob für "klein genug" ϵ die obige Bedingung gilt (alle ϵ- Gleichgewichte liegen nahe an den Nash-Gleichgewichten).$n$$\epsilon$$\epsilon$
   2. Vielleicht im Wesentlichen die gleiche Frage, aber ob die Bedingung gilt, wenn Unterschiede in den Auszahlungen durch eine Konstante wie .$n \to \infty$

3. Gleiche Frage wie (2), jedoch in Bezug auf die tatsächlichen Gleichgewichte, die durch Algorithmen berechnet wurden. Ich denke, wahrscheinlich werden wir entweder algorithmische / konstruktive Antworten erhalten oder gar keine, daher spielt die Unterscheidung keine große Rolle.

Das folgende Papier formalisiert zumindest den Begriff der ungefähren Gleichgewichte, die nahe an den exakten Gleichgewichten liegen, und beweist einige verwandte strukturelle Ergebnisse.

Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum oder Sheffet und Santosh Vempala (2010). Auf Nash-Gleichgewichten von approximationsstabilen Spielen. In Proceedings of the Third International Conference on Algorithmic Game Theory (SAGT'10), 78-89.

Insbesondere gibt das Papier ein Beispiel für eine Klasse von Spielen für Frage 3.