Równowaga w grze w postój

Rozważ następującą grę 2-osobową:

• Natura losowo wybiera program
• Każdy gracz gra liczbę w [0, nieskończoność] włącznie w odpowiedzi na ruch natury
• Weź minimalną liczbę graczy i uruchom program dla (maksymalnie) tak wielu kroków (chyba że obaj gracze wybiorą nieskończoność)
• Jeśli program się zatrzyma, gracz, który zagrał minimalną liczbę, otrzymuje 1 punkt. Jeśli program się nie zatrzymuje, gracz traci 1 punkt. Każdy gracz, który zagrał w nie-minimalną liczbę, otrzymuje 0 punktów, a obaj gracze otrzymują 0, jeśli grają w nieskończoność.

(Przypadki narożne mogą być obsługiwane w jakikolwiek sposób, który najlepiej zachowuje ducha problemu - np. Pomocne może być zachowanie górnej półciągłości).

Pytanie: czy ta gra ma obliczalną równowagę Nasha?

Bez wymogu obliczalności każdy gracz po prostu wykonuje dokładną liczbę kroków, w których program się zatrzymuje (lub nieskończoność, jeśli się nie zatrzymuje).

Jeśli spróbujesz zwykłego argumentu diagonalizacji problemu zatrzymania, zobaczysz, że równowaga istnieje w strategiach mieszanych, więc oczywiste podejście nie działa od razu. Może jest jakiś sposób, żeby to poprawić?

Z drugiej strony równoważność rzeczywistych pól zamkniętych oznacza, że skończone gry z obliczalnymi wypłatami mają obliczalną równowagę . Ta gra nie jest skończona, ale przestrzeń strategii jest zamknięta, a wypłaty można obliczać, więc może ta sama sztuczka mogłaby zostać zastosowana z twierdzeniem Glicksberga lub czymś w tym stylu? Problem polega na tym, że bez wymogu obliczalności równowaga jest w czystych strategiach, więc każda próba udowodnienia istnienia równowagi obliczalnej za pomocą istnienia równowagi możliwej do obliczenia musi wyjaśniać, dlaczego równowaga jest obniżona z czystej do mieszanej.

Wydaje się to być rodzajem problemu, w którym ludzie mogli wcześniej nie zająć się dokładnie tym pytaniem, ale mogli spojrzeć na coś podobnego. Nie byłem w stanie dużo się pojawić, ale jeśli ktoś wie coś o duchu, daj mi znać!

Motywacja: panuje powszechna intuicja, że ​​samodzielne odniesienie jest głównym blokiem obliczalności - tzn. Że każdy niewyobrażalny problem w jakiś sposób zawiera odniesienie. Jeśli gra z grubsza taka jak ta ma obliczalną równowagę Nasha, byłaby dowodem na tę intuicję.

AKTUALIZACJA: Aby wyjaśnić, równowaga powinna być „obliczalna” w sensie obliczalnych liczb rzeczywistych: prawdopodobieństwa opisujące mieszany rozkład strategii powinny być obliczalne z dowolną dokładnością. (Zauważ, że tylko skończenie wiele prawdopodobieństw będzie powyżej jakiegokolwiek określonego precyzyjnego punktu odcięcia.) Oznacza to również, że możemy próbkować z arbitralnie bliskiego przybliżenia strategii równowagi.

$1/2^i$$i$$t$$j$$t$$j$$j$$t$