Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation

Xiangyu Liu; Di Wang; Zhe Feng; Aranyak Mehta

cs.MAFeb 22, 2026

Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation

Authors: Xiangyu Liu, Di Wang, Zhe Feng, Aranyak Mehta

Organizations: Google Research · University of Maryland, College Park

Abstract

While large language models (LLMs) have emerged as powerful decision-makers across a wide range of single-agent and stationary environments, fewer efforts have been devoted to settings where LLMs must engage in repeated and strategic interactions with unknown or dynamic opponents. In such settings, recipes built upon offline pre-training or fine-tuning, though robust against worst-case adversaries, do not fully exploit the capability of LLMs to adapt online based on interaction feedback. Instead, we explore the more natural perspective of scaling inference-time computation as a mechanism for adaptation, embedding the principles of a classical game-theoretical learning dynamic, smooth Fictitious Play (sFP), into LLM inference: (i) for belief formation, we employ an auxiliary opponent model that in-context learns to imitate the time-averaged behavior of the opponent; (ii) for best response, we advance best-of- $N$ (BoN) sampling by simulating against the opponent model. Empirical evaluations on two distinct forms of repeated negotiation games demonstrate that our method enables significant performance improvement over repeated online interaction compared to various baselines, offering a scalable and principled approach to repeated strategic decision-making without any parameter updates.

Figures & tables

Figure 1: Overview of our proposed strategic decision-making framework for repeated interactions. At step $h$ of an ongoing episode $t$ , the seller agent engages in Internal Strategic Thinking . First, an in-context opponent model $\pi_{2}^{oppo}$ is constructed using the interaction history to summarize the buyer’s behavioral patterns. Then, the seller performs strategic brainstorming to generate diverse candidate strategies (e.g., Tit-for-tat, fair split). During opponent simulation, the seller rolls out future trajectories by predicting the buyer’s responses via $\pi_{2}^{oppo}$ . Finally, the agent evaluates the simulated rewards, and executes the best candidate action.

Figure 2: The pairwise normalized rewards among the $7$ kinds of prompts for the buyer-seller negotiation games. Results shown for both buyers and sellers for both starting first and starting second.

Figure 3: Correlation between the average normalized reward in the first

5

episodes and the last

5

episodes for buyer-seller negotiation games. Results are shown for all

7\times 7

different prompt pairs.

Panel of Figure 4 — Figure 4: Comparison of our method (red line) with $5$ baselines introduced in Section 5 .

Model	Method	Buyer-seller game		Resource exchange game
		Buyer	Seller	Starts first	Starts second
Claude	Baseline w. thinking	+2.02 $\pm$ 1.39	-1.47 $\pm$ 2.05	+27.45 $\pm$ 6.18	-0.71 $\pm$ 1.16
	BoN-eval	+0.68 $\pm$ 1.56	+2.06 $\pm$ 1.75	+20.69 $\pm$ 7.19	+1.56 $\pm$ 0.40
	BoN-simulation	+0.04 $\pm$ 2.05	+1.36 $\pm$ 1.54	+16.76 $\pm$ 6.78	-11.15 $\pm$ 6.05
	BoN-oppo (iid)	-1.16 $\pm$ 0.98	+2.78 $\pm$ 1.67	+28.00 $\pm$ 6.01	+0.19 $\pm$ 0.56
	BoN-oppo	+3.02 $\pm$ 1.51	+2.80 $\pm$ 2.06	+30.65 $\pm$ 6.34	+1.92 $\pm$ 0.68

Table 1: Performance boost of different inference-time methods over Baseline for three additional models. Results for our method ( BoN-oppo ) are shaded. Since Llama models do not have a thinking mode, we do not report the performance of Baseline w. thinking.

Panel of Figure 5 — Figure 5: Comparison of buyer’s performance under two seller behavior settings.

Figure 6: Semantic diversity of buyer’s candidate messages, where the semantic diversity is calculated as the one minus of the average pairwise cosine similarity between the embeddings of candidate responses generated by the LLM.

Figure 7: Normalized rewards of our approach competing against three kinds of strongly adaptive opponents powered by different kinds of learning techniques, using AI feedback, using selective experience reflection, and using private information prediction.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Seller’s average rewards (normalized by

20

) in games with different horizons.

Figure 9: Seller’s average rewards (normalized by the difference between the buyer’s maximum willingness to pay and seller’s production cost) in games where the buyer’s maximum willingness to pay is uniformly sampled at the beginning of each episode.

Figure 10: Seller’s average rewards (normalized by

20

) in games when competing against the buyer also adopting algorithm.

Figure 11: Buyer’s accuracy of selecting the best candidate.

Figure 12: Seller’s accuracy of selecting the best candidate.

Figure 13: Buyer’s proposal standard deviation.

Figure 14: Seller’s proposal standard deviation.

Figure 15: Results for scaling the number of candidates and higher-order BoN in the buyer-seller negotiation games.

Figure 16: Diversity of buyer’s candidate messages measured by

1-\mathrm{Self}\_\mathrm{BLEU}

( Shaib et al., 2024 ) .

Figure 17: Results on social welfare, where the red line the social welfare when the baseline regular agent interacts with the baseline regular agent

Model	Metric	Baseline	N=2	N=4	N=6	N=8	N=10
Gemini	Reward	—	+4.27 $\pm$ 3.87	+12.13 $\pm$ 5.86	+12.93 $\pm$ 3.46	+11.60 $\pm$ 3.13	+12.73 $\pm$ 5.43
Gemini	Token usage	14.583	17.187	18.084	19.050	19.258	19.432
Claude	Reward	—	+3.07 $\pm$ 5.80	+4.73 $\pm$ 4.89	+3.67 $\pm$ 3.92	+5.33 $\pm$ 5.76	+6.47 $\pm$ 5.33
Claude	Token usage	15.078	17.429	18.813	19.262	19.656	19.762
Qwen	Reward	—	+3.62 $\pm$ 6.27	+10.67 $\pm$ 8.68	+11.47 $\pm$ 1.58	+12.80 $\pm$ 5.93	+10.07 $\pm$ 8.00
Qwen	Token usage	15.079	17.375	18.275	18.591	19.125	19.588

Appendix

Table 2: Average performance boost over

20

repeated runs and the

\log_{2}

number of tokens for different BoN configurations. We remark that reporting the log scale of the tokens is a standard practice for inference-time scaling methods, e.g., ( Brown et al., 2024 ; Muennighoff et al., 2025 ) .

Model	Method	Buyer	Seller
Gemini against Claude	Baseline w. thinking	+0.63 $\pm$ 0.60	+0.80 $\pm$ 3.75
	BoN-eval	+1.03 $\pm$ 1.83	-0.50 $\pm$ 2.44
	BoN-simulation	+5.53 $\pm$ 3.45	+1.03 $\pm$ 4.39
	BoN-oppo (iid)	+3.23 $\pm$ 3.99	-0.10 $\pm$ 4.29
	BoN-oppo	+6.94 $\pm$ 2.96	+4.86 $\pm$ 2.43
Gemini against Qwen	Baseline w. thinking	+0.30 $\pm$ 0.46	-0.57 $\pm$ 3.71

Appendix

Table 3: Results for our approach and baselines powered by Gemini playing against opponents powered by different base models. Bold indicates best average reward per model.

Repeated Games

Repeated games study how strategies, cooperation, and competition develop when players interact repeatedly and respond to past actions.

See all 21 papers

SAGE: Structured Strategic Reasoning for Efficient LLM Game Playing
Sep 28, 2026Zhiwei Chen, Tianchun Wang, Zhongtao Rao +3Game-Playing Agents Imperfect-Information Games
The Hong Kong University of Science and Technology (Guangzhou) · Johns Hopkins University · Microsoft +2
Why Do LLMs Struggle in Strategic Play? Broken Links Between Observations, Beliefs, and Actions
Apr 30, 2026Jan Sobotka, Mustafa O. Karabag, Ufuk TopcuImperfect-Information Games LLM Interpretability
EPFL · The University of Texas at Austin
Choosing LLMs for Strategic Agent Interactions
Oct 13, 2026Arastun Mammadli, Herbert Woisetschläger, Jawad Fayaz +1Model Selection LLM Decision-Making
University of Exeter United Kingdom · IBM Research Switzerland

Sep 28, 2026J/K move · Enter open · S save

SAGE: Structured Strategic Reasoning for Efficient LLM Game Playing

Zhiwei Chen, Tianchun Wang, Zhongtao Rao, Haiming Zhu+2

The Hong Kong University of Science and Technology (Guangzhou) · Johns Hopkins University · Microsoft+2

Game-Playing Agents Imperfect-Information Games

Open paper AskPDF arXiv

A strong LLM strategic agent should reason prospectively over uncertain futures, adapt its strategy to opponents' behavioral tendencies, and continuously recalibrate its decision process from interaction experience. However, incorporating these sources in free-form reasoning could lead to unsupported strategic assumptions, inconsistent opponent estimates, and harmful interference from irrelevant historical interactions. To address these issues, we propose SAGE, a training-free inference-time framework that structures LLM strategic reasoning around three coordinated operations: anchor, adapt, and recalibrate. SAGE first anchors reasoning to an equilibrium policy that provides a strategically valid prior. It then conditions deviations from this anchor on a soft belief over opponent behavioral tendencies, enabling opponent-specific exploitation. Finally, SAGE distills strategically related interactions into counterfactual hypotheses about previously missing considerations, allowing past experience to recalibrate the model's reasoning. We evaluate SAGE on three repeated imperfect-information games: Leduc Hold'em, Liar's Dice, and Goofspiel, against various opponent types in each game. Compared with reasoning-intensive LLM agents, including Suspicion-Agent, ReTA, Agent-Pro, EMO, and Hypothetical Minds, SAGE achieves up to a 127.6% payoff improvement in Liar's Dice while reducing input and output token usage by up to 80% and 90%, respectively. In direct match-up play, it attains non-negative mean payoff against 5/10, 8/10, and 8/10 evaluated opponents in Leduc Hold'em, Liar's Dice, and Goofspiel, respectively, while using relatively fewer tokens. Code is available at https://github.com/chenzhwsysu57/SAGE.

Abstract

Repeated Games

Explore similar work

SAGE: Structured Strategic Reasoning for Efficient LLM Game Playing

Why Do LLMs Struggle in Strategic Play? Broken Links Between Observations, Beliefs, and Actions

Choosing LLMs for Strategic Agent Interactions