¿Qué tan difícil es la mafia?

Mafia es un popular juego de rol en fiestas, una descripción detallada está disponible en wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 .

Básicamente, funciona de la siguiente manera:

• Al principio, a cada uno de los jugadores se le asigna un rol en secreto, ya sea alineado con la mafia o con la ciudad. Cada rol puede tener habilidades especiales; Más sobre eso más tarde.$N$

• Hay dos fases de juego: día y noche. Por la noche, la mafia puede comunicarse en secreto entre sí; y pueden ponerse de acuerdo sobre un jugador objetivo al que asesinan esa noche. En Day, todos los jugadores (vivos) se comunican en un foro abierto. Los jugadores pueden acordar linchar a un jugador, se necesita una mayoría absoluta de todos los jugadores.

• El juego termina si solo queda la mafia o solo queda la ciudad. La parte sobreviviente gana.

• Supongamos que hay tres roles: ciudadano, investigador y mafioso. Los ciudadanos no tienen poderes. Los mafiosos tampoco tienen habilidades más allá de poder comunicarse entre sí por la noche y votar por una víctima de asesinato cada noche. Los investigadores pueden investigar a otro jugador cada noche, descubriendo su papel exacto.

• Supongamos que el juego comienza en el día y que el papel de un jugador se revela al morir

Estrategias ganadoras

Dada una configuración de Investigators, Citizen Mafiosi, decimos que la configuración está ganando para Town , si hay una estrategia para los jugadores de Town, de modo que ganen, sin importar cómo La mafia juega.i c $(i,c,m)$$i$$c$$m$

Tenga en cuenta que podemos suponer que la Mafia juega con toda la información, ya que queremos dar cuenta de cualquier decisión que puedan tomar.

Ejemplo: La configuración gana para la ciudad.$(4,1,1)$

Día 1: Todos los jugadores de Town informan sinceramente su papel en el chat abierto. El jugador de la mafia tiene que reclamar ser investigador o ciudadano.

Si él reclama Ciudadano, entonces el Mafioso es uno de los dos supuestos Ciudadanos. Cada investigador puede investigar cualquiera de los dos y descubrirá el verdadero. Como máximo, un investigador puede morir en la noche, y los otros dos simplemente cuelgan al mafioso.

Por lo tanto, el mafioso debe reclamar Investigador. Hay 5 presuntos investigadores. En el chat abierto, los investigadores acuerdan una permutación para comprobarse entre sí.

Noche 1: Los investigadores verifican sus objetivos, y el mafioso mata a uno.

Día 2: quedan 3 investigadores. Todos los presuntos investigadores informan sus hallazgos. No importa quién fue asesinado, al menos uno de ellos también es confirmado por otro investigador vivo. Como el mafioso reclamó al investigador, también necesita decir si su objetivo asignado era la mafia o no. Si enmarca a alguien, entonces la Ciudad sabe que él o el enmarcado es Mafia, contra la otra 3 Ciudad confirmada. Si no enmarca a nadie, también habrá 3 Town confirmados. De cualquier manera, sin colgar a nadie, e investigando los únicos 2 sospechosos que quedan gana para Town.

Preguntas

• ¿Qué tan difícil es decidir si una configuración dada admite una estrategia ganadora para Town? Intuitivamente, esto suena como un problema completo de ¿Alguien puede llegar a una reducción?$PSPACE$
• ¿Podemos encontrar configuraciones ganadoras mínimas? Como en podemos minimizar las proporciones o ( i + c ) : m ?$i:m$$(i+c):m$

Aquí hay una referencia que querrá ver: http://www.jstor.org/stable/10.2307/25442651

Mafia: un estudio teórico de jugadores y coaliciones en un entorno de información parcial Braverman, M. y Etesami, O. y Mossel, E. The Annals of Applied Probability 2008

En primer lugar, tenga en cuenta que siempre es beneficioso comenzar el juego preguntándole a cada ciudadano su papel si estamos buscando una estrategia ganadora determinista para Town. Esto se debe a que si no importa lo que los mafiosos declaren que el pueblo gana, obviamente no es malo preguntar. Y si los mafiosos pueden declararse algo y ganar en ese caso, fingen que hicieron la declaración y actúan en consecuencia.

Además, un juego como este probablemente no será completo para PSPACE ya que no hay una estructura subyacente. Creo firmemente que no es difícil analizar el juego para todos los valores de i, c, m. A continuación hago esto para m = 1. Entonces, de ahora en adelante, supongamos que hay un solo mafioso, M, y el juego comienza con la pregunta de los roles. Ahora M o reclama investigador o ciudadano. Veamos ambos casos.

Caso 1: investigador de reclamos M

Si i = 0, entonces Town gana si c es al menos 2.

Si i = 1, entonces Town gana si c es al menos 4. Para números más pequeños pierden porque M puede matar a un ciudadano cada noche.

Si i = 2, entonces Town gana si c es al menos 3. Los 3 presuntos investigadores pueden preguntarse entre sí en orden circular. M se revela a menos que uno de ellos muera, por lo que debe matar a un investigador. Esto reduce el juego al caso i = 1.

Si i = 3, entonces Town gana si c es al menos 1. Los 4 presuntos investigadores pueden preguntarse entre sí en orden circular. M se revela a menos que uno de ellos muera, por lo que debe matar a un investigador. Ahora hay (como máximo) dos posibilidades para M y quedan al menos 5 personas, por lo que pueden matar a ambas. Si c = 0, entonces no importa cómo se pregunten, M siempre puede matar a alguien y permanecer oculto (por análisis de caso), por lo que Town no tiene una victoria determinista.

Si i> = 4, entonces Town gana por los supuestos investigadores preguntándose en orden circular, como en el caso i = 3.

Caso 2: M reclama ciudadano

Aquí el juego es mucho más simple, los investigadores preguntan a diferentes personas en cada ronda y M mata a uno de ellos cada noche (siempre es mejor matar a un investigador que a un ciudadano). Además, a veces pueden votar para matar a un ciudadano (de hecho, siempre está bien hacerlo, a menos que i = 2 y c = 1). Debido al uso de la recursividad, es mejor también permitir que los ciudadanos demuestren ser inocentes y denotar su número con n.

La ciudad gana si

i = 0, n> = c + 2, i = 1, n> = c + 1, i = 2, n> = c-2, y desde aquí podemos ver (y también probar fácilmente) que para la ciudad general i gana si y solo si n> = c + 2-i ^ 2. Como en el juego real no hay ciudadanos inocentes al principio, esto significa que la Ciudad gana si i ^ 2> = c + 2.

Poniéndolo todo junto: la ciudad no tiene una victoria determinista si i <= 2. Para i = 3, Town gana por 1 <= c <= 7 (en cuanto a 0 M puede reclamar investigador y para c> = 8, puede reclamar ciudadano). Para i> = 4, Town gana por c <= i ^ 2-2.