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

12

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 ?ϵ

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 ]s0sza[-1,+1]sb[+1,-1]

[p1_info, p2_info, num_of_choices, player_to_move, next_state_table] gdzie:

  • player_to_move{1,2)}
  • jest funkcją z { 1 , 2 , 3 , . . . , Num_of_choices } { 1 , 2 , 3 , . . . , S }next_state_table{1,2),3),...,num_of_choices}{1,2),3),...,S.}
  • p1_info,p2_info,num_of_choices1

Gdy komputer jest w takiej formie:

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

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

  • 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. s0=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.

Marzio De Biasi
źródło
Czy gracze znają wewnętrzną strukturę? Jaka jest zaleta posiadania dodatkowych informacji, daje więcej możliwych ruchów?
domotorp
Tak. Daje im to lepszy obraz tego, jaki jest obecny stan.
Przepraszam, ale wciąż nie rozumiem. Więc znają wewnętrzną strukturę, ale nie wiedzą, gdzie w tej chwili są? Wyjaśnij opis, jestem pewien, że nie jestem jedynym, który nie może zrozumieć problemu.
domotorp
3
Czy twój model jest taki sam jak „stochastyczna gra turowa o zerowej sumie z częściowymi informacjami”?
Kristoffer Arnsfelt Hansen
1
@Kristoffer: Nie jest (przynajmniej dla mnie) oczywiste, że mój model pozwala na kodowanie irracjonalne prawdopodobieństwa, chociaż mój model jest równoważny z tym innym.

Odpowiedzi:

6

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.pp

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.

Peter Shor
źródło
Ten pomysł randomizacji (przynajmniej tak, jak to opisałeś) może dać jedynie racjonalne prawdopodobieństwo. Również definicje użyte w dwóch pierwszych artykułach, które zbytnio powiązałeś, sugerują, że ich gry mają skończone drzewo gry, podczas gdy ja potrzebuję tylko skończonej przestrzeni stanów (gdzie „stan” nie obejmuje historii gry).
Masz rację ... pierwsza część mojej odpowiedzi jest niepoprawna. Pozwól mi to usunąć. Jestem całkiem pewien, że przybliżenie wartości prostych gier stochastycznych nie jest znane jako P, nawet jeśli prawdopodobieństwo wszystkich rzutów monetą wynosi 1/2.
Peter Shor,
1


ϵ0<ϵ

Dane wejściowe: gra opisana w moim pytaniu
musi mieć odpowiedź TAK, jeśli: wartość gry dla Gracza 1 jest większa niż 1-ϵ
ϵ

pozostaje RE- twarde, nawet gdy

player_to_move jest zawsze 1 (to znaczy, potrzebna jest tylko 1 gracz)
i
s 0 ≠ 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ł)



.


źródło