Mafia: A theoretical study of players and coalitions in a partial information environment

Mark Braverman, Omid Etesami, Elchanan MosselThe Annals of Applied Probability 2008 · DOI

Abstract

This paper investigates the game of "Mafia" as a formal model for understanding how information asymmetry and coordination influence the balance of power between a hidden minority and an uninformed majority. By treating the game as an extensive stochastic process, we derive the threshold sizes required for a coalition to dominate. We prove that in a standard game without specialized roles, a coordinated Mafia of size $M \approx \sqrt{R}$ can successfully challenge a population of size $R$. However, the introduction of even a single "detective" role—capable of private information gathering—fundamentally shifts this balance, requiring the Mafia to grow to a linear fraction of the population to maintain comparable winning odds. These theoretical results are validated through extensive Monte Carlo simulations.

Introduction

In many real-world social and political structures, small, coordinated groups with private information interact with larger, uncoordinated majorities. While classical game theory effectively models environments with perfect information, "partial information" environments—where the identities and interests of players are hidden—present a more complex challenge. This paper uses the popular social deduction game "Mafia" to quantify the power granted by coordination and private information.

In the model studied, players are divided into three groups: the Mafia, detectives, and ordinary citizens. The Mafia members know each other's identities from the start, while citizens and detectives initially only know their own roles. The game alternates between "open" rounds (democratic voting to eliminate a player) and "closed" rounds (where the Mafia eliminates a citizen). The citizens win if they eliminate all Mafia members; otherwise, the Mafia prevails.

Methodology

The study treats Mafia as an extensive game and employs tools from stochastic analysis and martingale theory to determine optimal strategies and winning probabilities.

1. Optimal Strategy Derivation

To establish a baseline for analysis, the authors define "optimal" play for both sides. For citizens, this involves a randomized voting strategy to prevent the Mafia from manipulating the outcome through coordinated voting. The model assumes the existence of cryptographic protocols or a trusted moderator to facilitate simultaneous announcements and anonymous voting, ensuring the Mafia cannot react to citizen votes in real-time.

2. Martingale Analysis

In the absence of detectives, the game is modeled using a martingale—a mathematical representation of a fair game—to track the ratio of Mafia members to the total population. This allows for the calculation of winning probabilities as the population size $R$ approaches infinity.

3. Information Dynamics

When detectives are introduced, the focus shifts to the speed of information acquisition. The authors propose a strategy where the detective's primary goal is not merely to identify the Mafia, but to identify a "trusted core" of citizens. By vouching for known innocents, the detective allows the citizens to form their own coordinated coalition, effectively mirroring the Mafia's primary advantage.

Key Insights

The Power of the Square Root

In a standard game without detectives, the Mafia’s coordination advantage is mathematically massive. The research demonstrates that a Mafia of size $M \approx \sqrt{R}$ has a roughly 50% chance of winning. If the Mafia size slightly exceeds this $\sqrt{R}$ threshold, they win almost surely. This highlights how minimal coordination can overcome a significant numerical disadvantage; in a population of 10,000, a mere 100 coordinated individuals can dominate.

The Detective Qualitative Shift

The most striking finding is the impact of information. Adding just one detective changes the fundamental mathematical scaling of the game. The Mafia's required size for a 50% win rate jumps from $\sqrt{R}$ (sub-linear) to $\eta R$ (linear). In the same population of 10,000, the Mafia would need thousands of members rather than 100 to maintain the same power level.

Vouching vs. Accusing

The optimal strategy for citizens reveals that a detective’s most potent move is identifying other citizens rather than just accusing Mafia members. By creating a "vigilante" group of verified innocents, the citizens can neutralize the Mafia's information advantage. If multiple detectives ($d^2$) are present and use a coordinated querying strategy, the citizens can win with high probability even if the Mafia constitutes nearly 50% of the population.

Results and Simulations

The theoretical findings were tested against Monte Carlo simulations of the game with population sizes up to $10^6$.

  • Without Detectives: Simulations confirmed that the Mafia wins with high probability if $M > c\sqrt{R}$, where the constant $c$ is approximately $0.643$.
  • With One Detective: The Mafia requires a linear fraction (e.g., $M = R/49$) to remain competitive.
  • Simulation Fit: The data showed an excellent fit with the theoretical $M = c\sqrt{R}$ curve, validating the martingale approach used in the proofs.

Limitations and Future Work

The study acknowledges that "optimal" citizen strategies rely on residents' ability to perform complex tasks like simultaneous message exchange and anonymous voting. In casual human play, psychological manipulation often bypasses these mathematical safeguards. Furthermore, the model assumes the game must progress to a conclusion and cannot reach a stalemate.

Future research may explore the "Liveness" problem—where games might stall—and a general power-law conjecture proposed by the authors: in games where groups take actions at different frequencies ($d$ rounds vs $n$ rounds), the power threshold may follow a law of $M = R^{d/r}$. Proving this for broader game structures remains an open challenge in the study of partial information environments.

Summary updated

Abstract

In this paper, we study a game called “Mafia,” in which different players have different types of information, communication and functionality. The players communicate and function in a way that resembles some real-life situations. We consider two types of operations. First, there are operations that follow an open democratic discussion. Second, some subgroups of players who may have different interests make decisions based on their own group interest. A key ingredient here is that the identity of each subgroup is known only to the members of that group. In this paper, we are interested in the best strategies for the different groups in such scenarios and in evaluating their relative power. The main focus of the paper is the question: How large and strong should a subgroup be in order to dominate the game? The concrete model studied here is based on the popular game “Mafia.” In this game, there are three groups of players: Mafia, detectives and ordinary citizens. Initially, each player is given only his/her own identity, except the mafia, who are given the identities of all mafia members. At each “open” round, a vote is made to determine which player to eliminate. Additionally, there are collective decisions made by the mafia where they decide to eliminate a citizen. Finally, each detective accumulates data on the mafia/citizen status of players. The citizens win if they eliminate all mafia members. Otherwise, the mafia wins. We first find a randomized strategy that is optimal in the absence of detectives. This leads to a stochastic asymptotic analysis where it is shown that the two groups have comparable probabilities of winning exactly when the total population size is R and the mafia size is of order $\sqrt{R}$. We then show that even a single detective changes the qualitative behavior of the game dramatically. Here, the mafia and citizens have comparable winning probabilities only for a mafia size linear in R. Finally, we provide a summary of simulations complementing the theoretical results obtained in the paper.
BibTeX
@article{braverman2008mafia,
  author = {Mark Braverman and Omid Etesami and Elchanan Mossel},
  title = {{Mafia: A theoretical study of players and coalitions in a partial information environment}},
  journal = {The Annals of Applied Probability},
  year = {2008},
  doi = {10.1214/07-aap456},
}
Figure