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

Abstract: 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/

## introduction despite the remarkable progress of large language models (llms) in natural language understanding and generation, they have largely been applied and evaluated in question-answering @xcite , instruction following @xcite , and cooperative dialogue @xcite tasks. an oft-overlooked, yet important setting is that of multi-party dialogue in cooperativecompetitive scenarios, where participants hold prithese representations are provided to the language model (llm) either by using data from a single round complemented with a carried-over belief (round-based context) from the preceding round or by using the entire history since the game's beginning (full context). subsequent role predictions made by the llm are validated for consistency with the predefined avalon roles. in this work, we aim to explore these limitations by introducing a new benchmark and associated dataset for a multi-party cooperative-competitive task based on the game of avalon: the resistance 1 . our task features two teams of players with hidden roles and conflicting goals; one side seeks to fulfill a series of objectives and the other sabotage them. through rounds of dialogue and voting, the players must discover each other's identity while concealing their own to win. we model the identification of player roles as a long-horizon dialogue understanding task, and show that it poses a challenge for recent state-of-the-art llms due to three factors: 1) a large number of participants in a multi-party dialogue, 2) the need to ground reasoning in both dialogue and game state, and 3) the active usage of deception and persuasion by players. while prior works have explored dialogue understanding in multi-party settings, they typically involve a small number of participants @xcite or unnatural dialogue captured from online forums @xcite . our task, in contrast, involves natural dialogues with six participants, each of whom have their own privileged information and agendas. this significantly increases the complexity of the task, as participants may address each other over longer horizons. compounding the issue is the need to incorporate game state into the reasoning process, further increasing the horizon if translated to natural language as is common in zero-shot paradigms. however, the ability to reason over extended horizons is crucial in our context, as inconsistencies in behavior, evasive responses, and self-contradictions which can be used to identify deceptive behavior may only manifest over time. we explore a selection of recent, publicly available llms, varying in size and training data, to evaluate their effectiveness in understanding long-horizon relations in our proposed benchmark. under the assumption that llms encode large amounts of general knowledge, we aim to ascertain whether specific state representations can facilitate the comprehension of long-horizon tasks. we find this to be a critical aspect given the small context windows associated with many state-of-the-art llms, despite recent improvements @xcite @xcite . in addition, we publicly release our datasetas well as our browser-based version of avalonin order to promote further research in this direction. consisting of 20 games with 30 unique human players and 19 unique team compositions, our dataset comprises 2384 pieces of dialog with handannotated persuasion strategies for each player, deception strategies for evil players, player beliefs over the roles of other players throughout the game, and ground truth game state. to the best of our knowledge, this is the only high-quality dataset of its kind for a long-horizon multi-party dialogue featuring deception and persuasion. in keeping with recent trends advocating for quality over quan-tity @xcite @xcite , we expect this dataset to be useful for both fine-tuning and evaluation of models. during data collection, we have ensured that no spurious information channel exists between the players, ensuring that all conversation relevant to the game is captured by our dataset. concretely, our contributions are as follows: while games have long served as challenges in the ai community, they often lack such dialog understanding due to the difficulty in generating and evaluating realistic dialog in commonly employed reinforcement learning paradigms @xcite . as a result, cooperative games with human partners often utilize simple, codified communication protocols such as in the game of @xcite or ignored entirely @xcite . when dialogue is incorporated @xcite , it is often through dialogue state tracking (dst) @xcite in which participant beliefs @xcite and intentions are modeled as semantic slots @xcite , and are inferred throughout the course of a conversation. however, cooperative-competitive games involving negotiation, persuasion, or deception often require a more nuanced application of language that leaves room for subjectivity and interpretation. past work on strategic dialogue systems has avoided these issues by focusing on simpler settings @xcite @xcite , which involve only a single partner, shorter dialogue contexts, or simpler strategies. recent advances in llms have shown great potential @xcite across varying problems, including conversing (openai), knowledge parsing @xcite , and instruction following @xcite @xcite , leading to the development of capable languagebased agents @xcite @xcite . as shown in @xcite , the inherent knowledge embedded in these models' weights allows for intricate answers, if the prompt is posed correctly. such agents have recently been successfully applied to the game of @xcite , although a significant source of relevant domain data was required for fine-tuning. this differs from the game of avalon, in which a) all communication is public and b) hidden roles explicitly encourage deception, which leads to a more challenging dialogue understanding problem as an agent must carefully understand, analyze, and ground each player's utterance. deception and persuasion in dialogue: while deception is increasingly studied in terms of misinformation on social media @xcite , in this work we focus on its analysis and detection in dialogue. unlike prior works which explore deception through analysis of verbal @xcite or visual @xcite cues in spoken language from two-party dialogues, our benchmark is based on textual linguistic cues in multi-party dialogues. although datasets have previously been introduced for the games of mafia @xcite and one night werewolf @xcite , we find avalon to be a significantly more challenging task due to the increased game length, resulting in more than double the number of utterances per game in our dataset -49, 64, and 119 for mafia, werewolf, and avalon, respectively. this requires dialogue models to reason over significantly longer context horizons, but also provides enough information for us to reason over hidden player roles as opposed to simply inferring utterance labels. in addition, we provide high-quality annotated persuasion strategy labels for each utterance in our dataset, following annotation schemes introduced in prior works @xcite , as well as deception labels, covering the type of lies utilized by the evil players @xcite . though persuasion has often been studied in the context of negotiation @xcite or other two-party dialogues @xcite , multi-party persuasion analysis is often limited to online social media discussions @xcite which often meaningfully differ from real-time dialogue. ## the game of avalon in this section, we provide a description of the game avalon: the resistance foot_1 , which is a social deduction board game that can be played by five to ten players. players assume various roles in the game that differ in knowledge and goals, including the assassin, merlin, morgana, and percival. avalon is a cooperative-competitive game in which two groups of players attempt to infer the roles of the other players by forming allegiances while hiding or intentionally pretending to be a role different from their own. in this work, avalon is played among six human players @xmath0, . . . , p 6 } -four good, two evil. generally, the goal of the evil players is to hide their identity and to convince the good players that they can be trusted. the game progresses through up to five rounds -referred to as quests -with players engaging in discussions and voting to determine the composition of a party that is subsequently sent on a quest. the required size of a party that is sent on a quest differs in each round and has to be approved by a public majority vote amongst all players. after a party has been formed, each player in that party votes anonymously whether or not the quest should succeed, requiring all players to vote for success in order to succeed the quest. if the evil players succeed in failing three quests, they automatically win the game. similarly, if the good players succeed three quests, they win the game, unless the assassin can identify who plays merlin (see section a.1). if the assassin is successful, evil wins the game instead. avalon: the resistance introduces multiple special roles that impact gameplay, adding layers of strategic depth to the game's dynamics. in our setting, the roles consist of merlin, percival, and two loyal servants as the forces of good, with morgana and the assassin on the side of evil. detailed role descriptions can be found in section a.1 we don't have any info so just selected randomly game started player-4 proposed a party: player-2, player-6 p4 sorry for the last turn, its still random but just included myself p4 system player-4 proposed a party: player-2, player-4 system party vote outcome: player-1: yes, player-2: yes, player-3: no, player-4: yes, player-5: yes, player-6: yes system vote succeeded! initiating quest vote! system quest succeeded! system system seems like a weird choice of party in my opinion. little bit suspicious of player-4 for not picking themself. p5 i don't have opinions at this point p6 well, technically we don't know anything yet. but i agree that this choice is a little weird p1 i'm good, but i agree this choice is weird. however, i don't know what changes we can make since this is the first turn. i'll approve the current party unless you make some good arguments p2 no opinions but a good guy will always place themselves in the team... the online nature of our data collection. particularly, we enforce a turn-based discussion in which each player has a fixed amount of time to convey their thoughts via a chat interface, thus ensuring that all game-related interactions are captured. should a player exceed their allotted time, the game will automatically progress to the next player, initiate appropriate votes, or apply default votes depending on the situation. more details can be found in section a.2 ## dialogue understanding we formulate our problem as identifying a player's character c i given the chat history h chat and game state h state . formally, predict the role p role (c i |h chat , h state ) for each player in p. additionally, we also predict which of the six players is merlin: in the remainder of this section, we address the two fundamental issues of 1) understanding longhorizon conversations, and 2) utilizing the environment's state to enhance the inference capabilities of the llm. ## experiments the following sections detail our data collection process and provide comparisons between three current state-of-the-art llms, including fine-tuned versions of these models, in utilizing different modalities and context representations. ## conclusion in this work, we present a novel benchmark, associated dataset, and testbed for long-horizon dialogue understanding in scenarios of conflicting interests among multiple participants. this task combines utterances from six human players at a time, handlabeled persuasion and deception strategies, player beliefs, and comprehensive game states recorded over more than 24 hours of gameplay. we demonstrate that current state-of-the-art llms do not reach human-level performance in environments that require the understanding and tracking of longhorizon dialogue between multiple participants in challenging social cooperative-competitive settings. compared to similar datasets, our benchmark contains longer context horizons, stricter game rules, and high-quality dialogue, making it well-suited for nlu research as all game-relevant communication has been captured and is thus, available to learning algorithms. this dataset opens doors for diverse research avenues, from detecting deception to developing conversational agents for cooperativecompetitive settings. we hope that our high-quality dataset will be valuable to further tune and evaluate the capabilities of large language models in challenging social settings.