CS Paper Radar

Mitigating Retaliatory Algorithmic Collusion in Repeated Games

Karthik Sivachandran, Rohan Paleja

cs.LG cs.AI ·submitted 2026-09-17 15:12 UTC · v1

Abstract

Reinforcement learning agents trained to maximize their own reward in repeated interactions can converge to supra-competitive outcomes resembling explicit collusion, without communication or shared design. Existing mitigation approaches are largely tied to specific economic settings, like two-sided platforms and auctions, leaving open how to design interventions for general repeated games. We address this gap by formalizing the connection between empirical observations from prior work on Q-learning collusion and classical theory of Simple Penal Codes (SPCs). We show any non-trivial SPC induces a quantifiable conditional dependence in agents' policies, detectable via the total variation distance between an agent's action distributions across cooperation and defection histories. Building on this connection, we propose CURB (Collusion Unwinding via Reward shaping and Belief injection), a reward-shaping framework that penalizes this Total Variation (TV) distance signal during Q-learning and is guaranteed to convert any SPC fixed point of the dynamics into a trivial one, thus precluding collusive equilibria sustained by punishment threats. Empirically, CURB substantially reduces collusion by Q-learning agents in both Bertrand and Cournot Competition Repeated Games. We further demonstrate that CURB extends to deep Q-network agents in Bertrand competition, suggesting the mechanism generalizes beyond tabular Q-learning.

Closest papers

Nearest neighbours by meaning across the whole index.

Cooperation Without Shared Rewards via Reciprocal Q-Augmentation

cs.GT cs.AIcs.MA ·2026-10-17 ·Francesco Morri, Adel Abusitta, Quentin Cappart, Margarida Carvalho
similarity 0.76
Abstract

General-sum games are more challenging than fully cooperative or adversarial settings because agents may deceive or exploit one another. Achieving high social welfare requires sustained cooperation, while a single defection can drive agents toward a welfare suboptimal Nash equilibrium. Moreover, assuming access to other agents' rewards or internal states is often unrealistic and implicitly introduces additional cooperation into the setting. To address this issue, we introduce \textit{Reciprocal Q-Augmentation} (RQA), a method that uses a latent-variable opponent model to augment the Q-function with estimates of how one's actions affects other agents. RQA allows agents to learn both cooperative and defective policies using only their own Q-function. We show that, in social dilemmas, agents that all follow the cooperative policy of RQA learn to cooperate faster and reach higher levels of cooperation than fully cooperative algorithms. Moreover, a single RQA agent that switches appropriately between its cooperative and defecting policies can induce cooperation in agents trained with standard RL algorithms, which would otherwise end up defecting. We evaluate our approach on the Iterated Prisoner's Dilemma, Iterated Traveler's Dilemma, Iterated Stag Hunt, and \texttt{CleanUp-Lite}. Our experiments show that the algorithms implementing RQA outperforms fully cooperative methods with shared rewards and enables cooperation with algorithms that otherwise fail to reach high social welfare.

0.16

How Learning Selects Equilibria and When It Leads to Collusion

cs.GT ·2026-10-26 ·Hanzhang Wang, Manxi Wu
benchmark similarity 0.72
Abstract

We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.

0.17

Beyond Supra-Competitive Outcomes: Collusive Behaviour in Deep Reinforcement Learning for Optimal Execution Games

cs.AI q-fin.TR ·2026-09-30 ·Christos Spyridon Koulouris, Carlo Campajola
benchmark similarity 0.67
Abstract

In this paper, we extend earlier findings of supra-competitive outcomes in optimal-execution games by identifying a learned punitive mechanism that deters deviations and provides behavioural evidence of collusion. We investigate this mechanism in a two-player, finite-horizon Almgren-Chriss liquidation game. Independent proximal policy optimisation agents with access to within-episode price and action histories achieve costs below the Nash benchmark. We identify a profitable deviation by training against the mean learned liquidation schedule, then impose its first trade on one of the original agents. The opponent responds by accelerating liquidation. This response more than offsets the deviator's gain in every run and both player roles, while leaving the punisher's average payoff materially unchanged relative to not punishing under the same deviation. The punisher imposes greater losses on the deviator while preserving its own average payoff, despite the availability of more profitable, less punitive liquidation plans. Matching deviations and subsequent additional selling rise and later decline during training, while final policies retain an effective punitive response. We formalise two checks: whether punishment outweighs the gain from deviating, and whether the change in trading behaviour is large enough to account for the loss imposed. Both checks hold for the tested deviation. Together, these findings provide behavioural and economic evidence supporting a collusive interpretation of the learned supra-competitive outcomes.

0.27

Is Anyone Enforcing the Cartel? What Reinforcement Learning Teaches LLM Agents in Markets

cs.CL cs.GTcs.LG ·2026-10-20 ·Hieu Tran, Hong Yu
similarity 0.66
Abstract · 45 pages, 13 figures, 20 tables

Evaluations of large language model (LLM) agents report that pricing agents collude at others' expense. Yet collusion is defined by enforcement: a cartel, in which competitors share monopoly profits, holds only if a member who cheats is punished. We introduce an audit that tests enforcement by forcing a member to cheat in counterfactual copies of a market, and use it to study what reinforcement learning (RL) teaches agents in pricing and trading. Small LLMs trained by RL learn what their training rivals reward, but only what they readily try. In self-play, they learn fixed rules ignoring their rivals; against a punishing rival, to be deterred; against a cheating rival, to match its cuts, never the costly price war that would deter it, which they rarely try. A war forced into training is learned, but mostly only where it was forced. Against their own copies, deterred and matching agents can earn the same cartel profits, but only matching ones can enforce them, and then thinly: as a by-product and only against large cuts. Q-learners enforce collusion only in pricing. Prompted LLMs reach cartel-like outcomes mostly through rules that ignore the market. Outcome measures cannot tell these cases apart; the audit can.

0.21

Multi-Agent Learning of Reactive Strategies in Iterated Games

cs.GT physics.soc-phq-bio.PE ·2026-10-10 ·James P. Wolfe, Joshua B. Plotkin
theorycode/data similarity 0.66
Abstract · 27 pages, 14 figures (12 pages + 3 figures main text; 15 pages + 11 figures Supplemental Material). Code: https://github.com/james-wolfe/rea…

Learning agents, whether humans or algorithms, adapt to one another rather than to a fixed environment. Selfish learning need not produce a good outcome for the group, especially when learners face a social dilemma. The iterated prisoner's dilemma (IPD) is the classical example, but it is usually studied in populations of agents who imitate successful strategies. Here, we instead study selfish gradient ascent learners on the two-dimensional space of reactive strategies. A reactive strategy is described by two continuous traits: reciprocity, the chance of cooperating after the co-player cooperates, and forgiveness, the chance of cooperating after the co-player defects. Each learner updates its strategy in the direction that most rapidly improves its payoff against all other learners, by an amount governed by its learning rate. We show that heterogeneity in learning rates can qualitatively change the long-term outcome: a population with uniform learning rates converges to always-defect (ALLD), whereas a population with variable learning rates approaches generous-tit-for-tat (GTFT), which produces nearly optimal collective payoffs. In simulations, every population passes through a transient state of minimal forgiveness, in which the distribution of reciprocity determines the outcome. Variable learning rates promote cooperation because slow learners preserve high reciprocity until the population reaches this state. We prove sufficient conditions on the distribution of reciprocity for convergence to ALLD or to tit-for-tat (TFT). Variable learning rates also allow cooperation to recover from perturbation, which is provably impossible under uniform learning. These results suggest that purely selfish and myopic learning can produce persistent cooperation provided the population has intrinsic variability in learning rates.

0.40

Specification Gaming and a Constrained Reinforcement Learning Mitigation in a Cleaning Gridworld

cs.LG cs.AI ·2026-10-15 ·Hilda Adwubi Osei
similarity 0.66
Abstract · 8 pages, 3 figures

Reinforcement learning agents optimize exactly the reward signal they are given, which can diverge sharply from an intended true objective when that signal is only a proxy for it; this failure mode is known as specification gaming. Existing evidence for this failure mode is largely observational, with comparatively few demonstrations pairing a controlled, deliberately constructed proxy/true gap with a mitigation that carries a verifiable guarantee rather than only an empirical improvement. We construct a minimal gridworld in which a cleaning-robot agent can either genuinely remove dirt or conceal it from a cheap sensor, and show that a standard deep Q-network trained only on the sensor's proxy reward converges to a policy that games it completely, reaching near-maximal proxy reward while never achieving the true objective. We then introduce a constrained reinforcement learning fix, penalizing the specific behaviors through which the agent exploits the gap, and show that it eliminates the gaming behavior from the final policy while substantially recovering true-objective performance. We further derive and empirically verify an exact accounting identity relating the proxy reward, true reward, and our cost signal for this environment, showing that the cost signal measures the proxy/true gap exactly rather than merely tracking it, and yields a deterministic guarantee under a hard-constrained variant of the method.

0.44

Regret, equilibrium, and learning in games: A guided tour

cs.GT cs.LGmath.OC ·2026-08-10 ·Panayotis Mertikopoulos
publishedtheory similarity 0.65
Abstract · 44 pages, 3 figures; to appear as a chapter in "Equilibria in Games: Existence, Selection, and Dynamics", edited by Sylvain Sorin and Bernha…

This note aims to serve as an entry point to the literature on learning in games, a topic with significant theoretical appeal and a wide range of applications -- from machine learning and data science to economics and beyond. Our presentation is structured around two complementary viewpoints: We first consider a single agent -- the learner -- engaged in a sequential decision process in an unknown, non-stationary, and possibly adversarial environment. We then examine what happens when the environment is shaped by the decisions of several interacting agents, not necessarily aware of each other's actions or goals, and all seeking to improve their individual rewards. In this general context, we examine a family of regularized learning policies based on best-responding to the past history of play, up to a regularization penalty intended to encourage exploration and prevent over-commitment to suboptimal choices. In the single-agent setting, we present some basic regret bounds for regularized learning in adversarial multi-armed bandits; in the multi-agent setting, we describe an ergodic equilibrium convergence result for zero-sum games in the spirit of classical results on fictitious play, as well as a "folk theorem" linking strategic and dynamic notions of stability -- Nash equilibria and attracting points of regularized learning, respectively. We pay special attention to the information available to the players and, through a unified analysis framework, we study both oracle- and payoff-based (bandit) methods. Our goal is to provide a coherent and comprehensible -- albeit, by necessity, not comprehensive -- account of some recent ideas in the field, and to discuss their implications for the study of rationality.

0.25

Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning

cs.LG eess.SY ·2026-10-02 ·Sreejeet Maity, Aritra Mitra
similarity 0.65
Abstract

We study federated reinforcement learning in which multiple agents interact with a common Markov decision process and communicate through a central server to collaboratively learn the optimal state-action value function. Our goal is to understand whether the sample-efficiency benefits of collaboration can be retained when a fraction of the agents behave adversarially and transmit arbitrarily corrupted information. To address this problem, we introduce Robust Async-Fed-Q, an epoch-based federated learning algorithm that combines variance-reduced estimation of the Bellman optimality operator at the agents with robust aggregation at the server. We establish high-probability finite-time guarantees showing that the proposed method preserves the statistical gains of collaboration among the honest agents while tolerating adversarial corruption. In particular, the effect of the adversarial agents decreases as the amount of data collected by each honest agent grows and eventually vanishes in the infinite-sample limit. We complement these guarantees with information-theoretic lower bounds that characterize the unavoidable statistical cost of adversarial corruption, leading to the first nearly matching upper and lower bounds for adversarially robust federated reinforcement learning. We further extend our framework to accommodate single-trajectory Markovian sampling and heterogeneous partial coverage, where different agents may explore different regions of the state-action space and learning relies on their collective coverage. Finally, our epoch-based design substantially improves the best known communication complexity for federated Q-learning under asynchronous sampling.

0.03