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.

lo.logic computability gt.game-theory

— John Wentworth
źródło

Czy Twoja aktualizacja traktuje również sztuki jako obliczalne liczby rzeczywiste? (to znaczy, mogą odgrywać pewną liczbę z prawdopodobieństwem 1, nie wiedząc, czy nie-or-ta liczba jest nieskończoność?)

Czy wolno nam znać rozkład przeciwnika?

— Bjørn Kjos-Hanssen

Ricky: odtworzenia można traktować jako liczby obliczalne, ale obcięcie do liczby całkowitej powinno zdominować każdą grę skończoną niecałkowitą, ponieważ program będzie działał tylko dla liczby całkowitej (lub nieskończoności). Nie jestem jednak pewien, czy rozumiem twój nawiasowy przykład, więc mogę nie rozumieć twojego pytania.

— John Wentworth

Bjørn: Tak. Załóżmy, że rozkład przyrody jest znany i kładzie niezerową wagę na wszystkich prawidłowych programach. Załóż również, że każdy gracz zna strategię drugiego gracza (tj. Dystrybucję).

— John Wentworth

@ johnwentworth, użyj @ lub nie zobaczą twojej odpowiedzi.

— rus9384

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

— Lance Fortnow
źródło

Podoba mi się ta konstrukcja - ustala, że każda równowaga Nasha musi działać poprawnie dla wszystkich programów. Potrzebny jest dodatkowy krok, aby ustalić, że rozwiązuje on problem zatrzymania, ponieważ dystrybucje muszą jedynie zbiegać się w celu uzyskania doskonałej wydajności w granicach wysokiej precyzji (a zatem obliczeń nieskończonych). Ponieważ wiemy, że wyjście musi przypisywać wagę jednostkową do jednej liczby całkowitej, myślę, że wystarczy obliczyć prawdopodobieństwo strategii z dokładnością do 1/4, a następnie przyjąć dowolną liczbę całkowitą o wadze większej niż 1/2.

— John Wentworth