Pith.

Computer Science and Game Theory · arXiv:2611.16496 v1 · submitted 12 Nov 2026 · 18 references

How to Defeat a Mafia (of Size 1)

Michael Brand

The paper says

“The game "Mafia” is a social deduction game where n players attempt to uncover a covert coalition of m players among the n. Typically, d = 1 of the non-coalition players are labelled “Detective” and have special abilities.”

more of the abstract

Most game-theoretic analysis considers, however, only the variant without a Detective. Once the Detective role is introduced, extremely complex strategies can be employed, for which reason only upper and lower bounds for winning have been established, namely by considering specific strategies. We analyse the case m = d = 1, providing a first example where an explicit, provably-optimal strategy can be described beyond d = 0.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

The passes disagreed. Reader: holds up. Skeptic: holds up only with conditions. Referee: major revision.

Clever crypto application to a social deduction game, but the central optimality claim in Theorem 2 has a load-bearing gap: it asserts the elimination order is optimal without an independent proof. This line is wrong

4 major objections · 5 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 18 references say.

The paper says, at Section 5, Theorem 2

The review did not quote this passage.

Pith says: Objection 1 of 4 · major

The proof of Theorem 2 reduces the game under Random to a one-player probabilistic game and asserts that AnonymousLeader 'directly mimics this optimal strategy.' No argument is given that the specific elimination order (front-to-back during the day, back-to-front during the detective phase) is optimal for that one-player game.

more of objection 1

The win probabilities in Appendix C are computed from the dynamics of AnonymousLeader itself, not from an independent optimization. Without a proof that no other elimination order yields a strictly lower Mafia win probability (or a proof that the one-player game reduces to exactly this order via a dominance or dynamic programming argument), the claim that AnonymousLeader maximizes Villager win probability is unsupported. This lacuna undermines the paper's central result.

The paper says, at Section 5, Theorem 1

The review did not quote this passage.

Pith says: Objection 2 of 4 · major

The proof of Theorem 1 relies on the security of secret sharing to argue that the Mafia learns no information about σ' beyond what is revealed. While this is a standard assumption, the reasoning that the Mafia 'can only gain information from their N_i if they have the cooperation of non-Mafia members in revealing a shared secret' is correct only if the secret sharing scheme is also secure against chosen-ciphertext attacks or if the encryption prevents any leakage.

more of objection 2

The paper should explicitly state the exact security assumptions needed (e.g., semantic security of the encryption, perfect secrecy of the secret sharing shares) and confirm that the combination provides the claimed indistinguishability. As written, the step is too crisp.

The paper says, at Section 6 and Figure 1

The review did not quote this passage.

A classifier read this sentence of the paper as acknowledging the concern (probability 0.73):

“Whether this is, indeed, the asymptotic behaviour of the system is presently an open question. 10 Throughout our description of both algorithms and proofs, we have tried to address the generalmscenario as much as possible, and, indeed, much of our strategy is equally relevant to largerm.”

Pith says: Objection 3 of 4 · major

The asymptotic claims (1/n for odd n, 1.5/n for even n) are stated as 'conjecture' (lines [b174], [b177]), but the surrounding text, including the comparison to the d=0 asymptotic and the phrase 'the Mafia has roughly as much chance of winning a game with d=1 as two games with d=0,' presents these as more than speculation.

more of objection 3

The paper should clearly separate the rigorous finite-n recursion results from the asymptotic conjectures, and either prove the asymptotics or explicitly mark them as empirical or conjectural in all uses.

The paper says, at Appendix A, optional elimination

The review did not quote this passage.

A classifier read this sentence of the paper as acknowledging the concern (probability 0.68):

“We won’t go into the moral implications. 15 Though we have no proof that this trend continues for all (u, v, w) at all scales, we con- jecture that it does.”

Pith says: Objection 4 of 4 · major

The paper acknowledges (line [b265]) that the parity heuristic (eliminate when v+w even) is not proven for all (u,v,w). This is acceptable for an appendix, but the main text (line [b273]) states 'we thus expect the win probabilities ... to behave as 1/n regardless of the parity of n, and this is, indeed, what we are observing empirically.' This extrapolation from unproven conjecture should be flagged more clearly as an open question, not presented as a finding.

5 minor objections

The paper says, at Section 2.2

Pith says: minor objection 1 of 5

The synchronous network emulation via cryptographic commitments is described, but it is not explained how commitments interact with the later uses of SMC (which already assumes synchronous communication). Clarify whether the commitment layer is needed only for the voting rounds or is used throughout.

The paper says, at Section 4, step 6-7

Pith says: minor objection 2 of 5

The protocol for handling malformed or duplicate Detective messages relies on broadcasting private keys (priv_1,...,priv_n). This reveals all honest players' private signing keys, which would prevent any future use of digital signatures in the same game instance. The paper should note that this is acceptable because the game ends immediately after such an event (the Mafia is eliminated or the game ends).

show 3 more

The paper says, at Section 5, Theorem 1 proof

Pith says: minor objection 3 of 5

The proof states that for n≤4, the Mafia win probability under Random is given (1/2 for n=3, 2/3 for n=4). It would be helpful to briefly justify these numbers or cite where they come from (e.g., the recursion in Appendix C).

The paper says, at Appendix C, Equation (1) and (2)

Pith says: minor objection 4 of 5

The recursion formulas involve terms like P^0(v-2, u-2) that may be undefined if u-2 < 1. The paper notes that 'impossible evaluations ... are immaterial,' but to avoid ambiguity, the base cases should be explicitly defined for all argument ranges that can arise in the recursion. Currently the base cases are stated only for the overall game, not for all intermediate calls.

The paper says, at General

Pith says: minor objection 5 of 5

The paper uses 'they' as a singular pronoun inconsistently (e.g., 'the Mafia member ... they are eliminated'). For clarity, use consistent singular 'they' or restructure sentences.

What would settle it

Derive an upper bound on the non-Mafia win probability under Random, independent of any specific non-Mafia strategy, from the recursion: at each state (u,v,w) with w=1, the best possible chance to find the Mafia in one day phase is at most 1/u. Use this to bound the overall win probability via dynamic programming. Compare this bound to the win probability computed from the AnonymousLeader recursion in Appendix C. If they coincide, the optimality claim holds; otherwise, AnonymousLeader may be suboptimal and the proof must be revised.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up confidence moderate
  2. Skeptic disagrees: says it holds up only with conditions 1 min 39 s · 17,406 tokens read, 10,045 written Proof of Theorem 2 does not establish that AnonymousLeader is optimal for the one-player game; optimality of the front-to-back elimination order is assumed, not proven.
  3. Editor wrote the verdict above 26 s · 18,106 tokens read, 1,001 written
  4. Referee major revision: 4 major objections, 5 minor 40 s · 17,685 tokens read, 2,774 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

The paper does something genuinely new: it provides the first explicit, provably optimal strategies for Mafia(n,1,1) by marrying secure multiparty computation with a careful game-theoretic reduction. The cryptographic construction—SortBroadcast, sharding to control information release, and signature-based linkage—is clever and well explained. Theorem 1 (optimality of Random against AnonymousLeader) is solid and relies only on standard security of SMC and secret sharing. The recursive win probability computation is also clean.

But the stress-test concern is real and lands on the paper’s load-bearing result. Theorem 2 claims that AnonymousLeader maximizes the Villagers’ win probability when the Mafia uses Random. The proof reduces the game to a one-player probabilistic game and then asserts that AnonymousLeader 'directly mimics this optimal strategy.' No independent argument is given for why the specific front-to-back elimination order (from σc_f forward, investigation from σc_b backward) is optimal. The win probabilities in Appendix C are computed from the dynamics of AnonymousLeader itself, not from a separate optimization over all possible strategies. Without a proof that no other order (or different use of passes in the optional variant) yields a lower Mafia win probability, the central claim that AnonymousLeader is optimal remains unsupported. The authors acknowledge the optional variant's parity heuristic is unproven for all (u,v,w), which further underscores the gap: if optimality in mandatory elimination were rigorous, it would likely carry over, but here the optional case is explicitly conjectural.

The reliance on cryptographic assumptions (SMC, honest majority, synchronous network) is standard for this kind of work and the authors state it clearly. The paper is otherwise well structured and the optional elimination section is a reasonable exploratory extension, though it remains unproven.

Who this is for: readers interested in game-theoretic analysis of social deduction games or applications of privacy-preserving computation to game theory will find the construction and reduction thought-provoking. The paper deserves peer review because the core idea is novel and the cryptographic setup is nontrivial—but the referee should press hard on the missing optimality proof for the elimination order. I’d bring it to a reading group to discuss the gap, but wouldn’t cite it until that gap is closed.

The strongest objection

The proof of Theorem 2 reduces the game under Random to a one-player probabilistic game and then claims that AnonymousLeader is optimal for that game because it "directly mimics this optimal strategy." No independent proof is given that the specific elimination order (from σ_{c_f} forward and investigation from σ_{c_b} backward) is optimal. The win probabilities in Appendix C are computed from the dynamics of AnonymousLeader itself, not from a separate optimization. Without a proof that no other strategy (e.g., a different order, or using passes in the optional variant) yields a lower win probability for the Mafia (i.e., higher for non-Mafia), the central claim that AnonymousLeader maximizes Villager win probability is unsupported. The paper's own acknowledgment in Appendix A that the parity heuristic for optional elimination is not proven for all (u,v,w) further underscores that optimality of the mandatory strategy lacks rigorous justification.

The reader's weakest assumption was the cryptographic infrastructure (SMC, honest majority). While that is a practical limitation, the paper acknowledges it and the proof structure is logically consistent under those assumptions. However, a more fundamental logical gap appears in the proof of Theorem 2: the reduction to a one-player game is correct, but the claim that AnonymousLeader is optimal for that game is not proven. The paper asserts that the front-to-back elimination order is optimal without deriving it from first principles or comparing it to an upper bound. This is the single most load-bearing concern because if AnonymousLeader is not optimal, the claimed Nash equilibrium collapses. The concrete test would settle this by establishing whether the computed win probability equals the theoretical maximum.

The referee's report

If the optimality proof were fully rigorous, this would be a significant contribution: it provides the first exact optimal strategies for a Mafia variant with a Detective, demonstrates the use of privacy-preserving computation in game theory, and yields concrete win probability formulas. The methods are clever and the combination of cryptographic primitives is novel. However, the main proof of optimality for the non-Mafia strategy contains a load-bearing gap that weakens the central claim.

Pith's reading of the paper (a machine's summary, not the authors')

The paper aims to find optimal strategies for the social deduction game Mafia when exactly one player is Mafia and one is Detective. It uses cryptographic tools to allow the Villagers and Detective to coordinate their actions without revealing the Detective's identity to the Mafia. The resulting strategies, AnonymousLeader for the non-Mafia team and Random for the Mafia, are proven to be a Nash equilibrium, meaning neither team can improve its win probability by unilaterally changing strategy. The paper also computes the exact win probabilities for any number of players and conjectures their asymptotic behavior. This is the first time provably optimal strategies have been described beyond the case of no Detective.

What carries the argument. The central mechanism is SortBroadcast, an anonymous broadcast protocol built on secure multiparty computation (SMC). Each player submits a message; SMC computes the sorted list of messages without revealing which player sent which. This allows the Detective to publish a secret-shared random permutation σ of the player indices without the Mafia learning which indices correspond to whom. The Villagers then eliminate players in the order σ_1, σ_2, … while the Detective investigates players in reverse order σ_{n-1}, σ_{n-2}, … The shards of σ are revealed only as needed, ensuring the Mafia never learns future elimination targets.

Core claim. The central claim is that in the game Mafia(n,1,1), with one Mafia member and one Detective, the paired strategies AnonymousLeader (for Villagers and Detective) and Random (for Mafia) are mutually optimal: each is a best response to the other. The proof shows that the Mafia gains no information about the Detective's secret investigation order, so any night-phase choice is equivalent to random; and the Villagers and Detective, by using an anonymous broadcast to establish a shared elimination order, can replicate the optimal decision rule of a full-information game. Consequently, the win probabilities satisfy a simple recursion that yields exact numerical values for any n.

The premise it rests on. The AnonymousLeader strategy depends on the availability of secure multiparty computation (SMC) that works under the assumption of an honest majority and a synchronous network; if SMC is not available or the honest majority fails, the optimality proof collapses.

If the paper is right (Pith's inferences, not the authors')

If these strategies are used, the win probability for the Mafia decreases rapidly as n increases: asymptotically 1/n for odd n and 1.5/n for even n.

The non-Mafia team can guarantee a win probability of at least 1 - (1.5/n) for even n and 1 - (1/n) for odd n, which approaches certainty as n grows.

The results show that cryptographic tools can give a substantial advantage in social deduction games, beyond what is achievable without them.

The recursive formulas allow the non-Mafia team to compute exact win probabilities for any n in O(n^2) time, enabling them to make optimal decisions about when to eliminate or pass in the optional elimination variant.

The paper's reliance on SMC assumes an honest majority and synchronous network; a natural extension is to investigate whether similar optimality can be achieved with weaker cryptographic assumptions, such as only digital signatures and commitments.

The strategy for m=d=1 does not generalize directly to larger m; a plausible next step is to design a strategy where multiple Mafia members are forced into a similar position via cryptographic verification of claimed roles.

The empirical conjecture that optional elimination makes the Mafia win probability 1/n for all n (regardless of parity) suggests that the parity effect is an artifact of mandatory elimination; testing this conjecture with larger n would confirm the improved performance for the non-Mafia team.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

The game "Mafia” is a social deduction game where n players attempt to uncover a covert coalition of m players among the n. Typically, d = 1 of the non-coalition players are labelled “Detective” and have special abilities. Most game-theoretic analysis considers, however, only the variant without a Detective. Once the Detective role is introduced, extremely complex strategies can be employed, for which reason only upper and lower bounds for winning have been established, namely by considering specific strategies. We analyse the case m = d = 1, providing a first example where an explicit, provably-optimal strategy can be described beyond d = 0.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-13

The authors' main claim, as the classifier picked it out 1.00

“We analyse the case $m=d=1$, providing a first example where an explicit, provably-optimal strategy can be described beyond $d=0$.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.79 · states limitation 0.39 · human participants 0.10 · controlled comparison 0.12 · randomized assignment 0.02 · states quantitative result 0.30 · compares with prior results 0.83 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
The game "Mafia'' is a social deduction game where $n$ players attempt to uncover a covert coalition of $m$ players among the $n$. background 1.00 0.04 0.02 asserted 1.00
Typically, $d=1$ of the non-coalition players are labelled ``Detective'' and have special abilities. background 1.00 0.04 0.02 asserted 0.98
Most game-theoretic analysis considers, however, only the variant without a Detective. background 0.72 0.04 0.02 asserted 0.99
Once the Detective role is introduced, extremely complex strategies can be employed, for which reason only upper and lower bounds for winning have been established, namely by considering specific strategies. gap 0.66 0.06 0.04 asserted 0.98
We analyse the case $m=d=1$, providing a first example where an explicit, provably-optimal strategy can be described beyond $d=0$. contribution 0.95 0.96 0.91 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 4,230 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (2)
Figure 1 of the paper
Figure 1. Probability of Mafia to win in an n-player game with optimal strategies. phase, the Villagers remove from the beginning of this list elements until finding, voting for, and removing the first encountered element of U. At every Detective phase, the Detective does the same, but working from the end of the list. Whether or not the Detective is still present in the game, this ensures that the Villagers never vote out the Detective himself nor any Villager already investigated by the Detective, but rather only an element still in U. The counters cf and cb can never equal each other, or…
Figure 2 of the paper
Figure 2. Probability of Mafia to win in an n-player game with optimal strategies, with and without optional elimination. (c) The Detective himself. To ensure this knowledge, we can add to each round, beginning with the first, a step in which the Detective publishes a list R1, . . . , Rn, each Ri encrypted by the public key of Pi , such that these decrypt to tuples Decprivi (Ri) = (Si1, . . . , Sin). Each (S1j , . . . , Snj ), in turn, is a set of shards which, when put together by a coalition of size m + 1 at least, reveals S˜ j , the status, (a), (b) or (c), of player j. If Pj was…

Figures are the authors', reproduced from the paper.

References (18)
  1. [1] Imad Aad. Zero-knowledge proof.Trends in Data Protection and Encryption Technolo- gies, pages 25–30, 2023 on Pith
  2. [2] Archer L. Batcheller, Brian Hilligoss, Kevin Nam, Emilee Rader, Marta Rey-Babarro, and Xiaomu Zhou. Testing the technology: playing games with video conferencing. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI ’07, page 849–852, New York, NY... on Pith
  3. [3] Mark Braverman, Omid Etesami, and Elchanan Mossel. Mafia: A theoretical study of players and coalitions in a partial information environment.Ann. Appl. Probab., 18(3):825–846, June 2008 on Pith
  4. [4] Qiong Chang. A simulator for analyzing the balance of Mafia game. In2020 IEEE International Conference on Artificial Intelligence and Information Systems (ICAIIS), pages 622–627. IEEE, 2020 on Pith
  5. [5] Ronald Cramer, Ivan Bjerre Damg ˚ ard, and Jesper Buus Nielsen.Secure multiparty computation and secret sharing. Cambridge University Press, 2015 on Pith
  6. [6] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game, or a completeness theorem for protocols with honest majority. InProviding sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali, pages 307–328. ACM, 2019. 11 on Pith
  7. [7] Charles A Holt and Alvin E Roth. The Nash equilibrium: A perspective.Proceedings of the National Academy of Sciences, 101(12):3999–4002, 2004 on Pith
  8. [8] Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes. Commitments and efficient zero-knowledge proofs from learning parity with noise. InInternational Conference on the Theory and Application of Cryptology and Information Security, pages 663–680. Springer, 2012 on Pith
  9. [9] Ravneet Kaur and Amandeep Kaur. Digital signature. In2012 international conference on computing sciences, pages 295–301. IEEE, 2012 on Pith
  10. [10] Stephan Krenn and Thomas Lor¨ unser.An Introduction to Secret Sharing. Springer, 2023 on Pith
  11. [11] George Marsaglia and John CW Marsaglia. A new derivation of Stirling’s approximation ton!.The American Mathematical Monthly, 97(9):826–829, 1990 on Pith
  12. [12] Piotr Migda l. A mathematical model of the Mafia game.arXiv preprint arXiv:1009.1031, 2010 on PithPith's reviewarXiv
  13. [13] Sergey V. Petrov and E. N. Holopova. Non-verbal communication. educational role- playing games “Mafia” and “Killer”: educational and methodical manual. Technical report, Ministry of Internal Affairs of Russia, Kaliningrad, 1998 on Pith
  14. [14] Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. InProceedings of the twenty-first annual ACM symposium on theory of computing, pages 73–85, 1989 on Pith
  15. [15] Ronald L Rivest, Len Adleman, and Michael L Dertouzos. On data banks and privacy homomorphisms.Foundations of secure computation, 4(11):169–180, 1978 on Pith
  16. [16] Adi Shamir. How to share a secret.Communications of the ACM, 22(11):612–613, 1979 on Pith
  17. [17] Kaijie Xu, Fandi Meng, Clark Verbrugge, and Simon Lucas. CSP4SDG: Constraint and information-theory based role identification in social deduction games with LLM- enhanced inference.arXiv preprint arXiv:2511.06175, 2025 on PitharXiv
  18. [18] Erlin Yao. A theoretical study of Mafia games.arXiv preprint arXiv:0804.0071, 2008. A If elimination is optional A particularly interesting variation of the game is one where the Villagers do not have to choose one of their own, but can rather “pass” their turn during the day ... on PithPith's reviewarXiv

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment