Complexidade dos jogos de informação parcial em estado finito

Dado um jogo determinístico de soma zero com informações parciais determinísticas, com apenas muitos estados finitos,
cujos resultados possíveis são [perder, empatar, vencer] com valores [-1,0, + 1], respectivamente,
qual é a complexidade de se aproximar o valor de tais um jogo de forma aditiva dentro de ?$\epsilon$

Em particular, não consigo criar nenhum algoritmo para fazer isso.
O restante desta postagem é inteiramente dedicado a fornecer uma descrição mais completa
do problema. Portanto, se você já consegue descobrir o que significa a pergunta na parte superior
desta postagem, não há motivo para ler o restante desta postagem.

Dada uma máquina de estados árbitro com , com um estado inicial designado s 0 , um estado s a cujo par de escores é [ - 1 , + 1 ] , um estado s b cujo par de escores é [ + 1 , - 1 ] e estados da forma$\{1,2,3,...,S\}$$s_0$$s_a$$[-1,+1]$$s_b$$[+1,-1]$

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

• $\mbox{player_to_move} \in \{1,2\}$
• é uma função de { 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$

Quando a máquina estiver em um estado dessa forma:

• envia para Player_1 e envia p2_info para Player_2,$\mbox{p1_info}$$\mbox{p2_info}$
• $\mbox{num_of_choices}$$\{1,2,3,...,\mbox{num_of_choices}\}$
• $\mbox{next_state_table}$

$s_a$$s_b$

• pára com o par de pontuação desse estado como saída

$s_0 = 1$

Qual é a complexidade do seguinte problema?
Dada uma máquina de arbitragem e um número inteiro positivo N, produza um número racional
que é (aditivo) dentro de 1 / N do valor do jogo natural para o Jogador 1.

Como mencionado anteriormente nesta pergunta, não consigo
criar nenhum algoritmo para fazer isso.

NOTA: meu suposto algoritmo estava incorreto; Eu deletei.

$p$$p$

Para um limite inferior sobre a complexidade, a questão de aproximar o valor de um jogo estocástica simples é não conhecido por ser em P . Usando o truque de randomização que eu dei acima, é fácil escrever um jogo estocástico simples como um jogo de arbitragem com uma tabela de pesquisa de tamanho polinomial.

$\epsilon$$0<\epsilon$

Entrada: um jogo como descrito na minha pergunta
deve gerar SIM se: o valor do jogo para o Jogador 1 for maior que 1$\hspace{.025 in}\epsilon$
$\epsilon$

permanece RE- difícil, mesmo quando

player_to_move é sempre 1 (ou seja, é necessário apenas 1 jogador)
e
s ₀ ≠ s _um e s _um não está na Range (next_state_table)
(ou seja, é literalmente impossível para o jogador a perder)
e
p1_info e p2_info e number_of_choices são independentes do estado
(ou seja, o único feedback do jogador é se ele ganhou ou não)

.