Gleichgewicht in einem Haltespiel

10

Betrachten Sie das folgende 2-Spieler-Spiel:

  • Die Natur wählt zufällig ein Programm aus
  • Jeder Spieler spielt eine Zahl in [0, unendlich] einschließlich als Reaktion auf die Bewegung der Natur
  • Nehmen Sie das Minimum der Anzahl der Spieler und führen Sie das Programm für (bis zu) so viele Schritte aus (es sei denn, beide Spieler haben unendlich gewählt).
  • Wenn das Programm angehalten wird, erhält der Spieler, der die Mindestanzahl gespielt hat, 1 Punkt. Wenn das Programm nicht angehalten wird, verliert dieser Spieler 1 Punkt. Jeder Spieler, der eine nicht minimale Anzahl gespielt hat, erhält 0 Punkte, und beide Spieler erhalten 0, wenn beide unendlich spielen.

(Eckfälle können so behandelt werden, wie es den Geist des Problems am besten bewahrt - z. B. kann die obere Semikontinuität hilfreich sein.)

Die Frage: Besitzt dieses Spiel ein berechenbares Nash-Gleichgewicht?

Ohne die Berechenbarkeitsanforderung spielt jeder Spieler nur die genaue Anzahl von Schritten, in denen das Programm angehalten wird (oder unendlich, wenn es nicht anhält).

Wenn Sie das übliche Diagonalisierungsargument für das Stoppproblem ausprobieren, werden Sie feststellen, dass in gemischten Strategien ein Gleichgewicht besteht, sodass der offensichtliche Ansatz nicht sofort funktioniert. Vielleicht gibt es eine Möglichkeit, es zu optimieren?

Andererseits bedeutet die Äquivalenz realer geschlossener Felder, dass endliche Spiele mit berechenbaren Auszahlungen berechenbare Gleichgewichte haben . Dieses Spiel ist nicht endlich, aber der Strategieraum ist geschlossen und die Auszahlungen berechenbar. Vielleicht könnte der gleiche Trick mit Glicksbergs Theorem oder etwas in diesem Sinne angewendet werden? Das Problem ist, dass sich das Gleichgewicht ohne die Anforderung der Berechenbarkeit in reinen Strategien befindet. Daher muss jeder Versuch, das Vorhandensein eines berechenbaren Gleichgewichts unter Verwendung eines möglicherweise berechenbaren Gleichgewichts zu beweisen, erklären, warum das Gleichgewicht von rein auf gemischt herabgestuft wird.

Dies scheint ein Problem zu sein, bei dem die Leute diese Frage vielleicht noch nicht beantwortet haben, sich aber etwas Ähnliches angesehen haben. Ich konnte nicht viel auftauchen, aber wenn jemand etwas im Geiste weiß, lass es mich wissen!

Motivation: Es gibt eine verbreitete Intuition, dass Selbstreferenz der Hauptblock für die Berechenbarkeit ist - dh dass jedes nicht berechenbare Problem irgendwie Selbstreferenz einbettet. Wenn ein Spiel wie dieses ein berechenbares Nash-Gleichgewicht hat, würde dies Beweise für diese Intuition liefern.

UPDATE: Zur Verdeutlichung sollte das Gleichgewicht im Sinne berechenbarer reeller Zahlen "berechenbar" sein: Die Wahrscheinlichkeiten, die die gemischte Strategieverteilung beschreiben, sollten mit willkürlicher Genauigkeit berechenbar sein. (Beachten Sie, dass nur endlich viele Wahrscheinlichkeiten über einem bestimmten Präzisionsgrenzwert liegen.) Dies bedeutet auch, dass wir aus einer willkürlich engen Annäherung der Gleichgewichtsstrategie eine Stichprobe ziehen können.

John Wentworth
quelle
Betrachtet Ihr Update die Spiele auch als berechenbare reelle Zahlen? (dh sie können eine Zahl mit einer Wahrscheinlichkeit von 1 , ohne zu wissen , ob-oder-nicht spielen diese Zahl unendlich ist?)
Dürfen wir die Verteilung des Gegners kennen?
Bjørn Kjos-Hanssen
Ricky: Die Spiele können als berechenbare Realwerte betrachtet werden, aber das Abschneiden auf eine Ganzzahl sollte jedes nicht ganzzahlige endliche Spiel dominieren, da ein Programm nur für eine ganzzahlige Anzahl von Schritten (oder unendlich) ausgeführt wird. Ich bin mir nicht sicher, ob ich Ihr Beispiel in Klammern verstehe, daher verstehe ich Ihre Frage möglicherweise falsch.
John Wentworth
Bjørn: Ja. Angenommen, die Verteilung der Natur ist bekannt und alle gültigen Programme werden ungleich Null gewichtet. Nehmen Sie außerdem an, dass jeder Spieler die Strategie des anderen Spielers kennt (dh die Verteilung).
John Wentworth
@johnwentworth, benutze @ oder sie können deine Antwort nicht sehen.
Rus9384

Antworten:

11

Selbst wenn Sie ein Einspieler-Spiel haben, gibt es kein berechenbares Gleichgewicht. Betrachten Sie die Natur, indem Sie die Wahrscheinlichkeit auf Programm . Jede berechenbare Strategie erreicht einen Wert, der streng unter einem liegt, oder Sie können ihn verwenden, um das Stoppproblem zu lösen. Sie können jedoch jeden Wert kleiner als eins erreichen, indem Sie für einige feste, ausreichend große das Naturprogramm für Schritte simulieren und die Anzahl der Schritte ausgeben, die das Programm zum Anhalten benötigt, wenn in Schritten anhält , andernfalls unendlich.1/2it j t j j titjtjjt

Lance Fortnow
quelle
Ich mag diese Konstruktion - sie legt fest, dass jedes Nash-Gleichgewicht für alle Programme korrekt gespielt werden muss. Es ist ein zusätzlicher Schritt erforderlich, um festzustellen, ob das Problem des Anhaltens gelöst ist, da die Verteilungen nur innerhalb der Grenzen hoher Präzision (und damit unendlicher Berechnung) zu einer perfekten Leistung konvergieren müssen. Da wir wissen, dass die Ausgabe das Einheitsgewicht auf eine Ganzzahl setzen muss, reicht es meiner Meinung nach aus, die Strategie-Wahrscheinlichkeiten auf 1/4 zu berechnen und dann die Ganzzahl zu nehmen, deren Gewicht größer als 1/2 ist.
John Wentworth