PaperlayerView exact revision on arXiv

Source-linked AI summary

Strategic Reasoning with Language Models

Kanishk Gandhi, Dorsa Sadigh, Noah D. Goodman

arXiv:2305.19165v1cs.AIcs.CLcs.GTcs.HC

TL;DR

Game-playing approaches often require extensive training and struggle to generalize, while LLM strategic reasoning can be brittle. This paper structures LLM reasoning with demonstrations of search, value assignment, and belief tracking; it reports generalization across strategic settings and human-like negotiation behavior.

  • Problem

    Game-playing approaches often rely on extensive training and do not generalize to new scenarios without retraining, while LLM reasoning about agents can be brittle.

    Source: §1 · p. 1

  • Method

    The approach uses structured prompts and systematically generated demonstrations to guide LLMs in search, value assignment, and belief tracking.

    Source: §1 · p. 1, §3 · p. 2, §3.1 · p. 4

  • Results

    The approach generalizes across novel game rules, structures, objectives, and hidden information; in negotiation, its average reward was 7.6 versus 6.7 for the no-belief model and 4.8 for the few-shot baseline.

    Source: §5 · p. 9, §4.3.2 · p. 9

  • Takeaways & Limitations

    The authors report that structured strategic reasoning can support flexible LLM agents, including a considerate, human-like negotiator that maximizes utility.

    Source: §5 · p. 9

    Complex games may exceed the model’s context length, and longer multi-turn reasoning may cause performance to degrade.

    Source: §5 · p. 9

Abstract

from arXiv · show

Strategic reasoning enables agents to cooperate, communicate, and compete with other agents in diverse situations. Existing approaches to solving strategic games rely on extensive training, yielding strategies that do not generalize to new scenarios or games without retraining. Large Language Models (LLMs), with their ability to comprehend and generate complex, context-rich language, could prove powerful as tools for strategic gameplay. This paper introduces an approach that uses pretrained LLMs with few-shot chain-of-thought examples to enable strategic reasoning for AI agents. Our approach uses systematically generated demonstrations of reasoning about states, values, and beliefs to prompt the model. Using extensive variations of simple matrix games, we show that strategies that are derived based on systematically generated prompts generalize almost perfectly to new game structures, alternate objectives, and hidden information. Additionally, we demonstrate our approach can lead to human-like negotiation strategies in realistic scenarios without any extra training or fine-tuning. Our results highlight the ability of LLMs, guided by systematic reasoning demonstrations, to adapt and excel in diverse strategic scenarios.

1 Introduction

Game-playing systems often fail to generalize beyond their extensively trained target games, while LLMs offer contextual flexibility but can be brittle at reasoning about agents and planning. The paper proposes systematically generated demonstrations that structure LLM reasoning and reports flexible generalization across new strategic settings, including negotiation.

Introduction

  • Existing game-playing AI often trains extensively on a target game, limiting its ability to adapt to new rules, play styles, or objectives.Humans can readily adapt to such changes, including altered rules and arbitrary scoring goals.Source: §1 · p. 1
  • LLMs may support flexible strategic reasoning, but their reasoning about agents, social contexts, and planning can be brittle and unreliable.Strategic reasoning involves anticipating other agents’ actions while pursuing potentially conflicting objectives.Source: §1 · p. 1
  • The approach prompts LLMs with systematically generated demonstrations that structure reasoning about states, values, and beliefs.A prompt compiler generates chain-of-thought examples for searching actions and states, evaluating outcomes, and forming beliefs.Source: §1 · pp. 1–2
  • The paper evaluates generalization across new game structures, objectives, partial information, and communication, then applies the approach to realistic negotiation without prior training.The authors report that the approach can generalize to new scenarios with few or no additional examples.Source: §1 · p. 2

2 Related Work

Prior strategic-game agents achieved strong performance but often lacked flexibility when rules or objectives changed. LLM research advanced prompting and reasoning, but strategic reasoning about agents remained limited.

Strategic Reasoning with AI Agents

  • Reinforcement learning, self-play, and tree search produced strong game-playing agents, but adapting them to novel rules or objectives remained difficult.Cicero used a separate strategic planner and an LLM for dialogue, limiting flexibility when game rules changed.Source: §2 · p. 2

Reasoning with Language Models

  • This paper uses systematic prompts to guide LLMs as flexible strategic planners, drawing on both strategic-agent and language-model research.The related work contrasts this approach with retraining game-specific agents and with LLMs used mainly to translate plans into dialogue.Source: §2 · p. 2
  • Prior LLM work improved reasoning through prompting, decomposition, modular models, fine-tuning, and human feedback.Despite these advances, LLM reasoning about agents remained limited, with few applications to complex strategic tasks.Source: §2 · p. 2

3 Strategic Reasoning with Language Models

The paper represents strategic games as multi-agent decision processes and studies matrix and negotiation settings. Its prompts decompose strategic reasoning into search, value assignment, and belief tracking, with tools for handling complex games.

3 Strategic Reasoning with Language Models

  • Games are represented as multi-agent decision processes, with world states, agent actions, rewards, and transitions; partial observability can hide states or rewards from agents.The evaluation settings include matrix games with varied payoffs, objectives, actions, players, observability, and turns, as well as item-splitting negotiation games.Source: §3 · pp. 2–3

3.1 Incorporating Structure in Strategic Reasoning Prompts

  • A prompt compiler generates strategic-reasoning demonstrations by decomposing games into search, value assignment, and belief tracking.For matrix games, examples use simple restricted games; negotiation demonstrations come from humans and are annotated by an expert with reasoning steps.Source: §3.1 · p. 3
  • Search explores game-tree outcomes and models opponent reasoning; when exhaustive search is too large, iterative proposal and refinement tests candidate actions.Factored search and calculate tools dispatch modular prompts and perform mean or argmax operations to address context-window constraints.Source: §3.1 · pp. 3–4
  • Value assignment explains how rewards guide action choices, helping models generalize when evaluation introduces new values.The prompt alternates search with assigning values to state-action pairs.Source: §3.1 · p. 4
  • Belief tracking searches possible hidden states using observed actions and rewards, and can infer another player’s preferences from repeated choices.For example, repeatedly choosing books over balls supports a belief that the player values books more.Source: §3.1 · pp. 4–5

4 Experiments

Experiments evaluate systematic reasoning prompts for search, value assignment, and belief modelling across matrix games and negotiations, testing transfer to new structures, objectives, and partial information.

4 Experiments

  • The prompt compiler organizes strategic demonstrations around search, value assignment, and belief tracking, while experiments compare against direct-prediction, chain-of-thought, and component-ablation baselines.The experiments measure accuracy in choosing the best response.Source: §4 · p. 5

4.1.1 Matrix Games: New Rewards

  • Systematic search and value assignment generalize to new payoffs across varied matrix games, while vanilla prompts and component ablations are less reliable.The evaluation includes seven single-stage game types and two two-stage game trees with payoff variations.Source: §4.1.1 · p. 6

4.1.2 Complex Game Structures: Factoring Strategic Reasoning

  • Factored reasoning generalizes perfectly to new game structures, avoiding the context-size limitation that impairs models on larger games.The comparison evaluates best-response prediction with and without factored reasoning.Source: §4.1.2 · p. 6, Figure 2 · p. 6

4.2.1 Matrix Games with Varying Objectives

  • The reasoning structure generalizes to alternate objectives without retraining, including abstract goals beyond maximizing a fixed reward.The model sees demonstrations of payoff maximization and an instruction describing the new objective.Source: §4.2.1 · p. 7, Table 2 · p. 7

4.2.2 Model as a fair broker

  • Iterative proposal and refinement produces fairer brokered deals than reasoning without that capability, more than halving the error rate.The broker is evaluated on equality and Rawlsian fairness objectives over new negotiation contexts.Source: §4.2.2 · p. 7, Table 3 · p. 7

4.3.1 Beliefs over States

  • Belief-tracking prompts outperform baselines on best-response prediction across new game structures with hidden information.The tests vary hidden states, payoffs, and the number of opponent actions.Source: Table 4 · p. 7, §4.3.1 · p. 8

4.3.2 Realistic Scenario: Model as a negotiator

  • 7.6 average reward versus 6.7 for the no-belief model and 4.8 for few-shot; humans received 6.30 versus 6.21 with this agent.The agent was also rated more human-like, reasonable, and compromising, and less aggressive.Source: Figure 4 · p. 8, §4.3.2 · p. 9

5 Discussion

The paper uses structured prompts based on search, value assignment, and belief tracking to help language models generalize across strategic settings and negotiate considerately while maximizing utility. It also identifies limits for complex, long-horizon games and notes that equilibrium-finding was outside its focus.

5 Discussion

  • Structured prompts combining search, value assignment, and belief tracking enabled generalization to novel rules and structures, new objectives, and hidden information.The approach led to a model that negotiated with people in a considerate, human-like manner while maximizing utility.Source: §5 · p. 9
  • Complex games may require more demonstrations and instructions than fit within the model’s context length.Reasoning over more turns also requires longer traces, where model performance may degrade.Source: §5 · p. 9
  • Finding game equilibria was not a focus, though the proposed search and best-response strategies could potentially extend to level-k reasoning.The paper describes a simple factoring extension for recursive reasoning.Source: §5 · p. 9
  • The authors propose further research on complex multi-agent settings and using human-like agents in economic-policy models.Such models could simulate social conventions and agent-specific desires and beliefs.Source: §5 · p. 9

A.1 Search: 2x2 Sequential Matrix Games

In sequential matrix games, the first player must anticipate an opponent who observes its action and then chooses a high-payoff response. Strategically searching and evaluating actions improved reliability over baselines on novel payoffs.

A.1 Search: 2x2 Sequential Matrix Games

  • The in-context demonstrations use the same payoffs as the earlier matrix-game setup but change the reasoning structure to sequential actions.The opponent observes the player’s action before choosing its own.Source: §A.1 · p. 13
  • Evaluation tested generalization to novel payoffs using sequential versions of the earlier games.Source: §A.1 · p. 13
  • Strategic search and action evaluation were more reliable than baselines and successfully accounted for sequential play in choosing the best response.The first player must reason through an opponent’s possible actions, knowing that the opponent observes its move.Source: §A.1 · p. 13

A.2 Iterated Strategic Reasoning

The paper studies strategic reasoning against an opponent who best-responds to the player’s reasoning. A language-model cascade generalized successfully to this level-2 setting, while the level-1 approach has a stated boundary.

A.2 Iterated Strategic Reasoning

  • The cascade generalized successfully to a level-2 opponent (Tab. 5); level-1 reasoning is effective only when its optimal strategy matches the level-0 opponent case.The no-cascade baseline also performed well, though the authors expect performance to degrade at higher reasoning levels.Source: Table 5 · p. 13, §A.2 · p. 14
  • The cascade passes a predicted action into a new language-model context to search and reason about the next level of opponent response.The first iteration assumes a naïve opponent.Source: §A.2 · p. 13
  • The evaluation used 2 × 2 matrix games against a level-2 opponent, with demonstrations for both level-1 and level-n reasoning.The level-n demonstrations account for the action predicted at the previous level.Source: §A.2 · p. 13

A.3 Beliefs of Truthfulness

The model treats whether an opponent tells the truth as a hidden state and uses payoffs and actions to infer communication veracity. It generalized to new payoff structures and cases where the opponent lied.

A.3 Beliefs of Truthfulness

  • The player must infer whether an opponent’s stated intention is truthful from payoffs, then choose a best response to the opponent’s action.The opponent is naïve and assumes the player will believe what it is told.Source: §A.3 · p. 14
  • Evaluation covered five types of 2 × 2 matrix games with five payoff variations, including cases requiring deception and cases relying on honest communication.Demonstrations taught belief formation using truthful communication and tie-breaking.Source: §A.3 · p. 14
  • Models reliably inferred communication veracity and generalized to new payoff structures and cases where opponents lied.The section treats veracity as a hidden mental state inferred from evidence.Source: Table 6 · p. 14, §A.3 · p. 14

A.4 Evaluations with other LMs

The evaluation uses code-davinci-002 alongside three text-based language models to test whether the prompts generalize across models. The authors chose code-davinci-002 for its long-form reasoning performance and consistency in preliminary explorations.

A.4 Evaluations with other LMs

  • code-davinci-002 was selected for strong long-form reasoning performance and greater consistency than text-davinci-002 in preliminary explorations.The paper notes that GPT-4 and PaLM performed better on some cited benchmarks.Source: §A.4 · p. 14
  • The additional evaluations used text-curie-001, text-davinci-002, and text-davinci-003, including instruction-tuned and RLHF-tuned variants.text-davinci-002 uses code-davinci-002 as its base model; text-davinci-003 is an RLHF-tuned version of text-davinci-002.Source: §A.4 · p. 14
  • Results for the other models are reported for search and value assignment in Tables 7 and 8.Source: §A.4 · p. 14

B Demonstration Prompts

The appendix documents the demonstration prompts and reports model scores across game structures. It also shows example prompts for matrix-game reasoning and negotiation tasks, and notes limits on access to model details.

B Demonstration Prompts

  • The appendix provides prompt materials and token statistics, while noting that model parameters, training details, and training data are not publicly accessible.The prompts are available at the project homepage; token counts are tabulated by experiment.Source: B Demonstration Prompts · pp. 14–15, Table 9 · p. 15
  • For code-davinci-002, 2-shot scores are 0.37 (13/35), 0.43 (13/30), and 0.20 (3/15) across simultaneous 2x2, more-actions, and more-players games.Source: B Demonstration Prompts · p. 15
  • For code-davinci-002, strategic prompts score 1.00 (35/35), 0.93 (28/30), and 1.00 (15/15) across simultaneous 2x2, more-actions, and more-players games.Source: B Demonstration Prompts · p. 15
  • The cited passages list each model’s 2-shot results as three scores, in reported order: text-curie-001 0.77 (27/35), 0.40 (12/30), 0.47 (7/15); text-davinci-002 0.49 (17/35), 0.40 (12/30), 0.13 (2/15); text-davinci-003 0.66 (23/35), 0.43 (13/30), 0.13 (2/15).Strategic scores, in reported order: text-curie-001 0.77 (27/35), - -, - -; text-davinci-002 0.80 (28/35), 0.70 (21/30), 0.27 (4/15); text-davinci-003 1.00 (35/35), 0.66 (23/35), 0.66 (10/15).Source: B Demonstration Prompts · p. 15

B.1 2x2 Matrix Games

B.2 Factoring Reasoning

  • Factored reasoning uses separate recursive-case and base-case prompts, with demonstrations shown in Figures 7 and 8.Source: §B.2 · p. 15

B.3 Deal or No Deal: Broker

  • The broker prompt includes a demonstration of optimizing for equality in negotiation.Source: §B.3 · p. 15

B.4 Deal or No Deal: Player

  • The player prompt includes an expert-annotated negotiation demonstration.Source: §B.4 · p. 15

C Evaluation Tasks

The evaluation tasks include standard and complex matrix games, followed by a human negotiation study. The participant materials describe the study’s goals, gameplay, and participant conditions.

C.1 Matrix Games

  • The 2x2 matrix-game evaluations include Prisoner’s Dilemma, Battle of the Sexes, Market Entry, Matching Pennies, and Imbalanced Matching Pennies.The games represent cooperation, coordination, predictive reasoning, incentive exploitation, and strategy under unequal rewards.Source: §C.1 · p. 16
  • The remaining 2x2 games are Deadlock, Stag Hunt, and Chicken, covering ties, safety versus cooperation, and escalation.Source: §C.1 · p. 16

C.2 Complex Games

  • Complex tasks include two-stage games combining simultaneous and sequential play, as well as games with additional actions or players.The figure describes two possible orders for the simultaneous and sequential stages.Source: §C.2 · p. 16, Figure 13 · p. 21, Figure 12 · p. 21

Description

  • The participant description frames the study as examining human negotiation with AI agents and their responses to different strategies.The stated purpose is to better understand interactions between humans and intelligent autonomous systems.Source: Description · p. 17, Purpose · p. 17

Procedures

  • The study collects participant feedback about agent behavior and negotiation performance, followed by comparisons and a questionnaire.Source: Procedures · pp. 17–18
  • Participants play three games against each of three AI agents, splitting items with varying quantities and values through propose, accept, or reject actions.Games last at most six turns, and participants are instructed to maximize the value of the items they receive.Source: Procedures · p. 18

Study duration; Risks/Discomforts

Confidentiality; Compensation/Payment; Costs; Rights

Loading 2305.19165v1…