Source-linked AI summary
MARBO: Relational Belief Grounding for LLM Agents in Social Deduction Games
Hwang Yechan, Bae Sangjun, Kim Jeongmo, Bang Sangwoo, Han Seungyul
TL;DR
Social deduction agents must reason about hidden roles and alliances under partial observability, yet existing methods often optimize behavior without grounding it in reliable relational beliefs. MARBO integrates relational beliefs into preference optimization, and experiments across Werewolf and Among Us show consistent performance gains, especially for compact LLM agents.
Problem
Existing approaches often optimize actions and speech without explicitly grounding them in relational beliefs, leading to strategically inconsistent behavior, especially for compact LLM agents.
Method
MARBO uses relational beliefs to construct preference feedback and selectively reinforce decisions and speech supported by reliable reasoning and favorable social outcomes.
Results
Across Werewolf and Among Us, MARBO outperforms prompting-based and preference-learning baselines, with gains particularly evident for compact LLM agents.
Takeaways & Limitations
Optimizing hidden social reasoning can improve strategic consistency and social reasoning in partially observable multi-agent interaction.
Takeaways & Limitations
The framework is limited to turn-based interactions, may hallucinate actions inconsistent with the game trajectory, and restricts exploration through offline training.
Abstract
from arXiv · showhide
Social deduction games (SDGs) require agents to reason under partial observability by maintaining relational beliefs about hidden roles and team alignments. While recent LLM-agent approaches improve gameplay through prompting and preference optimization, they often optimize actions and in-game speech without explicitly grounding them in such beliefs. This frequently leads to strategically inconsistent behavior, especially for compact LLM agents. We introduce Multi-Agent Relational Belief Optimization (MARBO), a belief-grounded preference optimization framework that leverages relational beliefs to guide strategic decisions and in-game speech. MARBO provides preference feedback only when behaviors are supported by reliable relational beliefs and lead to strategically favorable social outcomes, encouraging more consistent learning under uncertainty. Experiments on representative SDGs show that MARBO enables compact LLM agents to consistently outperform existing baselines. The Code is available on https://github.com/PleaseTakemeAway/MARBO.
1 Introduction
Social deduction games test long-horizon social reasoning under partial observability, but existing approaches often fail to ground coherent actions and speech in relational beliefs. MARBO addresses this gap with belief-grounded preference optimization and improves compact agents’ performance on representative games.
- SDGs require agents to infer hidden roles and strategies while selecting actions and speech under partial observability.
- Existing approaches can produce goal-inconsistent actions, false suspicions, weakly grounded votes, and strategically ineffective speech.
- MARBO incorporates relational beliefs into preference optimization for strategic decisions and in-game speech.
- MARBO selectively reinforces behaviors supported by reliable reasoning and favorable social outcomes.
- MARBO improves compact LLM-agent performance on representative social deduction games and supports more strategically consistent behavior.
2 Related Work
Related work spans LLM reasoning, preference optimization, multi-agent systems, social deduction games, and relational belief modeling. These lines of research establish the surrounding methods and problem settings for MARBO.
- Enhancing Reasoning in LLMs: LLM reasoning research includes prompting, structured search, experience-based reasoning, learned verifiers, process supervision, self-play, and social interaction.
- Multi-agent Systems in Markov Games: Multi-agent systems research studies credit assignment, partial observability, robustness, and coordination in Markov and cooperative games.
- Multi-agent Systems in Markov Games: Text-based social deduction games require reasoning about hidden roles and intentions in multi-agent environments.
- Relational Belief Modeling: Relational belief modeling represents how agents stand toward one another, including social reasoning, Theory of Mind, and structured relational states.
3 Preliminaries
The paper formulates social deduction games as partially observable Markov games in which agents produce speech and task actions from incomplete observations. MARBO extends preference optimization by conditioning action generation and feedback on relational beliefs.
- Partially Observable Markov Games: A partially observable Markov game comprises agents, states, action spaces, transition dynamics, rewards, observations, and an episode horizon.
- Agent Actions and Observations: Each agent action combines natural-language speech with task-specific actions such as voting, elimination, investigation, or protection.
- Agent Actions and Observations: The game state contains hidden social information and publicly observable information, while agents act from partial observations and interaction history.
- Preference Optimization in SDGs: Preference optimization assigns desirable or undesirable feedback to responses, with KTO weighting independently labeled responses through λ_D and λ_U.
- Preference Optimization in SDGs: MARBO extends phase-specific preference optimization by incorporating relational beliefs into preferences for both speech and task actions.
4 Methodology
MARBO models agents’ relational beliefs about hidden social identities and uses them to construct selective preference feedback for speech and task actions. It jointly trains belief inference and KTO-based policy optimization so favorable behavior is reinforced only when grounded in reliable reasoning.
- Relational belief formulation: MARBO represents latent social information through relational beliefs about other agents’ hidden roles or team affiliations.An additional unknown label captures cases where another player’s identity cannot be reliably inferred.
- Relational belief supervision: MARBO first supervises agents to infer other players’ social identities from trajectory data.The belief objective uses Dbelief to improve relational belief inference.
- Belief-grounded preference construction: MARBO constructs preferences from both inferred beliefs and action types rather than rewarding favorable outcomes alone.This separates speech-action and task-action feedback so preference signals reflect whether behavior is grounded in reliable relational reasoning.
- Speech-action preference: Speech feedback rewards valid speech that shifts other players’ beliefs in a strategically favorable direction.For voting-based games, reducing suspicion toward an adversarial agent is favorable, and belief shifts are computed using non-adversarial players.
- Task-action preference: Task-action feedback is positive only when the selected target’s social identity is correctly inferred and the action is favorable under the game objective.Actions without explicit targets are evaluated solely through task validity.
- Data construction and optimization: MARBO jointly optimizes KTO-based preference learning and relational belief supervision using collected gameplay trajectories.Belief supervision uses the full trajectory dataset, whereas preference optimization uses trajectories generated by the SFT-initialized base model.
5 Experiments
MARBO is evaluated on Werewolf and Among Us through overall win rates, relational-belief accuracy, belief-shaping communication, target-directed actions, and component ablations. Across these analyses, it achieves stronger performance and shows that jointly grounding beliefs, actions, and speech is important.
- Overall Strategic Performance: MARBO remains strongest in head-to-head play, achieving 70%, 64%, and 58% in Werewolf and 79%, 73%, and 69% in Among Us against Base, ReCon, and MaKTO.These results are reported for trained 7B/E2B models.
- Relational Belief Construction: MARBO infers hidden roles most accurately overall at 57%, with gains consistent across roles and stable through Day 4.The largest improvement is reported for Villagers, whose identities must be inferred from discussion alone.
- Relational Belief Construction: MARBO reaches 57.2% belief accuracy, above random beliefs at 18.3%, and narrows the performance gap toward oracle beliefs associated with 78.5% game performance.Random beliefs reduce game performance to 30.1%, while oracle beliefs achieve perfect role prediction.
- Belief-Shaping Communication: MARBO-trained Werewolves induce more Villager-side errors and improve belief-shaping outcomes, including mispoison, misprotect, and intended-role inference.The reported effects indicate stronger concealment of Werewolf identity and more successful misdirection.
- Target-Directed Task Actions: MARBO leads on Poison Wolf, Heal Villagers, and Protect Villagers, showing that relational beliefs guide private, irreversible night actions.These measures evaluate whether special roles select appropriate targets without public discussion.
- Ablation Studies: Removing belief grounding lowers average win rate from 66% to 55%, while removing belief-action and belief-speech feedback reduces it to 39% and 34%.The ablation supports jointly optimizing relational beliefs, task actions, and speech actions.
6 Conclusion
MARBO supervises beliefs about hidden roles, team alignments, and strategic relations, then uses them to ground feedback for decisions and speech. Across Werewolf and Among Us, it outperforms prompting-based and preference-learning baselines, demonstrating the value of optimizing hidden social reasoning in partially observable interaction.
- Contribution: MARBO supervises agent-wise beliefs about hidden roles, team alignments, and strategic relations, then constructs belief-grounded feedback for task decisions and speech actions.The framework aligns behavior with inferred social relations and encourages communication that shapes others’ beliefs.
- Conclusion: Across Werewolf and Among Us, MARBO outperforms prompting-based and preference-learning baselines.The conclusion presents this as evidence for optimizing hidden social reasoning in partially observable multi-agent interaction.
Limitations
MARBO is limited to turn-based interactions with predefined communication turns, may hallucinate actions inconsistent with the game trajectory, and restricts exploration through offline training data.
- Turn-based interactions restrict communication to predefined turns.
- Occasional model hallucinations can produce actions inconsistent with the game trajectory.
- Offline training limits exploration to strategies observed in the training data.
Ethical Considerations
The study examines deception in social deduction games and acknowledges that learned behaviors could be misused to improve deceptive capabilities. It therefore advocates safeguards and ethical guidelines to mitigate potential misuse.
- Learned behaviors from deception-focused social deduction games could potentially improve deceptive capabilities outside gameplay.
- The authors oppose deceptive or manipulative uses and advocate safeguards and ethical guidelines to mitigate misuse.
Artifact Licenses and Intended Use
The work uses publicly available Werewolf and Among Us benchmarks within their original research intent and licenses, with game configurations, rules, roles, objectives, processes, and belief-label resources described for research use.
- Artifact use: The study relies on Among Us and Werewolf benchmarks released for research use and uses them within their original intended purposes and licenses.
- Werewolf: Werewolf assigns players to Werewolf or Villager factions, alternating hidden night actions with public daytime discussion and voting under asymmetric information.
- Werewolf: The experimental Werewolf setup uses nine players: three Werewolves, one Seer, one Witch, one Guard, and three ordinary Villagers.
- Werewolf objectives: Werewolves win by reaching numerical parity or superiority, while the Villager faction wins by eliminating all Werewolves before that condition.
- Among Us: Among Us uses Crewmate and Impostor roles in a map-based game combining task execution, movement, discussion, voting, and deception.
- Among Us objectives: Crewmates win by completing tasks or ejecting all Impostors, whereas Impostors win by reaching numerical parity or exhausting the 50-step limit.
- Among Us process: Among Us alternates task and meeting phases, with meetings triggered by reported bodies or emergency buttons and followed by discussion and voting.
- Supporting materials: The artifact includes belief-supervision labels, strategic task-utility definitions, preference-learning data, training details, prompts, and game-specific label tables.
B.4 Game-Specific Task Utility
Game-specific task utility assigns positive or negative values to actions according to game rules and ground-truth social labels, while the framework's supporting data and training materials are documented separately.
- Utility definition: Desirable task actions receive positive utility and undesirable actions receive negative utility for each game stage.
- Utility definition: Task utility is determined by game rules and ground-truth social labels to indicate whether an action benefits the acting agent’s role.
- Implementation materials: The appendix provides game-specific utility tables, expert and preference-learning data statistics, training details, and prompt templates.
C.1 Dataset Details
The framework uses game trajectories, expert demonstrations, belief-grounding samples, and preference labels to train agents with relational-belief supervision. Werewolf and Among Us use related but distinct training setups and compact backbone models.
- Werewolf: Werewolf training combines supervised fine-tuning on expert demonstrations with relational belief-based preference optimization.The demonstrations cover night actions, votes, speeches, and strategic behaviors.
- Preference data: Preference optimization decomposes trajectories into night-action, vote, speech, and belief-grounding samples labeled by relational belief-conditioned rewards.The data includes 300 random-play trajectories from a diverse agent pool.
- Data processing: Stored trajectories retain observable histories, actions, inferred beliefs, and ground-truth social labels for offline construction of belief targets and KTO preference labels.This decouples trajectory collection from optimization and avoids new environment rollouts at every optimization step.
- Among Us: Among Us uses direct relational belief-based preference optimization without an additional SFT stage, using 300 trajectories from a diverse agent pool.This setup evaluates scalability to smaller backbone models.
- Data quality: Belief-grounding samples use Unknown labels when evidence is insufficient and apply verification to filter hallucinated or game-state-inconsistent samples.Approximately 500 belief-grounding samples are constructed from available information and ground-truth role states.
- Models and training: Experiments use Qwen2.5-7B and Qwen2.5-14B for Werewolf and Gemma-E2B and Gemma-E4B for Among Us, with training distributed across four or eight A100 80GB GPUs.The Qwen 14B model uses eight GPUs; the smaller models and Qwen 7B use four.
E Experimental Details
The experiments define game-specific metrics for relational beliefs, belief-shaping communication, and belief-grounded decisions, then report fixed-opponent and head-to-head performance in Werewolf and Among Us. MARBO achieves the strongest reported results across the highlighted comparisons.
- Metric definitions: Werewolf metrics cover alignment accuracy, exact role prediction, and Wolf F1 for hidden-role and adversary inference.Wolf F1 accounts for false accusations and missed wolves.
- Metric definitions: Among Us metrics include Role Accuracy, Impostor Detection, and Belief F1 for role and adversary identification.Belief F1 accounts for both false accusations and missed Impostors.
- Belief-shaping communication: Communication metrics measure whether speech changes listeners’ beliefs toward an intended identity and whether suspicion toward an Impostor decreases or increases.Belief-shaping success averages evaluator judgments across listeners, speeches, and games.
- Belief-grounded decisions: Decision metrics measure role-specific actions, belief-consistent votes, correct votes for Impostors, and collective Impostor expulsion.The metric set includes Belief Vote, Vote Imp., and Expel Imp.
- Werewolf results: MARBO achieves the highest average win rates across Qwen7B and Qwen14B Werewolf variants and outperforms baselines in head-to-head competition.The reported gains are consistent for both sides and indicate robust role-conditioned behavior against trained opponents.
- Among Us results: MARBO achieves the highest average win rates across Gemma-E2B and Gemma-E4B Among Us variants, with head-to-head results outperforming Base, ReCon, and MaKTO.The comparison covers fixed-opponent and head-to-head settings.
- Behavior analysis: Figure F.3 analyzes Among Us behavior through relational belief construction, belief-grounded task actions, and belief-shaping communication.The three analyses correspond to the reported behavior dimensions.
F.2 Behavior Analysis in Among Us
MARBO improves relational belief construction, converts beliefs into more effective voting behavior, and produces more favorable suspicion dynamics in Among Us. The reported results cover the full path from hidden-role inference through downstream social outcomes.
- Relational belief construction: MARBO reaches about 0.62 Role Acc. and 0.48 Imp. Detect, outperforming all baselines in relational belief construction.Baselines remain below 0.30 on Role Acc. and below or around 0.40 on Imp. Detect.
- Belief-grounded task action optimization: MARBO obtains around 0.41 Belief F1 and 0.56 Belief Vote, indicating stronger belief quality and more consistent belief-to-vote use.It also achieves around 0.39 Vote Imp. and 0.29 Expel Imp. in downstream voting outcomes.
- Belief-shaping communication optimization: MARBO produces the most favorable suspicion dynamics by reducing suspicion toward Impostor speakers in about 0.59 of updated Crewmate beliefs.The passage introduces Suspicion Reduced and Suspicion Raised as complementary measures of belief updates.