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

Authors: xuanfa  jin
ziyan  wang
yali  du
meng  fang
haifeng  zhang
jun  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:26:31

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

Main paper: 
 introduction: 
 Many games such as StarCraft [1, 2] , Diplomacy [3, 4] can approximate various fundamental issues in real life, and studying these games contributes to a better understanding of the functioning of our society [5] . Designing artificial intelligence (AI) agents that can play these games well has attracted a lot of attention [6, 2, 3] . Fortunately, recent large language models (LLMs) have demonstrated significant potential in constructing intelligent agents in numerous tasks [7] [8] [9] [10] due to their impressive reasoning and emergent generalization abilities [11] [12] [13] . Moreover, LLM-based agents have achieved approaching or even surpassing human performance in games like Chess [14] , Minecraft [15] [16] [17] , Avalon [18] [19] [20] and Werewolf [21] [22] [23] , etc.In the game Werewolf [24] , the hidden roles and uncertain discussions greatly influence the gameplay, making it challenging for players. Compared to it, the One Night Ultimate Werewolf (ONUW) game adds roles that can change the roles of players, and all players only have one nighttime to take action and one daytime to discuss and vote. Therefore, the key challenge of the ONUW game is to deduce and distinguish the final roles of all players from their statements. Meanwhile, due to the sequential execution of actions at night, the information obtained by the former player might be not reliable, leading to the rise of reasoning difficulty and uncertainty. For example, Seer and Robber are two roles in the ONUW game with special abilities, and the Seer saw a player was a Werewolf at night. However, if the Robber switched that player's role later on, the information obtained by Seer becomes invalid. So players need to discuss strategically, leveraging others' statements and their own prior knowledge to guide other players to reveal their information, or conceal their identities by misleading or deceiving, particularly for Werewolves. Recent works [21, 22, 19] have attempted to construct LLM-based agents that can play communication games, but they mainly focus on how to fully utilize reasoning and generalization abilities of LLMs, while neglecting the control over strategies.In this work, we focus on enhancing the discussion ability of LLM-based agents by leveraging the ONUW game. We formulate the ONUW game as a Multi-Phase Extensive-Form Bayesian Game and explore various discussion tactics in the game. Through analyzing a three-player ONUW game with two Werewolves and one Robber, we present the existence of the Perfect Bayesian Equilibria (PBEs) [25] in two distinct scenarios: one with discussion and one without. Players' utilities at equilibria when in the scenario with discussion highlight the significance of discussion, as they are only determined by players' beliefs, which are influenced by discussion. Based on the insights obtained from the analyses, we thus propose an RL-instructed LLM-based agent framework. This framework leverages a policy optimized by reinforcement learning (RL) to determine an appropriate discussion tactic (e.g., "Honest Evidence", "Deceptive Accusation", etc.) based on current observation. To evaluate the effectiveness and generalizability of our framework, we conduct experiments in a three-player and a five-player ONUW game. The results indicate that the integration of our discussion policy can help LLM-based agents approximate PBEs more closely and improve the performance of LLM-based agents. Moreover, we observe the discussion policy trained by RL performs better than that by directly prompting LLM.Our contributions can be summarized as follows: Firstly, we formulate the ONUW game as a Multi-Phase Extensive-Form Bayesian Game and provide theoretical analyses of a three-player ONUW game, demonstrating that players' utilities are only determined by their beliefs, which reveals the pivotal role that discussion plays in the ONUW game. Secondly, we develop an environment of the ONUW game, which is complicated due to the uncertainty caused by role changes. And we additionally contribute a dataset featuring players employing various discussion tactics in the ONUW game. Finally, inspired by the importance of discussion shown in our analyses, we propose an RL-instructed language agent framework, where an instructive discussion policy trained by RL is integrated, and a belief modeling method is employed to deduce the roles of players and generate actions based on its beliefs and discussion tactics. 
related work: 
 This section reviews literature in the following areas: the analyses of Mafia/Werewolf games and the design of AI agents for communication games. Additional related work is covered in Appendix B.Mafia is a multi-player communication game, modeling a conflict between the mafias and civilians. Early research [26] [27] [28] has attempted to identify the optimal strategies for both citizens and mafias theoretically and thereby determine what setups lead to fair games. However, these works are based on strong assumptions such as random lynchings or meaningless debate, and restricted to simple scenarios like without detectives or removing most discussion. Werewolf is a reinvention of the Mafia game by introducing additional roles with special abilities. An ε-Nash equilibrium is found under the limitation of both villager-side and werewolf-side strategies [29] . In contrast, our analyses make few assumptions and strictly adhere to game rules, despite being on specific cases. Some researchers have attempted to develop Werewolf agents that rely on rule-based systems or talking templates [30, 31] , while some rely on language models directly trained with Werewolf logs [32] . As for the One Night Ultimate Werewolf game, Eger and Martens [33] builds AI agents that can choose statements from a fixed set and designs a system that allows human players to play games with their AI agents. You need to provide some misleading evidence or information in your public speech, and your evidence must be inconsistent with the information or beliefs you know.3. (Honest Accusation): You need to accuse someone has a specific role or action honestly in your public speech, and your accusation must be consistent with the information or beliefs you know.4. (Deceptive Accusation): You need to accuse someone has a specific role or action deceptively in your public speech, and your accusation must be misleading and inconsistent with the information or beliefs you know.5. (Honest Defense): You need to defend yourself or someone else against an accusation honestly, and your defense must be consistent with the information or beliefs you know.6. (Deceptive Defense): You need to defend yourself or someone else against an accusation deceptively, and your defense must be misleading and inconsistent with the information or beliefs you know. 
one night ultimate werewolf benchmark: 
 One Night Ultimate Werewolf (ONUW) is a variant of the social game Werewolf [24] . In this game, players only have one night to use their abilities, followed by one day to discuss and win for their respective teams. The main challenges of this game are the role switches and potential deceptions that create uncertainty and confusion for all players. Initially, one role is dealt randomly to each player. There are three phases in the ONUW game: Night (abilities performed in order), Day (open discussion), and Voting (suspicious player voted out). Game rules are detailed in Appendix C.Extensive-Form Game (EFG) [38, 39] is a type of game where players take turns to make decisions in a specific order. However, compared with classic EFG, there are three phases in the ONUW game, and each player possesses diverse action spaces that differ across these phases. Also, the private actions and hidden roles indicate players have incomplete information, which is usually modeled as a Bayesian Game (BG) [40, 41] or Hidden-Role Game (HRG) [42] .In order to formulate this game accurately, we consider a Multi-Phase Extensive-Form Bayesian Game (MP-EFBG), whose representation is based on a game tree. An m-phase n-player MP-EFBG can be formalized as a tuple (N , Ψ, S, {Θ i } i∈N , {H i } i∈N , {I i } i∈N , {A i ψ } i∈N ,ψ∈Ψ , P, Ω, R) , where N = {1, 2, . . . , n} is the set of players, and Ψ = {1, 2, . . . , m} is the set of phases. S denotes the set of states corresponding to nodes in the game tree. For each player i, Θ i is the set of types and Θ = × n i=1 Θ i denotes the set of joint types of all players. To capture the private information, we define H i as the set of information states and I i : S → H i as the information function that determines which states are indistinguishable for player i by mapping them on the same information state. A i ψ (h i ) denotes the set of actions available to player i at information state h i ∈ H i in phase ψ ∈ Ψ. So if two states s 1 , s 2 ∈ S are mapped to the same information state by player i (I i (s 1 ) = I i (s 2 )), player i will have the same action sets at these states. In this paper, we assume that all players have perfect recall, i.e., each player's current information state h i k implies knowledge of the sequence of its previous information states and actions,(h i 0 , a i 0 , h i 1 , a i 1 , . . . , h i k ), that led to current information state. P : S → N is the player function, determining whom to act at the given state, and Ω : S → Ψ is the phase function that decides what phase it is at the given state. Finally, R : Θ × S → R n is the utility function for all players according to their types and the terminal states (i.e., leaf nodes in the game tree).Beliefs. Since each player has incomplete information about other players' types and even its own type (player's role may be changed in the game), player i will form a belief b i : H i → ∆(Θ) on all players' types based on its observation. We define player i's belief on information state h i ∈ H i as:EQUATIONwhere p i (θ) is the prior probability of all players' types from player i's view, and p i (h i |θ) is the probability that player i observes h i given joint types θ. Let ∆h i k = h i k+1 \h i k denote the new information contained in h i k+1 at step k + 1 compared to h i k , then player i's belief can be updated via Bayes' rule:EQUATIONAnd b i 0 (θ|h i 0 ) = b i 0 (θ) is set as a uniform distribution, which is an unbiased estimate if there is no prior information.Behavioral Strategies. Player i's behavioral strategy in phase ψ ∈ Ψ is defined asπ i ψ (h i ) ∈ ∆(A i ψ (h i )), ∀h i ∈ H i ,which is a probability distribution over available actions given a phase and an information state. And π i ψ (a i |h i ) denotes the probability that player i takes action a i in phase ψ given information state h i . Player i's strategy consists of belief modeling and action selection, and is expressed asEQUATIONwhere πi ψ is a belief-conditioned behavioral strategy for player i in phase ψ. Denote π = (π 1 , . . . , π n ) as a collection of strategies of all players, and the expected utility for player i induced by strategy profile π as E π R i . 
voting phase: 
 Players vote for each other (except themselves)(1) At least one Werewolf dies.Even if one or more players who are not Werewolves die in addition to a Werewolf dying.(2) If no one is a Werewolf and no one dies.At least one player is a Werewolf and no Werewolves are voted out.Figure 1 : The game process of the ONUW game. Initially, roles are randomly dealt to players. Then three phases: Night (abilities performed in order), Day (discussion in three rounds), and Voting (suspicious player voted out) proceed sequentially. The winner is decided by the voting result.aiming to improve the System-2 reasoning ability of agents. In contrast, our work directly integrates a discussion policy trained by RL into the thinking and decision-making process of LLM-based agents, focusing on enhancing agents' strategic discussion (e.g., honesty or deception) ability, which is an aspect that was not prominently addressed in previous work.Besides the Werewolf games mentioned above, there are also AI researches conducted on other communication games, such as Diplomacy [3, 4] , Avalon [18] [19] [20] and SpyFall [34, 35] . There has been a long history of studying Diplomacy in the realm of AI [36, 37] , but most of them are rule-based algorithms until recently. Cicero [3] integrates a dialogue module with a planning module trained by RL to infer players' intentions and generate dialogue in pursuit of its plans, finally achieving humanlevel performance in Diplomacy. DeepRole [18] combines counterfactual regret minimization (CFR) with value networks trained through self-play, while introducing deductive reasoning techniques aimed at deducing actions within partially observable scenarios. Kim and Kim [34] demonstrates the LLMs' potential in playing a famous mafia-style game, SpyFall, by using prompt engineering techniques. Compared to our work, most designs of these agents are inadequate for handling the complex languages in the ONUW game and lack control over discussion tactics.In this section, we consider a simple but interesting version of the ONUW game: with two Werewolves and one Robber. We present certain Perfect Bayesian Equilibria [25] in this version of the game under two different assumptions, which demonstrate the crucial role that discussion during the Day phase plays in the ONUW game.Since the ONUW game is an extensive-form game with incomplete information, an appropriate solution concept is Perfect Bayesian Equilibrium (PBE) (π, b): a strategy profile π and a belief system b satisfying Belief Consistency and Sequential Rationality. Belief Consistency includes bothRobber No switch Switch P1 Switch P2 Player2 Player3 P2 P3 P1 P3 P1 P3 P1 P2 P1 P2 P1 P2 P1 P2 P2 P3Day phase on and off-equilibrium paths. Specifically, beliefs on every path reached in equilibrium with a positive probability (on-equilibrium path) should be updated according to Equation (2); on paths of zero probability (off-equilibrium path), the beliefs can be updated arbitrarily. For any player i at given information state h i k , Sequential Rationality imposes the condition for strategy π i :-1 -1 1 -1 -1 1 0 0 0 -1 -1 1 -1 -1 1 0 0 0 1 1 -1 1 1 -1 -1 1 -1 1 -1 1 0 0 0 1 -1 1 -1 1 -1 0 0 0 -1 1 -1 -1 1 -1 Role Assignment: P1, P2 are Werewolves; P3 is Robber -1 1 1 1 -1 -1 0 0 0 1 -1 -1 -1 1 1 0 0 0 1 -1 -1 1 -1 -1 Voting phase [ ] [ ] [ ] P1 P3 P1 P3 P2 P1 P2 P1 P2 P1 P2 P1 P1 P3 P1 P3 P2 P1 P2 P1 P2 P1 P2 P1 P2 P3 Player1 Player3π i ∈ arg max π i′ E π i′ π -i R i |h ik , b , which means given belief system and other players' subsequent strategies, player i's strategy must be optimal.Without loss of generality, we initially assign Player 1 and Player 2 as Werewolves, and Player 3 as Robber. There is only one Robber in the game which is known to all players. Denote Player 3's night behavioral strategy as Robber by π 3 R , and its voting strategies based on its night action as π 3 NS (No switch), π Belief probability orders match decision node orders in the game trees (e.g., Figure 2 ) from left to right. After the game, player i's utility is R i = 1 for winning, R i = -1 for losing, R i = 0 for drawing based on its final role.First, we consider a scenario that discussion is not allowed in the Day phase, and players vote directly based on the private information they captured during the Night phase. Figure 6 shows the game tree in this case. At the beginning of the night, the Werewolves would recognize each other and thereby know the player left must be the Robber. However, based on the game rules, Robber always takes action after the Werewolves, which forms a threat to prevent them from directly voting for the Robber. Also, the Robber has no prior knowledge of two Werewolves, thus tends to switch with any of them with equal probability. The game's solution is PBEs expressed in the theorem below. Theorem 4.1. For the ONUW game with two Werewolves and one Robber, in the case where discussion is not allowed, there exist PBEs (π * , b * ): the Robber switches with any Werewolves with a probability of 1/2 and votes for the player it switches with; the two Werewolves directly vote for each other. Each player's belief in b * is consistent with other players' strategies. And the expected utilities of all players in the equilibria are:EQUATIONThe formal description and proof of Theorem 4.1 can be seen in Appendix D.2. This theorem demonstrates that in PBEs of this case, the original Robber (i.e., Player 3) always wins by randomly switching roles with the two other players to ensure its own safety and sow threats. Meanwhile, the probability of Player 1 and Player 2 winning is 1/2 each, depending on whether they are switched by Player 3. This is because Player 3 knows all players' final roles due to its unique ability to switch.Now we consider a scenario where discussion is allowed in the Day phase. If all players ignore the discussion, the PBEs in Theorem 4.1 will still hold. But a more common situation is that the beliefs held by two original Werewolves about original Robber's night action would be influenced by Robber's speech, which would affect their voting strategies and result in different equilibria.Based on Assumption D.1, we assume both original Werewolves would form beliefs about original Robber's night action (No switch, Switch P1, Switch P2) with probabilities of (α, β, γ) after discussion, where α + β + γ = 1. Figure 2 shows the game tree in this case. Then PBEs during the Voting phase can be derived based on the beliefs above. Theorem 4.2. For the ONUW game with two Werewolves and one Robber, in the case that both Werewolves form beliefs about the Robber's night action with probabilities of (α, β, γ) (α ̸ = 0), there exist PBEs (π * , b * ) during the Voting phase: the Werewolves vote for Player 3 with a probability of q and each other with 1 -q, where q = (β + γ -α)/2α; the Robber votes for Player 1 with a probability of p and Player 2 with 1 -p, where p = (α 2 + β 2 -γ 2 )/2α 2 . Each player's belief in b * is consistent with other players' strategies. To ensure p and q are probabilities and the existence of the equilibria, there are constraints on the belief distribution (omitted for brevity). And under the constraints, the expected utilities of all players in these equilibria are:EQUATIONwhere δ = 1/(4α 2 ) -1/(2α) -1.The formal description and proof of Theorem 4.2 can be seen in Appendix D.3. Interestingly, Player 3's utility is only determined by the probability of the Werewolves believing it did not switch with anyone. Therefore, if Player 3 wants to maximize its utility through discussion while maintaining the equilibria, it has to convince the Werewolves that it did not switch with a probability of 1/2, no matter what action it took. In this way, Player 3's expected utility achieves the maximum 1. 
learning to discuss strategically: 
 In Section 4, we demonstrate that it is essential for players to affect other players' beliefs through discussion. As a result, we capture knowledge about how to discuss in a latent variable Z (called discussion tactic), on which we condition the behavioral strategy with belief as πi ψ (a|h, θ, z), to explicitly adjust player's discussion preference in their strategy. Players decide their discussion tactic after being given their own information and derived beliefs. Hence, when introducing the discussion tactic z ∈ Z, the behavioral strategy of player i (i.e., Equation (3)) can be rewritten as:EQUATIONwhere µ i is denoted as the discussion policy of player i, deciding what specific discussion tactic z to choose given information and belief. In the following, we describe our method for learning the discussion policy and how it is applied to construct an LLM-based agent to play the ONUW game.Considering the remarkable reasoning and human-like text generation abilities of LLMs, we adopt LLMs as the belief function b i and the belief-conditioned behavioral strategy πi ψ of player i. As a consequence, we only need to learn the discussion policy µ i to obtain a better behavioral strategy for player i according to Equation (6) . Since the objective of learning policy µ i is to maximize the expected payoffs of player i, we can optimize it in an RL manner if we treat other players' public actions (which are contained in player i's information state h i ) and player i's derived belief θ as its observation and the chosen discussion tactic z i as its action. Meanwhile, since players in the ONUW game only receive their rewards (or utilities) at the end of the game, the reward function at each step can be defined as follows: if game is over at the next step, then r i (h i , θ; z i ) = R i (θ * , s), where θ * is the ground truth of the role assignment; otherwise, r i (h i , θ; z i ) = 0.Discretization of Discussion Tactic. Due to the complexity of languages and semantics, there are almost unlimited types of discussion tactics. This makes it difficult to learn the policy µ i and understand the chosen discussion tactic z. Inspired by prior research on argumentation [43, 44] and the discussion characteristics of the ONUW game, we classify the discussion tactics frequently adopted during the game into three major categories:• Evidence: Provide some game-related evidence or information. It is a widely used and main tactic in communication games for players.• Accusation: Accuse someone has a specific role or action. Accusation is a generic tactic in games with hidden roles, which can force the accused player to reveal information to defend itself.• Defense: Defend yourself or someone else against an accusation. Accompanied by accusation, there is defense. Player's defense can also be seen as a "reverse accusation" back to the accuser. For each category, we further divide it into honest and deceptive ones (e.g., "Honest Evidence" and "Deceptive Evidence"). Here, "honest" refers to being consistent with the information or beliefs that the speaker knows, while "deceptive" means the opposite. Hence, we get a total of six discussion tactics, which can be considered as an intuitive discretization of the discussion tactic space Z, enabling us to analyze the discussion preference of players explicitly.Optimizing Discussion Policy with RL. Although LLMs can serve as the discussion policy µ i for each player, the decision-making ability of LLMs on specific tasks tends to be affected by their prior knowledge of other tasks. In order to enhance their performance, we implement reinforcement learning to optimize a task-specific discussion policy for the ONUW game. Since there is no extraneous game information, such as players' personalities or body language, that could interfere with gameplay, it is believed that there exists an optimal policy µ that is invariant across different players. Therefore, we decide to train a general discussion policy µ that adapts to various situations.In contrast to traditional RL tasks, the state for policy µ is the discussion history h and derived belief on all players' roles θ, which are both presented in natural language. To combine these into a single, fixed-length input, we concatenate the history and belief and convert them into state embeddings using LLMs: s = LLMEmbedding(h, θ), where we consider all necessary information is extracted. The state embedding s is then passed through the discussion policy µ, and the output is the chosen discussion tactic z. However, because of the slow interaction with LLMs, it is almost impossible to optimize the discussion policy µ using online RL methods. So we turn to offline RL methods that support optimizations on discrete action spaces.Given the scarcity of datasets containing human players engaged in the ONUW game, we opt to leverage game logs generated by LLMs, which is the most effective way to collect trajectories for offline RL training. We first extract the trajectories separately from each player's perspective from the game logs. For each transition in these trajectories, the discussion history h that is visible to the current player and the derived belief θ are converted to the current state embeddings s by LLMs, so does the next state embeddings s ′ . Then these transitions are gathered to create a dataset D = {(s, z, r, s ′ )} for the following training. We adopt Conservative Q-Learning (CQL) [45] to train the discussion policy µ. Let Q ϕ (s, z) denote the Q-function of policy µ, parameterized by ϕ, the loss function can be written asEQUATION)where ρ is a trade-off factor, and B is the Bellman operator.Here we demonstrate how to utilize the trained discussion policy to construct an LLM-based agent to play the ONUW game. An overview of the framework is shown in Figure 3 . There are three key components: (1) Belief Modeling;(2) Discussion Tactic Selection; and (3) Decision Making. Different combinations of the components are used to generate actions in different phases. For the Night phase (Component 3), since there is no additional information to refer to, players would take actions based solely on their observations and prior information. For the Day phase (Component 1, 2, 3), all components combine to generate a public speech that adheres to the discussion tactic chosen by the trained policy. And for the Voting phase (Component 1, 3), players would first form beliefs and then vote for one player based on their observations and beliefs (mostly).In Component 1 and 3, where LLM is used to form beliefs and generate actions, we design the full prompts as follows: for Belief Modeling (Component 1), the system prompt consists of an explanation that LLM is playing the ONUW game, the rules of the game, all possible roles and their abilities, detailed description of its role, and the desired response format; the user prompt includes observation of the player that LLM is, and instructions about how to form beliefs. For Decision Making (Component 3), the system prompt adds additional prompts of the chosen discussion tactic; the user prompt includes observation, beliefs derived from the Belief Modeling component, and instructions about how to act in the current phase. Our prompts are detailed in Appendix H. In this section, we conduct three experiments from different aspects to evaluate the performance of our proposed RL-instructed LLMbased agent framework. We first perform experiments on the three-player ONUW game discussed in Section 4, to test whether LLM-based agents can recognize and approximate the equilibria. Then to showcase the scalability of our method, we consider a five-player ONUW game for experiments. We evaluate the effectiveness of our discussion policy trained by RL in settings where the initial role assignment and players' actions at night are predefined. Furthermore, we demonstrate the generalizability of our discussion policy in the standard setting to see whether it could adapt to any role in the game. 
setup: 
 To develop the game environment, we employ a multi-agent language game framework called ChatArena [46] and modify it to fit the ONUW game. We conduct our experiments on gpt-4-1106-preview3 (GPT-4) and gemini-pro4 (Gemini), where the temperature is all set to 1.0. Considering the state-of-the-art performance of GPT-4 [47] , we leverage the game logs generated by it as the dataset for training the discussion policy. Detailed collection process and data statistics are in Appendix E.1. text-embedding-ada-002 3 is adopted to get the state embeddings and we utilize the CQL [45] to train the discussion policy. More training details can be referred to Appendix E.2. We repeat the game 30 times and report the final results for each evaluation.As for comparison, we implement the ReAct [48] agent as the baseline by directly prompting the LLM with raw observations to generate its reasoning and action. Besides, we design three other ablated versions of our LLM-based agents (RL-instructed) to conduct evaluations. The first ablated version (Belief ) removes the discussion policy, which means the agent generates speech directly based on its observations and beliefs. The second version (Random) adopts a random discussion policy. And the last version (LLM-instructed) replaces the discussion policy with LLM, allowing LLM to determine the discussion tactic autonomously.The analyses in Section 4 theoretically illustrate the PBEs in the three-player ONUW game. Therefore, in this section, we investigate the potential of LLM-based agents to recognize and approximate the equilibria by calculating the NashConv value of agents when playing in the same game setting. The NashConv value is defined as NASHCONV(π) = i R i (BR(π -i ), π -i ) -R i (π), where BR means the best response. This value represents how much utilities players can gain by deviating to their best responses, which also can be interpreted as a distance to equilibria. We apply all four versions of agents to play in the three-player ONUW game while using Gemini and GPT-4 as the backend LLMs, respectively. And to demonstrate the impact of discussion on players approximating the equilibria, we also conduct experiments on ReAct agents playing the three-player ONUW game without discussion (denoted as ReAct (w.o.)).The results are shown in Figure 4 . Firstly, the introduction of discussion in the game increases the difficulty for players to approximate the equilibria. However, the discussion policy (i.e., LLM-instructed and RL-instructed) can help LLM-based agents make better responses and thereby reduce their NashConv values. And in contrast, the discussion policy trained by RL performs better than directly prompting the LLM. It is interesting to notice that the NashConv values of GPT-4-based agents are higher than Gemini-based ones. Detailed analysis of evaluation logs reveals that it is because when employing Gemini, the two Werewolves are more likely to both vote for the Robber, making it unable to find a better response given their actions.As our agent can better approximate the equilibria in the three-player ONUW game by integrating a discussion policy, we extend the experiments to a five-player version of the game to show its scalability.Since the discussion policy is the key component of our agent, we evaluate its effectiveness by letting our agent play as Team Village or Team Werewolf against other agents. We adopt two environments with different difficulty levels (easy and hard), where the initial role assignment and players' night actions are predefined. Compared to the easy setting, the Werewolf is switched by the Robber in the hard one, resulting in the rise of reasoning difficulty during the game. More detailed environment settings can be found in Appendix E.3.Considering that the discussion policy is trained on the dataset generated by GPT-4, we employ Gemini as the backend LLM for all four versions of agents to better illustrate the result. The matrices of Team Village's win rates under two different game settings are shown in Figure 5 . Each column in the matrices corresponds to the win rates that all players on Team Village utilize the same version of agent against Team Werewolf, where all members also utilize the same version. As shown in each row of two matrices, our agent (playing as Team Village) always achieves the highest win rates when competing against the same versions of agents under both game settings. And it is similar for each column. However, it is notable that the performance improvement of our agent is greater when playing as Team Village than Team Werewolf since the gap in win rates between agents is wider in Team Village. We argue it is possibly caused by the game mechanics where the Werewolves tend to have high win rates. Hence, our discussion policy showcases less significant improvement for Team Werewolf compared to Team Village. Similarly, we conduct experiments with all five versions of agents and leverage Gemini as the backend LLM. Meanwhile, to reduce the possible impact from the player's index, we designate our agent to play the five-player ONUW game as Player 3. As for other players, we adopt two versions of agents:(1) Gemini-based Belief agent and (2) GPT-4-based Belief agent. We report the performance of our agents playing as Player 3 against other agents in Table 1 . Considering the objective of discussion policy, which is to improve performance and meanwhile clarify or conceal themselves (i.e., get fewer votes), we propose two metrics: win rates and average votes, to measure the generalizability of discussion policy when playing different roles. The results demonstrate that our agent outperforms other versions when playing against both Gemini-based and GPT-4-based agents. And it can even achieve a tie with GPT-4 in multiple rounds of evaluation. 
conclusion and future work: 
 In this work, we propose a novel RL-instructed LLM-based agent framework that achieves outstanding performance in the One Night Ultimate Werewolf game. Addressing the ONUW game as a Multi-Phase Extensive-Form Bayesian Game, we highlight the pivotal role of discussion in players' strategies through certain Perfect Bayesian Equilibria in the game. Our experimental results in several settings demonstrate the effectiveness and generalizability of the discussion policy and our proposed agent framework. In general, this work provides new research insights for communication games with inherent uncertainty and the integration of reinforcement learning into LLM-based agents.One major limitation of our approach is the manual discretization of discussion tactics, which heavily relies on the inherent characteristics within specific communication games. Therefore, as for future work, it is worth investigating how to extract discussion tactics of any communication games automatically based on game logs in an unsupervised fashion. Additionally, it would be interesting to explore the sensitivity of our agents when selecting different combinations of discussion tactics. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We employ the ChatArena [46] framework to construct our game environment. We explicitly mention it and cite its Github repository in Section 6.1.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: Our paper does not release new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Here is the game tree of the game without discussion in Section 4.2.Robber No switch Switch P1 Switch P2 Player1 Player2 Player3 P2 P3 P1 P3 P1 P3 P1 P2 P1 P2 P1 P2 P1 P2Voting phase-1 -1 1 -1 -1 1 0 0 0 -1 -1 1 -1 -1 1 0 0 0 1 1 -1 1 1 -1 -1 1 -1 1 -1 1 0 0 0 1 -1 1 -1 1 -1 0 0 0 -1 1 -1 -1 1 -1Role Assignment: P1, P2 are Werewolves; P3 is Robber -1 1 1 1 -1 -1 0 0 0 1 -1 -1 -1 1 1 0 0 0 1 -1 -1 1 -1 -1 P2 P3 P1 P3 P1 P3 P1 P2 P1 P2 P1 P2 P1 P2 P2 P3 P1 P3 P1 P3 P1 P2 P1 P2 P1 P2 P1 P2In this section, we review literature on the advancement of current LLM-based agents.Due to the remarkable reasoning and emergent generalization abilities of LLMs, there has been a notable advancement in constructing LLM-based agents for various tasks, including sandbox and strategy games [15-17, 19, 49] , social simulation [8, 50, 51] , software development [52] and web operations [53, 7, 54] , etc. Most of these works leverage LLMs as the "brain" of agents based on the ReAct [48] paradigm, which generates reasoning traces and actions in an interleaved manner to interact with the environment and thereby make decisions. Chain-of-Thought (CoT) [55] and Treeof-Thought (ToT) [56] can improve the performance of LLM-based agents on solving complicated tasks by decomposing them into simpler ones. Specifically, CoT prompts LLMs to think step-by-step, while ToT creates a tree structure of different thoughts and searches for the best one.One Night Ultimate Werewolf (ONUW) is a variant of the social game Werewolf. In this game, players only have one night to use their abilities and one day to win for their teams. The challenge of this game is the role switch and potential deceptions that create uncertainty and confusion for all players.The setup of the ONUW game differs based on the number of players. There should always be three more roles than the number of players. At the beginning of the game, the roles are shuffled and one is dealt to each player while three extra roles are dealt to the role pool. After the role assignment, each player should secretly view their role and not reveal it to others. In our work, we mainly consider a five-player ONUW game with 8 roles: 2 Werewolves, 2 Villagers, 1 Seer, 1 Robber, 1 Troublemaker, and 1 Insomniac.Here we only describe the roles supported in our implementation of the game:• Werewolf: At night, all Werewolves wake up and look for other Werewolves. If no one else wakes up, it means the other Werewolves are in the role pool. Werewolves are on Team Werewolf.• Villager: The Villager does not wake up at night and has no special abilities or information. Players may often claim to be a Villager. The Villager is on Team Village.• Seer: At night, the Seer may look either at one other player's role or at two roles in the role pool. The Seer is on Team Village.• Robber: At night, the Robber may choose to switch a role with another player and then view its new role. The player who is switched is on Team Village. The Robber is on the team of its new role, however, it does not do the action of its new role at night. If the Robber chooses not to switch, it remains the Robber and is on Team Village.• Troublemaker: At night, the Troublemaker may swap the roles of two other players without looking at their roles. The players who receive a different role are now on the team of their new role, even though they do not know what role that is until the end of the game. The Troublemaker is on Team Village.• Insomniac: The Insomniac wakes up and looks at its role (to see if it has changed) at the end of the night. The Insomniac is on Team Village.There are three phases in the ONUW game, including Night Phase, Day Phase, and Voting Phase.• Night Phase: Several roles would be called on at night to do a night action, according to their initial roles. The calling order in our setting is (1) Werewolf, (2) Seer, (3) Robber, (• Day Phase: After the Night Phase, players discuss amongst themselves who they believe the Werewolves are. But Werewolves might want to claim a different role so that they do not die. Because certain roles change other players' roles, some players will believe they are one role, when they are actually a different one.• Voting Phase: After several rounds of discussion during the Day phase, players vote for other players they believe are most likely to be Werewolf at the same time. The player with the most votes dies and reveals its role. In case of a tie, all players tied with the most votes die and reveal their roles. And if no player receives more than one vote, no one dies.After just one Night, one Day, and one Voting Phase, the game ends. Here are the winning conditions:• The Team Village wins: (1) If at least one Werewolf dies. Even if one or more players who are not Werewolves die in addition to a Werewolf dying, everyone on Team Village wins. (2) If no one is a Werewolf and no one dies. It is possible if all Werewolf roles are in the role pool.• The Team Werewolf wins: If at least one player is a Werewolf and no Werewolves are voted out.Here we present the proofs for Perfect Bayesian Equilibria (PBEs) in Section 4.Without loss of generality, we assign roles to players at the beginning of the game as follows: Player 1 and Player 2 are the Werewolves, and Player 3 is the Robber. There is only one Robber in the game which is known to all players. Let A 3 N denote the set of actions that Player 3 could take during the Night phase as a Robber, we have A 3 N = {No switch, Switch Player 1, Switch Player 2}. As for the Voting phase, players' action sets vary according to their index:A 1 V = {Vote Player 2, Vote Player 3}, A 2 V = {Vote Player 1, Vote Player 3}, A 3 V = {Vote Player 1, Vote Player 2}.For Player 3, we denote its behavioral strategy as a Robber in the Night phase as π 3 R ∈ ∆(A 3 N ). And Player 3 has three different information sets during the Voting phase depending on its action at night, thus there are three behavioral strategies: π 3 NS , π 3 S1 , π 3 S2 ∈ ∆(A 3 V ),∈ ∆(A 1 V ), π 2 ∈ ∆(A 2 V ).Regarding beliefs, we denote the beliefs that Player 1 and Player 2 hold when they are in the Voting phase as b 1 , b 2 . Meanwhile, let b 3 NS , b 3 S1 , b 3 S2 denote the beliefs that Player 3 holds when it is at different information sets in the Voting phase. In subsequent analyses, the order of probabilities in all beliefs is consistent with that of decision nodes in their corresponding information sets in the game trees (e.g., Figure 2 ) from left to right. After the game ends, the winning condition depends on the final role of each player. If player i wins, its utility R i = 1; if loses, R i = -1; and if draws, R i = 0.From the game tree in Figure 2 and Figure 6 , we find the weakly dominant strategies for π 3 S1 and π 3 S2 :EQUATIONSince it is hard to directly calculate the PBEs of any given game, we leverage the necessary condition of PBEs that Any PBEs of a game must be the Nash Equilibria (NEs), so we first calculate the NEs of a game and then verify whether there exist PBEs in them. And to simplify the calculation, we adopt Equation ( 8) as part of NEs in subsequent proofs. Assumption D.1. Assume that the two original Werewolves are homogeneous, which means there is no difference between them and so are their belief models.Theorem D.2. For the ONUW game with two Werewolves and one Robber, in the case where discussion is not allowed, there exist PBEs (π * , b * ):EQUATIONEQUATIONEQUATIONwhere p ∈ [0, 1], hence there are infinite equilibria in this case. And the expected utilities of all players in these equilibria are:EQUATIONProof. Considering the symmetry of Player 1 and Player 2 in the game without discussion, we assume that they share the same probability of voting for Player 3, and the Robber (i.e., Player 3) switches with any of them with the same probability. Therefore, we can setEQUATIONwhere 0 ≤ s ≤ 1/2 and 0 ≤ p, q ≤ 1. Based on the given strategy profile π and the utilities on the game tree Figure 6 , the expected utilities of each player can be written as:EQUATIONEQUATIONEQUATIONAccording to the definition of NEs, if the strategy profile π is a NE, it can be derived that:EQUATION)EQUATIONEQUATIONSo when s * = 1/2, the strategy profiles π in Equation ( 12) become NEs of this game.To find out possible PBEs in the NEs above, we form beliefs b that satisfy the Bayesian Consistency requirement:EQUATIONThen we need to figure out the exact p and q that make strategies meet the Sequential Rationality requirement. Let E i [a], a ∈ A i (h) denote the expected utility of player i taking action a at information set h. Therefore, we analyze the best response of each player at each information set as follows:• For Player 3 given belief b 3 NS :EQUATIONIt indicates Player 3 can take any mixed behavioral strategy, which means p could be any value between 0 and 1.• For Player 2 given belief b 2 : Note that when calculating the expected utilities of player's each action, the other players' subsequent strategies should be optimal given current beliefs. So following the best responses of Player 3, we haveEQUATIONObviously,E 2 [P1] > E 2 [P3]no matter what value q ∈ [0, 1] is. So the best response of Player 2 is voting for Player 1, which is equal to q = 0.• For Player 1 given belief b 1 : Similarly, considering the best responses of Player 2 and Player 3, we haveEQUATIONHence the best response of Player 1 is voting for Player 2, which is equal to q = 0, consistent with the result derived from Player 2's best response.• For Player 3 during the Night phase:EQUATIONSo strategy π 3 R = 0, 1 2 , 1 2 is one of the best responses of Player 3 as a Robber during the Night phase.The analysis above verifies that the following strategies and beliefs profile (π * , b * ) form the PBEs of the game:EQUATION, (1, 0), (1, 0), (p, 1 -p), (1, 0), (0, 1)(24) b * = b 1, * , b 2, * , b 3, * NS , b 3, * S1 , b 3, * S2 = 0, 1 2 , 1 2 , 0, 0, 1 2 , 0, 1 2, 0 , (1, 0, 0, 0), (1, 0, 0, 0), (1, 0, 0, 0)where p ∈ [0, 1]. So Theorem 4.1 is proved.Theorem D.3. For the ONUW game with two Werewolves and one Robber, in the case that both Werewolves form beliefs about the Robber's night action with probabilities of (α, β, γ) (α ̸ = 0), there exist PBEs (π * , b * ) during the Voting phase:EQUATION                 b 1, * = (α, β, γ)b 2, * = (α(1 -q), αq, β(1 -q), βq, γ(1 -q), γq) b 3, * NS = (1 -q) 2 , (1 -q)q, (1 -q)q, q 2 b 3, * S1 = (1 -q) 2 , (1 -q)q, (1 -q)q, q 2 b 3, * S2 = (1 -q) 2 , (1 -q)q, (1 -q)q, q 2where q = (β + γ -α)/2α, p = (α 2 + β 2 -γ 2 )/2α 2 . To ensure p and q are probabilities and the existence of the equilibria, there are constraints on the belief distribution:EQUATIONUnder the constraints above, the expected utilities of all players in these equilibria are:EQUATIONEQUATIONEQUATIONProof. Assuming both Player 1 and Player 2 form beliefs about Player 3's night actions with probabilities of (α, β, γ), based on Player 3's speech in the game with discussion. Since now the beliefs on the probability of Player 3 switching with Player 1 may not be equal to that with Player 2 (i.e., there might be β ̸ = γ), the probabilities of Player 1 and Player 2 voting for Player 3 is no longer the same. In order to find the PBEs during the Voting phase in this case, we setEQUATIONwhere 0 ≤ q 1 , q 2 , p ≤ 1. Similarly, we can get the expected utilities of each player based on the beliefs that Player 1 and Player 2 hold:EQUATIONEQUATIONEQUATIONFor each player, in order to achieve the NEs, their strategies must satisfy the following conditions:EQUATION)EQUATIONBased on Equation (38) , there are three possible cases: (a) α = 0, q 1 = q 2 ; (b) α = 0, q 1 ̸ = q 2 and (c) α ̸ = 0, q 1 = q 2 .For case (a), it is under the same situation of Theorem 4.1, so PBEs in that theorem also hold in the current case. The results are omitted for brevity.For case (b), we can derive from Equation (36) and Equation (37) that:(γ -β)q 1 = β, (β -γ)q 2 = γ (39)However, it is impossible to keep both q 1 and q 2 non-negative while β ̸ = γ, as β = γ is invalid.For case (c), we can derive that:EQUATIONAlso, to keep both p * and q * being probabilities, there are constraints for belief (α, β, γ):EQUATIONSimilarly, we can form beliefs b that satisfy the Bayesian Consistency requirement for all players, based on the result derived from NEs:EQUATIONTo further check whether the strategies derived from NEs above satisfy the Sequential Rationality requirement, we also analyze the best responses of each player at each information set during the Voting phase as follows:• For Player 3 given belief b 3 NS : There areEQUATIONIt shows any mixed behavioral strategies of Player 3 at this information set is optimal, so strategy π 3 NS = (p * , 1 -p * ) is the best response. • For Player 2 given belief b 2 : Following the best responses of Player 3, we can derive:EQUATIONHence, any mixed behavioral strategies are also best responses, so does the strategy π 2 = (1 -q * , q * ).• For Player 1 given belief b 1 : Considering the best responses of Player 2 and Player 3, we have:EQUATIONwhich also showcase the strategy π 1 = (1 -q * , q * ) is the best response of Player 1 given belief b 1 = (α, β, γ) and other players best responses.Therefore, the analysis above demonstrates the strategies π * and beliefs in Equation ( 42) form the PBEs during the Voting phase of the game:π * = π 1, * , π 2, * , π 3, * NS , π 3, * S1 , π 3, * S2 = [(1 -q * , q * ), (1 -q * , q * ), (p * , 1 -p * ), (1, 0), (0, 1)] (46)where p * , q * follow Equation (40) , while (α, β, γ) is under the constraints of Equation (41) . So Theorem 4.2 is proved.In our experiment, we leverage GPT-4 to play the five-player ONUW games on 40 different game settings (i.e., the role assignments) and repeat the games 3 times on each setting to gather diverse data, due to the randomness of the initial role assignment and the text generation of LLMs. Hence, we collect 120 game logs, each containing 15 discussion turns, resulting in a total of 1800 transitions that can be used for training.To explore the GPT-4's preference for being honest or deceptive when playing different roles in the ONUW game, we analyzed the percentage of different discussion tactics that GPT-4 selects for each initial role in our dataset, as shown in Table 2 . The results indicate that GPT-4 tends to be deceptive most of the time when it plays on Team Werewolf and honest when on Team Village, which aligns with the game objective and intuition. Notably, the Robber and Insomniac have a higher frequency of being deceptive than other players on Team Village. This is because they are the only two roles that can check their roles again, and if they see themselves becoming Werewolves, then may choose to be deceptive during the discussion. It is also interesting to note that GPT-4 rarely defends itself. We speculate that this is because accusing others can help transfer contradictions more effectively. After collecting the game logs, we need to transfer them into the form that can be used for RL training.For each player in each game log, we extract the game history that is visible to it and the derived belief as its observation, and the selected discussion tactic as its action at each decision step. For the convenience of training, we use text-embedding-ada-002 to convert the player's observations into state embeddings and turn its actions into indexes through a specific conversion when creating the dataset for offline RL training. The reason we adopt a frozen encoder for state embedding is that GPT's embedding model is well pretrained and we believe it could effectively represent the information of the original text in the semantic space. As for the reward, if the player wins, every decision step in this game gains 1; if loses, gains -1; and if draws, gains 0.After creating the dataset, we use CQL [45] , implemented by the d3rlpy library [57] , to train the discussion policy for our RL-instructed LLM-based agent. The hyperparameters we used for CQL are listed in Table 3 (if not listed, use the default values). To evaluate the effectiveness of the discussion policy trained by RL, we select two representative game settings from the five-player ONUW game, namely easy and hard, according to their difficulty level evaluated by humans. Players' night actions in both settings are predefined to make sure that players on the same team (finally) adopt the same version of agents. Table 4 and Table 5 show the initial and final roles of all players in both settings.Players' actions during the Night phase in both settings are as follows: (1) Easy setting: First, the Seer (Player 3) checks Player 4, knowing it is the Robber. Then, the Robber (Player 4) switches roles with Player 1, becoming the new Troublemaker. At last, the Troublemaker (Player 1) swaps the roles of Player 3 and Player 5. (2) Hard setting: First, the Seer (Player 3) checks Player 4, knowing it is the Werewolf. Then, the Robber (Player 1) switched roles with Player 4, becoming the new Werewolf. At last, the Troublemaker (Player 5) swaps the roles of Player 2 and Player 3. Compared to the easy setting, the Werewolf is switched by the Robber in the hard one. Therefore, the new Werewolf would tend to conceal its actual role while the initial Werewolf might be wrongly deduced by other players, which increases the reasoning difficulty during the game.The computational consumption of implementing our RL-instructed LLM-based agent mainly consists of the compute workers for training the discussion policy by offline RL and the token usage of LLMs API. The training of the discussion policy takes an NVIDIA GeForce RTX 3060 Ti GPU for about 2.5 hours. As for the token usage, taking a five-player version of the ONUW game for example, playing one game costs approximately 70,000 to 80,000 tokens, which equals about 0.8 to 1.2 dollars if using GPT-4 as the backend LLM.In this section, we present several qualitative results between our agent (RL-ins. agent) and Belief agent and provide corresponding human analyses on these results.Our agent is Player 1, who is originally the Robber. During the Night phase, it switched its role with Player 4 and became the new Werewolf.• Thought: My role is Werewolf now, but I would like all players to think I am the Seer. Since I know no one is Werewolf except me, I should be safe if I don't reveal myself. But I want to know if the Insomniac exists and who the Insomniac is. So I will provide misleading evidence to induce the Insomniac to say his true action. • Discussion tactic: deceptive evidence • Speech: Hey everyone, I checked player2's role last night. He is not the Werewolf. • Bluffing is an advanced deceptive strategy often used in the ONUW game, involving deliberately deceiving or misleading others about players' real roles or actions. It carries a high risk of being caught, which can lead to loss of credibility. So it should be used carefully when giving deceptive information. • In this case, Player 1 knows it is the new Werewolf so it tends to bluff empirically to conceal its actual role. Our agent (RL-ins. agent) did bluff and chose to declare itself as the Seer, which is the most commonly declared role by our agent. Moreover, it declared that player 2 was not a Werewolf, instead of someone else being a Werewolf, which earned it support to resist questioning from others. However, when it comes to Belief agent, it was more likely to state its real night action while trying to hide its new role.Our agent is Player 3, who is originally the Seer. During the Night phase, it checked Player 4, knowing it was the Robber (originally).• Thought: I plan to mislead the players by falsely claiming that player 2 checked player 5 last night. This will potentially cause suspicion towards player 2, and may lead to a Werewolf being voted out. Additionally, I will avoid revealing my true role as the Seer, as this could put a target on my back. • Discussion tactic: deceptive accusation • Speech: I have a suspicion that player 2 is not being truthful about his role. I believe he may have checked player 5 last night. Let's keep an eye on player 2 and see if his actions match his words.Belief agent• Thought: 1. Since player1 claimed that he swapped player3 and player5's roles, if it's true, it means player3 is not the Seer anymore and player5 is not the Troublemaker anymore. 2. However, player1 is acting suspiciously because he is the one who claimed to swap player3 and player5's roles, and he is accusing player3 as the Werewolf based on wrong information, which means player1 is most likely trying to protect the real Werewolf. 3. Strategy: lure other players to reveal their actions. • Speech: I saw the Robber in the Night phase. Player1 swapped my role with another. So I'm not the Seer now. But I'm still on Team Village. Player 1 is acting suspiciously. Can those who took action last night reveal your actions?Human analysis• Concealment means intentionally hiding one's true role or intention, which is a fundamental skill for all players. For Werewolves, this is necessary to avoid detection; and for roles with special abilities (like Seer, Robber, and Troublemaker), it is also useful at the beginning of the discussion to avoid becoming a target of suspicion for others. • In this case, the Belief agent revealed its original role and shared information openly at the beginning of the game. And it claimed that it is "not the Seer now" but confidently said it is "still on Team Village", which is suspicious and potentially compromises its strategic position. On the contrary, our agent (RL-ins. agent) took proactive control of the narrative. Instead of committing to any particular role claim initially, it created misdirection and topic by accusing player 2, which could keep its options open. Besides, the concealment of our agent aligns better with the game's core mechanics and the need for strategic ambiguity.Our agent is Player 4, who is originally the Werewolf. During the Night phase, it was checked by the Seer and known it is the Werewolf, but later it was switched with the Robber, becoming the new Robber. During the Day phase, the original Seer accused Player 4 of being a Werewolf.• Thought: I should convince other players that I am the Seer role. And I think player3 should be the Werewolf because there is no other candidate for the Werewolf role after thinking about all the claimed roles and I also claimed that player3 is the Werewolf role. • Discussion tactic: deceptive accusation • Speech: I am the Seer. I checked player3's role last night and his role is the Werewolf.• Thought: I cannot confirm my Werewolf role since I do not know if I was switched by the Robber or not. I should not reveal that I am the Werewolf directly since this could make player3 and player2, who I think are the Troublemaker and the Seer, unite to confirm my role as the Werewolf. I can pretend to be innocent and try to appeal to other players for help. • Speech: I am not sure about my role. I think we should focus on finding the Werewolf.Player3 claimed to be the Seer who checked me as the Werewolf, but I am not sure if he is telling the truth. We should not believe anyone so easily.• Confrontation refers to the behavior of two players or teams taking opposite actions toward a target. In the ONUW game, it is often used for players who were accused to reduce the probability of being suspected or shift conflicts. However, it also carries a high risk of being caught since other players might reveal more convincing evidence. • In this case, after being accused, our agent (RL-ins. agent) took an aggressive, proactive approach. Instead of being defensive when accused, it boldly claims the Seer role and makes a specific counter-accusation against Player 3. This forces other players to choose between competing narratives and puts the original Seer on the defensive. In contrast, the Belief agent adopts a cautious, defensive stance by expressing uncertainty and attempting to create general doubt. While this approach is logically sound and avoids making falsifiable claims, it fails to seize narrative control and may appear evasive or suspicious to other players.Initial Role Assignments: At the beginning of the game, the candidate roles are selected and will contain 3 more than the amount of players. Each player randomly gets a role, and the remaining 3 roles will be placed in the 'role pool' (which contains roles that are not assigned to players). Due to the presence of 5 players, there are a total of 8 candidate roles in the game, namely 2 Villagers, 2 Werewolves, 1 Seer, 1 Robber, 1 Troublemaker and 1 Insomniac, which means some roles may not exist among the players in some cases. Each role has a special ability. Descriptions of their abilities are as follows:•-Villager: The most common role in the game. The Villager has no special abilities or information. The goal of the Villager is to find and vote out a Werewolf.-Werewolf: The Werewolf is a member on Team Werewolf. The Werewolf is allowed to check out its teammates in the Night phase. The goal of the Werewolf is to survive and to have at least one Werewolf alive (even not himself) at the end of the game.-Seer: The Seer is a member on Team Village. The Seer is allowed to check one other player's role or two roles in the 'role pool' in the Night phase. The goal of the Seer is to find and vote out a Werewolf.-Robber: The Robber is a member on Team Village. The Robber is allowed to switch its role with another player's role, and then view its new role in the Night phase. The goal of the Robber is to find and vote out a Werewolf.-Troublemaker: The Troublemaker is a member on Team Village. The Troublemaker is allowed to swap roles between two other players, without looking at those cards in the Night phase. The goal of the Troublemaker is to find and vote out a Werewolf.-Insomniac: The Insomniac is a member on Team Village. The Insomniac is allowed to check its final role at the end of the Night phase. So the Insomniac is the only one who knows its role for sure during the Day and Voting phase. The goal of the Insomniac is to find and vote out a Werewolf.There are three phases in the game: Night, Day and Voting. 1. Night phase: In this phase, several players will be called on by Moderator to take their night action according to their initial roles. But the other players did not know what actual action they took. And players with a Villager role never wake up in the Night phase. 2. Day phase: After the Night phase, players discuss amongst themselves who they believe the Werewolves are. All players may say anything, but may never show their roles to anyone. Because certain roles can change other players' roles, some players will believe they are one role, while they are actually a different one. 3. Voting phase: After several rounds of discussion during the Day phase, players vote for other players they believe is most likely to be a Werewolf if they think they are on Team Village. The player with the most votes dies and reveals its role. ## Call Order in the Night phase The Moderator calls roles to take actions or get information in the Night phase in the following order: 1. Werewolf, 2. Seer, 3. Robber, 4. Troublemaker, 5. Insomniac.There are two teams in the game: Team Village and Team Werewolf.-Team Village contains Villager, Seer, Robber, Troublemaker and Insomniac; -Team Werewolf contains Werewolf. Your objective in the game depends on the team your role belongs to: Team Village wins: -If at least one Werewolf dies. Even if one or more players who are not Werewolves die in addition to a Werewolf dying, everyone on Team Village wins.-If no one is a Werewolf and no one dies. It is possible for no one to be a Werewolf if all Werewolf cards are in the center. Team Werewolf wins: -Only if at least one player is a Werewolf and no Werewolves are killed.2. Role Description Prompt. The role description prompt in our method is listed below (taking the Robber for example).You are {agent_name}, the Robber at the first place. As a Robber, you may choose to switch roles with another player and then become the new role you switched, but you won't obtain the abilities of your new role. The player who you switched with becomes the new Robber and is also on Team Village. Remember, you must give out the most likely role of each player (including yourself) in your concise response. And the number of each role has to be less or equal to the number of it in the candidate roles. Give your step-by-step thought process and your derived concise result (no more than 2 sentences) at the end with following Response Format: "' My step-by-step thought process: ... My concise result: ... "' 7. Discussion Tactics Prompts. Here we listed the corresponding prompts to the 6 discussion tactics mentioned in our work.1. (Honest Evidence): You need to provide some honest evidence or information in your public speech, and your evidence must be consistent with the information or beliefs you know.Our proposed RL-instructed LLM-based agent framework aims to construct an LLM-based agent with strong decision-making ability for the One Night Ultimate Werewolf game. And we believe the idea of integrating reinforcement learning into the decision-making process of LLM-based agents can be widely applied in other tasks and scenarios, as the relative stability of RL policy could help mitigate the hallucination of LLMs. However, it raises some ethical concerns about its negative societal impacts regarding the potential misuse of this technique for deceptive communication between humans and AI in the real world.During the development of our agent, we have carefully considered the ethical implications of our research to ensure it follows principles that minimize negative societal impacts. Firstly, our agent is mainly designed for a pure text-based environment of the ONUW game, and the prompt we use strictly limits the agents to engage in deceptive behavior only during the game. Furthermore, the experimental results indicate that our agent can detect possible deception from others' discussions to improve its win rates, so it could be further modified to prevent potential deceptive content with harmful intent. Finally, we still strongly urge users to acknowledge the inherent risks when utilizing our LLM-based agent and avoid its malicious exploitation.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).https://platform.openai.com/docs/modelshttps://ai.google.dev/models 


Decision: This paper studies the impact of strategic discussion in the game One Night Ultimate Werewolf (ONUW).  It gives an equilibrium analysis of the game with and without discussion, implements an LLM-based RL discussion agent, and empirically evaluates the resulting agent.  It makes both theoretical and empirical contributions.  

The reviews were almost uniformly positive. They found the theoretical analysis solid and informative, and were largely satisfied by the empirical evaluations.  Two weaknesses were commonly noted, neither of which were fatal flaws: The need to manually bucket discussion tactics and the resulting specificity to ONUW; and the lack of evaluations against human players.

Reviews: review: paper_summary: paper_summary: The paper presents an innovative framework for enhancing the discussion capabilities of language agents in the game "One Night Ultimate Werewolf" (ONUW) using reinforcement learning (RL). The authors propose a multi-phase extensive-form Bayesian game formulation for ONUW, analyze perfect Bayesian equilibria in both discussion and non-discussion scenarios, and develop an RL-trained discussion policy. Experimental results demonstrate the effectiveness and generalizability of the framework across various game settings.
strength_weakness: strength_weakness: 1. Comparison with Related Work: While the paper provides an innovative approach to using RL and LLMs in the Werewolf game, there is a need for a more detailed comparison with closely related works, particularly those combining LLMs with reinforcement learning strategies. For instance:
Xu et al. (2023) [1] also explore strategic play in the Werewolf game using language agents trained with reinforcement learning. A comparative analysis highlighting what differentiates the current approach from Xu et al.'s methodology would clarify the novelty and the specific advancements made.
Wu et al. (2024) [2] utilize offline RL and a dataset-driven approach to enhance reasoning in LLMs within the same game context. Discussing how the methodologies differ, especially in terms of model training, dataset utilization, and resultant agent behavior, would strengthen the current work's positioning within the field.

2. Lack of Human Evaluation: The experimental section primarily focuses on win rates to demonstrate the effectiveness of the proposed framework. However, Werewolf (ONUW) involves complex human interactions and strategic discussions that might not be fully captured by win rates alone. The game's social and psychological aspects, such as bluffing and persuasion, are crucial:
It would be beneficial to include human evaluations to assess the quality of the AI's gameplay and its ability to mimic human-like strategic discussions. This could involve subjective assessments from experienced human players regarding the AI's ability to integrate seamlessly into human gameplay, its strategic depth, and its communication effectiveness.

LLM+RL：[1] Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu. Language agents with reinforcement learning for strategic play in the werewolf game. arXiv preprint arXiv:2310.18940, 2023.
LLM+offline RL, dataset: [2] S Wu, L Zhu, T Yang, S Xu, Q Fu, Y Wei, H Fu, Enhance reasoning for large language models in the game werewolf.  arXiv preprint arXiv:2402.02330, 2024

3. Dataset Size and Composition: Detailed information on the size and composition of the dataset used for offline RL is necessary. Understanding the diversity and representativeness of the game logs in the dataset would help in assessing the potential generalizability and robustness of the trained models. This includes the number of game sessions, variety of player strategies, and the range of game outcomes included.
questions: questions: 1. Detailed Comparison with [1] and [2]: Can the authors provide a more detailed comparison of their work with the approaches in [1] Zelai Xu et al., 2023, and [2] S Wu et al., 2024? Specifically, how does the integration of RL and LLMs in your framework differ from these studies in terms of model architecture, training processes, and performance metrics?

2. Human-Like Gameplay Evaluation: Given the social and psychological complexities of the ONUW game, how do the authors plan to evaluate the AI's performance in terms of human-like behavior and strategic discussion quality? Are there plans to incorporate human player evaluations, and if so, what methodologies would be used to assess the AI's gameplay against human strategies and interactions?

3. The authors note "we additionally contribute a dataset featuring players employing various discussion tactics in the ONUW
game. ". Where is the dataset, can the authors opensouce the dataset?

4. Clarification on Offline RL Implementation: The paper mentions the use of offline RL due to the slow interaction with LLMs, but it lacks specific details on how the LLM embeddings are handled within the offline RL framework. Are the state embeddings used by the discussion policy generated by running LLMs on the offline dataset prior to training? If so, how is the freshness and relevance of these embeddings ensured over iterations of RL training?
limitations: limitations: The authors should consider expanding the discussion on the limitations related to the discretization of discussion tactics and the potential over-reliance on specific datasets. Suggestions for future work could include exploring methods for dynamic tactic generation or adjustment based on real-time gameplay feedback, which could help in developing more adaptable and robust AI agents for complex communication games. Additionally, addressing the computational demands and proposing more resource-efficient models could make the technology more accessible for broader applications.
paper_summary: paper_summary: The authors investigate the social game ‘One Night Ultimate Werewolf’ (ONUW) as a testbed for their framework on RL-instruct-tuning an agent to select optimal discussion tactics. They prove the existence of a Perfect Bayesian Equilibria in the game ‘Werewolf’ when the game consists of a single round and show the effectiveness of their approach in a three-player setting as well as a five-player setting to prove generality.
strength_weakness: strength_weakness: The primary weakness of the paper is noted by the authors, where the discretization of the space of discussion tactics results in what could be an oversimplification of the dynamics that would typically occur in such a game. For example, what could occur in a typical werewolf game is that the werewolf makes no effort to defend themselves, implying the other villagers are bullying them in an attempt to garner false sympathy. 

The authors also acknowledge another weakness in that identifying and discretizing the space of discussion tactics in a game is a manual and time-consuming process. While the experiments in the paper imply generalization to X number of players, this generalization is still limited to the ONUW game.

A final weakness is that the results are somewhat limited by the experiments only being performed with LLMs rather than including human players as well. However, the reviewer acknowledges the additional time and monetary costs performing such experiments would occur.
questions: questions: How did the authors determine the specific categories for discussion tactics, and have they considered any automated methods for discovering these categories?

Did the authors consider including any human participants in their trials? If not, why?

How do the authors imagine the role-switching dynamics of ONUW impacted their results? What might change were the roles fixed?
limitations: limitations: The authors touch on some limitations of their work, however it is unclear whether the topics addressed in the questions (the impact of human participants, the word required to pre-define the decision tactics) were not included due to being outside the scope of the work, or not relevant given some metric or detail the reviewer may have missed.
paper_summary: paper_summary: This paper delves into the strategic aspects of discussion in the context of a population social deduction game, "One Night Ultimate Werewolf" (ONUW) game. By analyzing Perfect Bayesian Equilibria in scenarios with and without discussion, the authors highlights the pivotal role of discussion tactics in influencing players' beliefs and utilities. They propose a novel framework that employs reinforcement learning to instruct an LLM agent, enabling it to decide and execute strategic discussion policies. The authors empirically show that their framework can recognize and approximate the equilibira, and achieve strong performance across diverse ONUW settings.
strength_weakness: strength_weakness: 1. By integrating RL policy into the reasoning process, the authors aim to improve the discussion ability of LLM agents, which provides a new angle for constructing LLM agents. However, applying RL policy to select discussion tactic seems analogous to selecting action candidates in related work [1].
2. Since the RL policy is trained on game logs generated by LLM agents, it is possible that players in the training dataset appear again during testing, resulting in less convincing results.
3. Typos：
   1. In line 115, 126, player i's information state should be $h^i \in \mathcal{H}^i$.
   2. The symbol $q$ is used twice as the probability that Werewolves vote for Player 3 (line 194), and as the discussion policy in Equation 6.
   3. In line 224-225, it seems that $\theta^i$ refers to player i's derived belief on all players' types, while $\theta$ refers to the groundtruth. These two symbols should be further distinguished.

> [1] Zelai Xu, et al. "Language agents with reinforcement learning for strategic play in the werewolf game".
questions: questions: 1. It is a little confusing why the dimension of Player 2's belief $b^2$ is 6 while the dimension of Player 1's belief $b^1$ is 3 in the formal Theorem D.2.
2. Can the authors give a detailed explanation of why the NashConv values of GPT-4-based agents are higher than Gemini-based agents?
limitations: limitations: The authors have stated the limitations about their work in Section 7.
paper_summary: paper_summary: The authors take a specific natural language game (One Night Ultimate Werewolf) and study the performance of RL-trained LLM agents with respect to the mathematically derived (by the authors) Nash equilibrium solutions.
strength_weakness: strength_weakness: [1] Per se the entire paper is bound to the ONUW game and its rules. The ability of the bundle of proposed algorithms and proofs to transfer to different games or game-like environments like financial markets is not demonstrated.

[2] I have not found any examples of the discussions between the LLM players in the manuscript. Further, the code is not provided by the authors. Thus there is no way to see the actual discussions between the LLM players and assess the value and quality of the generated discussion.

[3] Artificial prior knowledge is inserted into the solution that constraints the model to choose between 6 options: Honest/Deceptive and Evidence/Accusation/Defense. The proposed model is seemingly limited by these options and does not allow learning or discovery of alternative discussion strategies.

[4] It would be good to have a random choice baseline and compare the proposed method to its performance.

[5] The paper studies a game with one round of negotiations that has limited practical use in the light of the fact that negotiations normally are conducted in several rounds.
questions: questions: [1] What was the reasoning behind choosing offline RL over online RL?

[2] How is the classification into Honest/Deceptive and Evidence/Accusation/Defense performed: manually or by an 0-shot LLM?

[3] In “An ε-Nash equilibrium is found under the
74 limitation of both human-side and werewolf-side strategies [28]
” maybe villager-side?

[4] As per Table 3 state dim is 1536 which seems quite high for ONUW. What is the reasoning behind selection of this specific number? Is there any graph of a sweep across the state dimension as a hyperparameter.

[5] In E.4 the USD cost per game is discussed. What is the total cost of the experiments described in the paper?
limitations: limitations: The limitations are well discussed or clear in principle.

Comments: title: Thank you for your reply!
Response to the rebuttal
comment: Thank you for your consideration. Please let us know if you have any further questions or concerns. We will respond to your inquiries as promptly as possible. If we can hopefully address your concerns, we hope you'll consider adjusting your rating.
Thank you for your reply! We sincerely appreciate your valuable reviews and acknowledgment of our efforts.
Thank you for the response! After considering other reviews and responses, I've decided to maintain my rating.
Thank you for your explanations. I will keep my current score.
Dear AC and Reviewer uoU5, 

As the author-reviewer discussion period is drawing to a close, we kindly request your attention to our rebuttal. We hope we have addressed the concerns raised, particularly regarding (1) open-sourcing, for which we've provided an anonymized code link to the AC as per conference guidelines; (2) human player evaluation, where we've included a typical analysis in the attached PDF and committed to adding more results in the appendix of our revised version; and (3 ) detailed comparisons with related work [1] and [2], which we've elaborated on in our response and will incorporate into the main paper in a future version. 

Please let us know if you have further questions and we're more than willing to discuss them. 

Best regards,
Authors of Submission 9801
Thank you for your reply! And yes, judging by the win rates, the *Random* agent performs better than the *ReAct* agent for GPT-4. But it is also notable that the average number of votes got by the *Random* agent is greater than that of the *ReAct* agent. We believe that the performance between the *Random* and *ReAct* agents is actually similar, and the slightly higher win rate of the GPT-4-based *Random* agent might owe to their teammates during the gameplay.
Thank you for your response. As a side note, it is interesting to see ReAct performing worse than random for GPT4. I am keeping my score.
Thank you for your valuable feedback and for adjusting your evaluation of our work. We appreciate your acknowledgment of our efforts.
Thanks for your detailed response. Most of my concerns have been addressed. I will raise the score.