Wednesday, August 31, 2005

How Commoners can beat the Mafia (most of the time)

For those who have never played the party game Mafia, here are the rules:

  1. An arbiter is selected at random from the players. Call the other players "townspeople".
  2. The arbiter uses some random, secret procedure to designate some small fraction (say, 1/4) of the townspeople as Mafia, and the rest as Commoners. One way that works is to take one slip of paper for each player, write down "Mafia" or "Commoner" on each slip, and have players draw from a hat.
  3. All the players to close their eyes. Then, at the arbiter's signal, only the Mafiosi open their eyes and look around, so they know the identities of all the other Mafia.
  4. The play proceeds in rounds. Each round goes as follows:
    1. First, all the players discuss who might be Mafia, and then vote to execute one person as a Mafioso.
    2. The person who gets the most votes is executed. If there is a tie, the arbiter should flip a coin. The dead player leaves the game, at which point the arbiter informs the town whether that person was a Commoner or a Mafioso.
    3. Dead players tell no tales. Once dead, a player may not communicate with living players for the remainder of the game.
  5. Play proceeds until either the entire Mafia is dead, or all the Commoners are dead. The living team wins.

In practice, the Mafia wins as soon as they're a majority, because then they can always outvote the Commoners and execute them all.

What makes this game fun is the social interaction and politicking that goes on when you're deciding whom to execute. The Mafiosi are all trying to influence the voting so that a Commoner gets executed on each round. Meanwhile, the Commoners are trying to detect excessive certainty or bloodlust (which probably indicates a Mafioso --- after all, only Mafia know for certain whom they want executed), so the Mafia can't appear too eager or obvious. It's also a game of teamwork --- a lone clever Commoner can't beat the Mafia unless (s)he can also convince the other suspicious townspeople to trust him/her. A cleverly played game of Mafia will ultimately be won by the Mafia, if they're better actors, or by the Commoners, if they're better at "reading" people. With the right group, this can be lots of fun.

Now I'm going to tell you how to take all the fun out of Mafia. Propose the following strategy to your fellow townspeople:

  1. During the first round of discussion, use some mechanism to produce a random ordering of players. One way that works is for everyone to roll a pair of dice, and sort people from highest to lowest roll, rolling again to break ties. Note: if you use this method, you must decide on the exact method for sorting, including whether you're going from low-to-high or high-to-low, before you actually roll the dice.
  2. Agree that everyone will vote to eliminate the players in order. Anyone who dissents from this plan must be a Mafioso, and becomes the next target of execution instead of the scheduled player.

Why does this work? Notice the victory conditions: the Commoners win when 100% of the Mafia dies; the Mafia wins when when they outnumber the Commoners. Given that the Commoners have a large majority, most random orderings of the townspeople will list 100% of the Mafia before any point where the remaining Mafia outnumber the remaining Commoners.

Proving this claim formally requires some fairly intense math. I looked at it for a few minutes with one of my friends (who was also a computer scientist). We decided it was hard, and just handwaved our way through it.

(If you're curious, here's the handwaving: on average, over all random sortings, you expect the proportion of Mafia and Commoners in the remaining population to remain roughly constant as the population decreases; so the Mafia will usually not attain a majority. Then, once you get down to a small number of remaining players --- say, N, where 1/N is the fraction of Mafiosi in the original population --- then you expect that, on average, there will be 1 Mafioso left out of those N players. The chance that this Mafioso will be the last one standing is 1/N. Since N > 2, the last Mafioso probably doesn't survive.)

So, on average, over a large number of games, this is a winning strategy for the Commoners. Only Mafiosi would dissent from it; but the really cool thing is that they can't do anything about it, because if they dissent then they reveal that they belong to the Mafia. Even if all of them dissent together, they're outnumbered, so the Commoners will just execute them all. And even if the Mafia win --- as they sometimes will --- the win doesn't give them much satisfaction, since it wasn't through the exercise of wit and deception but just a random roll of the dice.

When you play the game by this strategy --- and I have done it once --- the game goes pretty fast. Everyone votes unanimously to execute the next player on the list. There's no discussion, no politicking, no doubt, and the game becomes a rather grimly fatalistic exercise until the arbiter calls the end. On the other hand, as the person who devised this strategy, I enjoyed watching it play out.

The Commoners won, by the way. Ironically, I was on the Mafia team that time.


UPDATE 9:30 p.m.: I got curious, so I wrote a Python script to simulate many games of Mafia in aggregate. Basically, the handwaving analysis above is a decent approximation of the actual results for typical party-sized populations (6-30 people) and small fractions of Mafia. At a population of 25% Mafia, the Mafia wins about 25% of the time. As the number of Mafia increases, however, the results begin to diverge from this analysis, due to the asymmetry in winning conditions: the Mafia win at a rate that exceeds their fraction of the population. At about 39% Mafia, the game becomes 50/50 Commoners v. Mafia.

The source for the script follows. It's a pretty direct interpretation; I haven't tried to do any of the obvious optimizations for simulating games.

#!/usr/bin/env python

import random

TRIALS         = 100000
MAFIA_FRACTION = 0.39
MIN_POP        = 6
MAX_POP        = 30
HIT_VARIANT    = 0

COMMONER = 0
MAFIA    = 1

maf_wins = 0
com_wins = 0

def init_town():
    popsize = random.randint(MIN_POP,MAX_POP)
    town = [COMMONER for j in range(0,popsize)]
    maf_count = int(MAFIA_FRACTION * popsize)
    for j in range(maf_count):
        while 1:
            idx = random.randint(0,popsize-1)
            if town[idx] != MAFIA: break
        town[idx] = MAFIA
    return town

def hit_commoner(town):
    if COMMONER not in town:
        return town
    else:
        com = town.index(COMMONER)
        return town[:com] + town[com+1:]

for i in range(TRIALS):
    town = init_town()
    while len(town) > 0:
        town = town[1:]
        if HIT_VARIANT: town = hit_commoner(town)
        maf_left = town.count(MAFIA)
        pop_left = len(town)
        if maf_left > (pop_left/2):
            maf_wins += 1
            break
        elif maf_left == 0:
            com_wins += 1
            break

print "Commoner wins  : " + str(com_wins)
print "Mafia wins     : " + str(maf_wins)
print ("Mafia fraction : " +
       str(float(maf_wins)/float(maf_wins+com_wins)))

UPDATE 1 Sept: In comments, Andrew and AJ reminded me of a variation of the rules, wherein the Mafia get to secretly "hit" one Commoner in each round, after execution. I've fixed the script so that the HIT_VARIANT flag controls whether to play with this variation. The results are surprising --- see comments for details...

21 comments:

  1. You must play a different version than I'm used to - when I play, the townspeople "go to sleep each night" (i.e. after each round of execution) and the mafia kill one townsperson.

    ReplyDelete
  2. I've played that variant before, too. In my opinion, it makes the game both unbalanced and less fun. The Mafia has an enormous advantage, and the game goes really quickly because the deaths go twice as fast.

    I'm not sure how my strategy fares in this variation. Presumably the Commoners need a larger numerical advantage to win reliably. I could fix my script to simulate it, but it's late and I'm feeling lazy.

    ReplyDelete
  3. Oh, I don't know, I guess with the mafia-killing version it would be more unbalanced (though this is less of an issue if you have more people and fewer mafia), but then you get to have a lot more fun accusing each other of vengeance etc., eg "See! John just got killed and who was he accusing last round? Alice and Bob!! It must be them!" "Oh please, that's just a decoy - the real mafia killed John to make you *think* it was Alice and Bob..." Maybe this is more fun when you're friends with the other players...

    ReplyDelete
  4. OK, now I'm really surprised, because I modified my simulation script to use this variation, and it appears that the tipping point where Commoners have an advantage is about 36% Mafia. In other words, giving Mafia the option to "hit" only gives them a 3% bump against the random-sort strategy! And at 25% Mafia, the strategy outlined above still keeps Mafia down to about 29.7% wins.

    I've updated the script above with a flag that enables this variation. Try it yourself to see...

    ReplyDelete
  5. Hmmm, I think I was too hasty. I fixed a bug and now I'm getting tipping points closer to 33% Mafia. Still, pretty surprising.

    ReplyDelete
  6. Your mafiosi aren't using a very smart strategy: if they know the execution order in advance, they should clearly execute the lowest ranking commoner each round, until they reach a mafioso. At this point, assuming the commoners maintain their order, the mafioso are guaranteed victory. Alternately, if the commoners adopt the strategy as programmed, and not as described in the text, where the execution is randomized each round, the mafioso don't gain nearly as much of an advantage.

    ReplyDelete
  7. Ah, clever!

    Actually, in the simulation, the execution order is determined in advance (town = town[1:] is the line that performs executions --- we execute the first person on the list). Nothing would really be gained by making the simulation choose a random person to execute in each round, since the knowledge of the players is not taken into account in simulation; the execution order is effectively secret.

    In the real-world "hit variant", your strategy indeed defeats the naive Commoner strategy I proposed. However, there's a further wrinkle. The execution order is public, so as soon as the Mafia stops executing people in lowest-to-highest order, the next person in order is known to be a mafioso, and can be scheduled for execution. Unless, that is, the Mafia are crafty, and stop one person short; but then, the Commoners could take this into account, and execute the next two; but then the Mafia could...

    At this point we return to the same wilds of infinitely recursive second-guessing and uncertainty that characterize the original game. Clearly, as you suggest, the execution order should not be determined in advance, so that the Mafia cannot strategize against it. I suggest that the townspeople arrange to draw slips of paper from a hat in each round.

    ReplyDelete
  8. nice analyses - thought you would be interested: original rules

    i also was trying to find winning mafia's strategies for a long time. failed so far. also take a look at this: multi-agent mafia.

    nice thinking, anyway.

    ReplyDelete
  9. Thanks, very useful!

    So, under the original rules, "Mafia night" (when the hits happen) only occur when a majority of townspeople agree. Therefore, the Commoners ("Honest") can postpone "Mafia night" indefinitely as long as they're in the majority, making it equivalent (under the randomization strategy) to the non-hit variant.

    Incidentally, the existence of a Commoner-winning strategy rules out the existence of a Mafia-winning strategy, doesn't it?

    ReplyDelete
  10. sure one can postpone mafia night indefinately, and just kill everybody around thus winning the game. but for an honest player to save as much lives as possible is one of the game priorities. thats why your random killing scheme would be rejected by me - even if i am not in the mafia. and in fact i did succesfully argue this point in few mafia games against the similar strategies.

    by winning mafia's strategies, i meant strategies for winning a mafia game. as a commoner or mafia - doesn't matter.

    ReplyDelete
  11. Saving lives is only an argument for rejecting the randomized strategy if one can propose a strategy with a better success rate.

    Anecdotally, people report that "straight" games seem to go roughly 50/50, which means 100% of Commoners die about half the time and some (probably large) fraction dies the other half of the time. In simulation, the randomized strategy has a much better victory ratio for Commoners. Unless most of the 50% of Commoner wins are overwhelming victories (where very few Commoners die), I don't believe that rejecting the randomized strategy actually saves lives on average.

    ReplyDelete
  12. sure, just handful of game ends up with one commoner standing (best outcome for a randomized strategy). usually, group learns from previous games and number of survivors grows with experience.

    ReplyDelete
  13. this is a very interesting strategy. so basically, if the towns people stick to their order, the mafia have a %50 chance of winning (if they stick to killing the lowest person till it hits a mafioso)that is, if theirs only one. if 2; 75%, if 3; 87.5%, and so on, adding half of the previous commoner winning percent. i say this because they have a 50/75/87.5 or whatever % of mafioso being lower then half. because if all are higher then half then they can never kill ALL the people after them before they get killed themselves. BUT if the commoners see a sudden stop in the killings of the last person, then the commoners will obviously change the plan, but then again they could think it was a trick and so on and so on.

    ReplyDelete
  14. To use a reverse order hit-list without detection the Mafia could use the fact that with complete information any player in a certain position relative to the mafia members is equivalent to any other player in the same relative position.
    Then they should eliminate players to be lynched after the final mafia member in an order cloe enough to random that it won't immediately appear to be ordered selection. This apparent disorder would allow some numbers to be 'skipped' for several turns without arousing suspicion even if somone does realise the strategy in use - it could be Mafia(n) or it could be a commoner who has been given a few turns reprieve in order to make selection appear random.

    ReplyDelete
  15. I've never played mafia where mafia doesn't kill.. that just seems stupid. Also, the number of mafia is generally known and is about 1/3-1/4 of the total population, depending. But i absolutely refuse to believe that determining a public random order of lynching will result in a higher town win rate...

    Also, plenty of townies will dissent from the plan -- you claim that only a mafia would dissent from the plan. In fact, if I were mafia, I would probably encourage the plan and accuse the townies who don't like it.

    It's intuitively unbelievable. I believe that reading people is much more effective and a much better way to win at mafia.

    But say a random situation using probability (my math isnt amazing, tell me if I messed up soemwhere):

    For example, for a 2 mafia 5 townies situation, the possibilities are:

    Town win (where M denotes a mafia lynched, T denotes townie lynched):

    M-M
    M-T-M
    T-M-M
    Mafia win:

    M-T-T
    T-M-T
    T-T

    Looking at the three town winning possibilities:

    M-M

    This is saying mafia are the two top of the 7 person list. This is a 1/21 chance.

    M-T-M

    So one mafia is first, the other is third. 1/21 chance.

    T-M-M

    Mafia is second and third. 1/21 chance.

    That's about a 1/7 chance win for town...

    Am I not missing something? I believe this random ordering doesn't work at all for any variant that mafia can night-kill in.

    ReplyDelete
  16. Try this way- Townspeople, Mafia, one doctor, one detective. Everyone goes to sleep. Mafia wake up, mafia choose to kill one person, mafia sleep. Doctor wakes up, chooses to save one person (prevents them from death by mafia, they can also save themself!), goes to sleep. Detective wakes up, chooses one person who the arbiter nods is mafia or is not, goes to sleep. Everyone wakes up. If mafia chooses someone who doctor doesn't save, that person is dead in the morning. Then you debate who is mafia with the townspeople.

    Interesting dynamics, when the sheriff and doctor are both known and the doctor has to figure out who to save. Especially when the sheriff reveals the mafia.

    ReplyDelete
  17. Playing the game where the mafia (or werewolves, in the version I play) don't kill anyone each night seems kind of pointless to me. The whole fun of the game is in the alternation between phases of "lynching" (killing by vote) and werewolves killing who they choose. Also, the fact that this random strategy works for the lynch-only game suggests to me that that version is the one that is less interesting.

    ReplyDelete
  18. "And even if the Mafia win --- as they sometimes will --- the win doesn't give them much satisfaction, since it wasn't through the exercise of wit and deception but just a random roll of the dice."

    Doesn't that same issue arise with villagers winning by this method? Except you can't even have the lesser satisfaction of being unusually lucky, as you only won a die roll using weighted dice.

    For theory only this is a fun thought exercise, but using it in-game seems like a perfect fun killer.

    ReplyDelete
  19. In the version I play, there are multiple different roles which could disrupt this pattern. I'v only ever played the version where the mafia get to kill someone each night. But there's also the Sheriff, who gets to investigate someone each night; the Doctor, who gets to save them (protect them from any attacks); the Cupid, who creates a pair of "star-crossed lovers" who must try to keep each other alive at all costs because if one dies so does the other; and a Prostitute, who has the option to sleep with a client, where if they do so and the mafia attempt to kill them, the murder fails since they are not at home, but if the mafia attempt to kill their client they instead kill the prostitute by accident. But I think the point for us is the stories of how people died and the alibis which are produced; I've heard death by pool noodle, death by flying robot ninja, death by evil chicken and evil candy cane, and a five-minute alibi about buying a birthday present for one's father. Generally we give the greater weight to the best stories. I think using a predetermined order defeats the purpose of the game completely.

    ReplyDelete
  20. I've played a version, which is really fun. You play with approx. 8-10 people, 2 are Mafia, one is a doctor and one is a cop. at night you 'sleep' and first mafia wakes up. they point at who to kill, then doctor wakes up he points who to save, then cop wakes up, cop guesses mafia and is told if he's right. Then the people wake up the death/ save is told in an interesting way, and the people vote. It's really fun.

    ReplyDelete
  21. Just a question. How exactly will this work? The mafia will obviously vote out the players who are at the end of the list, until the player at the end of the list is a Mafia member. Maybe they'll even fool around once or twice to throw the Townies off their scent, and to make it less obvious once they stop.

    So let's say the doctor chooses to counter these attacks. Every night, he chooses the save the player at the end of the list. However, any Mafia member with a half-decent brain will catch on to this in two rounds, tops, and start mixing up the order a bit more.

    In your strategy, it's an easy Mafia win, not a Townie win.

    ReplyDelete