Jogos arbitrados com moedas semi-privadas não correlacionadas

Eu estava (e ainda estou) realmente interessado na resposta a essa pergunta, porque essa é uma variação interessante da complexidade dos jogos que não foi resolvida, então eu ofereci uma recompensa. Eu pensei que a pergunta original provavelmente era muito difícil, então eu postei três perguntas relacionadas que também seriam dignas da recompensa. Ninguém postou nenhuma resposta antes que a recompensa expirasse. Posteriormente, fui capaz de responder a duas perguntas relacionadas (perguntas 3 e 4, discutidas abaixo na minha postagem original), mostrando que a aproximação do valor dos jogos com arbitragem com moedas semi-privadas correlacionadas (definidas abaixo) estava EXPTIME-completa. A pergunta original ainda não foi respondida. Eu também estaria interessado em quaisquer resultados colocando jogos relacionados entre PSPACE e EXPTIME em classes de complexidade interessantes.

POSTO ORIGINAL:

Essa questão foi inspirada na discussão sobre a questão hexadecimal do Itai . Um jogo de arbitragem é um jogo em que dois jogadores computacionalmente ilimitados jogam comunicando-se através de um verificador de tempo polinomial que pode jogar moedas privadas (portanto, o número de turnos e a quantidade de comunicação também são limitados no tempo polinomial). No final do jogo, o árbitro executa um algoritmo em P para determinar quem vence. Determinar quem vence esse jogo (mesmo que aproximadamente) está EXPTIME completo. Se você possui moedas públicas e comunicação pública, esses jogos estão no PSPACE. ( Veja Feige e Killian, "Tornando os jogos curtos". ) Minha pergunta diz respeito à fronteira entre esses dois resultados.

• Pergunta: Suponha que você tenha dois jogadores sem limites computacionais que jogam um jogo de comprimento polinomial. O papel do árbitro é limitado a, antes de cada jogada, dar a cada jogador um certo número de jogadas privadas de moedas (sem correlação com as do outro jogador). Todos os movimentos do jogador são públicos e, portanto, são vistos pelo oponente - a única informação privada é o lançamento da moeda. No final do jogo, todos os lançamentos de moedas particulares são revelados, e o árbitro do tempo múltiplo usa esses lançamentos de moedas e os movimentos do jogador para decidir quem ganha.

  Pelos resultados dos jogos arbitrados, a aproximação da probabilidade de o primeiro jogador vencer está em EXPTIME, e também é claramente difícil para o PSPACE. Qual (se houver) é? Existe algo conhecido sobre esse problema?

Observe que os jogadores podem ter que usar estratégias mistas, pois você pode jogar jogos de matriz com soma zero (à la von Neumann) dessa maneira.

MATERIAL ADICIONADO:

Vamos chamar essa classe de complexidade de RGUSP (todos os idiomas que podem ser reduzidos a um jogo com arbitragem com moedas semi-privadas não correlacionadas, conforme descrito acima, de modo que, se$L$ , jogador 1 vitórias com probabilidade ≥ 2 / 3 , e se x ∉ L , jogador 1 ganha com probabilidade ≤ 1 / 3 ). Minhas três perguntas relacionadas são:$x \in L$$\geq 2/3$$x \notin L$$\leq 1/3$

• Pergunta 2: O RGUSP parece bastante robusto. Por exemplo, se mudarmos o jogo para que o árbitro não envie mensagens, mas apenas observe as mensagens públicas dos jogadores 1 e 2 e receba delas mensagens privadas, aproximar o valor desse jogo ainda é equivalente ao RGUSP. Eu gostaria de demonstrar que o RGUSP é robusto, por isso estou disposto a dar a recompensa a qualquer pessoa que encontre uma classe C de complexidade natural para que PSPACE C ⊆ RGUSP, em que nenhuma das contenções pareça exata.$\subseteq$$\subseteq$

• Pergunta 3: Também suspeito fortemente que a classe RGCSP (Jogos com arbitragem com moedas semi-privadas correlacionadas) esteja EXPTIME completa e também estou disposto a dar a recompensa a alguém que comprove esse fato. No RGCSP, no primeiro passo, o árbitro dá aos dois jogadores variáveis ​​aleatórias correlacionadas (por exemplo, ele pode dar ao primeiro jogador um ponto em um grande plano projetivo e ao segundo jogador uma linha que contenha esse ponto). Depois disso, por um número polinomial de rodadas, os dois jogadores alternam o envio de mensagens públicas de tamanho poligonal. Depois que o jogo é disputado, o árbitro de tempo livre decide quem ganhou. Qual é a complexidade de aproximar a probabilidade de ganhar para o jogador 1?

• Pergunta 4: Finalmente, eu tenho uma pergunta que pode realmente ser sobre distribuição de criptografia e probabilidade: dar a capacidade de executar transferências inconscientes para dois jogadores em um jogo de arbitragem com moedas semi-privadas não correlacionadas permite que eles joguem um jogo de arbitragem arbitrário com moedas correlacionadas (ou, alternativamente, ele permite que eles joguem um jogo determinando qual vencedor é EXPTIME-complete)?

Não consigo responder à minha pergunta original, mas posso responder à pergunta 3 (e 4), que adicionei quando ofereci uma recompensa porque achava que a pergunta original provavelmente era muito difícil. De fato, tenho duas provas da pergunta 3.

Aqui está o cenário para a pergunta 3: Temos um árbitro em tempo polinomial que, no início do jogo, fornece aos jogadores 1 e 2 variáveis ​​aleatórias correlacionadas. Os jogadores 1 e 2 então jogam o jogo, sem qualquer interferência do árbitro. No final do jogo, o árbitro examina a transcrição e decide quem ganha. Eu posso mostrar que decidir quem ganha tal jogo um é EXPTIME completa, mesmo se você é dado a promessa de que as vitórias vencedor com probabilidade de pelo menos .$2/3$

======== Prova 1 ============

A primeira prova usa o fato de que a transferência inconsciente é universal para o cálculo seguro de duas partes. Assim, se os jogadores 1 e 2 puderem realizar uma transferência inconsciente, eles poderão simular um árbitro arbitrário em tempo polinomial, para que os resultados anteriores que os jogos com arbitragem estejam EXPTIME completos possam ser aplicados.

Agora, para obter uma ou duas transferências inconscientes, no início do jogo, o árbitro dá aos dois jogadores um grande número de "caixas de transferência inconscientes". Nós descrevemos uma dessas caixas de transferência alheias. P1 obtém dois números aleatórios, e r 2 . P2 recebe um desses números aleatórios, r i e a variável i ( = 1 ou 2 ), dizendo que de números aleatórios do P1 que ele tem. Para executar uma transferência inconsciente, P1 pega os dois dados que ele deseja transferir e os XOR com $r_1$$r_2$$r_i$$i$$=1$$2$ e r $r_1$$r_2$. P2 pode então decodificar um desses, mas P1 não pode dizer qual P2 pode decodificar. Esta é uma transferência inconsciente de 1-2. (Obviamente, o árbitro também deve dar aos jogadores caixas de transferência inconscientes direcionadas para o outro lado, de P2 para P1.)

Quando fiz a pergunta 4, fiquei preocupada que os resultados da computação segura de duas partes não se aplicassem a esse tipo de computação interativa com um árbitro, mas, na verdade, é muito fácil mostrar que sim.

=========== Prova 2 ===========

$2^n$$t$$Q_t($$, \ldots,$$)$$p$$Q_t$$t$ onde as avaliações de P1 e P2$Q_t$$Q_{t+1}$

A primeira coisa que usaremos é que, mesmo com moedas aleatórias não correlacionadas, o árbitro pode fazer com que os jogadores 1 e 2 realizem um comprometimento de bits, solicitando a XOR os dados que eles desejam confirmar com as moedas aleatórias. Assim, podemos falar sobre P1 e P2 colocando as coisas em envelopes selados.

$p_i$$\ell_i$$p_i$$\ell_i$$Q_{t}(p_i)$$Q_t(\ell_i)$$(p_i, \ell_i)$

$(p_i, \ell_i)$

$Q_t(p_i)$$Q_t(p_j)$${p}'_k$${\ell}'_k$ao conjunto de linhas de P2. Deixe cada linha fictícia ter dois pontos nela. Se P1 der o valor certo para um ponto fictício em uma linha e o valor errado para o outro ponto fictício, ele se revelou um mentiroso, já que não há como P2 dar o valor para uma linha que é corrija um dos dois pontos de P1 e não o outro. Podemos fazer um truque semelhante para fazer com que a resposta P2 seja consistente. A única coisa que resta é mostrar que o último passo da prova Feige-Kilian ainda funciona. Isso acaba sendo direto, embora analisar os detalhes tornaria essa resposta muito mais longa.