Złożoność częściowych gier informacyjnych o skończonym stanie

Biorąc pod uwagę deterministyczną grę z sumą zerową z częściową informacją i tylko skończoną liczbą stanów,
których możliwymi rezultatami są odpowiednio [przegrana, remis, wygrana] o wartościach odpowiednio [-1,0, + 1],
jaka jest złożoność przybliżenia wartości takich gra w dodatku ?$\epsilon$

W szczególności nie mogę wymyślić żadnego algorytmu do tego.
Pozostała część tego postu jest poświęcona w całości dokładniejszemu opisowi
problemu, więc jeśli możesz już dowiedzieć się, co oznacza pytanie na początku
tego postu, nie ma powodu, aby przeczytać resztę tego postu.

Biorąc pod maszynę sędzia ze stanów , z wyznaczonym stanem początkowym , stanem którego parą wyników jest , stanem którego parą wyników jest , i stanami postaci$\{1,2,3,...,S\}$s a [ - 1 , + 1 ] s b [ + 1 , - 1 $s_0$$s_a$$[-1,+1]$$s_b$$[+1,-1]$

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ gdzie:

• $\mbox{player_to_move} \in \{1,2\}$
• jest funkcją z { 1 , 2 , 3 , . . . , Num_of_choices } → { 1 , 2 , 3 , . . . , S $\mbox{next_state_table}$$\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
• $\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

Gdy komputer jest w takiej formie:

• wysyła do Player_1 i wysyła p2_info do Player_2,$\mbox{p1_info}$$\mbox{p2_info}$
• wysyła do wskazanych, odtwarzacz oczekuje na elemencie { 1 , 2 , 3 , . . . , num_of_choices } jako dane wejściowe od tego odtwarzacza,$\mbox{num_of_choices}$$\{1,2,3,...,\mbox{num_of_choices}\}$
• następnie przechodzi do stanu wskazanego przez $\mbox{next_state_table}$

Gdy maszyna wejdzie w jeden z dwóch pozostałych stanów lub s b ,$s_a$$s_b$

• zatrzymuje się, gdy jego wynikiem jest para wyników tego stanu

Istnieje naturalna gra dla dwóch graczy: maszyna sędziowska jest uruchamiana w stanie , gracze zapewniają dane wejściowe, na które czeka maszyna sędziowska, jeśli maszyna sędziowska zatrzyma się, wówczas Gracz 1 zdobędzie pierwszą wartość pary wyjściowej maszyny a Gracz 2 zdobywa drugą wartość pary wyjściowej maszyny, w przeciwnym razie obaj gracze otrzymują 0. $s_0 = 1$

Jaka jest złożoność następującego problemu?
Biorąc pod uwagę taką maszynę sędziowską i dodatnią liczbę całkowitą N, wypisz liczbę wymierną,
która ( dodatnio) mieści się w granicach 1 / N wartości naturalnej gry dla Gracza 1.

Jak wspomniano wcześniej w tym pytaniu, nie mogę wymyślić
żadnego algorytmu do tego.

UWAGA: mój rzekomy algorytm był niepoprawny; Usunąłem to.

Należy pamiętać, że nie ma znaczenia, czy gra jest deterministyczna, czy nie. Aby losować, sędzia może poprosić każdego z graczy o wniesienie losowej liczby mod , a następnie ich dodać. Łatwo jest wykazać, że jeśli gracze zastosują swoją optymalną strategię, suma jest modem liczb losowych mod p , który następnie może wykorzystać sędzia do losowej strategii. Nie zwiększa to znacznie liczby stanów w grze.$p$$p$

Dla dolnej granicy złożoności nie jest znane pytanie o przybliżenie wartości prostej gry stochastycznej . Korzystając z podanej powyżej sztuczki losowej, łatwo jest napisać prostą grę stochastyczną jako grę referencyjną z tabelą wielomianów.

$\epsilon$$0<\epsilon$

Dane wejściowe: gra opisana w moim pytaniu
musi mieć odpowiedź TAK, jeśli: wartość gry dla Gracza 1 jest większa niż 1-$\hspace{.025 in}\epsilon$
$\epsilon$

pozostaje RE- twarde, nawet gdy

player_to_move jest zawsze 1 (to znaczy, potrzebna jest tylko 1 gracz)
i
s ₀ ≠ s i s nie jest w zasięgu (next_state_table) (to znaczy, że to dosłownie niemożliwe gracz stracić) i p1_info i p2_info i number_of_choices są niezależne od państwa (tzn. jedyną informacją zwrotną gracza jest to, czy wygrał)

.