First Provably Optimal Strategy for Mafia With a Detective — Solved for One Mafioso

Game theory meets social deduction: an explicit, provably optimal strategy for the Detective in Mafia when there's exactly one hidden killer. A closed-form first in a domain that's resisted exact solutions.

Imagine you're playing Minesweeper, but the mine can lie to you. You click squares to gather information, but the board is actively trying to deceive you about which square is dangerous. That's the Detective's problem in Mafia: you're gathering probabilistic signals in an adversarial environment where the target is strategically hiding. The question isn't just 'where is the mine?' — it's 'what's my optimal investigation sequence when the mine knows I'm looking?' The committed claim: for the first time, an explicit, provably optimal strategy exists for the Detective role in the party game Mafia, specifically for the case where exactly one Mafioso hides among n players and exactly one Detective investigates. Previous game-theoretic work on Mafia either ignored the Detective entirely (d=0) or could only establish upper and lower bounds on winning probability by analyzing specific strategies without proving any was optimal. This paper closes that gap for m=d=1. Why is this hard? The Detective introduces what the paper calls 'extremely complex strategies.' Without a Detective, Mafia reduces to a voting game where information is symmetric — everyone knows only who got eliminated. The Detective breaks that symmetry by gaining private information each night (checking whether a player is Mafia), then must decide how to act on it publicly. The strategy space explodes because the Detective's voting behavior leaks information about their identity and findings, and the Mafioso can reason about that leakage. Optimal play requires reasoning about what your actions reveal to the adversary about what you know — a nested deception problem. The architecture here is pure combinatorial game theory — no simulation, no approximation, no ML. The paper works within the established framework of Mafia as a sequential game of imperfect information, analyzing it through strategy profiles and probability calculations. The method leans on the structure of the specific m=d=1 case to make the strategy space tractable. This is a mathematical proof, not a computational result. The 19-page treatment with 2 figures suggests a careful case analysis rather than a brute-force enumeration. The integrity story is strong for what it is: mathematical proof is the gold standard of validation. There's no simulation to cherry-pick, no benchmark to game. The result either holds or it doesn't. The prior art comparison is well-framed — previous work by Migdal (2010), Yao (2008), and others established bounds but couldn't pin down optimality. The limitation is that m=d=1 is the simplest non-trivial case; the paper is honest that this is a first example, not a general solution. The milestone ladder is clear but steep. Going from m=d=1 to m=1,d=2 (two Detectives) or m=2,d=1 (two Mafiosi) likely requires fundamentally new techniques, not just scaling the current approach. The combinatorial explosion in strategy space as m or d increase is the core barrier. This is the kind of result where the first case takes a decade and the general case may take another decade — or may require entirely different methods. The obvious experiment not run: m=2,d=1 or m=1,d=2. The honest read is (a) — the combinatorial complexity genuinely explodes, and the techniques that work for m=d=1 probably don't generalize cleanly. This isn't a paper where the authors are sandbagging; the single-Mafioso case is likely the frontier of what current methods can handle with exact solutions. The paper's contribution is proving that exact solutions are possible at all once the Detective is introduced, which was an open question.