PaperlayerView exact revision on arXiv

Source-linked AI summary

Long-Horizon Dialogue Understanding for Role Identification in the Game of Avalon with Large Language Models

Simon Stepputtis, Joseph Campbell, Yaqi Xie, Zhengyang Qi, Wenxin Sharon Zhang, Ruiyi Wang, Sanketh Rangreji, Michael Lewis, Katia Sycara

arXiv:2311.05720v1cs.CLcs.AIcs.LG

TL;DR

The paper addresses whether LLMs can understand long-horizon, deceptive multi-party dialogue when participants have hidden roles and conflicting goals. It introduces an Avalon benchmark, human-game dataset, and multimodal role-prediction framework combining chat with game state. Current state-of-the-art LLMs do not reach human-level performance, while state representations and fine-tuning provide avenues for improvement.

  • Problem

    Current LLMs face limited evidence and major challenges in multi-party dialogue requiring long-horizon reasoning over conflicting goals, deception, persuasion, and game state.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces a benchmark and dataset of 20 human Avalon games and evaluates role prediction using chat, game state, full histories, and round-based carried-over beliefs.

    Source: §1 · p. 2, §4.1 · p. 4

  • Results

    Current state-of-the-art LLMs do not reach human-level performance on long-horizon dialogue understanding in multi-party cooperative-competitive settings.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The dataset and online testbed provide a benchmark for studying deception detection, role identification, and long-horizon decision-making in realistic multi-party dialogue.

    Source: §1 · p. 2, §6 · p. 9

    Performance depends on pretrained language-model capabilities, and the authors expect fine-tuning to improve with a larger dataset.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Deception and persuasion play a critical role in long-horizon dialogues between multiple parties, especially when the interests, goals, and motivations of the participants are not aligned. Such complex tasks pose challenges for current Large Language Models (LLM) as deception and persuasion can easily mislead them, especially in long-horizon multi-party dialogues. To this end, we explore the game of Avalon: The Resistance, a social deduction game in which players must determine each other's hidden identities to complete their team's objective. We introduce an online testbed and a dataset containing 20 carefully collected and labeled games among human players that exhibit long-horizon deception in a cooperative-competitive setting. We discuss the capabilities of LLMs to utilize deceptive long-horizon conversations between six human players to determine each player's goal and motivation. Particularly, we discuss the multimodal integration of the chat between the players and the game's state that grounds the conversation, providing further insights into the true player identities. We find that even current state-of-the-art LLMs do not reach human performance, making our dataset a compelling benchmark to investigate the decision-making and language-processing capabilities of LLMs. Our dataset and online testbed can be found at our project website: https://sstepput.github.io/Avalon-NLU/

1 Introduction

The paper introduces Avalon as a benchmark for long-horizon, multi-party dialogue understanding under hidden roles, conflicting goals, deception, and persuasion. It contributes a human-game dataset and evaluates whether LLMs can combine dialogue with game state for role identification.

  • The study evaluates LLMs across chat-only, chat-and-state, and state-only representations using round-based or full-context inputs.Source: Figure 1 · p. 1, §1 · p. 2
  • The benchmark targets challenges arising from many participants, joint dialogue-and-state grounding, and active deception and persuasion over extended horizons.Source: §1 · pp. 1–2
  • The benchmark models player-role identification in Avalon as long-horizon dialogue understanding with six participants, hidden roles, conflicting goals, deception, persuasion, and game-state reasoning.Source: §1 · pp. 1–2
  • The released dataset contains 2,384 utterances from 20 human games, annotated with persuasion, deception, player beliefs, and ground-truth game state.Source: §1 · p. 2
  • The paper analyzes current LLM performance, explores state representations for long-horizon modeling, and releases a browser-based Avalon testbed.Source: §1 · p. 2

2 Related Work

Prior dialogue research has generally used smaller, shorter, simpler, or less natural interactions than Avalon. This paper positions Avalon as a longer-horizon, multi-party benchmark combining realistic dialogue with hidden roles, persuasion, and deception.

  • Existing multi-party dialogue datasets often involve few participants or unnatural online-forum conversations, unlike Avalon’s natural six-player interactions.Source: §2 · pp. 2–3
  • Strategic dialogue systems have typically focused on single partners, shorter contexts, or simpler strategies, limiting their coverage of negotiation and deception.Source: §2 · pp. 2–3
  • Avalon differs from Diplomacy-style agents because all communication is public while hidden roles explicitly encourage deception and require grounding each utterance.Source: §2 · p. 3
  • Compared with Mafia and One Night Werewolf, Avalon contains longer games with 119 utterances per game versus 49 and 64, respectively.Source: §2 · p. 3
  • The dataset extends prior deception and persuasion resources with multi-party textual dialogue, hidden-role inference, persuasion labels, and deception labels.Source: §2 · p. 3

3 The Game of Avalon

Avalon is a six-player cooperative-competitive social deduction game in which good and evil teams infer roles while concealing or misrepresenting identities. Players discuss and vote on quests under rules that determine victory and defeat.

  • The six-player setting contains four good roles—Merlin, Percival, and two Loyal Servants—and two evil roles—Morgana and Assassin.Source: §3 · p. 3
  • Players form allegiances and infer others’ roles while hiding or pretending to hold different identities, with evil players seeking trust from the good team.Source: §3 · p. 3
  • The game proceeds through up to five quest rounds involving discussion, party formation, and public majority votes.Source: §3 · p. 3
  • A quest succeeds only when every selected player votes for success; evil wins after three failed quests, while good must complete three quests and avoid Assassin identification of Merlin.Source: §3 · p. 3
  • Online data collection uses turn-based discussion and fixed speaking times so game-related interactions are captured through the chat interface.Source: §3 · pp. 3–4

4 Dialogue Understanding

The paper formulates Avalon role identification as long-horizon dialogue understanding, combining player chat with structured game state and carried-over beliefs. It represents conversations by rounds, evaluates state-aware inference, and uses schema validation to enforce structured role predictions.

4 Dialogue Understanding

  • Avalon role inference predicts each player’s role from chat history and game state, while separately identifying Merlin using the evil players’ privileged knowledge.Source: §4 · p. 4

4.1 Long-Horizon Dialogue Representation

  • Round-based context divides dialogue into discussion rounds and carries structured beliefs about player identities forward to update predictions after each round.Each belief is one of good, evil, Merlin, or unknown.Source: §4.1 · p. 4
  • The framework compares full-game history with round-based context, using TypeScript to validate that every player receives a role assignment.Source: §4.1 · p. 4

4.2 State Representation

  • State representation converts proposed parties, quest outcomes, prior parties, and votes into linguistic inputs so models can reason about hidden roles in the game environment.Global state summarizes prior quests, while round-based updates communicate changes during the current discussion.Source: §4.2 · p. 5, §4.2.1 · p. 5

4.2.1 Global State

  • Global state records each quest’s outcome, party, player votes, and currently proposed party using templated textual statements.Source: §4.2.1 · p. 5

4.2.2 Round-Based State Change

  • During a conversation round, a seventh system participant reports proposals, votes, and quests so ongoing state changes remain available to the model.Source: §4.2.2 · p. 5

4.3 Tasks and Prompt Generation

  • Hand-designed prompts support role and Merlin prediction while enabling ablations that provide chat, game state, or both as model inputs.The chat-only condition removes state and system messages, whereas the state-only condition removes player utterances.Source: §4.3 · p. 5

4.3.1 Structured LLM Outputs

  • TypeChat uses a schema and compiler checks to convert model outputs into valid JSON role predictions, with follow-up queries repairing incomplete responses.The schema requires a role for each player but does not enforce a unique Merlin assignment.Source: §4.3.1 · pp. 5–6

5 Experiments

The experiments introduce and evaluate a human-played Avalon dataset, comparing context representations, modalities, model families, fine-tuning, and a Werewolf benchmark. Results show persistent challenges for LLM role identification, with performance shaped by game state, context length, deception, and model-specific adaptation.

5.1 Data Collection

  • The dataset contains 20 games from 30 participants, over 2300 utterances, hand-labeled persuasion and deception strategies, player beliefs, and game state.Source: §5.1 · p. 6, §5.1.2 · p. 6

5.1.2 Strategy Labels

  • Fine-tuned GPT-3.5 reaches micro-F1 0.43 for persuasion-strategy prediction, ahead of GPT-4 at 0.37, while Llama-2-13B reaches 0.15 and its fine-tuned version 0.20.Source: §5.1.2 · p. 7

5.2 Turn Order and Utterances

  • Good-player identification improves when Merlin is among the first three players or when Morgana or Percival speaks more, while frequent evil-player lies improve Merlin identification.Source: §5.2 · p. 7

5.3 Comparing Model Performance

  • Only GPT-4 using round-based chat exceeds the human baseline for identifying Merlin, while models generally lose accuracy on evil players and struggle more with Merlin.Source: §5.3 · pp. 7–8, Table 2 · p. 7
  • For GPT-based models, full-context Chat+State yields the highest good-and-evil role F1 scores, whereas Merlin prediction benefits from game-state information.Source: §5.3 · p. 8

5.3.1 LLM Fine-Tuning for Role Prediction

  • Fine-tuning improves Llama-2 role prediction, while GPT-3.5 gains substantially for Merlin identification and can outperform GPT-4 and humans on that task.Source: §5.3.1 · p. 8

5.4 Comparison to other Deception Tasks

  • Werewolf role prediction is stronger than Avalon prediction, which the authors associate with Werewolf’s shorter context horizon; fine-tuning benefits GPT-3.5 more consistently than Llama-2 there.Source: Table 3 · p. 9, §5.4 · p. 9

6 Conclusion

The paper presents a benchmark, dataset, and testbed for long-horizon dialogue understanding under conflicting interests. Its six-player annotated conversations and game states expose a gap between current LLMs and human-level performance while supporting research on deception and cooperative-competitive agents.

  • The benchmark combines six-player conversations, persuasion and deception labels, player beliefs, and comprehensive game states collected over more than 24 hours of gameplay.Source: §6 · p. 9
  • Current state-of-the-art LLMs do not reach human-level performance on tracking long-horizon dialogue in cooperative-competitive social settings.Source: §6 · p. 9
  • Compared with similar datasets, the benchmark offers longer context horizons, stricter rules, and high-quality dialogue with game-relevant communication captured for learning algorithms.Source: §6 · p. 9
  • The released dataset supports future work on deception detection and conversational agents for cooperative-competitive settings.Source: §6 · p. 9

Limitations

The evaluated models’ performance is constrained by the capabilities of their pretrained language models, and the authors expect more data could improve fine-tuning.

  • Model performance depends on pretrained language-model capabilities, and the fine-tuning results may improve with a larger dataset.Source: Limitations · p. 9

Ethics Statement

The appendix defines Avalon’s roles, turn-based communication, online rule modifications, and human role-labeling procedure. It also documents consent, privacy protections, and research-only data use.

Ethics Statement

  • Participants provided consent and privacy notices, and the study used collected data solely for research purposes.Source: Ethics Statement · p. 9

A.1.1 How to Play

  • Avalon pits Good against Evil, with teams pursuing opposing quest outcomes while concealing and inferring hidden identities.Source: §A.1.1 · p. 13

A.1.2 Roles

  • The five roles distribute asymmetric knowledge: Merlin knows the evils, Percival sees Merlin and Morgana ambiguously, Servants lack special knowledge, and Evil roles know each other.Source: §A.1.2 · p. 13

A.1.3 Communication

  • Players communicate through a chat interface during individual turns and may privately label each message with its strategy or motivation.Source: §A.1.3 · p. 13

A.1.4 Communication Labels

  • The interface captures persuasion labels including assertion, questioning, suggestion, agreement, logical deduction, concession, critique, and appeal or defense.Source: §A.1.4 · pp. 13–14

A.1.5 Turns

Round 1

The first round begins with a successful party vote and quest, while players express tentative support for a two-person party despite limited information.

  • The first proposed party included player-2 and player-3, received unanimous approval, and completed the quest successfully.Source: Round 1 · pp. 14–15
  • Players largely supported the initial party while acknowledging that the first round provided little information for role inference.Source: Round 1 · pp. 14–15
  • Player-2 justified proposing themself and player-3 by claiming both were good, while player-3 independently made the same identity claim.Source: Round 1 · pp. 14–15

Quest results after quest 1: Success

After the first successful quest, the survey asks participants to assign role beliefs using only the observed history, while the appendix specifies Merlin prompts and prediction schemas.

Quest results after quest 1: Success

C.1 Identifying Merlin

  • The Merlin-identification materials include a prompt for inferring which player is Merlin from the game evidence.Source: §C.1 · p. 15, Table 4 · p. 15

C.2 Familiarity with Avalon

  • GPT-4, GPT-3.5, and Llama-2-13B were all judged familiar with Avalon in the provided sample-answer assessment.Source: §C.2 · p. 15, Table 5 · p. 15

C.3 TypeScript Schemas

  • The role-prediction schema assigns each of six players one of the labels good, evil, or Merlin.Source: §C.3 · p. 15
  • A separate schema identifies Merlin by selecting one of player_1 through player_6.Source: §C.3 · pp. 15–16

D.1 Werewolf Individual Roles

The Werewolf experiments show strong role-prediction performance overall, but sparse or strategically confusing roles remain difficult; fine-tuned GPT-3.5 performs best for persuasion strategies.

D.1 Werewolf Individual Roles

  • Many key Werewolf roles receive high F1 scores, whereas Mason and Minion perform poorly because they have few test-set representations.Source: §D.1 · p. 16
  • Tanner and Robber are commonly confused with Werewolf because their objectives or late-game behavior can resemble that role.Source: §D.1 · p. 16

D.2 Persuasion Strategy Prediction

  • Fine-tuned GPT-3.5 performs best on persuasion-strategy prediction, outperforming vanilla GPT-4, while fine-tuned Llama-2-13B underperforms.Source: §D.2 · p. 16
Loading 2311.05720v1…