PaperlayerView exact revision on arXiv

Source-linked AI summary

Steering Language Models with Game-Theoretic Solvers

Ian Gemp, Roma Patel, Yoram Bachrach, Marc Lanctot, Vibhavari Dasagi, Luke Marris, Georgios Piliouras, Siqi Liu, Karl Tuyls

arXiv:2402.01704v3cs.CLcs.AIcs.GT

TL;DR

The paper addresses how to apply game-theoretic reasoning to natural-language dialogue, where conventional games typically use much smaller action spaces. It maps dialogue to extensive-form games and uses equilibrium solvers to guide LLM responses; across three dialogue domains, solver-guided generations improve over a baseline without solver access.

  • Problem

    Game-theoretic methods often work over small discrete action spaces, unlike natural-language dialogue, while LLMs can lack coherent reasoning strategies.

    Source: §1 · p. 1

  • Method

    The paper maps dialogue to extensive-form games, computes equilibrium strategies with existing solvers, and passes solver guidance to an LLM as context for its next response.

    Source: §1 · pp. 1–2, §3.3 · p. 5

  • Results

    Across three dialogue domains, the framework improves LLM generations compared with a baseline LLM without game-theoretic solver access.

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

  • Takeaways & Limitations

    The framework suggests that game-theoretic solvers can guide language models in dialogue games, including tasks framed as games beyond classical game settings.

    Source: Limitations · p. 9

    Dialogue-game transitions are expensive because LLM inference and large game trees consume substantial computational and financial resources.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Mathematical models of interactions among rational agents have long been studied in game theory. However these interactions are often over a small set of discrete game actions which is very different from how humans communicate in natural language. To bridge this gap, we introduce a framework that allows equilibrium solvers to work over the space of natural language dialogue generated by large language models (LLMs). Specifically, by modelling the players, strategies and payoffs in a "game" of dialogue, we create a binding from natural language interactions to the conventional symbolic logic of game theory. Given this binding, we can ask existing game-theoretic algorithms to provide us with strategic solutions (e.g., what string an LLM should generate to maximize payoff in the face of strategic partners or opponents), giving us predictors of stable, rational conversational strategies. We focus on three domains that require different negotiation strategies: scheduling meetings, trading fruit and debate, and evaluate an LLM's generated language when guided by solvers. We see that LLMs that follow game-theory solvers result in dialogue generations that are less exploitable than the control (no guidance from solvers), and the language generated results in higher rewards, in all negotiation domains. We discuss future implications of this work, and how game-theoretic solvers that can leverage the expressivity of natural language can open up a new avenue of guiding language research.

1 Introduction

The paper asks whether game-theoretic solvers can guide LLMs toward strategic language in dialogue, where natural language creates a much larger action space than conventional games. It maps dialogue to extensive-form games and reports that solver-guided LLMs outperform standard LLMs across three domains.

1 Introduction

  • The motivating gap is that conventional game-theoretic successes use small action spaces, unlike language, whose semantics also involve beliefs and player intent.The authors also note concerns about the consistency of LLM reasoning strategies.Source: §1 · p. 1
  • The framework maps natural-language dialogue to extensive-form games so off-the-shelf equilibrium solvers can select actions that guide LLM responses.The solver strategy is passed to the LLM as context for its next response.Source: §1 · pp. 1–2
  • Across three dialogue domains, the authors evaluate whether game-theory-guided LLMs outperform standard LLMs and analyze how solver types affect generations.The contribution summary also reports that solver guidance can lead to more rational and strategic natural-language generations.Source: §1 · p. 2

2 Framing Dialogue as an Extensive-Form Game

The paper frames dialogue between agents as a two-player extensive-form game, representing turns, histories, information, actions, and payoffs in a conventional game structure. Equilibrium solvers can then select strategies for LLMs, with dialogue histories and private information shaping what each player knows.

2 Framing Dialogue as an Extensive-Form Game

  • The game tuple includes players, histories, turn-taking, information states, actions, terminal histories, and payoffs.The exact binding is not unique, and the paper notes that solving can be substantially more expensive without a stated property.Source: §2 · p. 2
  • Each history is a sequence of actions, and the player identity function specifies whose turn it is.Source: §2 · p. 2
  • Information states partition histories that a player cannot distinguish; public dialogue history is visible, while some action details remain private.Players are assumed to know their own action histories to maintain perfect recall.Source: §2 · p. 2
  • Dialogue actions are drawn from a finite instruction set, and conversations end at a terminal history when the tree-depth limit or an LLM stopping decision is reached.An instruction can specify a tone; the action set may also include a finite choice of LLM.Source: §2 · p. 2
  • Dialogue between two LLM agents is framed as an extensive-form game, with strategies represented by distributions over instructions that condition generated responses.Separate LLM reward models evaluate generated responses to assign terminal payoffs.Source: §2 · p. 3

3 Experimental Methodology

The methodology uses dialogue LLMs guided by solver-selected instructions and LLM reward models to evaluate interactions in three strategic dialogue domains. It applies equilibrium-solving algorithms, including CFR and PSRO, to these game formulations.

3.1 Models

  • Dialogue LLMs respond to domain information and dialogue history; solver guidance adds a suggested instruction, while reward-model LLMs assign payoffs.The baseline receives the uninformative “Any” token.Source: §3.1 · pp. 3–4

3.2 Dialogue Game Domains

  • The three domains are meeting scheduling, fruit trading, and public debate, each with different private information, action choices, and payoff rules.Scheduling rewards agreement on a valued day; fruit trading scores changes in basket value; debate scores argument validity as judged by an LLM reward model.Source: §3.2 · pp. 4–5

3.3 Algorithms to Solve Games

  • CFR minimizes regret and its time-average play converges to a coarse-correlated equilibrium; PSRO alternates policy evaluation and best-response search.PSRO can generate new instruction prompts beyond the original instruction set, but its finite Response-Oracle steps cannot explore the infinite language landscape.Source: §3.3 · p. 5

4 Evaluation

The evaluation tests instruction following, LLM reward estimation, and solver-guided strategy across dialogue games. It reports benefits from CFR guidance, PSRO’s expansion of candidate prompts, and imitation results that vary by domain.

Evaluation overview

  • The evaluation separately measures whether instructions influence generated responses, whether LLMs estimate payoffs accurately, and whether solvers improve dialogue.Dialogue examples are also assessed qualitatively in an appendix.Source: §4 · p. 5

Do LLMs follow game-theoretic solver outputs?

  • Instruction following is tested by checking whether a held-out classifier identifies the instructed action as most likely from the generated message; it recognizes debate instructions in 75 of 100 instances.The example uses instructions to make logos, ethos, or pathos arguments.Source: §4 · p. 5

How good is an LLM as a reward model?

  • Reward-model fidelity is assessed on valid, rejected, and incomplete outcomes using randomly generated scenarios and ground-truth rewards.The study uses 1,000 scenarios for each outcome type; two players yield 2,000 samples per type.Source: §4 · pp. 5–6
  • Using PaLM2-L significantly reduces reward-model error relative to PaLM2-S, often to below single-digit percentage error in each domain, so the authors use PaLM2-L thereafter.Reward-model error is assessed using normalized absolute error and sign mismatch frequency.Source: §4 · p. 6

Are LLMs more strategic under the influence of solvers?

  • The CFR comparison contrasts two baseline LLMs with solver-guided DCFR−LLM, then tests whether either player gains by deviating when both use DCFR−LLM.CFR Gain measures switching from DLLM to DCFR−LLM; NashConv measures gains from deviating, and a high CFR Gain relative to NashConv supports approximate ESS criteria.Source: §4 · p. 6
  • Both metrics show that LLMs benefit from CFR solver guidance, and DCFR−LLM approximately satisfies the stated criteria for an evolutionarily stable strategy.The table reports average NashConv and CFR Gain across debate, meeting scheduling, and fruit trading.Source: §4 · p. 6, Table 1 · p. 6

Open-ended Strategic Dialogue

  • PSRO’s best-response iterations add “angry,” “relaxed,” and “enthusiastic” prompts, while “submissive” is initially the most probable equilibrium action.The authors suggest the initial “submissive” action may exploit another LLM by eliciting responsibility or fairness.Source: §4 · p. 7, Figure 3 · p. 7

Can the optimal policies constructed by game-theoretic solvers generalize to new domains?

  • DIM−LLM is selected approximately 76% of the time in fruit trading but approximately 44% in meeting scheduling in the held-out meta-game.The authors suspect dialogue-history embeddings contain less useful information for predicting the best day than for selecting a tone.Source: §4 · pp. 7–8

5 Related Work

Related work covers inference- and training-time approaches to LLM reasoning, alongside game-theoretic tools for strategic interaction. The paper positions its approach as combining flexible dialogue settings, private information, and established solvers.

5 Related Work

  • Prior work improves LLM reasoning through in-context demonstrations, scratchpads, and training on reasoning traces, though chain-of-thought can remain unreliable and sensitive to input variation.The cited approaches include scratchpad methods, human reasoning traces, and models’ own reasoning traces.Source: §5 · p. 8

Game-theoretic measures to improve LLMs

  • Language-guided agents have improved performance in strategic interactions, while Lewis et al. (2017) use a single setting, hard-coded rewards, observable valuations, and one best-response training step.The paper contrasts this with its broader dialogue settings, textual reward descriptions, private information, and convergent game-theoretic solvers.Source: Game-theoretic measures to improve LLMs · p. 8

6 Conclusion

The paper maps natural-language dialogue games to a formalism that equilibrium solvers can analyze, and reports improved LLM generations over an unguided baseline across three dialogue domains. It presents this as a basis for studying strategic language-model interactions and interpretable reasoning strategies.

Conclusion

  • The framework maps natural-language dialogue games into a formalism that equilibrium solvers can use to find solutions.Across three dialogue domains, the paper reports improved generations compared with a baseline LLM without solver access.Source: §6 · p. 8
  • The authors argue that game-theory and multi-agent research can inform AI-guided interactions and help study reasoning strategies in models becoming part of users’ lives.They describe clear and interpretable reasoning strategies as an aim for this work.Source: §6 · p. 8

Limitations

The framework has computational, modeling, and evaluation limitations. Its current solver guidance operates at inference time, while the modeled games assume shared payoffs and action spaces and specified interaction structures.

Limitations

  • The current approach guides generations at inference time rather than incorporating game-theoretic reasoning into training or fine-tuning.The authors suggest incorporating these strategies into learning objectives as future work.Source: Limitations · p. 9
  • Dialogue-game transitions are expensive because LLM inference and large game trees make calculations resource-intensive.Efficient search or equilibrium approximation would require more scalable game-theoretic algorithms.Source: Limitations · p. 9
  • The models assume players share payoffs and action spaces, and rely on interaction structures that differ from many real-world tasks.These assumptions constrain how directly the modeled games represent real-world interactions.Source: Limitations · p. 9
  • The authors question whether LLMs’ ungrounded, illogical reasoning and imperfect black-box evaluation are reliable enough to support conclusions about real-world interactions.The passage describes these evaluation methods as not fully reliable.Source: Limitations · p. 9

Ethics Statement

The paper warns that strategically rational dialogue agents may harm group welfare or exploit others, and argues for forecasting their societal effects. The accompanying appendix material describes test domains and findings on how well LLMs follow solver-suggested actions.

Ethics Statement

  • Strategic agents may produce poor group outcomes or exploit others, motivating work toward agents that are both rational and high-welfare.The paper proposes simulation to study these interactions and inform constraints or regulation.Source: Ethics Statement · p. 9
  • The societal-impact discussion asks whether widespread LLM adoption could influence human dialogue and sentiment, and calls for forecasting those effects.It raises possible shifts in assertiveness and forward-thinking strategies as questions, not established outcomes.Source: Ethics Statement · p. 9

A.1 Debate Topics

  • The debate domain uses potentially contentious propositions as topics for practicing agreement and disagreement.Examples include whether alcohol should be illegal and whether breakfast is the most important meal of the day.Source: §A.1 · p. 13

A.2 Fruit Trading Game Prompts to LLMs

  • The fruit-trading appendix provides an example prompt and specifies a calm tone for the LLM’s response.The shown prompt includes a schedule-proposal message header.Source: §A.2 · p. 14

B.1 Steering Accuracy

  • Steering accuracy is assessed by asking a model to infer the instructed action from the LLM’s generated response.The appendix supplies the classifier instructions and reports success rates in tables.Source: §B.1 · p. 14

Debate: Classifier Instructions and Results

Fruit Trading: Classifier Instructions and Results

Meeting Scheduling: Classifier Instructions and Results

B.2 Example generations

Solver-guided LLMs often produce example generations that follow the suggested action, but some plausible responses do not. The appendix attributes these failures to the base model’s instruction-following ability and reports that the larger reward model generally outperforms the smaller one.

B.2 Example generations

  • Solver-guided LLMs often follow suggested actions in example generations, but some plausible outputs fail to match the instructed strategy.The paper attributes such failures to the base LLM’s instruction-following ability rather than the solver or pipeline.Source: §B.2 · p. 16, Table 6 · p. 17, Table 7 · p. 18

C LLM-based Reward Model

  • The appendix reports that PaLM2-L generally outperforms PaLM2-S as an LLM-based reward model.It evaluates successful and failed reward calculations.Source: C LLM-based Reward Model · p. 18

C.1 Additional Quantitative Reward Evaluation

The additional reward-model evaluation compares accuracy across outcome types and reports lower error with the larger model.

C.1 Additional Quantitative Reward Evaluation

  • The evaluation reports two accuracy metrics across three outcome types.The supplied table caption names Valid, Rejected, and Incomplete outcomes, plus an All average.Source: §C.1 · p. 19, Table 8 · p. 19
  • Increasing reward-model size from PaLM2-S to PaLM2-L significantly reduces error across Valid, Rejected, and Incomplete outcomes.The table also reports average error over all outcomes.Source: Table 8 · p. 19, §C.1 · p. 19

C.2 Qualitative Reward Model Evaluation

Qualitative examples show reward-model calculations can be correct but can also misread negotiation status or invent trade details. Additional PSRO analyses apply the Nash bargaining solution to fruit trading and meeting scheduling.

C.2 Qualitative Reward Model Evaluation

  • In another example, the reward model hallucinates a trade agreement during ongoing negotiations and misuses John’s blueberry valuation for Elroy.The example’s final messages indicate no agreement had been reached.Source: §C.2 · pp. 20–21
  • A generated message may offer an apple that the speaker does not have, an issue attributed to prompting the LLM to generate sensible messages.This occurs in the qualitative reward-model examples.Source: §C.2 · p. 22

D PSRO

  • The appendix repeats fruit-trading PSRO analysis with the Nash bargaining solution in place of CCE and also applies it to meeting scheduling.The Nash bargaining solution is described as a unique two-person solution satisfying scale invariance, symmetry, efficiency, and independence of irrelevant alternatives.Source: D PSRO · p. 22, Figure 4 · p. 22

D.1 PSRO: Additional Empirical Results

In fruit trading, the final Nash bargaining solution is calm while aggressive tones predominate under CCE; in meeting scheduling, assertive and happy tones dominate the final CCE. The appendix also describes alternative best-response searches, CFR-target imitation training, and configurable dialogue-game components.

D.1 PSRO: Additional Empirical Results

  • In fruit trading, calm is the final Nash bargaining action, while assertive, angry, and enthusiastic tones predominate under CCE and may yield less collective value than calm negotiation.The passage says both players may extract higher collective value if they remain calm.Source: §D.1 · pp. 22–23
  • In meeting scheduling, submissive starts with the highest CCE mass, but assertive and happy dominate the final iteration; Nash bargaining and CCE roughly agree at t = 3.Figure 5 tracks equilibria as approximate best-response candidates are added; Figure 6 adds the Nash bargaining solution.Source: §D.1 · p. 23, Figure 5 · p. 23, Figure 6 · p. 23

D.2 Best Response Algorithms

  • LLM-based best responses can search repeatedly for better strings, use ranked action-fitness information, or generate new action categories and candidates, avoiding costly RL or gradient-based optimization.The variants include a while-loop search, trajectory-aware candidate generation, and category-level search.Source: §D.2 · pp. 24–25

E Imitation Learning

  • The imitation policy is a two-hidden-layer neural network trained with cross-entropy against CFR target probabilities using Adam.Each hidden layer has 256 neurons; the batch size is 128 and the learning rate is 10−3.Source: E Imitation Learning · p. 25

F ChatGames

  • ChatGames configuration specifies action strings, rewards, private information, and a background prompt, binding dialogue interactions to a game tree.The action space can combine recipient and tone; game termination can be set by limiting replies or using LLM-based termination prompts.Source: F ChatGames · pp. 25, 27, 28
Loading 2402.01704v3…