How hard is Mafia?

Question

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.

Basically, it works as follows:

• At the beginning, each of the $N$ players is secretly assigned a role, either aligned with the Mafia or with the Town. Each role may have special abilities; more about that later.

• There are two game phases: Day and Night. At Night, the Mafia can communicate secretly with each other; and they may agree upon one target player who they murder that night. At Day, all (alive) players communicate in an open forum. The players may agree to lynch one player, an absolute majority of all players is needed.

• The game ends if there is only the Mafia left, or there is only the Town left. The surviving party wins.

• Let's assume that there are three roles: Citizen, Investigator, and Mafioso. Citizens have no powers. Mafiosi also have no abilities beyond being able to communicate with each other at night and voting for one murder victim each night. Investigators can investigate one other player in each night, finding out their exact role.

• Assume the game starts at day, and that the role of a player is revealed upon death

Winning strategies

Given a setup $(i,c,m)$ of $i$ Investigators, $c$ Citizen, and $m$ Mafiosi, we say that the setup is winning for Town, if there is a strategy for the Town players, such that they win, no matter how the Mafia plays.

Note that we can assume that the Mafia plays with full information, since we want to account for any decision they can make.

Example: The setup $(4,1,1)$ wins for Town.

Day 1: All Town players truthfully report their role in the open chat. The Mafia player has to claim to be either Investigator or Citizen.

If he claims Citizen, then the Mafioso is one of the two alleged Citizens. Each Investigator can investigate either one, and will find out the true one. At most one Investigator can die in the night, and the other two simply hang the Mafioso.

Hence, the Mafioso must claim Investigator. There are 5 alleged Invesigators. In the open chat, the Investigators agree upon a permutation to check each other.

Night 1: The Investigators check their targets, and the Mafioso kills one.

Day 2: There are 3 Investigators left. All alleged Investigators report their findings. No matter who was killed, at least one of them is also confirmed by another alive Investigator. Since the Mafioso claimed Investigator, he also needs to say if his assigned target was Mafia or not. If he frames someone, then the Town knows that either he, or the framed one is Mafia, against the other confirmed 3 Town. If he does not frame anybody, there will also be 3 confirmed Town. Either way, not hanging anyone, and investigating the only 2 left suspects wins for Town.

Questions

• How hard is it to decide whether a given setup admits a winning strategy for Town? Intuitively, this sounds like a $PSPACE$-complete problem. Can anybody come up with a reduction?
• Can we find minimal winning setups? As in can we minimize the ratios $i:m$ or $(i+c):m$?

Answer 1

Here's a reference that you will want to look at: http://www.jstor.org/stable/10.2307/25442651

Mafia: A theoretical study of players and coalitions in a partial information environment Braverman, M. and Etesami, O. and Mossel, E. The Annals of Applied Probability 2008

Answer 2

First of all, note that it is always beneficiary to start the game with asking each citizen their role if we are looking for a deterministic winning strategy for Town. This is because if no matter what the Mafiosi declare themselves the Town wins, then it is obviously no harm to ask. And if the Mafiosi can declare themselves something and win in that case, then they pretend that they did the declaration and act accordingly.

Also, a game like this probably won't be PSPACE-complete as there is no underlying structure. I strongly believe that it is not hard to analyze the game for all values of i, c, m. Below I do this for m=1. So from now on let us suppose that is there is only one mafioso, M, and the game starts with asking the roles. Now M either claims investigator or citizen. Let us check both cases.

Case 1: M claims investigator

If i=0, then Town wins if c is at least 2.

If i=1, then Town wins if c is at least 4. For smaller numbers they lose because M can kill a citizen each night.

If i=2, then Town wins if c is at least 3. The 3 alleged investigators can ask each other in a circular order. M is revealed unless one of them dies, so he must kill an investigator. This reduces the game to the case i=1.

If i=3, then Town wins if c is at least 1. The 4 alleged investigators can ask each other in a circular order. M is revealed unless one of them dies, so he must kill an investigator. Now there are (at most) two possibilities for M and at least 5 people left, so they can kill both. If c=0, then no matter how they ask each other, M can always kill somebody and stay hidden (by case analysis), so Town has no deterministic win.

If i>=4, then Town wins by the alleged investigators asking each other in a circular order, as in the case i=3.

Case 2: M claims citizen

Here the game is a lot simpler, the investigators ask different people in every round and M kills one of them each night (it is always better to kill an investigator than a citizen). Also, sometimes they might vote to kill a citizen (in fact, it is always ok to do so, unless i=2 and c=1). Because of using recursion, it is better to also allow citizens proved to be innocent, and denote their number by n.

Town wins if

i=0, n>=c+2, i=1, n>=c+1, i=2, n>=c-2, and from here we can see (and also easily prove) that for general i Town wins if and only if n>=c+2-i^2. Since in the real game there are no innocent citizens at the beginning, this means that the Town wins if i^2>=c+2.

Putting it together: Town has no deterministic win if i<=2. For i=3, Town wins for 1<=c<=7 (as for 0 M can claim investigator and for c>=8, he can claim citizen). For i>=4, Town wins for c<=i^2-2.