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

Sunday, August 21, 2005

How Red America thinks

Digby points to one of Rose Aguillar's interviews with Oklahomans. Read the Mary Fowler interview and weep. It may have seemed that I was exaggerating when I wrote about how stupid and blind conservative thinking is; but if anything, I was understating the truth. It is as if some alien creature has eaten Fowler's brain and implanted a little alien worm in her skull to replace it.

Thursday, August 18, 2005

Removing sound from video files

Just got back from a Bay Area trip, visiting my friend MS et al. While I was down there, we visited the world-famous Monterey Bay Aquarium, where, among other things, I found many reasons to play around with the movie recorder on my new digital camera. The results were impressive --- considering it's a camera and not a camcorder, the Canon PowerShot A95 takes really nice-looking videos at 640x480 --- but the ambient sound inside the aquarium was just crowd noise: murmuring strangers, screaming kids, and such. Sort of ruins the mood when you're looking at a video that looks like this:

The PowerShot A95 doesn't have a way to turn off the sound during video recording either. So, I wanted to strip the sound off my video files, without re-encoding the video (which would reduce the image quality).

"Surely," I thought, "this will be easy. The AVI file format stores audio in separate binary chunks from the video --- it's just a matter of erasing the audio chunks. Even if the software that comes with my camera can't do it, there will be multiple freeware utilities that can. Maybe not for Linux, but surely for Windows..."

Ha, ha.

Anyway, to make a long story short, I couldn't find a good free utility to do this under Windows. I found many programs that let me replace the soundtrack to a movie, but for some reason none of them could remove the sound altogether. I didn't feel like dropping a few hundred bucks on Adobe Premiere either. So, the best option turned out to be --- surprise! --- a Unix utility called transcode. I got mine via the freshrpms yum repository for Fedora Core 4, read the manual pages and the wiki, and came up with the following recipe:

transcode -i foobar.avi -P1 -o foobar_nosound.avi -y raw,null

Geeky details: this instructs transcode to read the video from foobar.avi, pass through the video track only, write the output to foobar_nosound.avi, and use raw encoding for the video and null encoding for the audio.

Here's a Python script that makes transcode batch processing easy; just give it a list of filenames of the format foobar.avi, and it will produce a list of silent video files named foobar_nosound.avi:

#!/usr/bin/env python

import os.path
import subprocess
import sys

def splitExtension(filename):
    lastdot = filename.rfind('.')
    return (filename[:lastdot], filename[lastdot:])

infiles = sys.argv[1:]
for infile in infiles:
    (prefix, ext) = splitExtension(infile)
    outfile = prefix + "_nosound" + ext
    idx = 0
    while os.path.exists(outfile):
        idx = idx + 1
        outfile = prefix + "_nosound_" + str(idx) + ext
    print infile + " stripped to:" + outfile
    retcode = subprocess.call(
        ['transcode',
         '-i', infile,
         '-P1',
         '-o', outfile,
         '-y', 'raw,null'])