PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Discuss Strategically: A Case Study on One Night Ultimate Werewolf

Xuanfa Jin, Ziyan Wang, Yali Du, Meng Fang, Haifeng Zhang, Jun Wang

arXiv:2405.19946v2cs.AI

TL;DR

ONUW’s role changes and strategic discussion create uncertainty, while prior LLM agents have largely neglected control over discussion tactics. The paper analyzes PBEs and introduces an RL-instructed LLM-agent framework that selects discussion tactics. Its experiments report improved performance and closer approximation to PBEs, with manual tactic discretization as a stated limitation.

  • Problem

    ONUW role changes make final roles uncertain, and recent LLM agents for communication games have largely neglected control over discussion strategies.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes ONUW equilibria and develops an LLM-agent framework combining belief modeling with an RL-trained policy for selecting discussion tactics.

    Source: §1 · p. 2

  • Results

    Experiments in three- and five-player ONUW settings indicate that the discussion policy improves agent performance and brings agents closer to PBEs; the RL-trained policy outperforms direct prompting.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The equilibrium analyses show that discussion can change players’ utilities by influencing beliefs, highlighting the role of discussion tactics in ONUW.

    Source: §1 · p. 2, §7 · p. 10

    Discussion tactics are manually discretized, and this approach relies heavily on characteristics of the specific communication game.

    Source: §7 · p. 10

Abstract

from arXiv · show

Communication is a fundamental aspect of human society, facilitating the exchange of information and beliefs among people. Despite the advancements in large language models (LLMs), recent agents built with these often neglect the control over discussion tactics, which are essential in communication scenarios and games. As a variant of the famous communication game Werewolf, One Night Ultimate Werewolf (ONUW) requires players to develop strategic discussion policies due to the potential role changes that increase the uncertainty and complexity of the game. In this work, we first present the existence of the Perfect Bayesian Equilibria (PBEs) in two scenarios of the ONUW game: one with discussion and one without. The results showcase that the discussion greatly changes players' utilities by affecting their beliefs, emphasizing the significance of discussion tactics. Based on the insights obtained from the analyses, we propose an RL-instructed language agent framework, where a discussion policy trained by reinforcement learning (RL) is employed to determine appropriate discussion tactics to adopt. Our experimental results on several ONUW game settings demonstrate the effectiveness and generalizability of our proposed framework. The project page of our paper: $\href{https://one-night-ultimate-werewolf.github.io}{one-night-ultimate-werewolf.github.io}$.

1 Introduction

ONUW’s role changes make it difficult to infer players’ final roles from their statements, while earlier LLM agents for communication games largely neglected control over discussion strategies. The paper analyzes discussion equilibria and proposes an RL-instructed agent framework, reporting improved performance and closer approximation to PBEs.

1 Introduction

  • Role switches can make earlier information unreliable, so players must infer final roles from statements and strategically reveal information or conceal identities.For example, a Robber acting after the Seer can switch the role of the player the Seer observed.Source: §1 · pp. 1–2
  • Recent LLM agents for communication games emphasized reasoning and generalization but largely neglected control over discussion strategies.Source: §1 · p. 2
  • The paper analyzes three-player ONUW equilibria with and without discussion, then proposes an LLM-agent framework whose RL-trained policy selects discussion tactics from observations.Its contributions also include an ONUW environment and a dataset of players using different tactics.Source: §1 · p. 2
  • Experiments in three- and five-player ONUW settings indicate that the discussion policy improves agent performance and brings behavior closer to PBEs.The RL-trained policy also performs better than a policy selected by direct prompting.Source: §1 · p. 2

2 Related Work

Prior work on Mafia and Werewolf games includes theoretical strategy analysis and game-playing agents, but some analyses rely on strong assumptions or restricted scenarios. The paper distinguishes its focus on RL-trained control of strategic discussion from work centered on other agent capabilities.

2 Related Work

  • Some theoretical Mafia analyses assume random lynchings or meaningless debate and restrict scenarios, whereas this paper analyzes specific cases while adhering to game rules.Source: §2 · p. 2
  • Prior Werewolf agents use rule-based systems, templates, or language models trained on logs; ONUW work has also used statements from a fixed set.Source: §2 · p. 2
  • Earlier LLM Werewolf work used action selection or RL for reasoning, while this paper integrates an RL-trained policy for strategic discussion such as honesty or deception.Source: §2 · pp. 2–3
  • Agents for other communication games often lack control over discussion tactics and are described as inadequate for ONUW’s complex language.Source: §2 · p. 3

3 One Night Ultimate Werewolf Benchmark

ONUW proceeds through night actions, open discussion, and voting, with role switches and deception creating uncertainty. The paper models this setting as a multi-phase Bayesian game in which players form beliefs from observations and choose phase-specific actions.

3 One Night Ultimate Werewolf Benchmark

  • ONUW randomly deals roles, then proceeds through Night abilities, Day discussion, and Voting, with the voting result determining the winner.Role switches and potential deception create uncertainty and confusion.Source: §3 · p. 3

3.1 Problem Formulation

  • The multi-phase extensive-form Bayesian-game formulation represents ordered decisions, phase-specific action spaces, private information, and hidden roles.Information states group game states that a player cannot distinguish, while the model assumes perfect recall.Source: §3.1 · pp. 3–4
  • Players form beliefs over all players’ types from observations and update beliefs using Bayes’ rule as new information arrives.The initial belief is described as uniform in the supplied formulation passages.Source: §3.1 · p. 4
  • A behavioral strategy assigns probabilities to available actions given a player’s phase and information state, and the player’s strategy combines belief modeling with action selection.Source: §3.1 · p. 4

4 Analyses on Three-Player ONUW

The paper analyzes a three-player game with two Werewolves and one Robber, using PBEs to compare play without discussion and play where discussion affects Werewolf beliefs. The equilibria show that discussion can change strategies and utilities by changing those beliefs.

4 Analyses on Three-Player ONUW

  • The analysis considers PBEs for a three-player ONUW game with two Werewolves and one Robber, and compares cases with and without Day discussion.Source: §4 · p. 4

4.1 Notation

  • A PBE pairs strategies with beliefs that are consistent on reached paths and makes each player’s strategy optimal given beliefs and others’ subsequent strategies.The game-tree caption identifies potential Robber speeches and information sets for the discussion case.Source: §4.1 · pp. 4–5, Figure 2 · p. 5

4.2 Game without Discussion

  • Without discussion, the Robber switches with either Werewolf with probability 1/2 and votes for that player, while the Werewolves vote for each other.In these equilibria, the Robber always wins and each Werewolf wins with probability 1/2, depending on whether the Robber switched that player.Source: §4.2 · p. 5

4.3 Game with Discussion

  • With discussion, Werewolves’ beliefs about the Robber’s night action determine equilibrium voting probabilities, subject to constraints that keep those probabilities valid.The Robber’s equilibrium utility depends on the Werewolves’ belief that it did not switch; convincing them that this probability is 1/2 yields expected utility 1.Source: §4.3 · p. 6

5 Learning to Discuss Strategically

The paper represents discussion tactics as choices conditioned on players’ information and beliefs, then learns a policy to select them with reinforcement learning. The trained policy guides an LLM-based agent’s discussion and decisions across game phases.

5 Learning to Discuss Strategically

  • Discussion tactics are a latent choice z that conditions a player’s belief-based behavioral strategy, with a policy selecting tactics from the player’s information and beliefs.This makes discussion preference explicit in the strategy.Source: §5 · p. 6

5.1 Learning Discussion Policy by RL

  • The learned policy aims to maximize expected player payoff, with reward assigned at game end from the ground-truth role assignment and zero reward at other steps.The paper proposes a general policy across players, assuming no extraneous information such as personality or body language interferes with gameplay.Source: §5.1 · pp. 6–7
  • The authors divide discussion into evidence, accusation, and defense, each honest or deceptive, yielding six tactics for learning and analysis.“Honest” means consistent with the speaker’s known information or beliefs; “deceptive” means the opposite.Source: §5.1 · p. 7
  • The offline RL policy uses state embeddings of discussion history and derived role beliefs, trained with Conservative Q-Learning on trajectories from LLM-generated game logs.The authors cite scarce human-game datasets as the reason for using LLM-generated logs.Source: §5.1 · p. 7

5.2 RL-instructed LLM-based Agent Framework

  • The agent combines belief modeling, policy-selected discussion tactics, and decision making; daytime speech follows the chosen tactic, while night and voting use different component combinations.The prompts provide game rules, role information, observations, and beliefs; decision-making prompts also include the chosen tactic.Source: §5.2 · pp. 7–8, Figure 3 · p. 8

6 Experiments

The experiments assess equilibrium approximation in a three-player game, then test policy effectiveness and generalizability in five-player settings. Results favor the proposed agent in the reported win-rate comparisons, with a smaller advantage for Team Werewolf and weaker advantages in the hard setting.

6 Experiments

  • The experiments extend from equilibrium approximation in the three-player game to five-player tests of policy effectiveness and generalizability across roles.For effectiveness, initial role assignments and night actions are predefined, with easy and hard settings.Source: §6 · p. 8, §6.3 · p. 9

6.2 Experiment on Three-Player ONUW

  • The three-player experiment evaluates agents’ NashConv as a measure of how much utility they could gain by deviating to a best response, or distance from equilibrium.The supplied passages describe the evaluation measure but do not report its comparative outcome.Source: Figure 4 · p. 8, §6.2 · p. 9

6.1 Setup

  • The setup compares ReAct with belief-only, random-tactic, LLM-instructed, and RL-instructed agents, using GPT-4-generated training logs and 30 evaluation runs.Experiments use GPT-4 and Gemini; CQL trains the discussion policy.Source: §6.1 · pp. 8–9, §6 · p. 8

6.3 Effectiveness of the Discussion Policy

  • In both easy and hard five-player settings, Team Village’s agent has the highest win rates against matching versions, while its improvement is greater for Village than Werewolf.The authors attribute the smaller Werewolf improvement to game mechanics and note that the hard setting weakens the agent’s advantage.Source: Figure 5 · p. 9, §6.3 · pp. 9–10

6.4 Generalizability of the Discussion Policy

  • The proposed agent outperforms the other versions against both Gemini-based and GPT-4-based agents in five-player evaluations, and ties GPT-4 in multiple rounds.The evaluation uses win rates and average votes for an agent playing as Player 3.Source: Table 1 · p. 10, §6.4 · p. 10

7 Conclusion and Future Work

The conclusion presents an RL-instructed LLM agent and reports effectiveness and generalizability across several ONUW settings, while identifying manual tactic discretization as a major limitation. The appendices describe the game tree, related LLM-agent work, and ONUW rules and phases.

7 Conclusion and Future Work

  • The RL-instructed LLM-based agent is reported effective and generalizable across several ONUW settings.The authors identify automatic extraction of discussion tactics and sensitivity to tactic combinations as future work.Source: §7 · p. 10
  • Manual discretization of discussion tactics relies heavily on characteristics specific to communication games.The authors propose investigating unsupervised extraction from game logs and sensitivity to different tactic combinations.Source: §7 · p. 10

A Game Tree of the Game without Discussion

  • Figure 6 depicts the game tree without discussion, with dashed lines marking information sets and leaf utilities ordered by player.P1, P2, and P3 denote the players.Source: Figure 6 · p. 16

B Additional Related Work

  • The additional related-work section surveys LLM agents across several task areas and describes ReAct, Chain-of-Thought, and Tree-of-Thought approaches.ReAct interleaves reasoning traces and actions; CoT prompts step-by-step thought, while ToT searches a tree of thoughts.Source: B Additional Related Work · p. 16

C Detailed Introduction to the One Night Ultimate Werewolf Game

  • ONUW centers on role switches and potential deception that create uncertainty, with one night of abilities followed by daytime discussion and voting.The game has Night, Day, and Voting phases.Source: C Detailed Introduction to the One… · p. 16

C.1 Game Setup

  • The described implementation focuses on a five-player setup with eight roles, including two Werewolves, a Seer, a Robber, a Troublemaker, and an Insomniac.Three extra roles are dealt to the role pool in the general setup.Source: §C.1 · p. 16

C.2 Role Descriptions

  • The role descriptions specify distinct night actions: Seers inspect roles, Robbers may switch and view a role, and Troublemakers swap two players without looking.Werewolves seek each other; Insomniacs check whether their role changed at night’s end, while Villagers have no night ability.Source: §C.2 · p. 17

C.3 Game Play and Winning Conditions

  • During the Day, players discuss suspected Werewolves, but role changes can leave them mistaken about their roles; players then vote simultaneously.The player with the most votes dies and reveals their role, with stated tie and no-majority rules; the game ends after one cycle.Source: §C.3 · p. 17

D Proofs for Perfect Bayesian Equilibria

The appendix sets notation for proving Perfect Bayesian Equilibria in ONUW. It defines players’ action strategies and beliefs, then outlines a Nash-equilibrium-first verification approach under an assumption of homogeneous Werewolves.

D.1 Notation

  • Player 3’s Robber night actions are no switch or switching with either Werewolf, while voting action sets differ by player.Player 3 has three voting strategies corresponding to its night action; Players 1 and 2 have voting strategies only.Source: §D.1 · pp. 17–18
  • The notation distinguishes voting-phase beliefs for Players 1 and 2 from Player 3’s beliefs across information sets, and defines win, loss, and draw utilities as 1, −1, and 0.Belief probabilities follow the left-to-right order of decision nodes in the corresponding game trees.Source: §D.1 · p. 18
  • The proof strategy first finds Nash equilibria, since every PBE must be a Nash equilibrium, and then checks Bayesian consistency and sequential rationality.The analysis adopts Equation (8) as part of the Nash-equilibrium conditions and assumes the original Werewolves are homogeneous in roles and belief models.Source: §D.1 · p. 18

D.2 Proof for Theorem 4.1

The proof establishes PBEs for the specified three-player game without discussion and finds infinitely many equilibria. It checks strategic best responses and reports indifference over some of the Robber’s actions.

D.2 Proof for Theorem 4.1

  • Theorem D.2 states that PBEs exist for the game with two Werewolves and one Robber when discussion is not allowed.Source: §D.2 · p. 18
  • There are infinitely many equilibria in this case, with the parameter p permitted to range from 0 to 1.The passage introduces the expected utilities of all players but does not provide their values in the supplied text.Source: §D.2 · p. 18
  • Player 3 can use any mixed behavioral strategy at the specified voting information set, because its expected utilities for voting Player 1 or Player 2 are equal.The cited passage says p may take any value between 0 and 1.Source: §D.2 · p. 19
  • At night, the Robber’s expected utility is 1 for no switch and for switching with either Werewolf, so each action is a best response.Source: §D.2 · p. 19
  • The proof derives voting best responses for Players 1 and 2, then verifies that the resulting strategy-and-belief profile forms a PBE.The voting best-response passages report Player 2 voting for Player 1 and Player 1 voting for Player 2.Source: §D.2 · p. 19

D.3 Proof for Theorem 4.2

The proof analyzes voting-phase PBEs when Werewolves form beliefs about the Robber’s night action. It identifies cases where earlier equilibria persist, where a belief configuration is infeasible, and where constrained probabilities yield a PBE.

D.3 Proof for Theorem 4.2

  • When α is nonzero and Werewolves’ voting probabilities are equal, the proof gives q = (β + γ − α)/2α and p = (α^2 + β^2 − γ^2)/2α^2, subject to belief constraints.The constraints are required to keep p and q valid probabilities and ensure equilibrium existence.Source: §D.3 · p. 20
  • For case (a), PBEs in Theorem 4.1 also hold under the same situation; the text further says both q1 and q2 cannot stay non-negative while β ≠ γ, because β = γ is invalid.Source: §D.3 · p. 21
  • For the analyzed belief configuration, the proof verifies that Player 1’s strategy is a best response given belief (α, β, γ) and the other players’ best responses.Source: §D.3 · p. 21
  • The proof concludes that the derived strategies and beliefs form PBEs during the Voting phase, with p* and q* following Equation (40).The conclusion applies under the constraints on (α, β, γ) specified in Equation (41).Source: §D.3 · p. 22

E.1 Data Collection and Statistics

GPT-4-generated game logs provide data for discussion-tactic analysis and show role-linked preferences in tactic selection.

E.1 Data Collection and Statistics

  • 120 game logs across 40 five-player role settings, repeated three times each, provide data for tactic analysis.Each log contains 15 discussion turns, yielding 1,800 transitions for training.Source: §E.1 · p. 22
  • GPT-4 mostly chooses deception as Werewolf and honesty as Village; Robber and Insomniac are more deceptive than other Village roles.Table 2 reports statistics for Evidence, Accusation, and Defense tactics.Source: §E.1 · p. 22, Table 2 · p. 22
  • GPT-4 rarely defends itself; the authors speculate that accusations can transfer contradictions more effectively.Source: §E.1 · p. 22

E.2 Offline RL Training and Hyperparameters

The paper converts game histories and beliefs into offline RL training data, evaluates two human-rated settings, and reports training and gameplay costs.

E.2 Offline RL Training and Hyperparameters

  • Each decision-step observation combines visible game history with derived belief, while the selected discussion tactic is the action.Observations are embedded with frozen text-embedding-ada-002; outcomes assign rewards of 1 for wins, -1 for losses, and 0 for draws.Source: §E.2 · p. 22
  • CQL trains the discussion policy on the offline dataset, with its hyperparameters listed in Table 3.Source: §E.2 · p. 22, Table 3 · p. 23

E.3 Game Settings in Section 6.3

  • The easy and hard five-player settings are selected by human-rated difficulty, with predefined night actions ensuring teammates use the same agent version.In the hard setting, a Robber becomes the new Werewolf, increasing reasoning difficulty relative to the easy setting.Source: §E.3 · p. 23, Table 4 · p. 23, Table 5 · p. 23

E.4 Computational Consumption

  • Discussion-policy training takes about 2.5 hours on an NVIDIA GeForce RTX 3060 Ti; one five-player GPT-4 game costs about 70,000–80,000 tokens.The stated token cost is approximately $0.8–$1.2 using GPT-4.Source: §E.4 · p. 23

F Human Analysis

This section examines human-facing analyses of agent discussion behavior, including contrasts in tactical disclosure, bluffing, and confrontation, with supporting game logs and prompts. It also describes how prompts guide misleading or honest statements and notes risks of deceptive communication alongside safeguards against misuse.

F.1 Bluffing

  • As the new Werewolf, the RL-instructed agent bluffed by claiming to be the Seer and saying Player 2 was not a Werewolf, while the Belief agent was more likely to state its real night action.The analysis characterizes bluffing as a risky strategy that can cost credibility if caught, and says the claim helped the agent resist questioning.Source: §F.1 · p. 24

F.2 Concealment

  • The RL-instructed agent concealed its role by accusing Player 2 and keeping its options open, whereas the Belief agent disclosed its original role and made a suspicious claim of remaining on Team Village.The analysis describes strategic ambiguity as better aligned with game mechanics and useful to avoid becoming a target of suspicion.Source: §F.2 · pp. 24–25

F.3 Confrontation

  • After accusation, the RL-instructed agent claimed to be the Seer and counter-accused Player 3, while the Belief agent expressed uncertainty and avoided specific claims.The analysis says the first approach seized narrative control but risked being caught; the second avoided falsifiable claims but could seem evasive or suspicious.Source: §F.3 · pp. 25–26

G Game Log Examples

  • In the example game log, Players 1 and 5 were voted out, Player 1 was the Werewolf, and Team Village won.The log records the players’ evolving role claims and votes before this outcome.Source: G Game Log Examples · p. 27

H Prompt Design in the LLM-based Agent

  • The prompt design asks the agent to reason from conversation history and role beliefs, follow a selected speaking tactic, and make concise public speeches that induce players to reveal their night actions.Prompts also caution against repeating others and against revealing thoughts when the agent believes it may be a Werewolf.Source: H Prompt Design in the LLM-based Agent · pp. 29–30
  • The prompt instructs agents to make misleading accusations and to defend themselves or others either honestly or deceptively.Honest defenses must be consistent with known information or beliefs, while deceptive accusations and defenses must be misleading and inconsistent with them.Source: H Prompt Design in the LLM-based Agent · p. 31

I Broader Impact Statement

  • The authors flag potential misuse for deceptive human–AI communication while describing safeguards and possible detection of deceptive content.The agent is designed for a text-based ONUW game, and its prompt limits deceptive behavior to gameplay; the authors say detecting deception could help improve win rates and urge users to avoid malicious exploitation. They also suggest RL policy stability could help mitigate LLM hallucination.Source: I Broader Impact Statement · p. 31

Related papers

Loading 2405.19946v2…