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