A Theoretical Study of Mafia Games - Quantitative Analysis of Winning Probability

Aug 20, 2026

Upload by Paura

Mafia game is analyzed as a structured model of human psychology and collective misperception, contrasting an informed minority with an uninformed majority. In a restricted setting without detectives, prior work showed comparable winning probabilities under optimal randomized strategies when the mafia size scales with the square-root of the total population. This paper identifies gaps in the earlier main theorem, constructs examples showing that the theorem alone cannot ensure the desired conclusion, then proves corrected results and validates the conjecture, extending the phenomenon to a broader framework.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

AccessFree to download

Introduction

Background and classification of mafia games

Prior results and conjecture

Existed works and deficiencies

Absence of detectives and optimal strategies

Main results and corrected conclusions

Recursive bounds for winning probability

Generalization via conjecture proof

Extending to a broader framework

Role of detectives

Qualitative behavior and research directions

Summary

A Theoretical Study of Mafia Games Erlin Yao 1 Key Lab of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, 100190 Beijing, China Abstract Mafia can be described as an experiment in human psychology and mass hysteria, or as a game between informed minority and uninformed majority. Focus on a very restricted setting, Mossel et al. [to appear in Ann. Appl. Probab. Volume 18, Number 2] showed that in the mafia game without detectives, if the civilians and mafias both adopt the optimal randomized strategy, then the two groups have comparable probabilities of winning exactly when the total player size is R and the mafia size is of order R . They also proposed a conjecture which stated that this phenomenon should be valid in a more extensive framework. In this paper, we first indicate that the main theorem given by Mossel et al. [to appear in Ann. Appl. Probab. Volume 18, Number 2] can not guarantee their conclusion, i.e., the two groups have comparable winning probabilities when the mafia size is of order R . Then we give a theorem which validates the correctness of their conclusion. In the last, by proving the conjecture proposed by Mossel et al. [to appear in Ann. Appl. Probab. Volume 18, Number 2], we generalize the phenomenon to a more extensive framework, of which the mafia game without detectives is only a special case. Keywords: Mafia Game; Quantitative Analysis; Winning Probability; Optimal Strategy 1 Corresponding address: Institute of Computing Technology (ICT), Chinese Academy of Sciences, 100190 Beijing, China. Tel.: +86 10 58813136. E-mail [address: yaoerlin@hotmail.com](address: yaoerlin@hotmail.com). 1. Introduction Mafia can be described as an experiment in human psychology and mass hysteria, or as a game between informed minority and uninformed majority. The history of mafia game can be traced to the 1970’s, when a game called Murder, which was the prototype of mafia game, had been played for many years [1] . This is a game which can train one’s expressive ability, discrimination ability, imagination ability and acting ability, etc. The game has common characteristics with many real life games, for example: workers, managers and stockholders at a company; students, teachers and management of a school; or citizens, the mafia and the police at a certain city. All of these games share the following three similar features: (1) each player may belong to one or more coalitions; (2) different groups make decision in different ways and take actions of different types; (3) different players accumulate information in different ways [2, 3] . According to the classification of games, the mafia game is a type of dynamic, partial information and group game. However, the previous works on the partial information and group games are mostly concerned with general definitions and abstract results in the context of extensive games. This line of research has not resulted in much quantitative analysis [3, 4] . Focus on a very restricted setting, Braverman, Etesami and Mossel obtained very precise results on the relative power of different groups. In particular, they first find a randomized strategy that is optimal in the absence of detectives, which leads to a stochastic asymptotic analysis using martingale arguments and the martingale stopping time theorem [5], where it is shown that the two groups have comparable winning probabilities when the mafia size is of order R . Then they propose a conjecture which states that the following phenomena should be valid in further generality: “In cases where there exists a distinguished group of size M that has complete information and acts at all rounds playing against a group of players of size R−M with no prior information that acts only at fraction α of the rounds, it is expected that the two groups will have comparable winning probabilities if M = Rα ” [2] . This paper investigates the quantitative analysis of m

FAQs

What prior phenomenon about winning probabilities is discussed for the mafia game without detectives?

It is shown that, under optimal randomized strategies, the civilians and mafias have comparable winning probabilities when the mafia size scales like the square root of the total population.

What deficiency is identified in the main theorem of earlier work?

The paper argues that the earlier main theorem cannot guarantee the desired conclusion about comparable winning probabilities under the stated conditions.

How does the paper extend the result beyond the special case without detectives?

By proving the conjecture from prior work, it generalizes the phenomenon to a more extensive framework, where the detective-free game is only a special case.

Aug 20, 2026

Upload by Paura