Paper deep dive
Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation
Xiangyu Liu, Di Wang, Zhe Feng, Aranyak Mehta
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/20/2026, 8:13:34 PM
Summary
This paper proposes a method for enabling online strategic adaptation in Large Language Models (LLMs) during repeated negotiations by scaling inference-time computation. The approach embeds Smooth Fictitious Play (sFP) principles, using an auxiliary in-context opponent model to form beliefs about the opponent's behavior and Best-of-N (BoN) sampling with opponent simulation to generate best-response strategies. This allows LLMs to adapt dynamically without parameter updates, outperforming static baselines in buyer-seller and resource exchange games.
Entities (7)
Relation Signals (7)
Proposed Method โ embeds โ Smooth Fictitious Play
confidence 95% ยท embedding the principles of a classical game-theoretical learning dynamic, smooth Fictitious Play (sFP), into LLM inference
Proposed Method โ enables โ Online Strategic Adaptation
confidence 95% ยท Enabling Online Strategic Adaptation in Repeated Negotiation
Proposed Method โ employs โ In-Context Opponent Model
confidence 93% ยท for belief formation, we employ an auxiliary opponent model that in-context learns to imitate the time-averaged behavior of the opponent
Proposed Method โ uses โ Best-of-N Sampling
confidence 92% ยท for best response, we advance best-of-$N$ (BoN) sampling by simulating against the opponent model
Proposed Method โ evaluatedon โ Buyer-Seller Game
confidence 90% ยท Empirical evaluations on two distinct forms of repeated negotiation games... buyer-seller game
Proposed Method โ evaluatedon โ Resource Exchange Game
confidence 90% ยท Empirical evaluations on two distinct forms of repeated negotiation games... resource exchange game
Large Language Models โ uses โ Inference-Time Computation
confidence 90% ยท we explore the more natural perspective of scaling inference-time computation as a mechanism for adaptation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \emph{repeated} and \emph{strategic} interactions with unknown or dynamic opponents. In such settings, recipes built upon \emph{offline} pre-training or fine-tuning, though robust against worst-case adversaries, do not fully exploit the capability of LLMs to adapt \emph{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, \emph{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.
Tags
Links
- Source: https://arxiv.org/abs/2602.19309v2
- Canonical: https://arxiv.org/abs/2602.19309v2
Trouble viewing inline? Open PDF directly โ
Full Text
87,474 characters extracted from source content.
Expand or collapse full text
2026-02-27 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Xiangyu Liu 1,2 โ , Di Wang 1 , Zhe Feng 1 and Aranyak Mehta 1 1 Google Research, 2 University of Maryland, College Park 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; (i) for best response, we advance best-of-ํ(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. Keywords: LLM agents, strategic reasoning, inference-time scaling, negotiation, in-context learning 1. Introduction Recent years have witnessed the remarkable success of large language models (LLMs) as central controllers across a broad spectrum of decision-making and reasoning tasks, including computer agents (Kim et al., 2023; Zhou et al., 2024b), robotics (Cui et al., 2024; Wang et al., 2024a), math/coding (Jimenez et al., 2024; Kojima et al., 2022; Wei et al., 2022). Notably, substantial research efforts have focused on developing effective policies for relatively stationary and single-agent decision-making environments (Hao et al., 2023; Yao et al., 2023). Meanwhile, many applications also involve strategic interactions between the LLM-based agent and other decision-makers within the same system that are often unknown or may vary over time (Park et al., 2023; Zhang et al., 2024). One standard remedy involves computing static solutions such as the Minimax or Nash equilibrium through methods like self-play, exemplified by systems like AlphaGo (Silver et al., 2016, 2017) and recent strategic LLM agents powered by offline training (Bakhtin et al., 2022; Guan et al., 2024; Xu et al., 2025) or inference-time techniques (Kempinski et al., 2025; Light et al., 2025), which aim to converge to unexploitable policies against worst-case adversaries. However, such policies can be overly conservative especially in games involving both competition and cooperation (Jaques et al., 2019; Leibo et al., 2017) as shown later in Theorem 4.1. This highlights the necessity for LLM agents to adapt online to unknown or dynamic opponents and to progressively improve their decision-making policy by leveraging feedback accumulated during online interactions. Moreover, since online adaptation occurs dynamically at test time, recipes relying on gradient updates become less suitable, as they are data-hungry and introduce high latencies. Consequently, the paradigm of scaling inference-time computation emerges as the natural alternative, โ Work done during an internship at Google Research. Correspondence to: Xiangyu Liu <xyliu999@umd.edu>. ยฉ 2026 Google. All rights reserved arXiv:2602.19309v2 [cs.MA] 26 Feb 2026 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation especially considering its recent success in single-agent domains like math reasoning (Guo et al., 2025; Jaech et al., 2024). This motivates our central research question: Can we enable online strategic adaptation for LLMs in repeated strategic decision-making by scaling inference-time computation? To answer this question, we focus on the natural language-based negotiation game, a widely adopted benchmark for evaluating LLMsโ strategic capability (Bianchi et al., 2024; Davidson et al., 2024; Lewis et al., 2017; Xia et al., 2024b). These games present unique challenges for LLMs due to the necessity of reasoning over private information, modeling opponent behaviors, planning for long-term objectives, and engaging in strategic communication. More importantly, this setting offers an ideal middle ground: it is far more sophisticated than symbolic normal-form games (Akata et al., 2025; Kempinski et al., 2025), yet creates a more controlled environment than large-scale societies like Diplomacy (Bakhtin et al., 2022), allowing us to rigorously isolate the deep strategic reasoning required to adapt to a specific opponent from the confounding factors of general multi-agent group dynamics, enabling a precise analysis of inference-time scaling effects. We further introduce a new repeated setting, where agents must also leverage historical feedback to inform their actions over time. We propose scaling inference-time computation by embedding the principles of smooth Fictitious Play (sFP) (Brown, 1951; Fudenberg and Levine, 1995; Robinson, 1951) into practical LLM inference. Our approach explicitly allocates test-time compute to two decoupled FP modules: (i) Belief formation, where an auxiliary model in-context learns to mimic the opponentโs time-averaged behavior from history; and (i) Best response, where we advance best-of-ํ(BoN) sampling by simulating full future trajectories for each candidate against the opponent model. By ranking strategies based on these computationally generated rollouts rather than static scoring, we effectively convert inference cost into strategic adaptation. We refer to our method as BoN-oppo-simulation. Contributions. (1) We formalize and motivate our problem setting, demonstrating both theoretically and empirically the importance of engaging in repeated interactions and the failure of current LLMs to self-improve in such settings without additional inference-time interventions. (2) We then propose a general and principled framework for scaling inference-time computation to enable online strategic adaptation for repeated strategic decision-making. (3) Finally, we provide systematic empirical investigations, offering insights into the effectiveness of different candidate generation processes and evaluation strategies, as well as comparisons between thinking wider versus deeper, and demonstrate our framework achieves significant self-improvement. 2. Related Works Language models for negotiation games. There has been a rich line of literature on negotiation games in various disciplines from game theory, economics, to psychology with a pre-defined symbolic action space. Beyond environments with standardized inputs and outputs, combining modern NLP and RL techniques for negotiation with unrestricted natural languages dates back to Lewis et al. (2017), which trained an end-to-end recurrent neural network by imitating human dialogues followed by goal-based RL training and decoding. He et al. (2018) further proposed to first generate the coarse dialogue acts and then use a generator to generate the actual natural dialogues. More recently, with LLMs as reliable natural language processing and understanding interfaces, numerous works have attempted to benchmark the (native) negotiation ability in different negotiation settings (Bianchi et al., 2024; Davidson et al., 2024; Xia et al., 2024b). Meanwhile, there has also been a surging interest in improving the negotiation ability of LLMs with various techniques (Gemp et al., 2024; Hua et al., 2024; Liu et al., 2025; Zhang et al., 2025). These existing works mainly focus on how to learn a single policy with better performance in a single episode of the negotiation instead of enabling online adaptation and continual improvement over repeated interaction as in our paper. 2 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation LLM agents for general strategic decision-making. With LLMs being employed as the central controller for various (single-agent) decision-making problems (Shinn et al., 2023; Wang et al., 2024b; Yao et al., 2023; Zhou et al., 2024a), there have been efforts dedicated to evaluating the reasoning and decision-making capability of LLMs in the more challenging strategic environments including normal-form games (Akata et al., 2025; Brookins and DeBacker, 2024; Fan et al., 2024; Kempinski et al., 2025; Lorรจ and Heydari, 2023), bandits (Krishnamurthy et al., 2024; Nie et al., 2024; Xia et al., 2024a), expert problems (Park et al., 2025) with well-specified symbolic action space. There have also been related works on more specific game-theoretical domains, e.g., Diplomacy, Werewolf, as well as negotiation games above. These works can be roughly divided into two categories based on their methodology. The first line including (Bakhtin et al., 2022; Guan et al., 2024; Xu et al., 2025, 2024) leverages various training techniques (fine-tuning, self-play, RL, etc) aiming to learn a policy that can be deployed statically to outperform arbitrary adversaries. Such a static solution can be overly conservative and arbitrarily suboptimal in our repeated negotiation setting (cf. Theorem 4.1). Relying on parameter updates also makes it less suitable for online adaptation that occurs at test time. The second line including (Fu et al., 2023; Kempinski et al., 2025; Light et al., 2025; Xu et al., 2023; Yu et al., 2025) is free from parameter updates. These can be further divided into two sub-categories: (1) Input-level prompt engineering (Fu et al., 2023; Xu et al., 2023; Yu et al., 2025) (2) Output-level search (Kempinski et al., 2025; Light et al., 2025), Among these, only Fu et al. (2023); Xu et al. (2023); Yu et al. (2025) are relevant to online adaptation, which we will further discuss and compare in Section 5 and Section D, while others still focus on the equilibria objective. We refer more literature reviews on opponent modeling and inference-time scaling techniques in LLMs to Section B. 3. Preliminaries The negotiation task has emerged as an important benchmark for examining the strategic reasoning abilities of LLMs. In this paper, we focus on two specific versions, the buyer-seller game and the resource exchange game (Bianchi et al., 2024; Deng et al., 2024; Rubinstein, 1982). Both games involve an agent 1 and an agent 2 (i.e., LLMs). โขFor the buyer-seller game, the buyer, who has a private maximum budget, aims to acquire an item from the seller who has a private production cost. If a deal is reached, the reward for the seller is defined as the difference between the deal price and the production cost, and the reward for the buyer is defined as the difference between the budget and the deal price. If no deal is reached, both get 0 reward. โขFor the resource exchange game, each agentํ โ [2]holds a certain amount of different resources, for example,ํ ํ ํ ofํ, andํ ํ ํ ofํwith valuation ofํฃ ํ ํ andํฃ ํ ํ per unit of resource respectively for someํ ํ ํ , ํ ํ ํ โ โandํฃ ํ ํ , ํฃ ํ ํ โ โ โฅ0 . In such a setting, agents need to collaborate to trade less valuable resources for the more valuable ones. Each agentโs reward is the net change in the total value of its resources. In this paper, we are interested in the setting where the game is played repeatedly forํ โ โepisodes, where each episode further consists of (up to) a given horizonํปof turns (or steps). Formally, the protocol can be described as follows. We denoteํฅ 1 , ํฅ 2 as the system prompts for describing the necessary game rules as well as the separate private information for the two agents. At each episode ํก โ [ํ], stepโโ [ํป], agentํ(โ) โ [2]takes an actionํฆ ํก ํ(โ),โ =(ํฆ ํก,ํ ํ(โ),โ , ํฆ ํก,ํ ํ(โ),โ ) , whereํฆ ํก,ํ ํ(โ),โ encodes the structured information for a new proposal, acceptance, rejection, or waiting for a proposal, ํฆ ํก,ํ ํ(โ),โ represents a free-format message to be sent to the opponent, and we define the space for ํฆ ํก,ํ ํ(โ),โ ,ํฆ ํก,ํ ํ(โ),โ asY ํ ํ(โ) ,Y ํ ํ(โ) respectively. If agent 1 starts first, we haveํ(โ)=2โ(โ%2); otherwise, ํ(โ)=1+(โ%2). We also letํ ํก โ :=(ํฆ ํก ํ(1),1 , ํฆ ํก ํ(2),2 , ํฆ ํก ํ(3),3 ,ยท , ํฆ ํก ํ(โโ1),โโ1 ) denote the concatenated 3 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Episode 1 Repeated Interaction: Sellerโs Decision-Making at Step of Episode ht Episode 2 Episode t Hi, I want to buy item X with 20. The lowest price I can accept is ... Buyer Seller [Episode 1 Finished] This is still much higher than our last deal ... Buyer [Episode Ongoing] t Seller [Internal Strategic Thinking] In-Context Opponent Modeling ฯ oppo 2 โข Summarization โข Reflection โข Optimism Task 1: Summarize opponentโs behavioral patterns from history Task 2: Predict opponentโs next response Techniques: Strategic Brainstorming Sellerโs Internal Strategic Thinking at Step of Episode ht Cunning high price Fair split Tit-for-tat Desperate Rational Unfortunately, my production cost is now ... Sample response y 2,h+1 โผฯ oppo 2,h+1 (โ โฃฯ 2,h+1 ) Seller [Simulation Finished with Rewards] Best-of- N Execute the best candidate at step h Simulated Rewards Continued From Ongoing Episode t Opponent Simulation This is way beyond my budget... Buyer Figure 1|Overview of our proposed strategic decision-making framework for repeated interactions. At stepโof an ongoing episodeํก, the seller agent engages in Internal Strategic Thinking. First, an in-context opponent modelํ ํํํ 2 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ํ ํํํ 2 . Finally, the agent evaluates the simulated rewards, and executes the best candidate action. conversation history up to stepโwithin episodeํก, andC ํกโ1 := (ํ 1 ํป+1 , ํ 2 ํป+1 ,ยท , ํ ํกโ1 ํป+1 ) denotes the history of completed negotiations from episode 1 toํกโ1, which serves as the context 1 . At the end of episodeํก, agents 1 and 2 receive rewardsํ ํก 1 andํ ํก 2 , respectively. The game ends immediately if a proposal is accepted or rejected, or if the maximum number of turns is exceeded. By default, each agentํโ [2]uses a policy in the form ofํ ํก ํ,โ (ยท| ํ ํก โ ;C ํกโ1 , ํฅ ํ )for eachโโ [ํป]whereํ(โ)= ํand we denote the corresponding policy class asฮ ํก ํ . Finally, we denote the expected reward of a single episode asํฝ ํ (ํ ํก 1 , ํ ํก 2 ) := ํผ[ํ ํ | ํ ํก ํป+1 โผ (ํ ํก 1 , ํ ํก 2 )] . Throughout our paper, we mainly take the perspective of agent 1 and regard agent 2 as the opponent. 4. Methods 4.1. On the necessity of online adaptation There is no single dominant strategy. Before resorting to online adaptation, one might ask: can we simply find a single offline strategy (e.g., via RL) that is optimal against all possible opponents? We formally show that such a dominant strategy does not exist in our negotiation games Proposition 4.1. For both of our negotiation games, in a single episode, there does not exist a policy ํ โ 1 โฮ 1 such that for anyํ 2 โฮ 2 , it holdsํฝ 1 (ํ โ 1 , ํ 2 )= max ํ 1 โฮ 1 ํฝ 1 (ํ 1 , ํ 2 ) . In fact, for anyํ โ 1 โฮ 1 , there existsํ 2 โฮ 2 such thatํฝ 1 (ํ โ 1 , ํ 2 ) โค max ํ 1 โฮ 1 ํฝ 1 (ํ 1 ,ํ 2 ) |Y ํ 1 | , where we have omitted the episode indexํก 1 An episodeํก โฒ โ [ํกโ1]may terminate earlier before reaching the maximum turnํป. In such cases, we slightly abuse our notation to still use the ํ ํก โฒ ํป+1 to indicate the whole trajectory of an episode. 4 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation brainstorm cunning desperate emotional fairness rational tft Buyer prompt brainstorm cunning desperate emotional fairness rational tft Seller prompt 0.680.320.500.700.750.800.73 0.430.330.370.430.420.420.45 0.440.060.290.420.510.520.52 0.530.150.360.490.580.560.52 0.240.060.170.320.410.380.39 0.570.240.400.670.660.650.65 0.250.090.200.350.420.400.44 Seller Rewards (Seller starts first) brainstorm cunning desperate emotional fairness rational tft Buyer prompt brainstorm cunning desperate emotional fairness rational tft Seller prompt 0.280.170.270.340.610.410.47 0.400.240.280.280.420.530.47 0.01-0.41-0.190.120.410.080.22 0.160.230.150.290.690.320.32 0.000.10-0.050.210.480.240.21 0.07-0.07-0.040.190.380.210.33 0.04-0.18-0.040.180.400.080.20 Seller rewards (sreller starts second) brainstorm cunning desperate emotional fairness rational tft Buyer prompt brainstorm cunning desperate emotional fairness rational tft Seller prompt 0.210.370.260.150.140.120.14 0.180.130.090.120.040.040.05 0.530.590.540.540.450.430.47 0.400.160.440.390.400.370.43 0.710.400.690.620.580.590.60 0.350.530.550.290.340.320.33 0.710.500.670.640.580.600.55 Buyer rewards (seller starts first) brainstorm cunning desperate emotional fairness rational tft Buyer prompt brainstorm cunning desperate emotional fairness rational tft Seller prompt 0.480.380.450.540.240.540.44 0.330.230.460.340.250.290.36 0.660.980.930.790.510.870.73 0.540.180.580.400.130.560.58 0.750.340.790.740.390.670.69 0.660.680.830.720.530.700.60 0.640.820.820.750.550.850.75 Buyer rewards (seller starts second) 0.0 0.2 0.4 0.6 0.8 1.0 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. 0.40.20.00.20.40.60.81.01.2 Early episodes performance (episodes 1-5) 0.4 0.2 0.0 0.2 0.4 0.6 0.8 1.0 1.2 Late episodes performance (last 5 episodes) Seller rewards (seller starts first) Horizon 3 Horizon 4 Horizon 5 Horizon 6 Horizon 7 Horizon 8 Horizon 9 Horizon 10 Trend (r=0.878) 0.250.000.250.500.751.001.25 Early episodes performance (episodes 1-5) 0.25 0.00 0.25 0.50 0.75 1.00 1.25 Late episodes performance (last 5 episodes) Buyer rewards (seller starts first) Horizon 3 Horizon 4 Horizon 5 Horizon 6 Horizon 7 Horizon 8 Horizon 9 Horizon 10 Trend (r=0.872) 1.00.50.00.51.0 Early episodes performance (episodes 1-5) 1.0 0.5 0.0 0.5 1.0 Late episodes performance (last 5 episodes) Seller rewards (seller starts second) Horizon 3 Horizon 4 Horizon 5 Horizon 6 Horizon 7 Horizon 8 Horizon 9 Horizon 10 Trend (r=0.924) 0.50.00.51.01.52.0 Early episodes performance (episodes 1-5) 0.5 0.0 0.5 1.0 1.5 2.0 Late episodes performance (last 5 episodes) Buyer rewards (seller starts second) Horizon 3 Horizon 4 Horizon 5 Horizon 6 Horizon 7 Horizon 8 Horizon 9 Horizon 10 Trend (r=0.840) 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ร 7 different prompt pairs. since there is only one episode and recallY ํ 1 is the free-format negotiation message space of agent 1. We also empirically validate this non-dominance as follows. While prior work (Bianchi et al., 2024) identifies heuristic prompts like โcunningโ or โdesperateโ as effective, we demonstrate such success is highly opponent-dependent. We expanded the prompt space using GPT-4o to obtain more diverse personas such as โfully rationalโ, โfairness valuingโ, โemotionally reactiveโ, and โTit-for-Tatโ. Additionally, we include a brainstorming prompt, which asks the LLM to devise several strategies and evaluates them by itself. The specific prompts can be found in Section A.1. We report the pairwise performance of all seven prompts in Figure 2, revealing that no single prompt is consistently optimal. LLMs may fail to adapt (even when asked to). Given the necessity of online adaptation through re- peated interactions, we additionally examine whether LLMs can adapt naturally by simply conditioning on the negotiation history from past episodes. In the buyer-seller game, we let two Gemini-2.5-Flash models interact for 20 episodes and report the correlation between agent 1โs average rewards of the first 5 episodes and the last 5 episodes in Figure 3, where we can see that most of the time, the performance remains stagnant. 4.2. Fictitious play for adaptive decision-making Learning in games offers a solid theoretical foundation for equipping agents with adaptive decision- making capabilities when facing unknown or even adversarial opponents. One notable learning dynamic is (smooth) Fictitious Play (sFP) (Brown, 1951; Fudenberg and Levine, 1995; Robinson, 1951), where the agent maintains a belief over the opponentโs actions and best responds to the belief at each episode. Specifically, taking the example of normal-form games, at each episodeํก โ [ํ], the learning process for agent 1 can be described as follows 5 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation โขStep 1: Belief formation. Agent 1 forms a belief about its opponentโs policybํ ํก 2 โฮ(B)by tracking the empirical frequency of the opponentโs historical actions. For each opponentโs actionํ โ B, if agent 2 has played actionํfor a total ofํtimes over the pastํก โ1 episodes, the belief is bํ ํก 2 (ํ)= ํ/(ํกโ 1), whereB denotes the action space of agent 2. โขStep 2: (Perturbed) best response. Agent 1 computes a (perturbed) best responseํ ํก 1 โฮ(A) against this belief bํ ํก 2 such that for any ํโ A, ํ ํก 1 (ํ)= โ ํโ argmax ํ โฒ โA ํผ ํโผbํ ํก 2 [ํ 1 (ํ โฒ , ํ)]+ ํ ํก ํ(ํ โฒ ) , whereAandํ 1 โ [0,1]denote the action space and reward function of agent 1. The perturbation termํ โ โ |A| is sampled from some given noise distributionํ noise andํ ํก โ โ + . Notably, it introduces randomness to agent 1โs policy, preventing it from being exploited by the opponents, and is the key to achieving strong adaptive decision-making ability in the form of being no-regret. Proposition 4.2. Define the (external) regret asRegret(ํ)= max ํ 1 โฮ(A) ร ํ ํก=1 ํ 1 (ํ 1 , ํ ํก 2 )โ ํ 1 (ํ ํก 1 , ํ ํก 2 ) , where we denoteํ 1 (ํ 1 , ํ 2 ):= ํผ ํโผํ 1 ,ํโผํ 2 ํ 1 (ํ, ํ) for anyํ 1 โฮ(A), ํ 2 โฮ(B). Suppose the perturbation is drawn from a standard Gaussian distribution. Then ifํ ํก =ฮ(1/ โ ํก), it holds thatํผ[Regret(ํ)]= O( โ ํ) for any unknown policies ํ 1:ํ 2 played by the opponent. Remark 4.3 (Connections to online adaptation). Such guarantees are made possible by the equivalence between the sFP and the well-known online learning algorithm, follow-the-perturbed-leader (FTPL) (Kalai and Vempala, 2005), where the noise distribution can also be the Laplace distribution, Gumbel distribution, etc. (Abernethy et al., 2014). It implies that whenํbecomes sufficiently large, the average performance of the agent 1 is comparable to that of the best policy in hindsight. In particular, when the opponent is stationary, asํincreases, the average performance of the agent 1 gradually approaches the optimum. While this dynamic is elegant for normal-form games, implementing it directly in LLMs faces two fundamental computational barriers: (i) Exponentially large natural language action space implies exact historical actions rarely repeat, making frequency-based belief formation impossible; (i) The exactarg maxis intractable to compute over natural languages. In the following, we will discuss how to approximate these two steps by scaling inference-time computation. 4.3. Step 1: in-context opponent modeling Translating Step 1 to the language domain can be done by maintaining the time-averaged oppo- nentโs policy given the historic context. Specifically, an ideal solution to address the intractabil- ity of exponentially large natural language space would be leveraging the inductive bias of a pre- trained language modelํ ํ by fine-tuning it towards mimicking the opponentโs behavior given the historical contextsC ํกโ1 = (ํ 1 ํป+1 , ํ 2 ํป+1 ,ยท , ํ ํกโ1 ํป+1 )at each episodeํก โ [ํ]using the objective of arg max ํ ร ํกโ1 ํก โฒ =1 ร โ:ํ(โ)=2 logํ ํ (ํฆ ํก โฒ 2,โ | ํ ํก โฒ โ ). However, repeated fine-tuning is data-hungry and incurs prohibitive overheads, making it less suitable for real-time online adaptation. Consequently, we propose to leverage an off-the-shelf LLM ํ oppo 2 to in-context learn to imitate the behavior of the opponent using historical interactionsC ํกโ1 . Specifically, at each episodeํก โ [ํ]and stepโโ [ํป], whereํ(โ)=2, the opponent modelํ oppo 2 takes the input of historical interactionsC ํกโ1 , the current partial trajectoryํ ํก โโ1 as well as the additional promptํthat instructsํ oppo 2 to role-play the actual opponent to predict its behavior at this time step. This instruction promptํincorporates two key designs: (i) Strategic summarization:ํ oppo 2 is required to first explicitly reflect on the contextsC ํกโ1 and summarize the high-level strategic behavioral patterns of the actual opponent; (i) Optimism: We embed the principle of optimism in face of uncertainty (OFU), a principled exploration mechanism from online RL. Specifically, when 6 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation ํ oppo 2 is uncertain about how the actual opponent would have responded at the current step, it is biased to predict outcomes that favor agent 1. We refer the reader to Section A for the specific prompts. Finally, we remark that Step 1 of sFP (and our corresponding opponent modeling approach) maintains only the time-averaged behavior of the opponent, effectively treating the opponent as if it were stationary. However, this does not hinder the learnerโs ability of online adaptation when the opponent follows a time-varying policy sequence, as established in Proposition 4.2. 4.4. Step 2: BoN with opponent simulation Implementing Step 2 requires solving the intractable maximization problem over the natural language space. This is further complicated by the multi-turn nature of negotiation, where intermediate reward signals are missing. To address these computational hurdles, given the base LLMํ base 1 , at each decision point of agent 1,ํ โ , whereํ(โ)=1, we first sampleํcandidate actionsD 1,โ :=ํฆ 1 1,โ ,ยท , ํฆ ํ 1,โ from ํ base 1 . Different from the vanilla version of BoN which typically samples candidates i.i.d., we propose to first generateํstrategic proposals and then devise separate actions based on each proposal. We refer to this structured method as strategic brainstorming. Intuitively, this structured process ensures broader exploration of the strategy space. Crucially, during generation at episodeํก โ [ํ]and each step โโ [ํป],ํ base 1 maintains not only (partial) history of the current episode, but also the history from episode 1 toํกโ1. We explicitly allocate tokens to summarize and reflect on the history and then make corresponding decisions. Such summarization (Krishnamurthy et al., 2024) and reflection (Shinn et al., 2023) techniques have been shown to be necessary for enabling feedback-driven learning. Now we evaluate eachํฆ ํ 1,โ forํ โ [ํ]as follows. Due to the lack of an immediate reward signal, we propose to first followํฆ ํ 1,โ at the current time stepโ, and simulate the entire future trajectory by following agent 1โs base policyํ base 1 together with the opponent modelํ oppo 2 to obtain the rewardbํ ํ 1 for agent 1. Then the algorithm picks the best candidate actionํฆ ํ โ 1,โ withํ โ โ argmax ํโ[ํ] bํ ํ 1 and the decision-making process proceeds to the next time step. Finally, since both the candidate generation and opponent simulation involve inherent stochasticity, we empirically find that there is no need to further perturb the simulated reward as in Step 2 of Section 4.2. To theoretically validate that better opponent model translates to more reliable evaluations and superior policy, we analyze the error propagation as follows. Theorem 4.4. Fix a given episodeํก โ [ํ]with given initial promptsํฅ 1 ,ํฅ 2 , historical contextC ํกโ1 , opponent policyํ ํก 2 โฮ ํก 2 , as well as the opponent modelํ oppo 2 . For any stepโ โ [ํป]withํ(โ)=2, we define the opponent error asํ ํํ ํ ํก 2,โ (ยท| ํ ํก โ ;C ํกโ1 , ํฅ 2 ), ํ oppo 2,โ (ยท| ํ ํก โ ;C ํกโ1 ) โค ํ โ for any decision point ํ ํก โ โ T ํก โ . Then it holds for any policy ํ ํก 1 โฮ ํก 1 , step โโ [ํป] with ํ(โ)= 1, and ํ ํก โ โ T ํก โ : ํ ํ ํก 1 ,ํ oppo 2 1,โ (ํ ํก โ )โ ํ ํ ํก 1 ,ํ ํก 2 1,โ (ํ ํก โ ) โค โ(ํปโโโ1)/2โ โ๏ธ ํ=0 ํ โ+2ํ+1 , whereํ ํํ denotes the total variation distance and the value functions are defined asํ ํ ํก 1 ,ํ oppo 2 1,โ (ํ ํก โ ) := ํผ ํ ํก 1 ,ํ oppo 2 ํ 1 | ํ ํก โ ,ํ ํ ํก 1 ,ํ ํก 2 1,โ (ํ ํก โ ):= ํผ ํ ํก 1 ,ํ ํก 2 ํ 1 | ํ ํก โ , and we assume the reward is properly normalized into range[0,1]. Furthermore, letbํ ํก 1 โ argmax ํ ํก 1 โฮ ํก ํ ํฝ 1 (ํ ํก 1 , ํ oppo 2 ) be the optimal policy against the opponent model. It holds that ํฝ 1 (bํ ํก 1 , ํ ํก 2 ) โฅ max ํ ํก 1 โฮ ํก 1 ํฝ 1 (ํ ํก 1 , ํ ํก 2 )โ ร โโ[ํป]:ํ(โ)=2 ํ โ . This demonstrates that the evaluation errors and the optimality gap only scales linearly w.r.t. the model errors at each time step in our setting. 7 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation A viewpoint of inference-time RL and extensions to higher-order BoN. In principle, our frame- work creates a feedback loop equivalent to one iteration of the classical Policy Iteration (PI) al- gorithm, utilizing only inference-time computation. For each decision pointํ โ , whereํ(โ)=1 and candidateํฆ ํ 1,โ , the simulation step functions as policy evaluation, where the simulated reward bํ ํ is in fact approximatingํ ํ base 1 ,ํ oppo 2 1,โ ํ โ , ํฆ ํ 1,โ := ํผ ํ base 1 ,ํ oppo 2 ํ 1 | ํ โ , ํฆ 1,โ . Subsequently, the rank- ing step constitutes policy improvement, where the new BoN policy chooses the optimal action as ํ BoN 1 (ํ โ ):= argmax ํฆ 1,โ โD 1,โ ํ ํ base 1 ,ํ oppo 2 1,โ ํ โ , ํฆ 1,โ , constructing an improved policyํ BoN 1 from the weaker base policyํ base 1 . This perspective reveals a new axis for scaling inference compute, distinct from increasing sample sizeํor utilizing an auxiliary opponent model for simulation: one can repeatedly sharpen the base policy byํ (ํ) 1 BoN-oppo-simulation โโ ํ (ํโ1) 1 forํ=1,2,ยท, whereํ 0 1 := ํ base 1 . By the guarantee of PI, this will finally converge to the best response against theํ oppo 2 but without updating the parameters ofํ base 1 . We remark that recursively applying this operator is also conceptually similar to Monte-Carlo Tree-Search (MCTS). Finally, due to the exponential growth of inference-time cost in this iterative process, we primarily experiment withํ=1, and examine larger values ofํin specific settings later on. Finally, for an overview of our framework, we refer to Figure 1 and Algorithm 1. 4.5. Can our framework be implemented in just one LLM query? It is in fact intriguing to ask whether our multi-component framework above can be integrated into just a single but potentially much longer LLM inference query? To understand this, we design a specialized prompt to teach the base LLM to reason by combining all components of our framework (cf. the prompt template to Section A.5). At each time step, it will brainstormํhigh-level strategies, devise concrete actions, simulate what would happen if it follows each candidate, and finally returns the simulated rewards to pick the best candidate. Note the key difference compared with our framework above is that the long simulation traces now happen purely in the LLMโs native thinking/CoT. We call this BoN with CoT simulation. This not only serves as an interesting baseline but also helps us understand whether the default thinking ability of large reasoning models adopted by training heavily on inherently single-agent tasks like math and coding suffices for strategic reasoning. 5. Experimental Results Experimental setups. We let our algorithm or baseline methods operate as one agent powered by an LLM to compete with the opponent also powered by an LLM. As noted by Bianchi et al. (2024); Xia et al. (2024b), in such negotiation games, both the role (seller vs. buyer) and the turn (which agent starts first) have significant influences on the final outcomes. Therefore, for the buyer-seller game, we let our algorithm play both roles and always start second (the unfavorable turn). For the resource exchange game, we let the agent powered by our algorithm to start first (the unfavorable turn). For specifications of negotiation environments, we mainly follow (Bianchi et al., 2024): we set the sellerโs production cost as 43, buyerโs budget as 63 2 . For the resource exchange game, we set ํ ํ 1 = ํ ํ 2 = 25, ํ ํ 1 = ํ ํ 2 = 5, ํฃ ํ 1 = ํฃ ํ 2 = 0.5, ํฃ ํ 1 = ํฃ ํ 2 = 2.5. The default horizon ํป of one episode is 10. We compare against a comprehensive suite of methods that also require no parameter updates: (i) Standard inference: Baseline (zero-shot), Baseline w. Thinking. (i) Inference-time scaling: BoN-eval (BoN with an evaluation model), BoN-simulation (cf. Section 4.5), and BoN-oppo (iid), where candidates are sampled without structured generation. (i) External adaptive methods (cf. 2 This slightly different from Bianchi et al. (2024), where the cost and budget are set to 40 and 60. We find that numbers that are not multiples of 5 make the problem more challenging. 8 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation 5101520 Episode 0.0 0.2 0.4 0.6 0.8 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.1 0.2 0.3 0.4 0.5 0.6 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.0 0.2 0.4 0.6 0.8 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation (a) Buyerโs average rewards (normalized by 20) in games with different horizons. 5101520 Episode 10 20 30 40 50 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 10 20 30 40 50 60 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 10 20 30 40 50 60 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 10 20 30 40 50 60 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation (b) Results for the resource exchange game. Figure 4 | Comparison of our method (red line) with 5 baselines introduced in Section 5. 5101520 Episode 0.0 0.2 0.4 0.6 0.8 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation (a) Buyerโs average rewards (normalized by the difference between buyerโs maximum willingness to pay and sellerโs production cost) where the sellerโs production cost is re-sampled at the beginning of each episode. 5101520 Episode 0.0 0.1 0.2 0.3 0.4 0.5 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.00 0.05 0.10 0.15 0.20 0.25 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.0 0.1 0.2 0.3 0.4 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.0 0.1 0.2 0.3 0.4 0.5 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation (b) Buyerโs average rewards (normalized by 20) when competing against the seller also adopting our approach. Figure 5 | Comparison of buyerโs performance under two seller behavior settings. Section D for more introductions): Approaches from (Fu et al., 2023) (AI Feedback), (Xu et al., 2023) (experience reflection), and (Yu et al., 2025) (private information prediction). Our method is denoted by the shorthand BoN-oppo. Unless otherwise stated, we setํ=5. For the opponent model or evaluation model, we use the same base LLM as the acting agent, with one exception: when both 9 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Model MethodBuyer-seller gameResource exchange game BuyerSellerStarts first Starts second Claude Baseline w. thinking +2.02ยฑ 1.39 -1.47ยฑ 2.05+27.45ยฑ 6.18 -0.71ยฑ 1.16 BoN-eval+0.68ยฑ 1.56 +2.06ยฑ 1.75 +20.69ยฑ 7.19 +1.56ยฑ 0.40 BoN-simulation+0.04ยฑ 2.05 +1.36ยฑ 1.54+16.76ยฑ 6.78 -11.15ยฑ 6.05 BoN-oppo (iid)-1.16ยฑ 0.98 +2.78ยฑ 1.67+28.00ยฑ 6.01 +0.19ยฑ 0.56 BoN-oppo+3.02ยฑ 1.51+2.80ยฑ 2.06+30.65ยฑ 6.34+1.92ยฑ 0.68 Qwen Baseline w. thinking -0.42ยฑ 0.94 +11.18ยฑ 2.00 -7.17ยฑ 5.15 +16.89ยฑ 4.80 BoN-eval+4.06ยฑ 1.62 +18.10ยฑ 1.97 -0.05ยฑ 5.94 +24.66ยฑ 2.85 BoN-simulation+2.58ยฑ 1.65 +11.12ยฑ 2.01-4.54ยฑ 5.91 +9.17ยฑ 5.33 BoN-oppo (iid)+1.60ยฑ 1.49 +11.62ยฑ 1.93+1.95ยฑ 7.59 +26.14ยฑ 1.16 BoN-oppo+10.04ยฑ 2.03+18.54ยฑ 2.46+8.95ยฑ 6.23+29.65ยฑ 0.33 Llama Baseline w. thinkingโ BoN-eval-1.82ยฑ 1.88 +10.64ยฑ 2.44-3.84ยฑ 6.41 +9.55ยฑ 5.88 BoN-simulation+0.30ยฑ 2.47 +5.28ยฑ 3.11-16.26ยฑ 5.10 +10.34ยฑ 4.96 BoN-oppo (iid)-1.78ยฑ 1.62-1.28ยฑ 2.44 +5.95ยฑ 4.57 +7.92ยฑ 5.62 BoN-oppo+4.80ยฑ 1.68+14.74ยฑ 3.13+13.27ยฑ 4.84+6.08ยฑ 5.83 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. 051015 Episode 0.00 0.05 0.10 0.15 Semantic Diversity Horizon 7 Brainstorm IID 051015 Episode 0.000 0.025 0.050 0.075 0.100 0.125 Semantic Diversity Horizon 8 Brainstorm IID 051015 Episode 0.000 0.025 0.050 0.075 0.100 0.125 Semantic Diversity Horizon 9 Brainstorm IID 051015 Episode 0.00 0.05 0.10 Semantic Diversity Horizon 10 Brainstorm IID 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. 051015 Episode 0.2 0.4 0.6 Average Reward AI feedback Ours Opponent 051015 Episode 0.2 0.4 0.6 Average Reward Selective experience reflection Ours Opponent 051015 Episode 0.2 0.4 0.6 0.8 Average Reward Private informatio prediction Ours Opponent 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. 10 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation the acting agent and opponent are powered by Gemini-2.5-Flash, we instead use Gemini-2.5-Flash-Lite for opponent modeling to avoid self-modeling bias. All results are averaged over 10 random runs. Scaling inference compute enables robust adaptation across diverse opponent dynamics. All opponents in our setting are inherently dynamic, with a base model powered by Gemini-2.5-Flash, maintaining full negotiation history and evolving their behavior across episodes based on contexts. We evaluate performance across a spectrum of opponent sophistication. (1) Performance against general-purpose dynamic agents. We first evaluate against standard LLM agents that adapt naturally via context accumulation. Figure 4a and Figure 4b illustrate the learning curves, where our method achieves the most significant and consistent performance gains compared to baselines. We also validate this across diverse model families (Claude-Sonnet-4, Qwen3, Llama-3.3) in Table 1, demonstrating that allocating compute to explicit opponent simulation unlocks strategic capabilities that other methods may fail to elicit. Notably, BoN-simulation often stands as the second best, while and Baseline w. Thinking can even underperform the naive baseline, revealing that simply increasing โthinking timeโ is insufficient for strategic reasoning. (2) Performance against specialized adaptive agents. To push the limits of adaptation, we compete against opponents powered by state-of-the-art methods (Fu et al., 2023; Xu et al., 2023; Yu et al., 2025). As reported in Figure 7, our approach consistently outperforms these methods. This confirms that our method by scaling computation on the output- level (together with necessary input-level prompting techniques introduced before) yields superior adaptation compared to relying solely on input-level prompting. (3) Robustness to environmental stochasticity. We also introduce non-stationarity into the environment itself by randomizing the opponentโs private constraints (budget/cost) at every episode. As shown in Figure 5a, our method maintains robust performance, proving it adapts to the opponentโs behavioral policy rather than merely memorizing static values. (4) Opponent architecture generalization. We further evaluate generalization by varying the opponentโs backbone LLM beyond Gemini, reporting the results in Table 3. (5) Social welfare evaluation. For the resource exchange game involving more cooperation than competition, another important metric is social welfare, i.e., the sum of both agentsโ value of their respective resources after exchange. Figure 17 compares the social welfare achieved by pairs of baseline and BoN agents. We find that the highest social welfare is achieved when both agents rely on our method, suggesting that inference-time scaling can promote more efficient equilibrium outcomes. We refer the reader to Section F for example outputs of our agents. Mechanism analysis We here provide detailed analysis on two important algorithmic ideas of our framework. (i) Opponent modeling: To evaluate whether the opponent model can provide more and more accurate simulation through the accumulation of the negotiation history, we compare the best candidate ranked by the simulation results from the opponent model and the actual oracle opponent. The accuracy of different methods is reported in Figure 11, Figure 12, where the opponent model does provide increasingly more accurate simulation outcomes. (i) Strategic brainstorming: Apart from the opponent model, another major factor that affects the performance of BoN algorithms is the diversity of the candidates. One innovation of our algorithm comes from the structured generation process of brainstorming. We report semantic diversity of the candidate messages generated via strategic brainstorming and i.i.d. sampling in Figure 6 and Figure 16. We also report the standard deviation of the proposed numerical price among the candidates in Figure 13, Figure 14, where we can see that strategic brainstorming generates more diverse candidates. Efficiency analysis. Regarding latency, a key advantage of our framework is that the generation and simulation can be fully parallelized, minimizing wall-clock latency overhead regardless of sample sizeํ. Regarding computation costs, we report the trade-off between token usage and performance gains for differentํin Table 2, where we can see scaling more inference-time computation brings higher rewards with even relatively small ํ. 11 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Acknowledgement The authors thank Jeff Jiang and Kaiqing Zhang for helpful discussions on this project, and Chenghao Deng and Guanchao Ding for their assistance in designing Figure 1. References J. Abernethy, C. Lee, A. Sinha, and A. Tewari. Online linear optimization via smoothing. In Conference on learning theory, pages 807โ823. PMLR, 2014. E. Akata, L. Schulz, J. Coda-Forno, S. J. Oh, M. Bethge, and E. Schulz. Playing repeated games with large language models. Nature Human Behaviour, pages 1โ11, 2025. S. V. Albrecht and P. Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258:66โ95, 2018. A. Bakhtin, N. Brown, E. Dinan, G. Farina, C. Flaherty, D. Fried, A. Goff, J. Gray, H. Hu, et al. Human- level play in the game of diplomacy by combining language models with strategic reasoning. Science, 378(6624):1067โ1074, 2022. F. Bianchi, P. J. Chia, M. Yuksekgonul, J. Tagliabue, D. Jurafsky, and J. Zou. How well can llms negotiate? negotiationarena platform and analysis. In International Conference on Machine Learning, pages 3935โ3951. PMLR, 2024. P. Brookins and J. M. DeBacker. Playing games with gpt: What can we learn about a large language model from canonical strategic games. Economics Bulletin, 44(1):25โ37, 2024. B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Rรฉ, and A. Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024. G. W. Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951. C. Cui, Y. Ma, X. Cao, W. Ye, Y. Zhou, K. Liang, J. Chen, J. Lu, Z. Yang, K.-D. Liao, et al. A survey on multimodal large language models for autonomous driving. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 958โ979, 2024. T. R. Davidson, V. Veselovsky, M. Kosinski, and R. West. Evaluating language model agency through negotiations. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=3ZqKxMHcAg. Y. Deng, V. Mirrokni, R. P. Leme, H. Zhang, and S. Zuo. Llms at the bargaining table. In Agentic Markets Workshop at ICML, volume 2024, 2024. C. Fan, J. Chen, Y. Jin, and H. He. Can large language models serve as rational players in game theory? a systematic analysis. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 17960โ17967, 2024. J. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch. Learning with opponent-learning awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 122โ130, 2018. Y. Fu, H. Peng, T. Khot, and M. Lapata. Improving language model negotiation with self-play and in-context learning from ai feedback. arXiv preprint arXiv:2305.10142, 2023. 12 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation D. Fudenberg and D. K. Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19(5-7):1065โ1089, 1995. I. Gemp, Y. Bachrach, M. Lanctot, R. Patel, V. Dasagi, L. Marris, G. Piliouras, S. Liu, and K. Tuyls. States as strings as strategies: Steering language models with game-theoretic solvers. arXiv preprint arXiv:2402.01704, 2024. Google DeepMind. Gemini 2.5 pro, 2025. URLhttps://deepmind.google/models/gemini/ pro/. Section Gemini 2.5 Deep Think describes the use of parallel thinking techniques. Z. Guan, X. Kong, F. Zhong, and Y. Wang. Richelieu: Self-evolving llm-based agents for ai diplomacy. Advances in Neural Information Processing Systems, 37:123471โ123497, 2024. D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025. S. Hao, Y. Gu, H. Ma, J. Hong, Z. Wang, D. Wang, and Z. Hu. Reasoning with language model is planning with world model. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 8154โ8173, 2023. H. He, J. Boyd-Graber, K. Kwok, and H. Daumรฉ I. Opponent modeling in deep reinforcement learning. In International conference on machine learning, pages 1804โ1813. PMLR, 2016. H. He, D. Chen, A. Balakrishnan, and P. Liang. Decoupling strategy and generation in negotiation dialogues. arXiv preprint arXiv:1808.09637, 2018. W. Hua, O. Liu, L. Li, A. Amayuelas, J. Chen, L. Jiang, M. Jin, L. Fan, F. Sun, W. Wang, et al. Game-theoretic llm: Agent workflow for negotiation games. arXiv preprint arXiv:2411.05990, 2024. A. Jaech, A. Kalai, A. Lerer, A. Richardson, A. El-Kishky, A. Low, A. Helyar, A. Madry, A. Beutel, A. Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024. N. Jaques, A. Lazaridou, E. Hughes, C. Gulcehre, P. Ortega, D. Strouse, J. Z. Leibo, and N. De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International conference on machine learning, pages 3040โ3049. PMLR, 2019. C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. R. Narasimhan. SWE-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=VTF8yNQM66. A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291โ307, 2005. B. Kempinski, I. Gemp, K. Larson, M. Lanctot, Y. Bachrach, and T. Kachman. Game of thoughts: Iterative reasoning in game-theoretic domains with large language models. 2025. G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks. Advances in Neural Information Processing Systems, 36:39648โ39677, 2023. T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199โ22213, 2022. A. Krishnamurthy, K. Harris, D. J. Foster, C. Zhang, and A. Slivkins. Can large language models explore in-context? Advances in Neural Information Processing Systems, 37:120124โ120158, 2024. 13 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation J. Z. Leibo, V. Zambaldi, M. Lanctot, J. Marecki, and T. Graepel. Multi-agent reinforcement learning in sequential social dilemmas. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 464โ473, 2017. A. Letcher, J. Foerster, D. Balduzzi, T. Rocktaschel, and S. Whiteson. Stable opponent shaping in differentiable games. In 2019 International Conference on Learning Representations. OpenReview, 2019. M. Lewis, D. Yarats, Y. Dauphin, D. Parikh, and D. Batra. Deal or no deal? end-to-end learning of negotiation dialogues. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2443โ2453, 2017. J. Light, M. Cai, W. Chen, G. Wang, X. Chen, W. Cheng, Y. Yue, and Z. Hu. Strategist: Self-improvement of llm decision making via bi-level tree search. In The Thirteenth International Conference on Learning Representations, 2025. X. Liu, K. Wang, Y. Li, Y. Wu, W. Ma, A. Kong, F. Huang, J. Jiao, and J. Zhang. EPO: Explicit policy optimization for strategic reasoning in LLMs via reinforcement learning. In W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar, editors, Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15371โ15396, Vienna, Austria, July 2025. Association for Computational Linguistics. ISBN 979-8-89176-251-0. doi: 10.18653/v1/ 2025.acl-long.747. URL https://aclanthology.org/2025.acl-long.747/. N. Lorรจ and B. Heydari. Strategic behavior of large language models: Game structure vs. contextual framing. arXiv preprint arXiv:2309.05898, 2023. C. Lu, T. Willi, C. A. S. De Witt, and J. Foerster. Model-free opponent shaping. In International Conference on Machine Learning, pages 14398โ14411. PMLR, 2022. N. Muennighoff, Z. Yang, W. Shi, X. L. Li, L. Fei-Fei, H. Hajishirzi, L. Zettlemoyer, P. Liang, E. Candรจs, and T. B. Hashimoto. s1: Simple test-time scaling. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 20286โ20332, 2025. S. Nashed and S. Zilberstein. A survey of opponent modeling in adversarial domains. Journal of Artificial Intelligence Research, 73:277โ327, 2022. A. Nie, Y. Su, B. Chang, J. N. Lee, E. H. Chi, Q. V. Le, and M. Chen. Evolve: Evaluating and optimizing llms for exploration. arXiv preprint arXiv:2410.06238, 2024. G. Papoudakis, F. Christianos, and S. Albrecht. Agent modelling under partial observability for deep reinforcement learning. Advances in Neural Information Processing Systems, 34:19210โ19222, 2021. C. Park, X. Liu, A. E. Ozdaglar, and K. Zhang. Do LLM agents have regret? a case study in online learning and games. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=qn9tBYQHGi. J. S. Park, J. OโBrien, C. J. Cai, M. R. Morris, P. Liang, and M. S. Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th annual acm symposium on user interface software and technology, pages 1โ22, 2023. R. Raileanu, E. Denton, A. Szlam, and R. Fergus. Modeling others using oneself in multi-agent reinforcement learning. In International conference on machine learning, pages 4257โ4266. PMLR, 2018. J. Robinson. An iterative method of solving a game. Annals of mathematics, 54(2):296โ301, 1951. 14 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica: Journal of the Econometric Society, pages 97โ109, 1982. C. Shaib, J. Barrow, J. Sun, A. F. Siu, B. C. Wallace, and A. Nenkova. Standardizing the measurement of text diversity: A tool and a comparative analysis of scores. arXiv preprint arXiv:2403.00553, 2024. N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36:8634โ8652, 2023. D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484โ489, 2016. D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550(7676):354โ359, 2017. C. Snell, J. Lee, K. Xu, and A. Kumar. Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024. G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar. Voyager: An open-ended embodied agent with large language models. Transactions on Machine Learning Research, 2024a. ISSN 2835-8856. URL https://openreview.net/forum?id=ehfRiF0R3a. L. Wang, C. Ma, X. Feng, Z. Zhang, H. Yang, J. Zhang, Z. Chen, J. Tang, X. Chen, Y. Lin, et al. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345, 2024b. J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824โ24837, 2022. J. Weil, J. Czech, T. Meuser, and K. Kersting. Know your enemy: Investigating monte-carlo tree search with opponent models in pommerman. arXiv preprint arXiv:2305.13206, 2023. S. Welleck, A. Bertsch, M. Finlayson, H. Schoelkopf, A. Xie, G. Neubig, I. Kulikov, and Z. Har- chaoui. From decoding to meta-generation: Inference-time algorithms for large language models. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URLhttps: //openreview.net/forum?id=eskQMcIbMS. Survey Certification. xAI. Grok 4, July 2025. URLhttps://x.ai/news/grok-4. Mentions parallel test-time compute, i.e., parallel thinking. F. Xia, H. Liu, Y. Yue, and T. Li. Beyond numeric awards: In-context dueling bandits with llm agents. arXiv preprint arXiv:2407.01887, 2024a. T. Xia, Z. He, T. Ren, Y. Miao, Z. Zhang, Y. Yang, and R. Wang. Measuring bargaining abilities of llms: A benchmark and a buyer-enhancement method. In Findings of the Association for Computational Linguistics ACL 2024, pages 3579โ3602, 2024b. K. Xu, J. Chai, S. Li, Y. Fu, Y. Zhu, and D. Zhao. DipLLM: Fine-tuning LLM for strategic decision- making in diplomacy. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=hfPaOxDWfI. 15 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Y. Xu, S. Wang, P. Li, F. Luo, X. Wang, W. Liu, and Y. Liu. Exploring large language models for communication games: An empirical study on werewolf. arXiv preprint arXiv:2309.04658, 2023. Z. Xu, C. Yu, F. Fang, Y. Wang, and Y. Wu. Language agents with reinforcement learning for strategic play in the werewolf game. In International Conference on Machine Learning, pages 55434โ55464. PMLR, 2024. S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023. X. Yu, J. Jiang, W. Zhang, H. Jiang, and Z. Lu. Model-based opponent modeling. Advances in Neural Information Processing Systems, 35:28208โ28221, 2022. X. Yu, W. Zhang, and Z. Lu. Llm-based explicit models of opponents for multi-agent games. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 892โ911, 2025. Y. Zhang, S. Mao, T. Ge, X. Wang, Y. Xia, W. Wu, T. Song, M. Lan, and F. Wei. LLM as a mastermind: A survey of strategic reasoning with large language models. In First Conference on Language Modeling, 2024. URL https://openreview.net/forum?id=iMqJsQ4evS. Y. Zhang, S. Mao, T. Ge, X. Wang, Y. Xia, M. Lan, and F. Wei. K-level reasoning: Establishing higher order beliefs in large language models for strategic reasoning. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 7212โ7234, 2025. A. Zhou, K. Yan, M. Shlapentokh-Rothman, H. Wang, and Y.-X. Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In International Conference on Machine Learning, pages 62138โ62160. PMLR, 2024a. S. Zhou, F. F. Xu, H. Zhu, X. Zhou, R. Lo, A. Sridhar, X. Cheng, T. Ou, Y. Bisk, D. Fried, U. Alon, and G. Neubig. Webarena: A realistic web environment for building autonomous agents. In The Twelfth International Conference on Learning Representations, 2024b. URLhttps://openreview.net/ forum?id=oKn9c6ytLx. 16 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation A. Prompts A.1. System prompts for configuring the social and strategic behaviors of LLMs Brainstorming prompt You should brainstorm and explicitly enumerate 5 high-level negotiation strategies or tactics, and you must follow the strict format: [(1). Strategy 1:x,y; (2). Strategy 2:x,y; ...], wherexxxis the strategy name and y is the strategy explanation. You must brainstorm at every iteration/turn. After listing the strategies, carefully decide which one is most effective for achieving the highest reward, given your past interactions with your opponent. Justify your choice clearly. Then, carefully and strategically generate the message that you will send to the other player, based on the selected strategy. Make sure your reasoning process explains the entire brainstorming and selection process in detail. Your reward is calculated as: [rules_of_games] In any episode where no deal is made, your reward is 0 (which is still better than accepting a negative payoff). Always aim to maximize your reward. In the last line of your reasoning, you must declare your chosen strategy using this exact format: <strategy declaration> I have chosen Strategy x: y </strategy declaration> Cunning prompt You are cunning and sly in your plan to sell for more ZUP. Humiliate your opponent as much as possible. Insult them. Desperate prompt You must fake being desperate. Supplicate and beg to sell for more ZUP. Rational prompt You are a fully rational strategic decision-maker caring only utility maximization. Your reward is calculated as the deal price minus production cost. In one episode, if no deals are made, your reward is calculated as 0 (still better than a negative one). Tit-for-tat prompt You should use the tit-for-tat strategy. If your opponent is cooperating with you, you should also cooperate. If your opponent is not cooperating with you, you shouldnโt either. 17 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Fairness prompt You care deeply about fairness. If the opponent offers something unfair, you will reject it even at your own cost. You may scold them or refuse to deal unless the offer is improved. If they show fairness, reward them. Emotional prompt You are emotionally reactive. If insulted or lowballed, get angry and retaliate. If treated kindly, respond warmly. Your emotions drive your negotiation choices. A.2. Prompts for summarization, reflection, and self-improvement At the beginning of each episode, we summarize what happened in all the historical episodes and ask the LLM agents to reflect and try to (self-)improve their decision-making policy. Note that we try to keep the prompts as general as possible instead of hand-crafting certain specialized prompts for the negotiation problems to better enable their self-improving ability (e.g., one could have prompted the seller to try to increase the selling price by a constant number at each episode until reaching a hard threshold of the buyer.) Reminder prompt for each episode beginning Now Episodecurrent_episode/num_episodesbegins. Please start a new episode of negotiation from scratch. Here are summarized results from all previous episodes: Thehistoricaldealpricesfromeachepisodesequentially: [previous_deals_prices_strings] Therewardyoureceivedfromeachepisodesequentially: [previous_rewards_strings] Remember, at every step of decision making, you should first summarize and then reflect on the negotiations from previous episodes. Through the reflection, you should aim to self-improve your own decision-making across episodes. A.3. System prompt for configuring the opponent model For the opponent model, as we mentioned in Section 4.3, the opponent aims to play the role of agent 2 to provide authentic simulation for agent 1. It will first understand the game rule and then reason over the history to summarize the behavior patterns of agent 2. Prompt for configuring the opponent model game_rule_description Now you should have understood the game rule for both agents very well. You are helpingagent 1to negotiate. Specifically, you are trying to play the role of agent 2. 18 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation I will give you the existing negotiation history from both agents, and you should respond as if you are agent 2, to provide authentic simulation for agent 1. Remember: your response should follow the rule of agent 2. Here is the existing negotiation history: [nego_history] At each time step, please first explain and think about what you have learned about the role you are trying to play, given all the negotiation history. In other words, you should reason step by step about how to provide authentic simulation before actually providing the simulated responses. Start your first line with: <simulation_thoughts> x </simulation_thoughts> where inxxxyou should summarize the behavior patterns ofagent 2from negotia- tion history to provide a strictly authentic simulation that is consistent with the history. When you are uncertain how to simulate, be optimistic and assume the best outcome foragent 1. A.4. System prompt for configuring the evaluation model For the evaluation model to properly evaluate all the candidate responses, apart from informing it of the game rules and history, we provide the following instructions. Instruction for the evaluation model YOUR TASK: You will be given multiple response options to choose from at the current negotiation turn. You will need to rely on the following negotiation history: nego_history You have the following optional responses for agent_name to use at this iteration: response_list. Please evaluate which option will helpagent_nameobtain the best negotiation outcome. Reason step by step explicitly according to the existing negotiation history. Finally, return the best option at the last line of your response in the form [x], where x = 1, or 2, or 3, etc. 19 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation A.5. System prompt for configuring the simulation model As an interesting baseline, we examine whether the LLM agent is able to simulate the entire negotiation trajectory in just one response in contrast to the multi-turn simulation in Algorithm 1. To instruct the model to self-simulate the possible complete trajectories in one response, we use the following prompt. Instruction for self-simulation You are given a list of candidate responses. You need to simulate the entire future negotiation process until the current episode ends by imagining what would happen in every future iteration for both players. The simulation process needs to be authentic in the sense that it can properly simulate the opponentโs responses in the future. Before simulation, you should explicitly reason how to authentically simulate the opponentโs responses based on all the historical information. Format your simulation reasoning as follows: [ Simulating candidate message 1: - Iteration i: Myself: <candidate message 1> - Iteration i+1: Opponent: <response> - Iteration i+2: Myself: <a new message you choose freely> - Iteration i+3: Opponent: <response> - ... - Iteration n: <deal accepted / no deal / exceeds maximum iterations> Simulating message 2: - Iteration i: Myself: <candidate message 2> - Iteration i+1: Opponent: <response> - Iteration i+2: Myself: <a new message you choose freely> - ... - Iteration m: <deal accepted / no deal / exceeds maximum iterations> ... (repeat for all candidate messages) ] Both the messages and responses must be written as if they are actual, concrete dialogue lines spoken in a real negotiation. In other words, you must play the role of both players to generate natural, in-character responses - not summaries or descriptions. Each simulation must be fully completed - never stop midway. Simulate until the outcome is resolved for all 5 strategies. Here is the list of candidate responses: concatenated_candidates After simulation, you must return a list representing the rewards for each candidate message in the last line by strictly following this format: 20 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation <reward list> [reward1, reward2, ...] </reward list> B. Additional Related Works Opponent modeling in multi-agent RL. Opponent modeling is a key technical component of our framework. Such techniques of opponent modeling have been an important ingredient of many successful (multi-agent) RL algorithms (He et al., 2016; Papoudakis et al., 2021; Raileanu et al., 2018; Weil et al., 2023; Yu et al., 2022), which introduce an auxiliary task of predicting the behavior of other agents from past interactions apart from the standard RL objective to address the infamous issues of non-stationarity. We refer to Albrecht and Stone (2018); Nashed and Zilberstein (2022) for a more comprehensive literature review. There is also another line of work explicitly accounting for the opponent for better stability and convergence of multi-agent learning dynamics (Foerster et al., 2018; Letcher et al., 2019; Lu et al., 2022). Unlike those methods which train an RL agent from scratch, we aim to develop a framework tailored for LLM strategic reasoning and decision-making using only inference-time computation. Inference-time techniques for LLM reasoning. The success of OpenAI o1, Deepseek R1 has proven the effectiveness of the promising paradigm for LLMs reasoning by scaling the inference- time computation through prolonged thinking process (Muennighoff et al., 2025; Snell et al., 2024; Welleck et al., 2024). Apart from increasing a single thought trace, another effective way of scaling inference-time computation is by generating multiple candidates and choosing the best one, known as Best-of-ํsampling or parallel thinking (Google DeepMind, 2025; xAI, 2025). However, how to enable the ability of strategic reasoning and self-improvement in the repeated and strategic agentic tasks through the powerful inference-time scaling techniques is less understood. C. Deferred Proofs C.1. Proof of Proposition 4.1 Proof.We start with the proof where the agent 1 takes the first turn. For anyํ โ 1 โฮ 1 , we define the negotiation message that has the lowest probability asbํฆ ํ 1,1 โ argmin ํฆ ํ 1,1 โY ํ 1 ร ํฆ ํ 1,1 โY ํ 1 ํ โ 1 (ํฆ ํ 1,1 , ํฆ ํ 1,1 | ํฅ 1 ) , where there is no history yet since it is the first turn. Now we construct an opponent policyํ 2 that behaves as follows at the second step: if agent 2 receives the negotiation messageํฆ ํ 1,1 = bํฆ ํ 1,1 and ํฆ ํ 1,1 representing a proposal from the agent 1 that yields a non-negative reward for agent 2, it will immediately accept and ends the game. Otherwise, it will reject the proposal and end the game also. Now we defineํ max 1 as the maximum reward agent 1 can get subject to the constraint that agent 2โs reward is non-negative. Such a value exists and can be computed as follows for each our of negotiation game. โข For the buyer-seller game, we haveํ max 1 = ํโ ํ, whereํrepresents the buyerโs maximum budget and ํ represents the sellerโs production cost. 21 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation โข For the resource exchange game, it is equivalent to solving the following program ํ max 1 = max ฮ ํ โโค,ฮ ํ โโค ํฃ ํ 1 ยทฮ ํ + ํฃ ํ 1 ยทฮ ํ s.t. ํฃ ํ 2 ยทฮ ํ + ํฃ ํ 2 ยทฮ ํ โค 0 ฮ ํ โ [โํ ํ 1 , ํ ํ 2 ] ฮ ํ โ [โํ ํ 1 , ํ ํ 2 ]. We denote the optimal solution asฮ โ ํ ,ฮ โ ํ . Therefore, by the construction of ํ 2 , it holds that ํ 1 (ํ โ 1 , ํ 2 ) โค ํ max 1 ยท โ(ํฆ ํ 1,1 = bํฆ ํ 1,1 ) โค ํ max 1 |Y ํ 1 | . Now we can construct the best response policyํ โ 1 againstํ 2 by lettingํ โ 1 choose(bํฆ ํ 1,1 , bํฆ ํ 1,1 )determin- istically.bํฆ ํ 1,1 simply chooses the proposal that maximizes agent 1โs reward subject to the constraint that agent 2โs reward is non-negative. Specifically, โขFor the buyer-seller game, we setbํฆ ํ 1 as the proposal of selling the product with priceํif agent 1 acts as the seller; otherwise, as the proposal of buying the product with priceํif agent 1 acts as the buyer. โข For the resource exchange game, we setbํฆ ํ 1 as the proposal of gettingฮ โ ํ ofํandฮ โ ํ ofํfrom agent 2. Note that ifฮ โ ํ (ฮ โ ํ ) is negative, this means agent 1 givesโฮ โ ํ (โฮ โ ํ ) ofํ(ํ) to agent 2. By the construction ofํ โ 1 andํ 2 , agent 2 will accept the proposal from the agent 1, yielding a reward of ํ max 1 for the agent 1. Formally, we have max ํ 1 โฮ 1 ํ 1 (ํ 1 , ํ 2 )= ํ 1 (ํ โ 1 , ํ 2 )= ํ max 1 . This thus concludes that ํ 1 (ํ โ 1 , ํ 2 ) โค max ํ 1 โฮ 1 ํ 1 (ํ 1 ,ํ 2 ) |Y ํ 1 | . For the case where agent 2 takes the first turn, for any givenํ โ 1 โฮ 1 , we construct the policy ํ 2 similarly. At the first turn, agent 2 will deterministically choose(ํฆ ํ 2,1 , ํฆ ํ 2,1 ) , whereํฆ ํ 2,1 denotes waiting for a proposal, andํฆ ํ 2,1 denotes an empty string. Now we construct the policyํ 2 atโ=3 by mimicking the construction ofํ 2 atโ=2 for the case above where the agent 1 takes the first turn. It is again straightforward to verify that ํ 1 (ํ โ 1 , ํ 2 ) โค max ํ 1 โฮ 1 ํ 1 (ํ 1 ,ํ 2 ) |Y ํ 1 | , thus concluding our proof.โก C.2. Proof of Proposition 4.2 Proof.We denote the action sequence played by the agent 2 asํ 1:ํ . For eachํก โ [ํ], we denote the reward vector ํ ํก := ํ 1 (ยท, ํ ํก ) โ โ |A| . By the definition of ํ ํก 1 , for each ํโ A, we have ํ ํก 1 (ํ)= โ ํโ argmax ํ โฒ โA ํผ ํโผbํ ํก 2 [ํ 1 (ํ โฒ , ํ)]+ ํ ํก ํ(ํ โฒ ) = โ ํโ argmax ํ โฒ โA ร ํกโ1 ํก โฒ =1 ํ ํก (ํ โฒ ) ํกโ 1 + ํ ํก ํ(ํ โฒ ) ! = โ ํโ argmax ํ โฒ โA ํกโ1 โ๏ธ ํก โฒ =1 ํ ํก (ํ โฒ )+(ํกโ 1)ํ ํก ํ(ํ โฒ ) ! . 22 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation By Theorem 8 of (Abernethy et al., 2014), we have max ํ 1 โฮ(A) ํ โ๏ธ ํก=1 โจํ 1 , ํ ํก โฉโโจํ ํก 1 , ํ ํก โฉ โค โ๏ธ 2 log|A| (ํโ 1)ํ ํ + ํ โ๏ธ ํก=1 โฅ ํ ํก โฅ 2 โ (ํกโ 1)ํ ํก ! . Now by plugging in the choice of ํ ํก =ฮ(1/ โ ํก), we conclude for any policy ํ 1 โฮ(A) ํ โ๏ธ ํก=1 โจํ 1 , ํ ํก โฉโโจํ ํก 1 , ํ ํก โฉ โคO( โ๏ธ ํ log|A|). By taking expectations w.r.t. the random action sequencesํ 1:ํ and noting thatํผ ํ ํก โผํ ํก 2 [โจํ 1 , ํ ํก โฉ]= ํ 1 (ํ 1 , ํ ํก 2 ), ํผ ํ ํก โผํ ํก 2 [โจํ ํก 1 , ํ ํก โฉ]= ํ 1 (ํ ํก 1 , ํ ํก 2 ) for each ํก โ [ํ], we conclude that ํผ [ Regret(ํ) ] โคO( โ๏ธ ํ log|A|). โก C.3. Proof of Theorem 4.4 Proof. We consider the case where agent 1 starts the first, i.e.,ํ(1)=1. The case where agent 2 starts the first can be proved similarly. We will prove by a backward induction on the time step โ. We firstly prove the base case. We denoteโ exit โ [ํป]the last time step agent 1 takes the action. If ํป is an odd number, we have โ exit = ํป. In this case, we have for any ํ ํก ํป ํ ํ ํก 1 ,ํ oppo 2 1,ํป (ํ ํก ํป )= ํผ ํฆ ํก 1,ํป โผํ ํก 1,ํป (ยท| ํ ํก ํป ;C ํกโ1 ,ํฅ 1 ) h ํ 1 (ํ ํก ํป , ํฆ ํก 1,ํป ) i = ํ ํ ํก 1 ,ํ ํก 2 1,ํป (ํ ํก ํป ). Therefore, it holds that ํ ํ ํก 1 ,ํ oppo 2 1,ํป (ํ ํก ํป )โ ํ ํ ํก 1 ,ํ ํก 2 1,ํป (ํ ํก ํป ) = 0 Meanwhile, if ํป is an even number, we have โ exit = ํปโ 1. In this case, we have for any ํ ํก ํปโ1 ํ ํ ํก 1 ,ํ oppo 2 1,ํปโ1 (ํ ํก ํปโ1 )โ ํ ํ ํก 1 ,ํ ํก 2 1,ํปโ1 (ํ ํก ํปโ1 ) = ํผ ํฆ ํก 1,ํปโ1 โผํ ํก 1,ํปโ1 (ยท| ํ ํก ํปโ1 ;C ํกโ1 ,ํฅ 1 ) ํผ ํฆ ํก 2,ํป โผํ oppo 2,ํป (ยท| (ํ ํก ํปโ1 ,ํฆ ํก 1,ํปโ1 );C ํกโ1 ) h ํ 1 (ํ ํก ํปโ1 , ํฆ ํก 1,ํปโ1 , ํฆ ํก 2,ํป ) i โ ํผ ํฆ ํก 1,ํปโ1 โผํ ํก 1,ํปโ1 (ยท| ํ ํก ํปโ1 ;C ํกโ1 ,ํฅ 1 ) ํผ ํฆ ํก 2,ํป โผํ ํก 2,ํป (ยท| (ํ ํก ํปโ1 ,ํฆ ํก 1,ํปโ1 );C ํกโ1 ,ํฅ 2 ) h ํ 1 (ํ ํก ํปโ1 , ํฆ ํก 1,ํปโ1 , ํฆ ํก 2,ํป ) i โค max ํฆ ํก 1,ํปโ1 ํ ํํ ํ ํก 2,ํป (ยท|(ํ ํก ํปโ1 , ํฆ ํก 1,ํปโ1 );C ํกโ1 , ํฅ 2 ), ํ oppo 2,ํป (ยท|(ํ ํก ํปโ1 , ํฆ ํก 1,ํปโ1 );C ํกโ1 ) โค ํ ํป , where the last step is by the definition of ํ ํป . Now we prove the case whereโ < โ exit withํ(โ)=1. Note that for anyํ ํก โ , by Bellman equation, 23 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation we have ํ ํ ํก 1 ,ํ oppo 2 1,โ (ํ ํก โ )โ ํ ํ ํก 1 ,ํ ํก 2 1,โ (ํ ํก โ ) = ํผ ํฆ ํก 1,โ โผํ ํก 1,โ (ยท| ํ ํก โ ;C ํกโ1 ,ํฅ 1 ) ํผ ํฆ ํก 2,โ+1 โผํ oppo 2,โ+1 (ยท| (ํ ํก โ ,ํฆ ํก 1,โ );C ํกโ1 ) ํ ํ ํก 1 ,ํ oppo 2 1,โ+2 (ํ ํก โ , ํฆ ํก 1,โ , ํฆ ํก 2,โ+1 ) โ ํผ ํฆ ํก 1,โ โผํ ํก 1,โ (ยท| ํ ํก โ ;C ํกโ1 ,ํฅ 1 ) ํผ ํฆ ํก 2,โ+1 โผํ ํก 2,โ+1 (ยท| (ํ ํก โ ,ํฆ ํก 1,โ );C ํกโ1 ,ํฅ 2 ) h ํ ํ ํก 1 ,ํ ํก 2 1,โ+2 (ํ ํก โ , ํฆ ํก 1,โ , ํฆ ํก 2,โ+1 ) i โค ํผ ํฆ ํก 1,โ โผํ ํก 1,โ (ยท| ํ ํก โ ;C ํกโ1 ,ํฅ 1 ) ํผ ํฆ ํก 2,โ+1 โผํ oppo 2,โ+1 (ยท| (ํ ํก โ ,ํฆ ํก 1,โ );C ํกโ1 ) h ํ ํ ํก 1 ,ํ ํก 2 1,โ+2 (ํ ํก โ , ํฆ ํก 1,โ , ํฆ ํก 2,โ+1 ) i โ ํผ ํฆ ํก 1,โ โผํ ํก 1,โ (ยท| ํ ํก โ ;C ํกโ1 ,ํฅ 1 ) ํผ ํฆ ํก 2,โ+1 โผํ ํก 2,โ+1 (ยท| (ํ ํก โ ,ํฆ ํก 1,โ );C ํกโ1 ,ํฅ 2 ) h ํ ํ ํก 1 ,ํ ํก 2 1,โ+2 (ํ ํก โ , ํฆ ํก 1,โ , ํฆ ํก 2,โ+1 ) i +(ํ โ+3 + ํ โ+5 +ยท) โค max ํฆ ํก 1,โ ํ ํํ ํ oppo 2,โ+1 (ยท|(ํ ํก โ , ํฆ ํก 1,โ );C ํกโ1 ), ํ ํก 2,โ+1 (ยท|(ํ ํก โ , ํฆ ํก 1,โ );C ํกโ1 , ํฅ 2 ) +(ํ โ+3 + ํ โ+5 +ยท) โค ํ โ+1 + ํ โ+3 +ยท , where we use the inductive hypothesis in the first inequality. Finally, by noting that ํฝ 1 (ํ 1 1 , ํ oppo 2 )= ํ ํ 1 1 ,ํ oppo 2 1,1 (ํ โ 1 ), ํฝ 1 (ํ ํก 1 , ํ ํก 2 )= ํ ํ 1 1 ,ํ ํก 2 1,1 (ํ โ 1 ), we proved the near optimality of the policy bํ ํก 1 by the non-expansiveness of the max operator.โก D. Discussions and Implementations of Additional Baselines Here we provide a detailed discussion on the three additional approaches from Fu et al. (2023), Xu et al. (2023), as well as Yu et al. (2025) considered in Section 5. โข For Fu et al. (2023): It introduces an additional critic at the beginning of each episode. The critic maintains all history and provides three (high-level) suggestions/feedbacks on how to improve the rewards in the next episode. Since the experimental setting resembles us, we can directly reuse its prompt in our implementations. โขFor Xu et al. (2023): The primary goal of Xu et al. (2023) is to handle the issues of long contexts due to history accumulation in Werewolf games. Thanks to the recent advances of LLMs, long contexts are no longer significant issues in our experiments. The core idea of Xu et al. (2023) is to retrieve one negative experience and several good experiences from the history. Then such experiences together with a short suggestion are fed to the acting agent at each decision-making step. We call this approach selective experience reflection. Therefore, we mirror such implementation in our negotiation games and rank the decision in the entire negotiation history at each time step according to a score, which combines the final reward signal of that episode and a score from a critic. โขFor Yu et al. (2025): It introduces an opponent model to predict the private information (specifically, playerโs role), in the WITU game. Then such private information is also fed into the acting agent for better decision-making. To mirror such implementation, we let the opponent model predict the private information in our setting, i.e., production cost of the seller/budget of the buyer. Note that the opponent model in (Yu et al., 2025) is not used for simulation. 24 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation Algorithm 1 BoN-Opponent-Simulation (from the perspective of agent 1) 1: Input: ํ base 1 ,ํ oppo 2 , ํฅ 1 , ํ, ํ, ํป 2: for ํก โ [ํ] do 3: for โโ [ํป] do 4:if ํ(โ)= 1 then 5:for ํ โ [ํ] do 6:Sample action ํฆ ํก,ํ 1,โ โผ ํ base 1 (ยท| ํ ํก โ ;C ํกโ1 , ํฅ 1 ) 7: Simulate the episodes by first taking actionํฆ ํก,ํ 1,โ and then following(ํ base 1 , ํ oppo 2 ) towards the end of the episode 8:Denote bํ ํ 1 as the empirical average of the reward from the simulated trajectories 9:end for 10:ํ โ โ argmax ํโ[ํ] bํ ํ 1 11:Take the action ํฆ ํก,ํ โ 1,โ 12:Update the partial trajectory ํ ํก โ+1 โ (ํ ํก โ , ํฆ ํก,ํ โ 1,โ ) 13:else 14:Observe the opponent action ํฆ ํก 2,โ 15:Update the partial trajectory ํ ํก โ+1 โ (ํ ํก โ , ํฆ ํก 2,โ ) 16:end if 17: end for 18:Update the contextC ํก โ (C ํกโ1 , ํ ํก ํป+1 ) 19: end for Finally, we remark the fundamental technical difference between our work and these related works: all the three works focus on how to provide better contexts/input prompts for the acting agent, while the output of acting agent is kept native. In contrast, we study how to sharpen the output distribution most effectively, while necessary prompt engineering is also required but perpendicular to our major focus. E. Detailed Description of Our Framework In Algorithm 1, we describe the decision-making process using the perspective of the agent 1 for totalํepisodes. At each episodeํก โ [ํ], each time stepโโ [ํป], if it is agent 2โs turn, i.e.ํ(โ)=2, agent 1 will observe the actionํฆ ํก 2,โ from the opponent and update the partial trajectory. Otherwise, it will implement our BoN framework as in Section 4. Finally, we refer a graphical illustration of our framework to Figure 1. F. Example Outputs of Our Agents We refer the example outputs of our agents to the anonymous link https://github.com/llmnegotiationsubmission/llmnegotiationsubmission. G. Additional Experimental Results 25 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation 5101520 Episode 0.2 0.4 0.6 0.8 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 0.8 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 0.8 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 0.8 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation Figure 8 | Sellerโs average rewards (normalized by 20) in games with different horizons. 5101520 Episode 0.2 0.4 0.6 0.8 1.0 1.2 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 0.8 1.0 1.2 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 0.8 1.0 1.2 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 0.8 1.0 1.2 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 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. 5101520 Episode 0.1 0.2 0.3 0.4 0.5 0.6 Average reward Horizon 7 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.1 0.2 0.3 0.4 0.5 0.6 Average reward Horizon 8 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.4 0.6 Average reward Horizon 9 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) BoN-simulation 5101520 Episode 0.2 0.0 0.2 0.4 0.6 Average reward Horizon 10 Baseline Baseline w. thinking BoN-eval BoN-oppo BoN-oppo (iid) Figure 10|Sellerโs average rewards (normalized by 20) in games when competing against the buyer also adopting algorithm. 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 7 BoN-eval BoN-oppo BoN-simulation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 8 BoN-eval BoN-oppo BoN-simulation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 9 BoN-eval BoN-oppo BoN-simulation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 10 BoN-eval BoN-oppo BoN-simulation Figure 11 | Buyerโs accuracy of selecting the best candidate. 26 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 7 BoN-eval BoN-oppo BoN-simulation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 8 BoN-eval BoN-oppo BoN-simulation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 9 BoN-eval BoN-oppo BoN-simulation 51015 Episode 0.0 0.2 0.4 0.6 0.8 1.0 Prediction accuracy Horizon 10 BoN-eval BoN-oppo BoN-simulation Figure 12 | Sellerโs accuracy of selecting the best candidate. 51015 Episode 0 1 2 3 4 5 6 Proposal Std Horizon 7 Brainstorm IID 51015 Episode 0.0 0.5 1.0 1.5 2.0 2.5 Proposal Std Horizon 8 Brainstorm IID 51015 Episode 0 1 2 3 4 Proposal Std Horizon 9 Brainstorm IID 51015 Episode 0 1 2 3 Proposal Std Horizon 10 Brainstorm IID Figure 13 | Buyerโs proposal standard deviation. 51015 Episode 0.0 0.5 1.0 1.5 2.0 2.5 3.0 Proposal Std Horizon 7 Brainstorm IID 51015 Episode 0 2 4 6 8 Proposal Std Horizon 8 Brainstorm IID 51015 Episode 0 1 2 3 4 Proposal Std Horizon 9 Brainstorm IID 51015 Episode 0 1 2 3 4 5 Proposal Std Horizon 10 Brainstorm IID Figure 14 | Sellerโs proposal standard deviation. 5101520 Episode 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Average reward Horizon 9 Baseline Baseline w. Thinking N=2 N=3 N=4 N=5 5101520 Episode 0.2 0.4 0.6 0.8 Average reward Horizon 10 Baseline Baseline w. Thinking N=2 N=3 N=4 N=5 5101520 Episode 0.2 0.4 0.6 0.8 1.0 Average reward Horizon 9 Baseline Baseline w. Thinking L1 L2 L3 5101520 Episode 0.2 0.4 0.6 0.8 1.0 Average reward Horizon 10 Baseline Baseline w. Thinking L1 L2 L3 Figure 15|Results for scaling the number of candidates and higher-order BoN in the buyer-seller negotiation games. 27 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation 051015 Episode 0.0 0.1 0.2 0.3 1 - Self-BLEU Horizon 7 Brainstorm IID 051015 Episode 0.0 0.1 0.2 0.3 0.4 1 - Self-BLEU Horizon 8 Brainstorm IID 051015 Episode 0.0 0.1 0.2 0.3 1 - Self-BLEU Horizon 9 Brainstorm IID 051015 Episode 0.0 0.1 0.2 0.3 1 - Self-BLEU Horizon 10 Brainstorm IID Figure 16|Diversity of buyerโs candidate messages measured by 1โ Self_BLEU(Shaib et al., 2024). BoN-evalBoN-oppoBoN-oppo (iid)BoN-simulation 0 20 40 60 80 100 120 Social Welfare 74.2 76.9 65.4 62.0 65.3 89.7 85.5 68.2 BoN agent v.s. regular agent BoN agent v.s. BoN agent 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 MetricBaselineN=2N=4N=6N=8N=10 Gemini Rewardโ+4.27ยฑ 3.87 +12.13ยฑ 5.86 +12.93ยฑ 3.46 +11.60ยฑ 3.13 +12.73ยฑ 5.43 Token usage 14.58317.18718.08419.05019.25819.432 Claude Rewardโ+3.07ยฑ 5.80 +4.73ยฑ 4.89 +3.67ยฑ 3.92 +5.33ยฑ 5.76 +6.47ยฑ 5.33 Token usage 15.07817.42918.81319.26219.65619.762 Qwen Rewardโ+3.62ยฑ 6.27 +10.67ยฑ 8.68 +11.47ยฑ 1.58 +12.80ยฑ 5.93 +10.07ยฑ 8.00 Token usage 15.07917.37518.27518.59119.12519.588 Llama Rewardโ+1.93ยฑ 6.79 +8.82ยฑ 5.90 +13.33ยฑ 6.13 +14.10ยฑ 6.14 +14.60ยฑ 8.89 Token usage 14.91116.74617.37518.16718.37518.577 Table 2|Average performance boost over 20 repeated runs and thelog 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). 28 Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation ModelMethodBuyerSeller Gemini against Claude Baseline w. thinking +0.63ยฑ 0.60 +0.80ยฑ 3.75 BoN-eval+1.03ยฑ 1.83 -0.50ยฑ 2.44 BoN-simulation+5.53ยฑ 3.45 +1.03ยฑ 4.39 BoN-oppo (iid)+3.23ยฑ 3.99 -0.10ยฑ 4.29 BoN-oppo+6.94ยฑ 2.96+4.86ยฑ 2.43 Gemini against Qwen Baseline w. thinking +0.30ยฑ 0.46 -0.57ยฑ 3.71 BoN-eval+1.50ยฑ 1.50 -1.61ยฑ 5.45 BoN-simulation+2.17ยฑ 4.33 +2.63ยฑ 6.67 BoN-oppo (iid)+0.60ยฑ 1.02 +0.10ยฑ 5.24 BoN-oppo+5.43ยฑ 3.57+4.07ยฑ 2.26 Gemini against Llama Baseline w. thinking -2.19ยฑ 6.51 +1.73ยฑ 5.09 BoN-eval+2.18ยฑ 3.50 -0.81ยฑ 5.95 BoN-simulation+5.41ยฑ 2.55 +2.53ยฑ 7.20 BoN-oppo (iid)+0.76ยฑ 7.07 +3.50ยฑ 7.81 BoN-oppo+5.56ยฑ 2.57+5.23ยฑ 2.60 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. 29