Jak ciężka jest mafia?

Mafia to popularna gra fabularna na imprezach, szczegółowy opis jest dostępny na stronie wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 .

Zasadniczo działa w następujący sposób:

• Na początku każdemu z graczy potajemnie przypisywana jest rola, dostosowana do mafii lub miasta. Każda rola może mieć specjalne umiejętności; więcej o tym później.$N$

• Istnieją dwie fazy gry: dzień i noc. W nocy mafia może się ze sobą potajemnie komunikować; i mogą uzgodnić jednego docelowego gracza, którego zamordują tej nocy. W dniu wszyscy (żywi) gracze komunikują się na otwartym forum. Gracze mogą zgodzić się na zlinczowanie jednego gracza, potrzebna jest absolutna większość wszystkich graczy.

• Gra kończy się, jeśli pozostała tylko mafia lub zostało tylko miasto. Drużyna, która przeżyła, wygrywa.

• Załóżmy, że istnieją trzy role: Obywatel, Śledczy i Mafioso. Obywatele nie mają uprawnień. Mafiosi nie mają też żadnych zdolności poza komunikowaniem się w nocy i głosowaniem na jedną ofiarę morderstwa każdej nocy. Badacze mogą badać każdego innego gracza każdej nocy, sprawdzając jego dokładną rolę.

• Załóżmy, że gra rozpoczyna się w dzień, a rola gracza ujawnia się po śmierci

Zwycięskie strategie

Biorąc pod uwagę konfigurację od í Detektywów, c obywateli, a m mafiosów, mówimy, że konfiguracja jest nagradzany za miasto , czy istnieje strategia dla graczy Town, tak, że wygrać, bez względu na to, w jaki sposób Gra mafia.$(i,c,m)$$i$$c$$m$

Pamiętaj, że możemy założyć, że mafia bawi się pełnymi informacjami, ponieważ chcemy uwzględnić każdą decyzję, jaką mogą podjąć.

Przykład: Setup wygrywa dla Town.$(4,1,1)$

Dzień 1: Wszyscy gracze z miasta zgodnie z prawdą zgłaszają swoją rolę na czacie otwartym. Gracz mafii musi twierdzić, że jest Badaczem lub Obywatelem.

Jeśli twierdzi, że jest Obywatelem, to Mafioso jest jednym z dwóch rzekomych Obywateli. Każdy Badacz może zbadać jedno z nich i odkryje prawdziwą. Co najwyżej jeden Badacz może zginąć w nocy, a pozostali dwaj po prostu zawieszają Mafioso.

Dlatego mafioso musi żądać Śledczego. Istnieje 5 domniemanych Invesigators. Na otwartym czacie Badacze uzgadniają permutację, aby się wzajemnie sprawdzić.

Noc 1: Śledczy sprawdzają swoje cele, a Mafioso zabija jednego.

Dzień 2: Pozostało 3 Śledczych. Wszyscy domniemani detektywi zgłaszają swoje ustalenia. Bez względu na to, kto został zabity, przynajmniej jeden z nich jest potwierdzony przez innego żyjącego Badacza. Ponieważ Mafioso zajął się Badaczem, musi także powiedzieć, czy jego wyznaczonym celem była Mafia, czy nie. Jeśli kogoś wrobi, to Miasto wie, że albo on, albo w ramce jest Mafia, w porównaniu z drugim potwierdzonym 3 Miastem. Jeśli nikogo nie oprawi, pojawią się również 3 potwierdzone miasta. Tak czy inaczej, nie wieszanie nikogo i badanie tylko dwóch pozostałych podejrzanych wygrywa dla Town.

pytania

• Jak trudno jest zdecydować, czy dany układ przyznaje zwycięską strategię Town? Intuicyjnie wydaje się, że jest to kompletny problem Czy ktoś może zaproponować obniżkę?$PSPACE$
• Czy możemy znaleźć minimalne zwycięskie konfiguracje? Czy możemy zminimalizować współczynniki lub ( i + c ) : m ?$i:m$$(i+c):m$

Oto odniesienie, które chcesz obejrzeć: http://www.jstor.org/stable/10.2307/25442651

Mafia: Teoretyczne badanie graczy i koalicji w częściowym środowisku informacyjnym Braverman, M. i Etesami, O. i Mossel, E. The Annals of Applied Probability 2008

Przede wszystkim zauważ, że zawsze korzystne jest rozpoczęcie gry od pytania każdego obywatela o jego rolę, czy szukamy deterministycznej strategii zwycięstwa dla Town. Wynika to z faktu, że jeśli bez względu na to, co mafiosi ogłaszają, że wygrywa Miasto, nie ma wątpliwości, że pytać. A jeśli Mafiosi mogą coś ogłosić i wygrać w takim przypadku, udają, że zrobili deklarację i działali zgodnie z tym.

Ponadto taka gra prawdopodobnie nie będzie kompletna z PSPACE, ponieważ nie ma żadnej podstawowej struktury. Mocno wierzę, że nie jest trudno analizować grę pod kątem wszystkich wartości i, c, m. Poniżej robię to dla m = 1. Odtąd przypuśćmy, że jest tylko jedno mafioso, M, a gra zaczyna się od pytania o role. Teraz M albo twierdzi śledczego, albo obywatela. Sprawdźmy oba przypadki.

Przypadek 1: dochodzenie roszczeń M.

Jeśli i = 0, Town wygrywa, jeśli c wynosi co najmniej 2.

Jeśli i = 1, miasto wygrywa, jeśli c wynosi co najmniej 4. W przypadku mniejszych liczb przegrywają, ponieważ M może zabić obywatela każdej nocy.

Jeśli i = 2, Town wygrywa, jeśli c wynosi co najmniej 3. Trzech rzekomych badaczy może zadawać sobie pytania w kolejności okrężnej. M zostaje ujawnione, chyba że jeden z nich zginie, więc musi zabić Badacza. Sprowadza to grę do przypadku i = 1.

Jeśli i = 3, Town wygrywa, jeśli c wynosi co najmniej 1. 4 rzekomych badaczy może zadawać sobie pytania w kolejności okrężnej. M zostaje ujawnione, chyba że jeden z nich zginie, więc musi zabić Badacza. Teraz są (co najwyżej) dwie możliwości dla M i pozostało co najmniej 5 osób, więc mogą zabić obie. Jeśli c = 0, to niezależnie od tego, jak się zadają, M zawsze może kogoś zabić i pozostać w ukryciu (na podstawie analizy przypadków), więc Miasto nie ma deterministycznego zwycięstwa.

Jeśli i> = 4, Town wygrywa przez rzekomych badaczy pytających się nawzajem w kolejności okrężnej, jak w przypadku i = 3.

Przypadek 2: M. twierdzi, że jest obywatelem

Tutaj gra jest o wiele prostsza, badacze pytają różnych ludzi w każdej rundzie, a M zabija jedną z nich każdej nocy (zawsze lepiej zabić badacza niż obywatela). Czasami też mogą głosować za zabiciem obywatela (w rzeczywistości jest to zawsze w porządku, chyba że i = 2 ic = 1). Z powodu korzystania z rekurencji lepiej jest również pozwolić obywatelom okazać się niewinnym i podać ich liczbę przez n.

Miasto wygrywa, jeśli

i = 0, n> = c + 2, i = 1, n> = c + 1, i = 2, n> = c-2, i stąd możemy zobaczyć (i również łatwo udowodnić), że dla ogólnego i Town wygrywa wtedy i tylko wtedy, gdy n> = c + 2-i ^ 2. Ponieważ w prawdziwej grze na początku nie ma niewinnych obywateli, oznacza to, że miasto wygrywa, jeśli i ^ 2> = c + 2.

Podsumowując: miasto nie ma deterministycznej wygranej, jeśli i <= 2. Dla i = 3 miasto wygrywa dla 1 <= c <= 7 (jak dla 0 M może żądać badacza, a dla c> = 8, może żądać obywatela). Dla i> = 4 Town wygrywa dla c <= i ^ 2-2.