Quão difícil é a máfia?

Mafia é um popular role-playing game em festas, uma descrição detalhada está disponível na wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 .

Basicamente, funciona da seguinte maneira:

• No início, cada um dos jogadores recebe secretamente um papel, alinhado com a Máfia ou com a Cidade. Cada função pode ter habilidades especiais; mais sobre isso mais tarde.$N$

• Existem duas fases do jogo: dia e noite. À noite, a máfia pode se comunicar secretamente entre si; e eles podem concordar com um jogador alvo que eles assassinaram naquela noite. No dia, todos os jogadores (vivos) se comunicam em um fórum aberto. Os jogadores podem concordar em linchar um jogador, é necessária uma maioria absoluta de todos os jogadores.

• O jogo termina se restar apenas a máfia ou apenas a cidade. O partido sobrevivente vence.

• Vamos assumir que existem três papéis: Cidadão, Investigador e Mafioso. Os cidadãos não têm poderes. Os mafiosos também não têm habilidades além de poderem se comunicar à noite e votar em uma vítima de assassinato a cada noite. Os investigadores podem investigar um outro jogador a cada noite, descobrindo seu papel exato.

• Suponha que o jogo comece no dia e que o papel de um jogador seja revelado após a morte

Estratégias vencedoras

Dada uma configuração de Investigators, Citizen e Mafiosi, dizemos que a configuração está ganhando para o Town , se houver uma estratégia para os jogadores do Town, de forma que eles ganhem, não importa como Máfia toca.$(i,c,m)$$i$$c$$m$

Observe que podemos assumir que a Máfia brinca com informações completas, já que queremos dar conta de qualquer decisão que eles possam tomar.

Exemplo: A configuração vence pela Cidade.$(4,1,1)$

Dia 1: Todos os jogadores da Town relatam sinceramente seu papel no chat aberto. O jogador da Máfia deve reivindicar ser Investigador ou Cidadão.

Se ele reivindica Cidadão, o Mafioso é um dos dois supostos Cidadãos. Cada investigador pode investigar qualquer um deles e descobrirá o verdadeiro. No máximo, um investigador pode morrer à noite e os outros dois simplesmente enforcam o mafioso.

Portanto, o mafioso deve reivindicar o investigador. Existem 5 supostos investigadores. No bate-papo aberto, os investigadores concordam com uma permutação para verificar um ao outro.

Noite 1: Os investigadores verificam seus alvos e o mafioso mata um.

Dia 2: Restam 3 investigadores. Todos os alegados investigadores relatam suas descobertas. Não importa quem foi morto, pelo menos um deles também é confirmado por outro investigador vivo. Desde que o mafioso reivindicou o investigador, ele também precisa dizer se o alvo designado era a máfia ou não. Se ele enquadrar alguém, a Cidade saberá que ele ou a pessoa emoldurada é a Máfia, contra a outra cidade confirmada. Se ele não enquadrar ninguém, também haverá três cidades confirmadas. De qualquer maneira, não enforcando ninguém, e investigando os únicos 2 suspeitos restantes vence o Town.

Questões

• Quão difícil é decidir se uma determinada organização admite uma estratégia vencedora para a Town? Intuitivamente, isso soa como um completo do . Alguém pode propor uma redução?$PSPACE$
• Podemos encontrar configurações vencedoras mínimas? Como podemos minimizar as razões ou ?$i:m$$(i+c):m$

Aqui está uma referência que você deseja consultar: http://www.jstor.org/stable/10.2307/25442651

Máfia: Um estudo teórico de jogadores e coalizões em um ambiente de informação parcial Braverman, M. e Etesami, O. e Mossel, E. Os Anais da Probabilidade Aplicada 2008

Antes de tudo, observe que é sempre bom começar o jogo perguntando a cada cidadão qual é o seu papel se estamos procurando uma estratégia determinista de vitória para a Town. Isso ocorre porque, não importa o que os mafiosos se declarem vencedores da cidade, obviamente não há mal algum em perguntar. E se os mafiosos podem se declarar alguma coisa e vencer nesse caso, então eles fingem que fizeram a declaração e agem de acordo.

Além disso, um jogo como esse provavelmente não será completo no PSPACE, pois não há estrutura subjacente. Eu acredito firmemente que não é difícil analisar o jogo para todos os valores de i, c, m. Abaixo eu faço isso para m = 1. Então, a partir de agora, vamos supor que exista apenas um mafioso, M, e o jogo começa com a pergunta dos papéis. Agora M afirma investigador ou cidadão. Vamos verificar os dois casos.

Caso 1: M alega investigador

Se i = 0, a cidade vence se c for pelo menos 2.

Se i = 1, a cidade vence se c for pelo menos 4. Para números menores, eles perdem porque M pode matar um cidadão a cada noite.

Se i = 2, Town vence se c for pelo menos 3. Os três supostos investigadores podem se perguntar em ordem circular. M é revelado, a menos que um deles morra, então ele deve matar um investigador. Isso reduz o jogo ao caso i = 1.

Se i = 3, Town vence se c for pelo menos 1. Os 4 supostos investigadores podem se perguntar em uma ordem circular. M é revelado, a menos que um deles morra, então ele deve matar um investigador. Agora existem (no máximo) duas possibilidades para M e pelo menos 5 pessoas restantes, para que elas possam matar as duas. Se c = 0, não importa como eles se perguntem, M sempre pode matar alguém e permanecer oculto (por análise de caso), para que Town não tenha vitória determinística.

Se i> = 4, Town vence pelos supostos investigadores perguntando um ao outro em uma ordem circular, como no caso i = 3.

Caso 2: M reivindica cidadão

Aqui o jogo é muito mais simples, os investigadores perguntam a pessoas diferentes a cada rodada e M mata um deles a cada noite (é sempre melhor matar um investigador do que um cidadão). Além disso, às vezes eles podem votar para matar um cidadão (na verdade, é sempre bom fazê-lo, a menos que i = 2 ec = 1). Por causa do uso da recursão, é melhor também permitir que os cidadãos se mostrem inocentes e denotar seu número por n.

A cidade vence se

i = 0, n> = c + 2, i = 1, n> = c + 1, i = 2, n> = c-2, e a partir daqui podemos ver (e também facilmente provar) que, em geral, i Town ganha se e somente se n> = c + 2-i ^ 2. Como no jogo real não há cidadãos inocentes no início, isso significa que a Cidade vence se i ^ 2> = c + 2.

Juntando: a cidade não tem vitória determinística se i <= 2. Para i = 3, a cidade vence por 1 <= c <= 7 (como 0 M pode reivindicar investigador e para c> = 8, ele pode reivindicar cidadão). Para i> = 4, a cidade vence por c <= i ^ 2-2.