CS Paper Radar

How to Defeat a Mafia (of Size 1)

Michael Brand

cs.GT cs.CR ·submitted 2026-11-12 09:02 UTC · v1

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$.

Comment
19 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Communication Shapes Collective Inference in Self-Adapting LLM Societies: Evidence from Mafia

cs.MA cs.AIcs.CL ·2026-10-04 ·Haonan Huang, Joey Xiao
similarity 0.64
Abstract

When does communication help a group identify hidden adversaries, and how does its value change as the group adapts? In Mafia, an informed minority hides inside an uninformed majority whose only evidence is open play. The zero-information game, where each day's vote eliminates a random player, is exactly solved and scores every society; matched-casting comparisons between protocols identify the effect of communication. Societies of 8-100 claude-haiku-4-5 agents (7,416 analyzed games, 1.9M model calls) adapt by rewriting and inheriting private strategy notes. Simultaneous broadcast improves adversary identification over silence in all nine compositions tested (8-46 players). Turn-taking removes most of this advantage; its voting landslides are as frequent as broadcast's but land on mafia near chance (1.08x versus 2.53x). At 70 players, agents reading eight statements per day identify adversaries worse than silent ones, and limited talk is worth less than at 46 players. Adaptation is fast but need not help. In their first broadcast games, citizens announce their role far more often than mafia (91% vs. 30%) and first-day votes find mafia at three times chance; within two generations citizens stop announcing and the cue fades, a change the inherited notes carry. In controlled redeployments at 16 players, societies carrying sixty generations of their own notes score below societies with none. Communication shapes both collective inference and the signals it depends on, so a protocol's value must be measured together with the adaptation that changes those signals.

0.21

Be Careful Who You Trust: Coordination Dynamics under Corrupted Communication in LLM Multi-Agent Games

cs.MA cs.LG ·2026-09-19 ·Xuanyi Liu, Niall Dalton, Hairi Amin, Xiyuan Yin, Lydia Lim
similarity 0.56
Abstract · To be published in REALM: The 2nd Workshop for Research on Agent Language Models at EMNLP 2026

Large language models are increasingly used as interacting agents, but it remains unclear how robust their coordination is when public communication is unreliable. We study this question in iterated $N$-player Stag Hunt games played by homogeneous LLM groups under controlled programmatic action inversion, which changes both the public transcript and the actions used for execution. Across an experimental grid spanning group sizes, coordination thresholds, corruption levels, and seven LLMs, we observe three main patterns. First, honest agents' pre-flip Stag choices decline as corruption increases, but the sharp fall in public success is primarily mechanical. In the focal $N=5,M=3$ setting, pre-flip success remains 78% at 80% corruption, while public success falls to 12%. Second, honest choices are associated with the public history available at decision time, particularly under high corruption. Third, three threshold-style public-report benchmarks yield similar action-match rates to the LLM agents, showing substantial descriptive agreement between LLM decisions and these benchmarks. Overall, our results show that original choices, public actions, and executed outcomes must be separated when evaluating multi-agent robustness, as corrupted communication can severely and predictably degrade mutually beneficial cooperation.

0.35

Performance of Zero-determinant Strategies in Repeated Games without Discounting

cs.MA physics.soc-pheess.SY ·2026-10-02 ·Masahiko Ueda
similarity 0.54
Abstract · 4 pages, 1 figure

Zero-determinant (ZD) strategies are a class of strategies in repeated games, which unilaterally control payoffs. It has been shown that several ZD strategies promote cooperation in social dilemma games. It has been widely believed that the performance of ZD strategies is expressed as ``unilaterally enforce linear relations between payoffs''. However, in order to interpret properties of ZD strategies in repeated games without discounting, previous studies assumed that the limit of the Cesaro average of the probability distribution of the action profile exists. Here, we explain the performance of ZD strategies without this assumption, which leads to a stronger result than previous ones.

0.41

Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria

cs.GT cs.CCcs.DScs.LG ·2026-09-19 ·Ioannis Anagnostides, Weiqiang Zheng
theory similarity 0.53
Abstract

A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by the problem of regulating algorithmic collusion, this refinement was introduced by Hartline, Wang, and Zhang [EC'26], who showed that it can be computed in polynomial time in explicitly represented normal-form game. In this paper, we examine the complexity of IVF(C)CEs in succinct games, which model more realistic strategic interactions that feature either many players or exponentially many pure strategies. We first show that computing an information-value-free CE is PPAD-complete in many-player polymatrix games or two-player Bayesian games, even when the approximation is a constant. We also prove an unconditional exponential query lower bound. Our results establish that IVFCEs are intractable, even in the centralized model, and rule out the existence of any efficient learning dynamics. This significantly strengthens the impossibility result of Hartline, Wang, and Zhang, which concerns a particular class of learning algorithms, and furnishes strong computational critiques of recent regulation on algorithmic collusion. To sidestep these hardness results, we examine the complexity of information-value-free CCE. Certain no-regret algorithms---such as regret matching or FTRL---provide a fully polynomial-time approximation scheme (FPTAS) for this problem. The complexity when the approximation is exponentially small turns out to be nuanced. On the one hand, leveraging no-regret dynamics, we establish membership in $\text{CLS} = \text{PPAD} \cap \text{PLS}$. On the other hand, we show that it is at least as hard as the P-matrix linear complementarity problem, and hence as hard as simple stochastic games. This shows that even IVFCCEs are unlikely to admit a polynomial-time algorithm barring a major breakthrough.

0.36

How a group that cannot communicate knows itself by its enemy

cs.GT cs.MAcs.ROeess.SY ·2026-10-29 ·Gregory Falco
similarity 0.53
Abstract · 6 pages main text; 35-page SI Appendix included as an ancillary file. Code and data: https://doi.org/10.5281/zenodo.23743441

Teams that cannot communicate seem stuck with what each member sees. We show that their opponent can tell them the rest. Silent hunters, jammed robots and traders who never meet all face an adversary that reacts to the group as a whole; every member can read that reaction, a tell, and learn what no member knows alone. One tell can do the work of a message from every member. The adversary would rather hide, but hiding interferes with its own task, and a team that commits in advance to how it will respond decides how much hiding is worth. A committed team never loses when its opponent cares more about its own goals, and does as well as a fully informed team exactly when the opponent's stake outweighs any gain from lying. Below that point the team learns more by trusting less: in a solved Gaussian model it obtains the truth by promising not to use all of it and keeps the cost the opponent would have paid to conceal; an exact test decides when this holds in finite games. How a team spreads its trust matters too. A lone uninformed member with a full-support prior needs a private coin, but with additive squared-error losses two interchangeable members who respond differently replace it, and a small discount on trust insures against misjudging the enemy. Information, on this view, is not only gathered or aggregated; it is produced by how a team commits to respond.

0.57

Games Over Observation Spaces in Multi-Agent Capture the Flag

cs.GT ·2026-09-05 ·Mae Frost, Michael Amir, Shaunak D. Bopardikar
published similarity 0.52
Abstract · 21 pages, 5 figures, To be published as a conference paper in the 17th International Conference on Game Theory and AI for Security (GameSec …

We consider a multi-agent Capture the Flag (CtF) scenario in a graph-based environment, where a team of attackers seeks to reach designated flag vertices while a defending team attempts to intercept them. In our setting, both teams operate using decentralized heuristic policies. While the attacking team may choose its heuristic from a diverse library of policies, the defense is restricted to playing a single fixed policy. To overcome this limitation, a centralized defense oracle strategically restricts the portion of the graph visible to each of its agents in order to elicit a wider range of emergent behaviors from its fixed policy. We formalize this interaction as a two-player zero-sum game, where the attacker reasons over its library of heuristics and the defense reasons over the combinatorial space of visibility profiles. To solve this intractably large game, we propose a Double Oracle algorithm to find approximate empirical equilibria, and we empirically validate that observation manipulation can improve the defense's performance.

0.34

Deception in Reach-Avoid Game with Unknown Heterogeneous Attackers Speed Information

cs.GT cs.RO ·2026-09-07 ·Xiangkai Wu, Shaolin Tan, Wei Wang, Zhen Han
similarity 0.52
Abstract

This letter investigates a reach-avoid game involving two Attackers and one Defender, where the Attackers aim to maximize the number reaching the target region while the Defender seeks to minimize it. In contrast to conventional complete information formulations, we consider an information asymmetry scenario where the Attackers' heterogeneous maximum speeds are privately known but publicly disclosed to lie within continuous ranges. Existing studies on uncertain speeds, however, have primarily focused on homogeneous settings, whereas heterogeneity extends the uncertainty from a common capability level to the relative capability configuration of the Attackers. To address the resulting capture-order ambiguity over infinitely many possible speed combinations, we establish a critical speed pair framework that characterizes when different capability configurations induce different optimal capture orders, and enables the analysis of the Defender's guessing behavior and the design of information-limiting strategies for the Attackers. We demonstrate that under certain initial conditions, the Attackers can mislead the Defender into making suboptimal decisions through a slow-speed deception strategy, achieving superior payoffs compared to the complete information game. Numerical visualizations reveal the widespread occurrence of such dilemma conditions.

0.20

The Open-Strategy Dictator Game: Cooperation Under Mutual Transparency

cs.GT cs.AIcs.MA ·2026-08-14 ·Michael Glass
similarity 0.51
Abstract

We introduce the Open-Strategy Dictator Game (OSDG), a variant of the classic dictator game in which each player's strategy is a natural-language document visible to all participants. The dictator's decision, to SHARE or TAKE an endowment, may depend on the text of the recipient's strategy. A large language model adjudicates each interaction by interpreting the dictator's strategy in the context of the recipient's. We run round-robin tournaments among diverse strategies and analyze the resulting payoff matrix using softmax equilibrium frequencies, dominance analysis, and sensitivity to the relative value of cooperation. Conditionally cooperative strategies, those that share with cooperators and take from exploiters, consistently dominate, while unconditional strategies (always share or always take) are weakly dominated. The results suggest that in environments where agents can inspect each other's decision procedures, conditional cooperation is evolutionarily robust across a wide range of payoff parameters.

0.04