# CSP4SDG: Constraint and Information-Theory Based Role Identification in Social Deduction Games with LLM-Enhanced Inference

arXiv: https://arxiv.org/abs/2511.06175 · HTML: https://mlsanity.com/paper/2511.06175/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 9 Nov 2025.

## Builds on (most cited first, 10 of 10)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Enhance Reasoning for Large Language Models in the Game Werewolf](https://mlsanity.com/paper/2402.02330/) (2024)
- [Finding Friend and Foe in Multi-Agent Games](https://mlsanity.com/paper/1906.02330/) (2019)
- [AMONGAGENTS: Evaluating Large Language Models in the Interactive Text-Based Social Deduction Game](https://mlsanity.com/paper/2407.16521/) (2024)
- [Linguistic Harbingers of Betrayal: A Case Study on an Online Strategy Game](https://mlsanity.com/paper/1506.04744/) (2015)
- [Putting the Con in Context: Identifying Deceptive Actors in the Game of Mafia](https://mlsanity.com/paper/2207.02253/) (2022)
- [The Mafiascum Dataset: A Large Text Corpus for Deception Detection](https://mlsanity.com/paper/1811.07851/) (2018)
- [Hidden-Role Games: Equilibrium Concepts and Computation](https://mlsanity.com/paper/2308.16017/) (2023)
- [Fine-Grained and Thematic Evaluation of LLMs in Social Deduction Game](https://mlsanity.com/paper/2408.09946/) (2024)
- [Training an Assassin AI for The Resistance: Avalon](https://mlsanity.com/paper/2209.09331/) (2022)

## Built on by (most cited first, 1 of 1)

- [Playing social deduction games with reinforcement fine-tuned large language models](https://mlsanity.com/paper/2610.04261/) (2026)

## Abstract (arXiv)

In Social Deduction Games (SDGs) such as Avalon, Mafia, and Werewolf, players conceal their identities and deliberately mislead others, making hidden-role inference a central and demanding task. Accurate role identification, which forms the basis of an agent's belief state, is therefore the keystone for both human and AI performance. We introduce CSP4SDG, a probabilistic, constraint-satisfaction framework that analyses gameplay objectively. Game events and dialogue are mapped to four linguistically-agnostic constraint classes-evidence, phenomena, assertions, and hypotheses. Hard constraints prune impossible role assignments, while weighted soft constraints score the remainder; information-gain weighting links each hypothesis to its expected value under entropy reduction, and a simple closed-form scoring rule guarantees that truthful assertions converge to classical hard logic with minimum error. The resulting posterior over roles is fully interpretable and updates in real time. Experiments on three public datasets show that CSP4SDG (i) outperforms LLM-based baselines in every inference scenario, and (ii) boosts LLMs when supplied as an auxiliary "reasoning tool." Our study validates that principled probabilistic reasoning with information theory is a scalable alternative-or complement-to heavy-weight neural models for SDGs.