MARBO: Relational Belief Grounding for LLM Agents in Social Deduction Games¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Social Deduction Games, Relational Belief Modeling, Preference Optimization, Partially Observable Markov Games, LLM Agents
TL;DR¶
Addressing the strategic inconsistencies, self-revealing speech, and blind voting of LLM agents in partially observable social deduction games, MARBO introduces explicit relational belief modeling into preference optimization, reinforcing speech only when it favorably shapes others' beliefs and rewarding actions only when grounded in correct target beliefs.
Background & Motivation¶
Large language model (LLM) agents have progressed from passive single-turn text generators into interactive systems capable of long-horizon coordination, negotiation, and decision-making under uncertainty. In social deduction games (SDGs) like Werewolf and Among Us, environments present extreme information asymmetry and partial observability. Agents must not only master game rules but also continuously infer latent inter-player relations—such as hidden role assignments, team alignments, and mutual suspicions—across multi-turn discussions and voting rounds. Consequently, SDGs serve as an ideal crucible for testing advanced social reasoning, Theory of Mind (ToM), and strategic communication in autonomous agents.
However, existing LLM agent architectures exhibit severe strategic incoherence and reasoning-to-decision gaps when placed in these deceptive social arenas. Approaches reliant on prompting, verbal reflection, or end-to-end multi-agent preference optimization (such as MaKTO) typically optimize behaviors against outcome-level returns or surface conversational fluency. This indiscriminate reinforcement mechanism introduces severe vulnerabilities: when an agent's underlying belief regarding other players is fundamentally flawed, fortuitous victories or fluent utterances nonetheless receive positive preference signals. Over training, this reinforces hallucinatory reasoning, causing agents to contradict their own deductions, inadvertently expose private allegiances, or cast elimination votes against declared allies. Such degradation is especially catastrophic in compact open-source LLM agents (e.g., 7B or 2B–4B parameter scales), which struggle with long conversational context retention.
The core tension underlying these failures is that observable actions—both strategic speech and target-directed task actions—are disconnected from verified internal beliefs, with preference optimization optimizing behaviors irrespective of latent relational veracity. To achieve genuine social intelligence, agents must ground their communications and actions in structured representations of what other players know and believe. Core idea: Formulate a Multi-Agent Relational Belief Optimization (MARBO) framework that explicitly tracks and supervises inter-player relational beliefs, assigning positive preference feedback only when actions are backed by verified target beliefs and when speech successfully steers listeners' beliefs toward strategically advantageous states.
Method¶
Overall Architecture¶
MARBO formulates social deduction gameplay as a Partially Observable Markov Game (POMG). Each agent maintains and updates an explicit relational belief vector \(\hat{b}_{ij}^t \in \mathcal{C} \cup \{\text{unknown}\}\) representing its deduction of other players' hidden roles or faction affiliations. The overall training pipeline operates across three integrated phases: trajectory collection, relational belief supervision, and belief-grounded preference optimization. Interaction rollouts are decoupled from training to support offline optimization. Agents first undergo supervised fine-tuning (SFT) or belief supervision to establish baseline role inference. Subsequently, preference optimization differentiates between communication (evaluating how an utterance alters listeners' beliefs) and task actions (evaluating whether a vote or skill matches both objective rules and internal target beliefs) within a unified KTO objective.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Trajectory History & Local Observation<br/>τ_i^t = (I_i, h_i^t, o_i^t)"] --> B["Relational Belief Inference & Supervision<br/>L_belief: Supervise Hidden Social Labels"]
B --> C["Belief-Conditioned Policy Generation<br/>π_θ(a_i^t | τ_i^t, b_i^t)"]
C --> D{"Action Demux"}
D -->|Public Speech Action| E["Belief-Shaping Speech Feedback<br/>Evaluate Favorable Listener Belief Shifts"]
D -->|Targeted Task Action| F["Belief-Grounded Task Action Feedback<br/>Verify Rule Utility & Target Belief Truth"]
E --> G["Joint Multi-Agent Optimization<br/>L_MARBO = L_KTO + λ_belief L_belief"]
F --> G
Key Designs¶
1. Relational Belief Formulation and Cognitive Constraint Supervision: Preventing overconfident early guessing Standard LLM agents tend to hallucinate rigid accusations early in the game when public evidence is virtually non-existent. MARBO formally models the relational belief of agent \(i\) about agent \(j\) as \(\hat{b}_{ij}^t \in \mathcal{C} \cup \{\text{unknown}\}\). To instill epistemic caution and prevent label leakage during offline training, \(D_{\text{belief}}\) enforces strict role-conditional masking: in Werewolf prior to Day-1 discussion, Villager-faction players are assigned \(\text{unknown}\) for all other agents (only Werewolves know partners, and the Seer knows the inspected target), transitioning to ground-truth labels only after Day-1 speeches are observed. In Among Us, Crewmates assign \(\text{unknown}\) until two discussion rounds elapse. The policy is optimized via cross-entropy loss: $\(\mathcal{L}_i^{\text{belief}} = \mathbb{E}_{(\tau_t^i, c) \sim D_{\text{belief}}} \left[ -\log \pi_i^\theta(c \mid \tau_t^i) \right]\)$ This forces agents to ground role attributions strictly in accumulated conversational and behavioural evidence rather than guessing blindly.
2. Belief-Shaping Speech Feedback: Shifting from superficial fluency to deliberate belief manipulation Rather than rewarding natural-sounding utterances or distant game wins, MARBO evaluates speech by its psychological impact on fellow players' perceptions. For speaker \(i\) uttering \(a_i^{\text{speech},t}\), the framework assesses the belief state of listener \(j\) before (\(\hat{b}_{ji}^t\)) and after (\(\hat{b}_{ji}^{t,+}\)) the utterance. Following an LLM-verifier check (implemented via Claude-3.5-Sonnet to eliminate rule-violating mechanical or format hallucinations), a belief shift function \(\delta \in \{-1, 0, +1\}\) scores the transition: \(\delta = +1\) if the speech induces a strategically favorable shift (e.g., reducing a Werewolf's or Impostor's suspicion among Villagers/Crewmates), \(\delta = -1\) if suspicion increases or roles are exposed, and \(0\) for neutral shifts. Aggregating over all non-adversarial listeners yields the signed speech preference: $\(d_i^{\text{speech},t} = \sum_{j \neq i} \delta(a_i^{\text{speech},t}, \hat{b}_{ji}^t, \hat{b}_{ji}^{t,+})\)$ This directly incentivizes deceptive agents to craft persuasive alibis and villager agents to present coherent, trust-building deductions.
3. Belief-Grounded Task Action Alignment: Eliminating false credit attribution in target selection In voting and nighttime skill actions (e.g., Witch poison/healing, Guard protection, Impostor assassination), baseline agents frequently display cognitive dissonance—verbally suspecting Player 2 while voting Player 1 due to majority bandwagons. Furthermore, an agent voting for an actual adversary by pure chance receives positive outcome reinforcement under naive RL. MARBO couples the objective game utility \(\eta_{\text{task}}(a_i^{\text{task},t}, c) \in \{-1, +1\}\) with internal belief consistency: $\(d_i^{\text{task},t} = \begin{cases} \eta_{\text{task}}(a_i^{\text{task},t}, c), & \text{if } \hat{b}_{ij}^t = c_j \text{ (where } j = \text{tar}(a_i^{\text{task},t})\text{)}, \\ -1, & \text{otherwise}. \end{cases}\)$ A task action receives positive utility if and only if the agent correctly identified the target's true identity (\(\hat{b}_{ij}^t = c_j\)) and executed a beneficial game move. Lucky guesses with false underlying beliefs are penalised as negative samples (\(-1\)), guaranteeing that behavioral policies reflect truthful internal reasoning.
Loss & Training¶
MARBO adopts a decoupled trajectory collection and optimization paradigm. Gameplay trajectories are harvested from a diverse pool containing SFT models and diverse LLM opponents (GPT-4o, GPT-4o-mini, Gemma4-31B, Qwen3.6-27B) across 300 games, yielding 3.5k–5k decision pairs. Optimization combines Kahneman-Tversky Optimization (KTO)—which models positive and negative preferences independently under prospect theory utility \(v(x, y)\)—with relational belief supervision: $\(\mathcal{L}_{\text{MARBO}}(\theta) = \mathcal{L}_{\text{KTO}}(\theta) + \lambda_{\text{belief}} \mathcal{L}_{\text{belief}}(\theta)\)$ Hyperparameters are standardized across benchmarks: KTO weights \(\lambda_D = 0.7, \lambda_U = 1.0\), belief loss weight \(\lambda_{\text{belief}} = 0.2\), per-device batch size 2 with 16 gradient accumulation steps, and learning rate \(1 \times 10^{-6}\). Werewolf models use Qwen2.5-7B/14B-Instruct, while Among Us scales down to Gemma-E2B/E4B without game-specific SFT, trained using DeepSpeed ZeRO-3 on A100-80GB GPUs.
Key Experimental Results¶
Main Results¶
Evaluation spans a 9-player Werewolf setup (3 Werewolves, 1 Seer, 1 Witch, 1 Guard, 3 Villagers; 100 games across 5 seeds) and a 7-player Among Us setup (5 Crewmates, 2 Impostors; 200 games), competing against five fixed opponent models.
| Game & Scale | Method | GPT-4o-mini | GPT-4o | Claude-4.5-Haiku | Gemma4-31B | Qwen3.6-27B | Avg. Win Rate (%) |
|---|---|---|---|---|---|---|---|
| Werewolf (7B) | Base | 46.6±3.7 | 40.4±4.2 | 25.2±4.6 | 23.8±3.9 | 29.8±4.4 | 33.2±2.1 |
| ReCon | 43.8±4.1 | 21.8±4.8 | 17.8±3.6 | 29.0±4.5 | 24.2±4.0 | 27.3±0.9 | |
| MaKTO | 52.2±4.3 | 46.8±3.8 | 45.0±4.7 | 33.8±4.2 | 30.2±3.9 | 41.6±1.6 | |
| MARBO (Ours) | 70.2±2.6 | 67.8±2.5 | 64.0±2.1 | 61.0±2.7 | 65.2±2.4 | 65.6±1.7 | |
| Werewolf (14B) | Base | 76.8±4.5 | 56.2±3.8 | 52.0±4.7 | 50.0±4.1 | 58.0±3.9 | 58.6±0.9 |
| ReCon | 69.8±4.3 | 52.0±4.6 | 48.0±3.7 | 51.0±4.8 | 52.0±4.0 | 54.6±1.6 | |
| MaKTO | 78.0±3.9 | 63.0±4.4 | 58.0±4.6 | 53.0±3.8 | 68.0±4.7 | 64.0±1.8 | |
| MARBO (Ours) | 80.2±2.4 | 74.8±2.8 | 66.2±2.2 | 68.0±2.6 | 73.2±2.0 | 72.5±0.8 | |
| Among Us (E2B) | Base | 36.0±5.7 | 24.0±4.4 | 38.0±1.4 | 13.0±2.0 | 14.0±5.5 | 25.0±3.8 |
| ReCon | 48.0±4.7 | 32.0±2.6 | 47.0±3.7 | 19.0±3.8 | 30.0±3.0 | 35.2±3.6 | |
| MaKTO | 47.0±4.8 | 35.0±3.0 | 46.0±2.0 | 20.0±3.9 | 34.0±3.9 | 36.4±3.5 | |
| MARBO (Ours) | 70.0±3.3 | 49.0±2.8 | 55.0±2.6 | 28.0±2.0 | 42.0±3.5 | 49.0±2.8 | |
| Among Us (E4B) | Base | 49.0±5.7 | 41.0±4.7 | 60.0±2.7 | 24.0±4.7 | 29.0±3.5 | 41.0±4.3 |
| ReCon | 42.0±5.0 | 38.0±3.1 | 54.0±5.2 | 22.0±4.8 | 26.0±2.8 | 36.0±4.2 | |
| MaKTO | 47.0±4.2 | 46.0±3.5 | 55.0±1.9 | 24.0±3.0 | 30.0±2.5 | 40.0±3.0 | |
| MARBO (Ours) | 73.0±3.1 | 71.0±3.3 | 69.0±2.3 | 30.0±3.3 | 51.0±2.4 | 59.0±2.9 |
Ablation Study & Detailed Metrics¶
Component ablation on Qwen2.5-7B in Werewolf reveals the specific contribution of each belief module:
| Variant | Win Rate (%) | Impact / Description |
|---|---|---|
| MARBO (Full model) | 65.6±1.7 | Joint optimization of relational beliefs, speech shaping, and task actions |
| w/o Belief construction | 55.0±2.6 | Drops explicit internal belief states; actions conditioned on history directly (-10.6%) |
| w/o Belief-Action optimization | 39.0±3.4 | Removes belief correctness filter from task preference; only uses outcome utility (-26.6%) |
| w/o Belief-Shaping optimization | 34.0±3.8 | Speech feedback ignores listener belief shifts, evaluating only fluency (-31.6%) |
Key micro-level diagnostic findings: 1. Belief Formation Accuracy: In Werewolf, MARBO achieves 66.0% alignment accuracy, 57.2% exact role prediction accuracy (vs. 37.8% for Base), and 56.4% Wolf F1 (vs. 31.2% for MaKTO). Crucially, Villager role prediction jumps from 27.2% to 52.2%, proving accurate social reasoning from public discourse alone without private nightly information. 2. Action-Belief Alignment: Voting accuracy targeting true werewolves climbs to 70.2% (vs. 51.2% for Base), translating into a 65.4% collective expulsion rate. In night actions, Witch Poison Wolf and Guard Protect Villager rates significantly outperform all baselines. 3. Deceptive Influence Success: When MARBO werewolves execute deceptive speech (e.g., claiming fake Seer), opponent models perceive them as the claimed role with 78.4% success against GPT-4o (vs. 36.4% for MaKTO). In Among Us, Impostor speech reduces Crewmate suspicion in 59% of updates (vs. 30%–33% for baselines), while suspicion-increasing blunders drop from ~70% to 41%.
Key Findings¶
- Belief-shaping communication is the foremost performance driver: Ablating speech belief shaping causes the steepest decline (\(-31.6\%\)), demonstrating that social deduction games are primarily won through informational steering rather than solitary deduction.
- Belief grounding outcompetes model parameter scaling: MARBO-7B (65.6% win rate) systematically defeats MaKTO-14B (64.0%) and Base-14B (58.6%), confirming that resolving reasoning-to-action disconnects provides greater strategic dividends than scaling model capacity.
- Temporal coherence over long horizons: Role prediction accuracy remains consistently high through Day 4, mitigating the typical decay caused by conversational context dilution in extended multi-agent interactions.
Highlights & Insights¶
- Differential belief tracking as communication reward: Rather than relying on generic linguistic scores, quantifying speech effectiveness as the directional delta in listeners' internal beliefs provides a principled, gradient-friendly paradigm for training communicative intent.
- Pruning fortunate errors via joint belief-action filtering: Discarding actions that are empirically successful but based on erroneous beliefs neutralizes reward hacking and ensures agents learn robust, generalizable causal reasoning.
- Feasibility on lightweight models: Demonstrating that 2B–4B edge models (Gemma-E2B/E4B) can master deceptive multi-agent coordination without SFT pre-training highlights the sample efficiency of belief-conditioned preference optimization.
Limitations & Future Work¶
- Strictly turn-based constraints: The current formulation operates within sequential speaking and voting phases, leaving real-time, asynchronous, or interruption-heavy human communications unaddressed.
- Offline exploration limitations: Relying on offline collected trajectories restricts policy exploration to pre-existing behaviors, which may prevent discovering novel emergent equilibrium strategies.
- Occasional factual hallucinations: In extended games with dense deceptive claims, models can occasionally reference past rounds inaccurately. Future directions include integrating online self-play RL with dynamic belief graph verifiers.
Related Work & Insights¶
- vs ReCon: ReCon relies on prompt-based recursive contemplation and memory retrieval without updating model parameters. Under long-horizon deception, prompting degrades significantly due to attention fatigue; MARBO instills intrinsic social reasoning into model weights via preference optimization.
- vs MaKTO: MaKTO pioneer phase-level KTO for multi-agent games but relies strictly on outcome rewards, frequently reinforcing flawed deductive chains that happened to win. MARBO resolves this reward hacking by enforcing strict belief consistency and belief-shaping feedback.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ [Pioneering integration of explicit relational belief states into both communicative and action-level preference optimization loops]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Comprehensive evaluations across Werewolf and Among Us, testing against multiple top-tier commercial LLMs with extensive ablation and psychological metrics]
- Writing Quality: ⭐⭐⭐⭐⭐ [Clear mathematical formulation, coherent problem motivation, and elegant alignment between theory and empirical analysis]
- Value: ⭐⭐⭐⭐⭐ [Provides a landmark methodology for training autonomous agents with Theory of Mind capabilities in high-stakes adversarial environments]