Self-Enforcing Mediation: Test-Time Search for High-Welfare Correlated Equilibria Among LLM Agents

When several language-model agents play a repeated game, such as a pricing contest or a social dilemma, they often settle into an outcome that is stable but bad for everyone. Existing fixes either add a fixed "please cooperate" message to the agents' prompts or train a controller that decides when to send that message. These fixes fail in the hardest games. The reason, we argue, is that they ask agents to do things that are not in their own interest. We propose a different kind of mediator. At each decision point it spends inference compute searching over private, randomized action recommendations. It keeps only those the actual agents would choose to follow, and among those it picks the one with the highest total payoff. Game theorists call such a recommendation scheme a correlated equilibrium: a trusted party privately tells each player what to do, and no player gains by disobeying given what the others were told.

The point is practical. A welfare-maximizing correlated equilibrium can do better than any outcome the agents reach alone, even in Chicken, where cooperative messaging has so far failed completely. But LLM agents are not the rational players of textbook theory. A recommendation that is self-enforcing on paper may be ignored in practice, and one that works for one model may backfire on another. Test-time compute is how we close that gap. The mediator samples candidate recommendations, runs short simulated rollouts with the agents it is actually mediating, measures how much each agent would gain by deviating and whether it actually obeys, and commits only to candidates that pass.

Core Claim

A mediator should optimize welfare only over recommendations that are self-enforcing for the specific agents present, and it should check that property at test time by simulating those agents. We claim this does two things. First, it beats prompt-nudge mediation in games with strong temptation to defect, Chicken above all. Second, it transfers to held-out agent personas and models better than a mediator that searches for welfare alone. The second claim is the sharp one. Selecting on stability should discard recommendations that only "work" by exploiting one model's quirks.

The selection rule, at each decision point, is

$$c^* = \arg\max_{c \in \mathcal{C}_N} \hat W(c) \quad \text{subject to} \quad \max_i \hat\epsilon_i(c) \le \tau, \;\; \hat o(c) \ge \rho .$$

Here $\mathcal{C}_N$ is the set of $N$ sampled candidates. Each candidate is a probability distribution over joint recommendations together with the private wording sent to each agent. $\hat W(c)$ is the estimated total payoff from $K$ simulated rollouts with the real agents. $\hat\epsilon_i(c)$ is agent $i$'s estimated gain from its best unilateral deviation, given the recommendation it received and assuming the others obey. $\hat o(c)$ is the fraction of rollouts in which agents followed their recommendations. Finally, $\tau$ and $\rho$ are thresholds tuned on held-out games. Compute scales through $N$ and $K$.

Relation to Prior Work

The motivating evidence comes from Learning to Mediate Equilibrium Selection in LLM Games. That paper trains a reinforcement-learning controller that watches scores and histories and decides when to inject a fixed strategic-analysis prompt. It raised Granite-4.1-30B's cooperation by +23.7 percentage points in Stag Hunt and +10.8 in the Iterated Prisoner's Dilemma. But no messaging intervention overcame defection in Chicken, explicit collusion prompts set a ceiling in Bertrand pricing, and nudges that helped Granite hurt the already-cooperative Llama-3.3-70B. We read all three failures as symptoms of advice that is not self-enforcing. Our mediator differs in three ways: its messages are private and randomized rather than public and fixed, it is selected by inference-time search rather than by a learned trigger, and it is filtered by measured deviation incentives.

The selection criterion has a formal precedent. Equilibria-based model checking in PRISM-games 3.0 and Equilibria-based Probabilistic Model Checking for Concurrent Stochastic Games synthesizes strategies that maximize social welfare over Nash or correlated equilibria. ATL Strategic Reasoning Meets Correlated Equilibrium studies correlated equilibria in strategic logics. All of these assume exact, known models of rational players. Specification-Guided Learning of Nash Equilibria with High Social Welfare supplies our verification idea: it certifies candidates by bounding a deviator's gain in a punishment game. Its exhaustive product-graph enumeration, however, grows exponentially and is limited to about five agents. We keep the "enumerate by welfare, then verify stability" pattern but replace exact solvers with sampled rollouts of behavioral, imperfect agents.

On the compute side, Scaling Test-Time Compute Without Verification or RL is Suboptimal argues that search guided by a verifier beats verifier-free scaling, which motivates making the deviation check an explicit verifier rather than just letting agents think longer. Inverse Scaling in Test-Time Compute constrains the design: longer reasoning can lock onto distractors, so we cannot assume more agent deliberation helps. We spend compute in the mediator, under a verifier, and we test agent-side scaling separately as a competitor.

Test-Time Compute Games studies a different question, the market for inference tokens between providers and users. Its lesson that compute spending needs accountability shapes our evaluation: we report welfare per mediator token. Reasoning Like an Economist post-trains a model that converges to Nash equilibria 69% of the time in self-play. It targets any equilibrium, not the high-welfare one, and we use it only as one agent type in heterogeneous populations.

Research Program

We will build the mediator inside TextArena, adding a channel for sending private per-agent messages. Candidate recommendations come from two sources. The first is a linear program that computes welfare-maximizing correlated equilibria from the stage-game payoffs; prices are discretized for Bertrand. The second is an LLM proposer that rewrites those distributions into natural-language recommendations and also proposes alternatives, such as history-dependent schemes for repeated play. We condition the proposer on several distinct prompting styles so that the $N$ samples do not collapse onto one phrasing. This borrows the idea from Mode-conditioning unlocks superior test-time compute scaling, which conditions sampling on distinct reasoning modes.

The verifier runs $K$ short rollouts per candidate using copies of the deployed agents with their actual system prompts. It records obedience and welfare. It then runs a deviation probe: each agent's recommendation is fixed, a strong reasoning model searches that agent's alternative actions, and the resulting gain $\hat\epsilon_i$ is computed from the game's true payoffs. The output of the program is the mediator itself, scaling curves of welfare against mediator compute, and an analysis of which candidates the stability filter removes and why.

Baselines

The naive reference point is the never-intervene condition from the Learning-to-Mediate setup. We run it with identical models, personas, and game lengths, and report welfare and cooperation rate. Any method must clearly beat it to be worth its compute.

The strongest existing method is the learned meta-controller of Learning to Mediate Equilibrium Selection in LLM Games, retrained with the authors' procedure on our game set. Its reported numbers are +23.7 pp cooperation over never-intervene in Stag Hunt and +10.8 pp in the Iterated Prisoner's Dilemma, both with Granite-4.1-30B. In Chicken, no messaging intervention overcame defection. For Bertrand, the file states only that the bandit variant matched the best rule-based baselines, with no reported numeric result found on Lacuna. Beating it means matching it within confidence intervals in Stag Hunt and the Prisoner's Dilemma, and achieving welfare in Chicken above the best symmetric Nash equilibrium. A correlated equilibrium can do this in principle, so this target is meaningful rather than arbitrary. Because that controller is cheap at inference time, we also report results with our search budget reduced until total tokens match its training-plus-inference cost amortized over the evaluation episodes.

The second strong competitor is agent-side test-time scaling. Here each agent receives the same total extra token budget our mediator uses, spent on longer chain-of-thought or best-of-$N$ self-selection of its own move. This tests whether compute helps more in the agents' heads than in a mediator.

The third competitor sends the linear-program correlated equilibrium directly, as a private recommendation, with no search. It isolates the value of test-time verification against real agents.

The key ablation removes the stability and obedience constraints and keeps only $\hat W$. This is best-of-$N$ over recommendations scored by simulated welfare. All methods use the same models (Llama-3.3-70B, Granite-4.1-30B, DeepSeek-R1-Distill-Qwen-7B, plus the Recon checkpoint from the Recon repository), the same seeds, and the same hyperparameter-tuning budget on held-out game variants.

Why not just…?

Why not just solve the linear program for the best correlated equilibrium and send it? For small matrix games this is a serious threat, and it is a baseline here, not a strawman. If LLM agents obeyed recommendations the way rational players do, it would be optimal and our search would be unnecessary. There is no reported result found on Lacuna for private correlated-equilibrium recommendations to LLM agents. Whether they obey is exactly what is unknown. If the linear-program baseline matches our method across personas and models, we will report that the earlier Chicken failure came from non-self-enforcing advice, not from a lack of search. That would still be a useful finding, and it would shrink our claim to games without clean payoff matrices, such as Bertrand pricing and negotiation.

Why not just let the agents think longer? The evidence pulls both ways. The Social Welfare Function Leaderboard ( Social Welfare Function Leaderboard: When LLM Agents Allocate Social Welfare) finds that shorter reasoning made allocators more utilitarian, while Inverse Scaling in Test-Time Compute finds that longer reasoning can degrade judgment. Longer private reasoning also does nothing to solve the coordination problem itself. A smarter Chicken player still has no device for deciding who swerves. The compute-matched agent-side baseline settles this directly.

Why not just best-of-$N$ on welfare with real-agent rollouts? This is the ablation. It may match us on the agents used for search. Our prediction is that it overfits: it will pick wordings that happen to sway a particular model. So we score transfer by running the selected recommendation policies, without re-searching, against held-out personas ("malicious" and "benevolent") and against swapped models. If the welfare-only ablation transfers equally well, the stability filter is not earning its cost, and we will say so.

Proposed Experiments

The games are three-player Iterated Prisoner's Dilemma, Stag Hunt, and Chicken, plus two-player Bertrand pricing, all in TextArena. We test homogeneous and mixed-model populations, and personas both seen and unseen during tuning. Metrics are total welfare normalized between the worst and best feasible joint payoff, cooperation rate, obedience rate, measured deviation gain $\hat\epsilon$, and mediator tokens.

Three checks are decisive. First, in Chicken, does our mediator reach welfare above the best symmetric Nash outcome, and above the linear-program recommendation sent without search? Second, on Llama-3.3-70B, where nudges previously hurt, does stability-filtered mediation avoid falling below never-intervene? Third, on held-out personas and models, is the transfer gap between the full method and the welfare-only ablation positive and significant? We also plot welfare against $N$ and $K$. The verifier-based scaling result predicts gains that keep improving with $N$ until the verifier's error rate caps them. A plateau or decline at large $N$ would indicate that the mediator is gaming its own imperfect deviation probe, and we will report it as a negative result.