The maths of Mafia

Sophie Maclean

1 May 2021

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

It was 8pm on a wintry Saturday and I was pleading for my life. “I would never betray you. I promise.” I searched desperately for someone, anyone, to back me up. Of course, they were right. I had been responsible for the murder of many of their friends but I wasn’t about to admit to that. My co-conspirators had gone quiet, well aware that to support me was to put themselves into the firing line. At 8.55pm a vote was held. By 9pm I had been executed.

OK, so that first paragraph may have been a bit misleading. Thankfully I was not actually put to death, and I haven’t killed anyone in real life. This all happened whilst I was playing Mafia. For those unfamiliar, Mafia is strategy game in which players are (secretly) assigned to be either citizens or mafia. The game is split up into day and night phases (when playing in person, night is simulated by everybody closing their eyes). During the night phase, the Mafia are able to communicate with each other and can vote to kill one person. During the day phase, all the residents (both citizens and mafia) discover who died, and then vote to execute one resident. The aim for each group is to eliminate the other.

Some of you may be reading this thinking “Hmmmm this is sus. It sounds very much like Among Us” and you’d be right. The popular online game was inspired by Mafia and is one of many adaptations of the game. The particular version I was playing—when I was outed as a Mafia member—was Harry Potter themed (if there’s one thing you’ll learn about me during this article, it’s that I’m incredibly cool). People found themselves either on Team Hogwarts or Team Death Eater, and there were some special Potter themed rules, which led to an interesting situation mathematically.

At the beginning of the game, Voldemort was allowed to select a horcrux. This essentially meant that Voldemort could not die until both he and this other character were killed. The crucial part of this power was that the horcrux didn’t know they were the horcrux. Towards the end of the game, there were four characters left alive: Voldemort, Fred Weasley (who was the horcrux), Fawkes the phoenix, and Ginny Weasley. By this point, everyone knew for certain which character had been assigned to each player. Fred, Fawkes and Ginny had also worked out that one of them was the horcrux but didn’t know who. They had guessed it was Fawkes. That night Voldemort attempted to kill Ginny (though didn’t succeed because magic). The next day, Team Hogwarts were informed of the failed assassination. What should they do next?

The Great (Monty) Hall

On the face of it, there seems to be no reason to alter who they suspect the horcrux is. The probability of Fawkes being the horcrux hasn’t changed, right? Well actually, wrong. When they settled on Fawkes, there was a 1/3 chance that he was the horcrux. In attempting to kill Ginny, Voldemort had shown that she wasn’t the horcrux (Voldemort could equally have attempted to kill Fawkes here). So the probability that Fred is the horcrux is 2/3. Therefore it’s best to kill Fred (sorry Fred!). Though at first glance, the situation doesn’t appear to have changed, the addition of new information means it actually has, and in Mafia information is crucial.

Harry Potter in the Great Hall during a feast.

Those of you familiar with a certain piece of mathematical lore will now be jumping out of your seats. This is equivalent to the infamous Monty Hall problem. In that problem, a contestant must pick one of three doors as part of a game show. The contestant is told that behind two of the doors is a goat, but behind the third is a car. After they have made their choice, Monty Hall (the presenter) opens one of the other doors to reveal a goat. The contest is then given the opportunity to swap doors. In our Mafia analogy, the horcrux is the car, with the other two characters being goats. Voldemort is our Monty Hall, and by attempting to kill Ginny he opens the door to a goat. And just like in our Mafia version, the contestant is better off swapping doors. If this is taking a while to get your head around, consider the following table (now framed in terms of the Monty Hall problem):

Each of the initial scenarios (ie each line) is equally likely to occur. You can now clearly see that when swapping, the contestant wins $2/3$ of the time, compared to only $1/3$ of the time when staying put. Another way of putting this is that to win when sticking with your first guess, you have to guess correctly first time (which has probability of $1/3$) but to win if you swap, you have to be wrong on your first guess (which has probability of $2/3$).

This whole scenario got me wondering how else maths could help when playing Mafia. I first learnt to play Mafia at maths camp (I told you I was cool) so I knew it was popular with mathematicians. Could it be that there’s a secret mathematical strategy to guarantee that you win the game?

Rules and Regulus-ions Black

In short, no. One of the great things about Mafia is there’s a huge psychological element. When playing with people you know well, you can observe changes in behaviour that indicate they’re lying—you can spot contradictions in alibis, you can notice voting patterns and compare that with known friendships. Interrogations can be carried out, pressure can be applied; I’ve even known someone to threaten to end a relationship if it transpired her partner was lying to her. But this doesn’t mean that there’s nothing we can say. If we take out the psychological aspect, and assume that murder choices are truly random, we can give a probability that the mafia win.

The first step in exploring the maths of any game is to clearly set the rules, and formalise our mathematical model. We will consider a simple version of the game, where everyone is either a mafia member or a citizen and there are no Potter-esque powers. Let’s define the game as follows:

• There are initially $N$ players, all of whom are called residents. There is also one more person, not playing, who coordinates the game (this allows anonymous and simultaneous votes)
• Before the gameplay begins, $M$ of these $N$ players are assigned to be mafia. The remaining $N-M$ players are citizens.
• Every player is told their own identity. The mafia are also told the identities of each other. The citizens only know their own identity.
• A turn is defined as a day phase, followed by a night phase:
  • A day phase consists of a debate, where all players can freely discuss strategy. After this there is a vote where all players simultaneously choose a resident to execute. The resident with the most votes is killed. In the event of a tie, one of the most voted residents is randomly chosen to die. It is then revealed whether this resident was a mafia member or not.
  • A night phase consists of only the mafia communicating and then voting on which citizen to kill, followed by their death. In this model, there is no way for this death to be prevented, and the mafia cannot kill one of their own.
• We assume no psychological aspect comes in to play, and so we assume citizens never have any information on who is and isn’t mafia (obviously this is a vast oversimplification because if, for example, a group of people exactly the same size as the mafia always vote the same way, and never vote for each other, even the least observant player may get suspicious.)
• The game continues until only one team (citizens or mafia) remains and this team is declared the winner.
• We will assume every player plays rationally and always makes the decision that maximises their chance of winning. This is perhaps the biggest assumption of all.

Regulus Black (Sirius’s late brother) during the day phase (left) and the night phase (right)

Let us write the current state with $n$ players and $m$ mafia as $(n,m)$. Let the probability of the mafia winning when there are $n$ players and $m$ mafia be $w(n,m)$.

There are a few things that we can immediately say, without much further calculation.

During a single turn, the possible transitions are $(n,m)$ $\to$ $(n-2,m-1)$ (when the residents execute a mafia member) or $(n,m)$ $\to$ $(n-2,m)$ (when the residents execute a citizen). Fans of Chalkdust may recognise this as a Markov chain (which you can read about in issue 12). One key thing to note here is that the number of residents decreases by $2$ each turn, therefore the game must end in a finite number of turns. By putting a time limit of the length of each phase, you can also guarantee the game ends in finite time. It would be very unsporting for the last remaining mafia member to refuse to stop talking and allow a vote to occur, thereby ensuring that although the mafia couldn’t win, they also couldn’t lose, but it wouldn’t be unheard of (looking at you, MPs).

Now we want to consider some probabilities. The probability of the mafia winning from each state is independent of what happened before. We can therefore say that \begin{equation} \begin{aligned} w(n,m) & = P(\text{mafia executed}\mid\text{$n$ players, $m$ mafia}) w(n-2,m-1) \\ & \quad+ P(\text{citizen executed}\mid\text{$n$ players, $m$ mafia}) w(n-2,m). \end{aligned} \tag{1} \label{mathia:eq1} \end{equation} Here, $P(A\mid B)$ is the probability of $A$ happening if $B$ has already happened (check out this article for more on conditional probability).

Sorting into houses cases

This is still a fairly general formula, and doesn’t give much insight. In order to say more, we’ll need to look at three separate cases:

• $m > n-m\quad$ (the mafia have a majority)
• $m = n-m\quad$ (there are an equal number of mafia members and citizens)
• $m < n-m\quad$ (the citizens have a majority)

Firstly, let’s look at when the mafia outnumber the citizens. In this case, the mafia are guaranteed to win. This is because during the day phase, they can all vote to kill the same citizen, win the majority vote, and ensure it is a citizen that is killed. This can be organised during the night phase. Therefore $w(n,m) = 1$ when $m > n-m$.

Sorting into cases

What about if the citizens have a majority (ie $m < n-m$)? In our model, the citizens have no information on who is and isn’t mafia. Therefore their strategy can only be to randomly select a resident to eliminate each day phase. The debate phase can be used to agree on which random resident to execute (for example using a random number generator). The citizens then all vote for this person, and (because they have the majority), the unlucky resident is executed. There’s nothing the mafia can do to change that. Each resident has an equal chance of being selected. Therefore the probability that a mafia member is executed is $m/n$, and the probability a citizen is executed is $(n-m)/n$.

The case when $m = n-m$ (ie $n = 2m$) is a special case. The citizens and mafia can propose a player each, and then one of them will randomly be executed. The probability that a mafia member is executed is therefore $1/4$ (and so the probability a citizen is executed is $3/4$). If a citizen is executed, the mafia outnumber the citizens, and so they win. If a mafia member is executed, there remains an equal number of mafia and citizens (as a citizen is killed during the night phase). This puts us in exactly the same situation as before, with the same probabilities. For the citizens to win, a mafia member must be executed on all remaining turns (of which there must be $m$ as two residents are killed per round). Hence $P(\text{citizens win})=$ $(1/4)^m = (1/2)^{2m} = (1/2)^n$, and so $w(2m,m) = 1 – (1/2)^n$.

If we combine all this, and use \eqref{mathia:eq1}, we get the following: \[ w(n,m) = \begin{cases} 1 & \text{if } m > n-m\\ \displaystyle1 – {\left(\frac{1}{2} \right)}^{n} & \text{if }m = n-m\\[3mm] \displaystyle\frac{m}{n}w(n-2,m-1) + \frac{n-m}{n}w(n-2,m) & \text{otherwise.}\\[3mm] \end{cases} \] This is pretty neat and is now just an iterative equation. It would be perfectly possible to calculate $w(n,m)$ now, by just plugging through the steps (or even writing some code to do it for you if you’re that way inclined). Finding a more general formula becomes pretty complicated pretty fast. But there is still more that we can say, without our brains hurting too much.

(The philosopher’s st)one mafia member

Let us consider the game with only one mafia member. In order for this mafia member to win, in every day phase a citizen must be executed. Remember that day phases precede night phases. Therefore \begin{equation} w(n,1) = \frac{n-1}{n}\frac{n-3}{n-2}\times\dots\times\frac{1 + n\;(\text{mod}\;2)}{2 + n\;(\text{mod}\;2)} = \frac{(n-1)!!}{n!!}. \tag{2} \label{mathia:2} \end{equation} Here $!!$ is the double factorial function (like factorial, but taking every other element). It’s worth noting that because $n\;(\text{mod}\;k)$ is the remainder when $n$ is divided by $k$, we have \begin{equation} n\;(\text{mod}\;2) = \begin{cases} 0 & \text{if $n$ is even}\\ 1 & \text{if $n$ is odd.} \end{cases} \tag{3} \label{mathia:3} \end{equation} This highlights a rather interesting property: the dependence on the parity of the number of residents. This doesn’t seem unreasonable, because two players are killed each day, and whether there are an even or odd number of players does affect the proportion of players needed to have a clear majority. A quick calculation using \eqref{mathia:2} shows that $w(2,1)= 1/2$ and $w(3,1)=2/3$. In the second case, despite there being a greater proportion of citizens, the probability that the mafia win is actually higher.

In fact, with a single mafia member, it is always true that adding an extra citizen to make the total number of players odd increases the mafia’s chance of winning. We can prove this by induction.

So now we’ve shown that the mafia’s chance of winning is higher with an additional citizen making the total number of players odd, which I found pretty surprising. So you can only imagine how shocked I was when I learned that the parity of the number of players has such an effect that $w(9,1) > w(4,1)$. In fact, we can plot a graph of $w(n,1)$ for odd and even $n$ using our expression in \eqref{mathia:2} to highlight this:

A graph of $w(n,1)$ against $n$ for $n$ odd (green), and $n$ even (blue).

Time to get Sirius

And now we can reach the limit of what I can explain without writing a thesis. Luckily for me, Piotr Migdał has written a paper for his bachelor’s degree. There is one main result from that, extending the ideas above, which I’d like to share with you. It considers the case of there being multiple mafia members.

In a similar way to how we derived $w(1,n)$, Migdał shows that \[ w(n,m) = 1 – \sum_{i=0}^{m} \begin{pmatrix} m \\ i \end{pmatrix} \frac{(n-i)!!}{n!!((n\;(\text{mod}\;2) – i)!! }. \] Now observe that $(n-i)!!/(n-1)!! \to 0$ as $i$ increases. Therefore only the first two terms of the sum contribute significantly. Hence we can write \begin{equation} w(n,m) \approx m\frac{(n-1)!!}{n!!}. \tag{4} \label{mathia:4} \end{equation} To write this in a nicer form involves a few neat ideas. One fact that will prove very useful is that for any $k$, $(2k+1)!! = (2k+1)(2k-1)!!$ (using the definition of double factorial above).

We first consider the product of $w(2k+1, m)$ and $w(2k,m)$. By \eqref{mathia:4}, this gives: \begin{align*} w(2k+1, m) w(2k, m) &\approx \frac{m(2k)!!}{(2k+1)!!} \times \frac{m(2k-1)!!}{(2k)!!}\\ &= \frac{m(2k)!!}{(2k+1)(2k-1)!!} \times \frac{m(2k-1)!!}{(2k)!!}\\ &= {m}^{2} \frac{1}{2k+1}. \tag{5} \label{mathia:5} \end{align*}

Now we’re going to look at ${w(2k+1,m)}/{w(2k,m)}$, again using \eqref{mathia:4}. This may seem a bit odd right now, but trust me on this one. \begin{align*} \frac{w(2k+1,m)}{w(2k,m)} &\approx \frac{m(2k)!!}{(2k+1)!!} \div \frac{m(2k-1)!!}{(2k)!!}\\ &= \frac{{(2k)!!}^{2}}{(2k+1)!!(2k-1)!!} \\ &= \frac{{(2k)!!}^{2}}{(2k+1){(2k-1)!!} ^{2}} \\ &= {\left(\frac{(2k)!!}{(2k-1)!!}\right)}^{2}\frac{1}{2k+1}. \tag{6} \label{mathia:6} \end{align*}

At this point, you’d be forgiven for having your doubts that I’m making anything more simple here. Fear not! It all becomes clear with the introduction of the Wallis formula: \[ \frac{\pi}{2} = \lim_{x\to\infty} {\left(\frac{(2k)!!}{(2k-1)!!}\right)}^{2}\frac{1}{2k+1}. \] We can now write \eqref{mathia:6} in the limit $k \to\infty$ as \begin{equation} \frac{w(2k+1,m)}{w(2k,m)} \approx \frac{\pi}{2}. \tag{7} \label{mathia:7} \end{equation}

Okay, we’re nearly there. I promise. The final clever idea requires considering even and odd $n$ separately. Write $n=2k$ for $n$ even (where $k$ is a positive integer). For $n$ odd, write $n = 2k+1$ (again for a positive integer $k$). Now here’s the magic. Write: \[ w(n,m) = \begin{cases} \displaystyle{\left(\frac{w(2k+1,m)}{w(2k,m)}\right)}^{-1/2}\sqrt{w(2k+1, m)w(2k, m)} & \text{for } n = 2k \quad \text{(ie $n$ is even)}\\[7mm] \displaystyle{\left(\frac{w(2k+1,m)}{w(2k,m)}\right)}^{1/2}\sqrt{w(2k+1, m)w(2k, m)} & \text{for } n = 2k+1 \quad \text{(ie $n$ is odd).} \end{cases} \]

Substituting in our values from \eqref{mathia:5} and \eqref{mathia:7} above gives \[ w(n,m) \approx \begin{cases} \displaystyle{\left(\frac{\pi}{2}\right)}^{-1/2}\sqrt{\frac{{m}^{2}}{2k+1}} & \text{for } n = 2k \\[7mm] \displaystyle{\left(\frac{\pi}{2}\right)}^{1/2}\sqrt{\frac{{m}^{2}}{2k+1}} & \text{for } n = 2k+1. \end{cases} \]

This can be put in to a single line by recalling \eqref{mathia:3}, and using the fact that for large $k$, $2k + 1 \approx 2k $: \begin{equation} w(n,m) \approx {\left( \frac{\pi}{2}\right)}^{n\;(\text{mod}\;2) – 1/2}\frac{m}{\sqrt{n}}. \tag{8} \label{mathia:8} \end{equation}

So we finally have an approximate expression for $w(n,m)$. Phew. From this, it’s only a small step to calculate how many of the $n$ players need to be made mafia initially in order to give the two teams equal chance of winning.

To do this, we set $w(n,m) = 1/2$ in \eqref{mathia:8}. Hence we find the optimal value of $m$ is approximately \[ \frac{\sqrt{n}}{2}{\left( \frac{\pi}{2}\right)}^{n\;(\text{mod}\;2) + 1/2}. \] This is particularly interesting as it means that when creating a game of mafia, you can choose the initial number of mafia to ensure that the mafia (or the citizens) are unlikely to win by luck alone, and some skill has to be involved. Unfortunately though, this gives no indication of what that skill should be.

A fair game with 13 people (during a night phase): 3.55 mafia members (top) v 9.45 citizens (bottom). In a real game, however, it will probably be easier to round the number of people on each team to the nearest integer.

One final thing that I’d like to point out is the effect of the parity of $n$ on $w(m,n)$ and the optimal value of $m$. We saw in the case of one mafia member how much of difference it makes, and we see it again here. It becomes even clearer when we plot the optimal value of $m$ against $n$:

A graph of the optimal value of mafia $m$ against $n$ for $n$ odd (green), and $n$ even (blue)

So there we have it: I don’t have any surefire winning strategy to reveal to you. But in a way, that’s what I love so much about Mafia. Yes, maths can be used to play the game better, or to give an idea of how to structure a perfect game, but maths doesn’t give a way to guarantee you’ll win. It can inform wiser choices, but ultimately it comes down to how much you trust your friends. And if there’s one thing I’ve learnt playing Mafia, it’s that you can never truly trust your friends.

Sophie Maclean

Sophie Maclean is a recent maths graduate from the University of Cambridge and very much misses her degree. She has no free time—she is a Chalkdust editor.

All articles by Sophie