{"id":"b5f7fb2f-74b5-445e-8e1c-1854629584d2","arxiv_id":"2611.16496","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Provably optimal strategies are found for the Mafia game with one Mafia and one Detective, yielding win probabilities that scale as 1.5/n and 1/n.","lead":"This paper provides provably optimal strategies for the social deduction game Mafia with one Mafia member and one Detective. It shows that a strategy using secure multiparty computation outperforms naive play and calculates exact win probabilities.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"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.","rationale":"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.","tokens_in":17406,"tokens_out":10045,"duration_ms":98800,"concrete_test":"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.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"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.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"This paper studies the social deduction game Mafia with one Mafioso and one Detective (m=d=1). The authors propose explicit strategies for both teams: the non-Mafia team uses AnonymousLeader (a cryptographic protocol employing secure multiparty computation, secret sharing, and digital signatures to enable anonymous voting and coordinated elimination), and the Mafia team uses Random (uniform random selection of night targets). They claim that these strategies form a Nash equilibrium, providing the first provably optimal strategies for this game variant beyond the case d=0. Win probabilities are computed numerically via recursion and asymptotic approximations are conjectured. The optional elimination variant is also discussed in an appendix.","tokens_in":17685,"tokens_out":2774,"duration_ms":39538,"significance":"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.","major_comments":[{"comment":"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. 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.","section":"Section 5, Theorem 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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. 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.","section":"Section 5, Theorem 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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. 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.","section":"Section 6 and Figure 1","authors_acknowledge":"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.","authors_acknowledge_p":0.73},{"comment":"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.","section":"Appendix A, optional elimination","authors_acknowledge":"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.","authors_acknowledge_p":0.68}],"minor_comments":[{"comment":"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.","section":"Section 2.2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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).","section":"Section 4, step 6-7","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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).","section":"Section 5, Theorem 1 proof","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"Appendix C, Equation (1) and (2)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"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.","section":"General","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"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.\n\nBut 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":18106,"tokens_out":1001,"duration_ms":26190},"pith_extraction":{"msc":["91A80","91A10","94A60"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"Using cryptographic anonymity, the paper derives the first provably optimal strategies for the social deduction game Mafia when exactly one player is Mafia and one is Detective.","keywords":["Mafia game","social deduction game","optimal strategy","Nash equilibrium","secure multiparty computation","anonymous broadcast","secret sharing","cryptographic protocol"],"falsifier":"A Monte Carlo simulation of the AnonymousLeader and Random strategies for n between 3 and 30, using the exact SMC-based SortBroadcast, that yields Mafia win probabilities deviating from the recursively computed values in Appendix C by more than one percent would indicate a flaw in the proof or implementation.","tokens_in":18909,"feed_emoji":"🔍","tokens_out":4799,"duration_ms":44769,"temperature":0.7,"pith_summary":"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.","feed_headline":"First optimal strategies for Mafia with one Detective","feed_subtitle":"Proven optimal strategies for the classic social deduction game with one Mafia and one Detective","key_machinery":"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_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the baseline upper and lower bounds for Mafia win probabilities without a Detective, which the current work extends to include the Detective.","marker":"[3]"},{"why":"Supplies the secure multiparty computation framework used to implement anonymous broadcast (SortBroadcast).","marker":"[5]"},{"why":"Shows that SMC tolerates malicious adversaries under the honest majority assumption, necessary for the protocol's security.","marker":"[6]"},{"why":"Introduces secret sharing, which the Detective uses to distribute information about the permutation without revealing it to the Mafia.","marker":"[10]"},{"why":"Provides exact win probabilities for the case d=0, used for comparison and to motivate the conjectured asymptotic behavior.","marker":"[12]"},{"why":"Demonstrates verifiable secret sharing that remains secure even with malicious participants, supporting the robustness of the shard distribution.","marker":"[14]"},{"why":"Supplies public-key cryptography used for private message channels and encryption of shards.","marker":"[15]"},{"why":"Provides the classic secret sharing scheme used to split the permutation among players.","marker":"[16]"}],"fun_headline_variants":["Optimal play found for Mafia with one Detective","Exact win probabilities for Mafia(n,1,1) game","Mutually optimal strategies for Mafia and Detective","First proven optimal strategies for 1-Detective Mafia"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Optimal play found for Mafia with one Detective","Exact win probabilities for Mafia(n,1,1) game","Mutually optimal strategies for Mafia and Detective","First proven optimal strategies for 1-Detective Mafia"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000309,"raw_usage":{"cost":0.000308728,"is_byok":false,"cost_details":{"upstream_inference_cost":0.000308728,"upstream_inference_prompt_cost":8.0528e-05,"upstream_inference_completions_cost":0.0002282},"total_tokens":1595,"prompt_tokens":780,"completion_tokens":815,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":746}},"tokens_in":780,"tokens_out":815,"cost_source":"openrouter_usage","duration_ms":8095,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":746,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T14:42:06.558825+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"A Monte Carlo simulation of the AnonymousLeader and Random strategies for n between 3 and 30, using the exact SMC-based SortBroadcast, that yields Mafia win probabilities deviating from the recursively computed values in Appendix C by more than one percent would indicate a flaw in the proof or implementation.","supporting_citations":[{"cited_title":"Mafia: A theoretical study of players and coalitions in a partial information environment.Ann","cited_arxiv_id":null,"evidence_quote":"Provides the baseline upper and lower bounds for Mafia win probabilities without a Detective, which the current work extends to include the Detective."},{"cited_title":"Cambridge University Press, 2015","cited_arxiv_id":null,"evidence_quote":"Supplies the secure multiparty computation framework used to implement anonymous broadcast (SortBroadcast)."},{"cited_title":"How to play any mental game, or a completeness theorem for protocols with honest majority","cited_arxiv_id":null,"evidence_quote":"Shows that SMC tolerates malicious adversaries under the honest majority assumption, necessary for the protocol's security."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces secret sharing, which the Detective uses to distribute information about the permutation without revealing it to the Mafia."},{"cited_title":"A mathematical model of the Mafia game","cited_arxiv_id":"1009.1031","evidence_quote":"Provides exact win probabilities for the case d=0, used for comparison and to motivate the conjectured asymptotic behavior."},{"cited_title":"Verifiable secret sharing and multiparty protocols with honest majority","cited_arxiv_id":null,"evidence_quote":"Demonstrates verifiable secret sharing that remains secure even with malicious participants, supporting the robustness of the shard distribution."},{"cited_title":"On data banks and privacy homomorphisms.Foundations of secure computation, 4(11):169–180, 1978","cited_arxiv_id":null,"evidence_quote":"Supplies public-key cryptography used for private message channels and encryption of shards."},{"cited_title":"How to share a secret.Communications of the ACM, 22(11):612–613, 1979","cited_arxiv_id":null,"evidence_quote":"Provides the classic secret sharing scheme used to split the permutation among players."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}