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...