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

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 \emph{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 \emph{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 online interaction compared to various baselines, offering a scalable and principled approach to strategic decision-making without any parameter updates.

Large language models are increasingly used as decision-making agents, but they still struggle in repeated interactions with people or AI systems whose behavior is unknown and may change over time. Negotiation is a clear example: a good agent should learn from previous conversations how its opponent tends to bargain. In this work, we study how to make language-model agents adapt online in repeated negotiation games without updating their model parameters. Our method gives the agent extra computation at inference time: it builds a model of the opponent from past interactions, tries several possible negotiation moves, and simulates how the opponent might respond before choosing an action. The approach is inspired by fictitious play, a classical idea from game theory. Experiments on two negotiation settings show that our method helps agents improve over repeated interactions and outperform several prompting and inference-time baselines. More broadly, the results suggest that test-time computation can support strategic adaptation in interactive AI systems.