Equilíbrio em um jogo de parada

10

Considere o seguinte jogo para 2 jogadores:

  • A natureza escolhe aleatoriamente um programa
  • Cada jogador toca um número em [0, infinito], inclusive em resposta ao movimento da natureza
  • Pegue o mínimo dos números dos jogadores e execute o programa por (até) muitas etapas (a menos que ambos os jogadores tenham escolhido o infinito)
  • Se o programa parar, o jogador que jogou o número mínimo ganha 1 ponto. Se o programa não parar, esse jogador perde 1 ponto. Qualquer jogador que jogou um número não mínimo recebe 0 pontos, e ambos recebem 0 se ambos jogam infinito.

(Os casos de canto podem ser tratados da maneira que melhor preservar o espírito do problema - por exemplo, a semicontinuidade superior pode ser útil.)

A questão: este jogo possui um equilíbrio computável de Nash?

Sem o requisito de computabilidade, cada jogador apenas executa o número exato de etapas em que o programa pára (ou infinito, se não parar).

Se você tentar o argumento usual de diagonalização para o problema de interrupção, descobrirá que existe um equilíbrio em estratégias mistas; portanto, a abordagem óbvia não funciona imediatamente. Talvez haja alguma maneira de ajustá-lo?

Por outro lado, a equivalência de campos reais fechados significa que jogos finitos com payoffs computáveis ​​têm equilíbrios computáveis . Este jogo não é finito, mas o espaço da estratégia está fechado e as recompensas computáveis, então talvez o mesmo truque possa ser aplicado com o Teorema de Glicksberg ou algo nesse sentido? O problema é que, sem o requisito de computabilidade, o equilíbrio está em estratégias puras, portanto, qualquer tentativa de provar a existência de um equilíbrio computável usando a existência de um equilíbrio talvez computável deve explicar por que o equilíbrio é rebaixado de puro para misto.

Esse parece ser o tipo de problema em que as pessoas podem não ter abordado exatamente essa pergunta antes, mas podem ter procurado algo semelhante. Não pude aparecer muito, mas se alguém souber de algo em espírito, me avise!

Motivação: existe uma intuição comum de que a auto-referência é o principal bloco da computabilidade - ou seja, que qualquer problema incontestável de alguma forma incorpora a auto-referência. Se um jogo desse tipo tivesse um equilíbrio computável de Nash, isso forneceria evidências dessa intuição.

ATUALIZAÇÃO: Para esclarecer, o equilíbrio deve ser "computável" no sentido de números reais computáveis: as probabilidades que descrevem a distribuição da estratégia mista devem ser computáveis ​​com precisão arbitrária. (Observe que apenas muitas probabilidades finitas estarão acima de qualquer corte de precisão específico.) Isso também significa que podemos amostrar a partir de uma aproximação arbitrariamente próxima da estratégia de equilíbrio.

John Wentworth
fonte
Sua atualização também considera as peças como números reais computáveis? (ou seja, eles podem desempenhar um número com probabilidade 1 sem saber se-ou-não que o número é infinito?)
Estamos autorizados a conhecer a distribuição do oponente?
Bjørn Kjos-Hanssen
Ricky: as jogadas podem ser consideradas reais computáveis, mas o truncamento para um número inteiro deve dominar qualquer jogo finito não inteiro, pois um programa será executado apenas por um número inteiro de etapas (ou infinito). Não tenho certeza se entendi seu exemplo entre parênteses, por isso posso estar entendendo mal sua pergunta.
John Wentworth
Bjørn: Sim. Suponha que a distribuição da natureza seja conhecida e coloque peso diferente de zero em todos os programas válidos. Suponha também que cada jogador conhece a estratégia do outro jogador (ou seja, distribuição).
John Wentworth
@ johnwentworth, use @ ou eles não podem ver sua resposta.
rus9384

Respostas:

11

1 1/2EuEutjtjjt

Lance Fortnow
fonte
Gosto dessa construção - ela estabelece que qualquer equilíbrio de Nash deve ser reproduzido corretamente em todos os programas. É necessário um passo adicional para estabelecer que ele resolva o problema de parada, uma vez que as distribuições precisam convergir para um desempenho perfeito no limite de alta precisão (e, portanto, computação infinita). Como sabemos que a saída deve colocar o peso unitário em um número inteiro, acho que é suficiente calcular as probabilidades da estratégia em 1/4 e depois pegar o número inteiro com peso maior que 1/2.
John Wentworth