Dilema do Prisioneiro Algorithm

Question

Depois de assistir The Dark Knight fiquei bastante encantado com o conceito de Dilema do Prisioneiro. Há deve ser um algoritmo que que maximiza o próprio ganho dada uma situação.

Para aqueles que encontrar este estrangeira: http://en.wikipedia.org/wiki/ prisioneiro% 27s_dilemma

Muito, coisas muito interessantes.

Edit:? A questão é, o é, se houver, o algoritmo mais eficiente que existe para o Dilema do Prisioneiro

Answer 1

Uma vez que existe apenas uma escolha a fazer, e na ausência de quaisquer entradas mutáveis, seu algoritmo é ou vai ser:

cooperate = true;

... ou ...

cooperate = false

É mais interessante para encontrar uma estratégia para o Dilema do Prisioneiro Iterated, que é algo que muitas pessoas têm feito. Por exemplo http://www.iterated-prisoners-dilemma.net/

Mesmo assim, não é 'solucionável', uma vez que o outro jogador não é previsível.

Answer 2

A página wikipedia parece dar todas as respostas ... para o dilema do prisioneiro de uma só vez, a solução mais ideal para cada preso (não ambos prisioneiros) é trair.

Para o dilema do prisioneiro iterado, é melhor ficar em silêncio sobre o primeiro, e depois disso fazer o que quer que o outro prisioneiro fez na última vez.

Answer 3

O ponto de todo o dilema é que a solução ideal (tanto prisioneiros estadia tranquila) é perigoso porque parte do problema está fora de suas mãos. Assim, a escolha da solução sub-óptima parece maximizar o seu ganho, mas ainda é sub-ótima

Eu não vejo como um algoritmo poderia fornecer uma solução quando uma parte do problema é desconhecido.

Answer 4

Eu recomendo a leitura de Axelrod a evolução da cooperação . Este é um experimento do computador de estratégias competindo para o dilema do prisioneiro iterado. Quando eu ouvi falar disso último, a estratégia tit-for-tat saiu primeiro. Ele pode ter mudado.

Answer 5

Para a versão do jogo one-off, a melhor estratégia é sempre a defeito já que não há chance de retaliação.

Ele fica mais interessante para uma versão iterada desde que os jogadores podem responder às escolhas anteriores de seus oponentes.

Se sabemos de antemão exatamente quantas rodadas haverá, então a estratégia lógica "melhor" ainda é desertar sempre. Isso é porque ele sempre faz sentido para desertar na última volta, pois não há possibilidade de retaliação. Naturalmente, o nosso adversário racional vai saber isso e também sempre desertar na última volta. Isto torna mais sensata para nós a desertar na penúltima volta, pois não há possibilidade de cooperação na volta final de qualquer maneira. Seguindo esta lógica à sua conclusão natural, devemos desertar em cada turno.

Quando o número total de rodadas é desconhecido, as coisas tornam-se mais interessante. Uma boa estratégia para o jogo deve tentar prever o que o adversário vai fazer. Eu pesquisei usando evolutiva algoritmos e aprendizagem de máquina simples com modelagem adversário para gerar estratégias para o jogo para o meu mestrado. Se você é realmente interessado, você pode ler minha tese .

Como recomendado por Yuval, provavelmente o melhor lugar para começar é livro seminal de Axelrod . Se você é realmente interessado neste material, houve uma 20 º aniversário de acompanhamento que incluiu um lote do mais recente trabalho sobre IPD (Dilema do Prisioneiro Iterated) por outros pesquisadores.

Além disso, eu gostaria absolutamente recomendado Dilema do Prisioneiro de William Poundstone, que faz parte biografia de John von Neumann e introdução parte para a teoria dos jogos.

Answer 6

Bem, o meu entendimento, reconhecimento de padrões é uma grande parte dela também. Encontrar hábito do outro prisioneiro - quantas vezes ele fica quieto e quando ele Narcs. Você também tem a referência cruzada que, para suas próprias escolhas para determinar o que você fez para fazê-lo reagir de uma determinada maneira.

Eu acho que é um pouco mais complexa do que a wiki explicou. A sua não é apenas o que o prisioneiro fez na última vez, mas em tudo correr antes que o alongamento até ao infinito.

Answer 7

Não existe desde que você não pode categoricamente prever o comportamento do segundo prisioneiro.

Existem todos os tipos de "soluções" que fazem subjacente mas suposições muito restritivas sobre o comportamento do segundo prisioneiro, mas eles têm pouco a dizer sobre o problema sem restrições (que é o que o torna um dilema tão convincente).

Os meus dois centavos, uma vez que você não pode contar com o segundo comportamento prisioneiros é que tudo se resume a: você é um otimista ou um cínico? São os dois prisioneiros vão ficar juntos (honra entre ladrões), ou eles vão delatar uns aos outros na primeira oportunidade para salvar a sua própria garganta ...?

Answer 8

Além disso, em jogo uma iteradas dos prisioneiros a estratégia ideal varia de acordo com as outras estratégias em jogo.

Em uma série contra um jogador que defeitos SEMPRE SEMPRE deserção é a melhor estratégia. Ao jogar contra um jogador que pode cooperar, uma estratégia que retalia, mas ocasionalmente perdoa é provável que seja melhor.

Devo acrescentar que isso só se aplica em um jogo de comprimento desconhecido. Qualquer jogo de comprimento conhecido é idêntica ao jogo única rodada.

Answer 9

A tentativa de encontrar uma solução ideal para o Dilema do Prisioneiro é como tentar encontrar um para Ro-Sham-Bo (pedra-papel-tesoura.) O melhor que você pode fazer é modelar o seu adversário e tentar explorar padrões.

Nos primeiros dias da teoria dos jogos e ciência da computação, John von Neumann e da Rand Corporation passou grandes quantidades de crânio suor tentando chegar a um algoritmo optimal para resolver o Dilema do Prisioneiro, sem sucesso e, IIRC, eventualmente provou matematicamente que não havia nenhuma solução ótima.

Answer 10

Ah sim. Isso me fez lembrar este velho artigo sobre O Dilema do Prisioneiro em Desenvolvimento de Software

Para um olhar competição PD algorítmica aqui

Este foi uma boa também

Answer 11

O ponto de todo o dilema do prisioneiro é que a sua estratégia ideal é trair o outro prisioneiro. O (1)

Answer 12

Mathemaically os outros postos responder à pergunta, mas, na realidade, pode haver opções adicionais. No entanto absurdo estas opções são, eles vão resultar em possibilidades de resultados adicionais, e podem resultar em aumento da possibilidade de ganhos pessoais. Por exemplo, no caso de Batman, isso poderia arruinar a trama, mas ele poderia ter acabado de matar o Coringa - assim arruinando quaisquer efeitos adicionais o Coringa teria sobre o resultado. Ao deixar o Coringa ao vivo, Batman inadvertidamente permite que o Joker a única "vitória" que ele precisa.

Answer 13

O jogo se torna muito mais interessante quando você passo para trás e considerar todo o torneio. Por exemplo, há alguns anos atrás uma PD torneio foi ganho por uma equipa do Reino Unido que apresentou múltiplas entradas. Um deles foi o "mestre" e o outro eram "escravos". Todos eles iriam começar jogando uma seqüência específica de ações que permitam os senhores e escravos a reconhecer uns aos outros. Uma vez reconhecido o mestre iria desertar eo escravo iria cooperar para o resto das iterações. Assim, o mestre ganhou o torneio, mas à custa dos escravos.

A estratégia faz sentido econômico como havia um prémio monetário para o primeiro lugar, mas o custo de entrada eram baixos.

De modo mais geral, ao escrever um programa para um torneio TD você precisa olhar para a foto maior:

1. como são os prémios atribuídos?
2. você pode conspirar com outros concorrentes?
3. Quais são os custos de entrada? penalidades?

Caso contrário, sim, a estratégia dominante é a de defeito no PD one-shot. Axelrod, como outros mencionados, mostrou que tit-for-tat foi robusto em uma série de torneios, mas nestes torneios ninguém pensou em conspirar com outros concorrentes.