Research map / Multi-agent systems and games / Games and equilibria
Mitigating Retaliatory Algorithmic Collusion in Repeated Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes algorithmic collusion of Q-learners as implicit Simple Penal Codes and proposes CURB, a reward-shaping penalty on a total-variation signal of punishment-conditioned policies plus belief injection, which drives the collusion index near Nash in Bertrand and Cournot games under tabular Q-learning and DQN.
Problem
Q-learning agents in repeated games can converge to supra-competitive collusive outcomes sustained by punishment threats, and existing mitigations are tied to specific market settings or platform rules.
Approach
Shows any non-trivial Simple Penal Code forces a minimum TV distance between an agent's action distributions conditioned on opponent defection vs cooperation, then penalizes this TV signal in the shaped reward so that collusive SPC fixed points are eliminated, with belief injection of synthetic unpunished deviations to push toward Nash.
Key results
- In Bertrand n=2 tabular, CURB lambda=0.2 reduces CI from 0.8824 (no intervention) to 0.0029, versus 0.0706 for PDP and 0.0426 for DPDP.
- In Cournot tabular, CURB lambda=0.5 drives CI to zero and outperforms imperfect monitoring, which only partially reduces collusion.
- CURB reduces collusion in Bertrand DQN across all tested lambda settings, and TV outperforms JSD variants at matched lambda.
Surprising findings
- Belief injection alone stays near baseline collusion; only the combined TV shaping plus belief injection drives CI near zero.
- CURB converges symmetrically near Nash price whereas PDP and DPDP induce asymmetric pricing.
Limitations
- Formal guarantees only for two-player collusion; n>2 extension open.
- Belief injection lacks formal guarantees.
- Targets punishment-based collusion only; other collusion mechanisms may evade detection.
Experimental setup
Datasets: simulated Bertrand logit oligopoly (K=15) simulated deterministic Cournot oligopoly (K=15)
Benchmarks: Bertrand competition (n=2, n=3) Cournot competition Bertrand DQN
Metrics: collusion index (CI) average prices/profits
Baselines: No intervention Price-Directed Prominence (PDP) Dynamic PDP (DPDP) Imperfect monitoring (Cournot) Jensen-Shannon divergence reward shaping
Builds on: Q-learning Simple Penal Codes (Abreu) Calvano et al. collusion Q-learning setup DQN
Closest papers by meaning
- Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma (ICML 2025 · similarity 0.89)
- Domination-Avoiding Learning Agents Cannot Collude (NeurIPS 2026 · similarity 0.89)
- Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos (AAAI 2024 · similarity 0.87)
- LOQA: Learning with Opponent Q-Learning Awareness (ICLR 2024 · similarity 0.86)
- Asymptotic Extinction in Large Coordination Games (AAAI 2025 · similarity 0.86)
- Colosseum: Auditing Collusion in Cooperative Multi-Agent Systems (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.