arXiv:2609.20548v1 [cs.LG] 17 Sep 2026
Mitigating Retaliatory Algorithmic Collusion in Repeated Games
Karthik Sivachandran Department of Computer Science Purdue University [email protected]
Rohan R. Paleja Department of Computer Science Purdue University [email protected]
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.
1
Introduction
In August 2024, the U.S. Department of Justice sued RealPage, alleging that its pricing software had helped landlords coordinate rent increases across millions of American apartments, without any landlord ever explicitly agreeing to fix prices [29]. The mechanism was algorithmic: pricing systems, acting on profit signals, learned a behavior pattern that in aggregate looked like a cartel. Millions of renters had to pay supra-competitive rents. This is one of several recent cases highlighting a phenomenon documented across diverse multi-agent settings: reinforcement learning agents trained to maximize their own reward in repeated interactions can converge to supra-competitive outcomes resembling collusion, without communication or shared design. The phenomenon has been observed in pricing oligopolies [10, 22], ad auctions [4], and richer multi-agent learning environments [23, 20]. Detecting and mitigating this behavior has become an active concern at the intersection of economics, computer science, and antitrust policy [8, 16, 9]. Despite the multi-domain nature of algorithmic collusion, existing mitigation frameworks are limited. They remain tied to specific settings or operate on learning hyperparameters such as exploration rate or discount factor (Section 2). We address a deeper question: what equilibrium object sustains the reward–punishment dynamics observed in algorithmic collusion across repeated games, and how can interventions provably dismantle it? We address this question by formalizing the connection between algorithmic collusion and the classical theory of repeated games. Our approach builds on a key observation from Calvano et al. [10]: Q-learning agents that converge to collusive outcomes implicitly Preprint.
implement Simple Penal Codes (SPCs) [1]—reward-punishment strategies in which deviations trigger retaliatory paths. Calvano et al. [10] noted this empirical resemblance, but the connection to Abreu’s theory [1] has not been formalized or used for intervention. We make this bridge explicit to derive a mitigation framework. We make three contributions: 1) We formalize the connection between Calvano’s empirical observation and Abreu’s SPC theory, proving (Proposition 2) that any non-trivial SPC induces a quantifiable conditional dependence in agents’ policies, detectable via a total variation distance bound ε∗ (δ) > 0 that depends only on game primitives. 2) We propose CURB (Collusion Unwinding via Reward shaping and Belief injection), a framework that penalizes the TV-distance signal during Q-learning. We prove (Theorem 1) that for sufficient penalty strength, every SPC fixed point of shaped Q-learning is trivial, thus preventing collusive equilibria sustained by punishment threats. 3) We empirically validate CURB across two repeated-game settings (Bertrand and Cournot competition) and two learning algorithms (tabular Q-learning and DQN), demonstrating that collusion is heavily mitigated.
2
Related Work
Observation of algorithmic collusion. A substantial body of work has documented algorithmic collusion across diverse settings. Bertrand et al. [5] show that self-play Q-learners can collude in the iterated prisoner’s dilemma, while Hansen et al. [15] and Asker et al. [2] demonstrate that even simple pricing algorithms can generate supra-competitive outcomes in standard pricing games. In oligopoly settings, Calvano et al. [10] and Klein [22] show that Q-learning agents can sustain collusion through reward–punishment dynamics in Bertrand competition, and Hettich [19] shows that deep Q-networks [25] converge to such outcomes more rapidly than tabular learners. Similar behavior has been observed in Cournot oligopoly [30], dealer markets [12], and auction environments [4]. More broadly, cooperation among learning agents arises naturally in sequential social dilemmas [23, 20]; while beneficial in some settings, these dynamics become problematic when coordination harms external parties. Recent work further shows that LLM-based agents can exhibit collusive behavior in strategic environments [14, 24]. Real-market evidence confirms these risks are not merely theoretical: Assad et al. [3] document an increase in duopoly margins where both stations adopt algorithmic pricing in Germany’s retail gasoline market, with similar findings in online retailers of over-the-counter pharmaceuticals [7] and on e-commerce marketplaces [26]. Mitigation approaches. Calvano et al. [11] demonstrate that imperfect monitoring of competitors’ actions modestly weakens but does not eliminate collusion. Banchio and Skrzypacz [4] disrupt collusion in ad auctions by switching first-price to second-price, an intervention tied to auction format. Platform-side approaches, learned policies via Stackelberg POMDPs [6] and the platform pricing rules of Johnson et al. [21], require a centralized platform with authority to modify payoffs or rules and do not generalize across repeated games. Hartline et al. [17, 18] propose ex-post auditing, which detects collusion but does not prevent it. Positioning of CURB. CURB targets the punishment-threat equilibrium structure that sustains collusion rather than the conditions surrounding learning, the infrastructure around the agents, or the symptoms collusion produces in market outcomes. Where prior approaches detect collusion after it occurs, redesign the strategic environment, or impose platform-side rules, CURB modifies the agent’s own learning rule with a penalty derived from the equilibrium structure of repeated games, providing a formal guarantee that the collusive equilibrium sustained by threats do not survive as a fixed point. The mechanism requires only observing competitors’ actions, which is standard in any repeated game with public actions, and applies across repeated games in the same independent-learner settings where collusion arises, without changing the strategic environment or requiring centralized infrastructure.
3
Preliminaries
All theoretical results are stated for a general stage game. Let G = ({Ai }ni=1 , {ri }ni=1 ), where N = {1, . . . , n} is the set of players, A = ×i∈N Ai is the joint action space with Ai finite for each player i, and r = (r1 , . . . , rn ) with ri : A → R is the profile of payoff functions. We denote a joint action at time t by q(t) = (q1t , . . . , qnt ) ∈ A, where qit is the action taken by player i at time t. The supergame G∞ (δ) is the infinitely repeated version of G with common discount factor δ ∈ (0, 1). A pure strategy for player i is a sequence of functions σi = (σi (1), σi (2), . . .) where σi (1) ∈ Ai and σi (t) : At−1 → Ai for t ≥ 2, mapping the history of all past joint actions to an action at period t. A strategy profile is σ = (σ1 , . . . , σn ) ∈ Σ ≡ ×i∈N Σi , where Σi is the ∞ strategy set of player i. A path Q = {q(t)}∞ is an infinite sequence of joint action profiles. t=1 ∈ A Every strategy profile σ generates a unique path Q(σ) defined inductively by q(σ)(1) = σ(1) and 2
q(σ)(t) = σ(t)(q(σ)(1), . . . , q(σ)(t − 1)). The discounted payoff to player i from path Q is defined P∞ by vi (Q) = t=1 δ t−1 ri (q(t)). Assumption 1 (Bounded Payoffs). There exist rmin , rmax ∈ R such that ri (a) ∈ [rmin , rmax ] for all i ∈ N , a ∈ A. Assumption 2 (Finite Action Space). Ai is finite for all i ∈ N . Assumption 3 (Markov State). The state st ∈ S observed by agents at period t is a sufficient statistic of the payoff-relevant history. The state space S is finite. Theoretical regime. Our results assume: (T1) The cooperative path Q0 is pure: qi0 (t) ∈ Ai is deterministic for all i ∈ N , t ≥ 1. (T2) Learned policies πj are stationary policies mapping S → ∆(Aj ), where ∆(Aj ) is the set of probability distributions on Aj . This includes deterministic greedy and ε-greedy policies. (T3) The total variation (TV) distance in the shaped reward is computed over the exact conditional action distributions induced by πj . Under (T2), πj (· | at−1 ∈ Diϕ ) and πj (· | at−1 ∈ Ciϕ ) are distributions on Aj , and TV ∈ [0, 1] takes i i continuous values. Our intervention operates in an empirical regime where TV is estimated from finite action-frequency windows. Empirical TV converges to theoretical TV as windows grow and exploration anneals. 3.1
Simple Penal Codes
We recall the central equilibrium concept from Abreu [1]. For definitions of Nash Equilibrium and subgame perfect equilibrium we defer to Rubinstein [27]. Definition 1 (Simple Strategy Profile). Let Q0 , Q1 , . . . , Qn ∈ A∞ be paths. The simple strategy profile σ(Q0 , Q1 , . . . , Qn ) specifies: 1. play Q0 until some player deviates singly 2. if player j deviates singly from any ongoing path, switch to Qj immediately 3. simultaneous deviations leave the ongoing path unchanged Definition 2 (Simple Penal Code). A simple strategy profile σ(Q0 , Q1 , . . . , Qn ) is a Simple Penal Code (SPC) if it is a subgame perfect equilibrium of G∞ (δ). For the statement of the sustainability condition, we introduce two quantities. The one-shot deviation gain for player j at period t along path Qi is given by Equation 1. i i ∆j (qj∗ , q−j (t)) = rj (qj∗ , q−j (t)) − rj (q i (t)) (1) i In Equation 1, qj∗ ∈ arg maxa∈Aj rj (a, q−j (t)) is player j’s best deviation. The continuation value of player j from period t + 1 onward along path Q is given by Equation 2 ∞ X vj (Q; t + 1) = δ s rj (q(t + s)). (2) s=1
The following result characterizes when a simple strategy profile is an SPC. Proposition 1 (Abreu [1]). Under Assumptions 1-3, the simple strategy profile σ(Q0 , Q1 , . . . , Qn ) is a subgame perfect equilibrium if and only if for all j ∈ N , i ∈ {0, . . . , n}, and t ≥ 1: i ∆j (qj∗ , q−j (t)) ≤ vj (Qi ; t + 1) − vj (Qj ) . | {z } | {z }
(3)
loss from punishment
gain from deviating
We call Equation 3 the sustainability condition. Collusion is sustained when deviation gains are outweighed by punishment losses. Remark 1 (One-shot deviation). Under Assumptions 1–3, Proposition 1 is equivalent to the one-shot deviation principle: σ is a subgame-perfect equilibrium iff no agent can profitably deviate for a single period and then revert to σ at any subgame. Remark 2. We consider agents that learn via tabular Q-learning [31]. Full details of the update rule are provided in Appendix A. In the repeated game G∞ (δ), the state observed by agents at period t is the k-period action history st = (q(t − 1), q(t − 2), . . . , q(t − k)) ∈ Ak . 3
3.2
Collusion as an Implicit Simple Penal Code
We use the term collusion to refer to outcomes where agents sustain supra-Nash payoffs at the expense of a third party whose welfare falls below its Nash level. Definition 3 (Collusive Strategy Profile). A strategy profile σP is collusive if it implements a non∞ trivial Simple Penal Code and W (Q0 ) < W (QNash ). W (Q) = t=1 δ t−1 w(q(t)) is the discounted third-party welfare under path Q, w : A → R is the per-period third-party welfare function, and QNash is the path generated by the stage-game Nash equilibrium. The trivial SPC σ(QNash , . . . , QNash ) is non-collusive since Q0 = QNash implies W (Q0 ) = W (QNash ). Observation 1. When Q-learning agents converge to a collusive outcome in the sense of Definition 3, their learned policies (π1 , . . . , πn ) implicitly implement a Simple Penal Code σ(Q0 , Q1 , . . . , Qn ), where Q0 is the collusive path satisfying W (Q0 ) < W (QNash ) and each Qj is a punishment path encoding state-contingent retaliation following a unilateral deviation by player j. Observation 1 is supported empirically by Calvano et al. [10], who document that converged Qlearning policies in the Bertrand game exhibit reward-punishment behavior consistent with an implicit Simple Penal Code: agents cooperate on a supra-Nash path and retaliate following unilateral deviations. We treat Observation 1 as an empirically motivated modeling assumption rather than a formally established property. Intervention rationale. Under Obs. 1, preventing any collusive SPC (Def. 3) from being a fixed point of Q-learning is sufficient to prevent collusive subgame perfect equilibrium payoffs sustained by punishment threats from emerging, guaranteeing W (Q0 ) ≥ W (QNash ) at convergence, provided Q-learning converges to a fixed point. This motivates us to detect and dismantle the punishment structure that sustains collusive outcomes rather than target collusive outcomes directly.
4
Detecting Simple Penal Codes via Total Variation Distance
We now develop the first component: a method for detecting whether a learned policy implements an Abreu punishment path. We begin by formalizing what it means for a learned policy to implement such a path and prove TV distance between conditional policy distributions is necessary and sufficient for detection. 4.1
Formalizing Punishment Strategies in Learned Policies
When Q-learning agents collude, their learned policies implicitly implement a Simple Penal Code 1. The punishment paths Q1 , . . . , Qn emerge implicitly in the Q-table. Agent j has learned a punishment strategy if its policy depends on whether agent i defected previously. Let Q0 ∈ A∞ denote the cooperative path and define the defection partition of Ai at period t as: Ci (Q0 , t) = a ∈ Ai : a = qi0 (t) , (4) Di (Q0 , t) = Ai \ Ci (Q0 , t),
(5)
where qi0 (t) is agent i’s prescribed action under Q0 at period t. The set Ci (Q0 , t) contains actions consistent with the cooperative path and Di (Q0 , t) contains all deviations from it. However, Q0 may not be observable during learning, and computing the Nash equilibrium, the natural alternative reference point, is PPAD-hard in general [13]. We therefore introduce a general defection criterion that subsumes both approaches and accommodates settings where neither Q0 nor the Nash equilibrium is directly available. Definition 4 (Defection Criterion). A defection criterion for agent i is a function ϕi : S ×Ai → {0, 1} mapping a state-action pair (s, ai ) to a binary defection indicator. The induced partition at period t is: Diϕ (t) = ati ∈ Ai : ϕi (st , ati ) = 1 , (6) Ciϕ (t) = Ai \ Diϕ (t). Remark 3. Three instantiations of Definition 4 are provided in Appendix B. 4
(7)
Assumption 4 (α-Precise Defection Criterion). The defection criterion ϕi has precision at least 1 − α on both sides: for all t ≥ 1, P at−1 ∈ Di (Q0 , t) ϕi (st , ati ) = 1 ≥ 1 − α, (8) i t−1 0 t P ai ∈ Ci (Q , t) ϕi (st , ai ) = 0 ≥ 1 − α, (9) where α ∈ [0, 1/2). Definition 5 (Punishment Strategy). Let (Diϕ , Ciϕ ) be the partition induced by an α-precise defection criterion (Assumption 4), and let ε > 0. Under the theoretical regime, a stationary policy πj : S → ∆(Aj ) is a (Diϕ , Ciϕ , ε)-punishment strategy if πj (· | at−1 ∈ Diϕ ) − πj (· | at−1 ∈ Ciϕ ) > ε, i i TV P where ∥µ − ν∥T V = 12 a∈Aj |µ(a) − ν(a)| is the total variation distance. 4.2
(10)
TV Distance as a Necessary Detector
Proposition 2 (TV Distance Detects Punishment). Let G∞ (δ) be a two-player repeated game under the theoretical regime, satisfying Assumptions 1–3. Let Q0 ∈ A∞ be a non-Nash pure path, and let πj be a stationary policy for agent j with path-consistent defection partition (Di (Q0 , t), Ci (Q0 , t)). If there exist paths Qi , Qj ∈ A∞ such that σ(Q0 , Qi , Qj ) is a non-trivial SPC of G∞ (δ) with Qi induced by πj ’s post-deviation behavior, then πj (· | at−1 ∈ Di (Q0 , t)) − πj (· | at−1 ∈ Ci (Q0 , t)) T V ≥ ε∗ (δ), i i
(11)
where
(1 − δ)∆∗ ∈ (0, 1], ∆∗ := vi (Q0 ; t∗ + 1) − vi (Qi ) > 0, rmax − rmin and t∗ is the period at which the sustainability condition (3) binds for agent i. ε∗ (δ) :=
(12)
Proof sketch. Since Q0 is non-Nash, the sustainability condition binds at some t∗ with ∆∗ > 0. e where agent i continues cooperating while agent j plays punishment Construct an intermediate path Q e Hence the actions. By subgame perfection, the true punishment path Qi weakly dominates Q. continuation-value gap ∆∗ must arise from differences in j’s conditional action distributions between cooperation and punishment phases. Expected payoff differences are bounded by total variation distance times the payoff range, yielding TV ≥ (1 − δ)∆∗ /(rmax − rmin ). A full proof is provided in Appendix C.1.2. Corollary 1. If the TV distance above equals zero, then the induced path Qi coincides with Q0 , and πj cannot implement any non-trivial punishment path against agent i. A full proof is provided in Appendix C.1.3 Observation 2. Let πjNash denote the stationary stage-game Nash policy: πjNash plays a stage-game Nash action at every period, independent of history. Then ∥πjNash (· | at−1 ∈ Diϕ ) − πjNash (· | at−1 ∈ Ciϕ )∥T V = 0 i i
for all i, j ∈ N.
Remark 4 (Non-stationary Nash equilibria). Observation 2 concerns the stationary stage-game Nash policy, which is what the trivial SPC σ(QNash , . . . , QNash ) uses. The repeated game admits additional subgame-perfect equilibria that are history-dependent (for example, grim trigger); these are not the object of Observation 2. Corollary 2 (α-precise extension). Let πj be a stationary policy for agent j consistent with the SPC structure of Definition 1: πj ’s action distribution at period t depends on whether the SPC is in the cooperation phase or the punishment phase triggered by player i’s deviation, and is characterized by two phase-conditional distributions πjC := πj (· | cooperation phase),
πjD := πj (· | punishment phase against i).
∗
0
i
(13)
j
Under Assumption 4 with α < ε (δ)/2, for any collusive SPC σ(Q , Q , Q ), ∥πj (· | ϕi = 1) − πj (· | ϕi = 0)∥T V ≥ ε∗ (δ) − 2α > 0. 5
(14)
A full proof is provided in Appendix C.1.4. Proposition 2 establishes that under the theoretical regime, punishment strategies cannot evade detection via vanishing TV distance: any non-trivial SPC forces πj ’s conditional distributions to differ by at least ε∗ (δ) > 0. Corollary 2 shows this detection signal degrades with classifier noise. Section 5 exploits this result to construct a reward penalty that fires when a collusive SPC is forming.
5
Suppressing Collusive SPCs via Reward Shaping
Proposition 2 establishes that any collusive SPC produces a detectable TV distance signal. We now show how to use this signal to dismantle the punishment structure sustaining collusion. Our intervention has two complementary components: reward shaping, which raises the cost of executing a punishment strategy and removes retaliation as a fixed-point property; and belief injection, which biases the dynamics among the surviving non-collusive fixed points toward the competitive equilibrium. The first has formal guarantees (Theorem 1); the second an empirically validated learning-dynamics heuristic. 5.1
Reward Shaping Against Punishment Strategies
We define the shaped reward for agent j at period t as rjshaped (st , at ) = rj (st , at ) − λ · ∥πj (· | at−1 ∈ Diϕ ) − πj (· | at−1 ∈ Ciϕ )∥T V . Here, λ > 0 is the penalty strength. The penalty is nonzero i i only when agent j implements a punishment strategy. By Observation 2, the penalty is zero at Nash equilibrium, so Nash play is never penalized. Proposition 3 (Conditional invariance and trivial SPCs). Under the theoretical regime and Assumption 4 with α < ε∗ (δ)/2, agent j’s policy πj satisfies ∥πj (· | ϕi = 1) − πj (· | ϕi = 0)∥T V = 0 if and only if every SPC consistent with πj is trivial, of the form σ(Q, Q, Q) in which all paths coincide and no punishment is executed. A full proof is provided in Appendix C.2. Proposition 4 (Shaping forces conditional invariance at SPC fixed points). Let G∞ (δ) be a twoplayer repeated game under the theoretical regime, satisfying Assumptions 1–4 with α < ε∗ (δ)/2. ⋆ Let (πj⋆ , π−j ) be a greedy-policy fixed point of the shaped Q-learning dynamics that implements an 0 SPC σ(Q , Qi , Qj ). For any rmax − rmin λ > λ∗ := ∗ , (15) ε (δ) − 2α πj⋆ is conditionally invariant on the defection partition: πj⋆ (· | ϕi = 1) − πj⋆ (· | ϕi = 0) T V = 0.
(16)
Proof sketch. Suppose for contradiction that a fixed-point policy πj⋆ has TV⋆j > 0. Construct πj′ by copying πj⋆ ’s cooperation-phase behavior to all states, giving TV′j = 0. Since πj⋆ is stationary, its TV penalty is constant per step, accumulating to λ · TV⋆j /(1 − δ) in the shaped Q-function. Policy πj′ incurs zero penalty. Both unshaped Q-functions are bounded in [rmin /(1 − δ), rmax /(1 − δ)], so the worst-case unshaped value loss from switching to πj′ is (rmax − rmin )/(1 − δ). For λ > λ⋆ , the penalty savings exceed this loss, so Q′j dominates Q⋆j , contradicting the optimality of πj⋆ at the fixed point. A full proof is provided in Appendix C.3. 5.2
Theoretical Guarantees
We now state the main theoretical result, combining Propositions 3 and 4 to characterize the fixedpoint structure of shaped Q-learning. Theorem 1 (Main Theorem). Under Assumptions 1–4 with α < ε∗ (δ)/2, for any λ > λ∗ , every SPC fixed point of the shaped Q-learning dynamics is trivial: of the form σ(Q, Q, Q) for some path Q ∈ A∞ , where all paths coincide and no punishment is executed. ⋆ Proof. Let (πj⋆ , π−j ) be a greedy-policy fixed point of the shaped Q-learning dynamics that imple0 ments an SPC σ(Q , Qi , Qj ). By Proposition 4, for λ > λ∗ , πj⋆ is conditionally invariant on the
6
defection partition:
πj⋆ (· | ϕi = 1) − πj⋆ (· | ϕi = 0) T V = 0. By Proposition 3, conditional invariance holds if and only if every SPC consistent with πj⋆ is trivial, of the form σ(Q, Q, Q) in which all paths coincide and no punishment is executed. Hence the SPC implemented at the fixed point is trivial. Corollary 3 (Punishment Dismantling). Under the conditions of Theorem 1, if shaped Q-learning converges to an SPC fixed point, no punishment paths are executed: agent behavior at the converged equilibrium does not condition on whether opponents defected. Proof. Immediate from Theorem 1. Any SPC fixed point is of the form σ(Q, Q, Q), in which the cooperative path and post-deviation continuation paths coincide. Hence no punishment is executed regardless of whether ϕi = 0 or ϕi = 1. Theorem 1 establishes that the punishment structure that sustains collusion is removed at any SPC fixed point of the shaped dynamics. We do not claim the resulting trivial SPC corresponds to the stage-game Nash path: shaped Q-learning optimizes the shaped reward, and a trivial SPC may sustain a non-Nash path so long as no punishment is executed. We address this gap with the belief-injection mechanism below and validate the combined intervention empirically in Section 6. Proposition 5 (Nash Stability). The stationary stage-game Nash equilibrium policy profile is a fixed point of shaped Q-learning. A full proof is provided in Appendix C.4. Combined with Theorem 1, Proposition 5 implies that the set of SPC fixed points of shaped Q-learning includes Nash and is restricted to trivial SPCs. The dynamics cannot sustain collusion via punishment threats. Belief Injection. The reward shaping component raises the cost of j having a policy conditioned on player i’s action. This could lead to a situation where player j always chooses the monopoly price regardless of what i chooses. Normally, this would not be an issue as through the Q-learning updates player j will still reduce its price to stay competitive. However, an issue arises if they both settle at always playing the monopoly price. For this we complement this with a belief injection mechanism targeting agent i’s incentive to cooperate. Collusion is sustained because agent i believes that defection will trigger punishment by agent j. If this belief is incorrect, if agent i expects no retaliation after defection, the cooperative path Q0 becomes individually irrational and collusion fails. In every k steps we inject m synthetic experiences of the form (s, ai ∈ Diϕ , no retaliation by j) into agent i’s replay buffer, shifting its estimated Q-value for defection upward. Through this we are able to bias exploration during learning towards away from a collusive policy. The CURB Algorithm. At each stage game, every agent (i) selects an action and observes the reward, (ii) updates its Q-values using a TV-shaped reward that penalizes behavior conditional on past opponent defection, and (iii) periodically receives synthetic experiences depicting a unilateral deviation going unpunished. The penalty uses the maximum TV across opponents so the shaping extends naturally to n > 2 agents. The full algorithm is given in appendix D.
6
Experiments and Results
We evaluate CURB in Bertrand and Cournot repeated games under both tabular Q-learning and DQN. In Bertrand competition, agents choose prices each round; unilateral undercutting constitutes defection and price wars act as punishment. We use the Calvano et al. [10] setup with K = 15 actions and n = 2 unless otherwise stated. In Cournot competition, firms choose quantities under linear inverse demand; overproduction constitutes defection. We report the collusion index CI = (π̄ −π Nash )/(π Mono −π Nash ) from [10], where CI = 0 denotes Nash play and CI = 1 full collusion. Since higher collusive profits in repeated oligopoly settings come at the expense of consumer surplus, increases in CI correspond to decreases in consumer welfare [28]. A summary of the experiments is in Appendix E. Defection criterion and belief injection. CURB requires a defection indicator ϕi to partition each agent’s action history into “cooperative” and “defective” subsets. We use a simple online instantiation: an action is flagged as defective if it falls on the deviator side of the rolling-history median (below the median for Bertrand prices, above the median for Cournot quantities). Belief injection is implemented by periodically writing synthetic transitions into each agent’s update target where that agent unilaterally defects against cooperative opponents and is not retaliated against, and 7
No intervention CURB =0.05 CURB =0.10 CURB =0.20 CURB =0.50
1.0 0.8
No intervention TV =0.20 Belief only CURB =0.20
1.2
Collusion Index
Collusion Index
1.2
0.6 0.4 0.2
1.0 0.8 0.6 0.4 0.2
0.0
0.0 0.0
0.5
1.0
1.5
2.0
Training steps (×106)
2.5
3.0
0.0
(a) λ ablation
0.5
1.0
1.5
2.0
Training steps (×106)
2.5
3.0
(b) Component ablation at λ=0.2
Figure 1: CURB on Bertrand Competition n=2 Condition No intervention PDP DPDP CURB λ=0.2 CURB λ=0.5
p0
p1
CI
1.8142 ± 0.0618 1.4464 ± 0.0213 1.5164 ± 0.1171 1.4729 ± 0.0000 1.4729 ± 0.0000
1.8239 ± 0.0669 1.7198 ± 0.1266 1.5671 ± 0.1317 1.4748 ± 0.0082 1.4748 ± 0.0082
0.8824 ± 0.1067 0.0706 ± 0.0786 0.0426 ± 0.0408 0.0029 ± 0.0124 0.0020 ± 0.0086
Table 1: Baseline comparison on Bertrand Competition n=2.
is rewarded with the analytic profit at that synthetic joint outcome. In tabular settings the synthetic transition triggers a direct Q-update, in DQN it is pushed into the per-policy replay buffer. Bertrand (tabular) ablations. 1. Penalty strength λ sweep. Figure 1(a) shows a clear threshold effect. λ = 0.05 behaves similarly to the no-intervention baseline, λ = 0.10 partially reduces collusion, and λ ∈ {0.2, 0.5} drives CI close to Nash level. 2. Component ablation. Figure 1(b) compares TV shaping alone, belief injection alone, and full CURB at λ = 0.2. TV-only partially reduces collusion, belief-only remains near baseline, and only the combined intervention drives CI near zero. 3. Platform-design baselines. We compare CURB against Price-Directed Prominence (PDP) and Dynamic PDP [21], interventions in which a platform controls which seller is shown to consumers based on current price (PDP) as well as price history (DPDP). Because PDP and DPDP require a centralized platform while CURB modifies only the agents’ update rule, we use a modified protocol: agents are trained under the platform rule, then evaluated in the full Bertrand environment, asking whether the platform-trained policy retains competitive behavior in the full Bertrand game. Table 1 shows all three substantially reduce collusion relative to baseline, with CURB achieving the lowest CI. Unlike PDP/DPDP, which induce asymmetric pricing, CURB converges symmetrically near the Nash price. This indicates that CURB mitigates collusion in a competitively neutral way that does not advantage one seller over the other. Further, by agents having more symmetry in prices consumers have more variety to choose from. 4. n = 3 extension. We test whether CURB scales beyond duopoly. Figure 2(a) shows the CI of the baseline reaches a substantially collusive equilibrium. CURB λ=0.2 partially reduces collusion. CURB λ = 0.5 drives the CI near zero for n = 3. 5. Divergence ablation. We chose TV distance for CURB due to its simplicity. However, from an information theoretic perspective it is natural to ask whether the TV penalty can be replaced by alternative divergence measures. We compare TV against Jensen–Shannon Divergence (JSD) at matched λ, using two conventions: JSD-norm rescales to [0, 1] to match TV’s range, JSD-raw keeps its native range [0, ln 2]. Figure 2(b) shows that all three metrics qualitatively reduce collusion below baseline, but at any given λ, TV > JSD-norm > JSD-raw in mitigation strength. This suggests the CURB framework may extend beyond TV distance to other divergence measures. 6. Forced-defection diagnostic. We manually force unilateral defections in converged rollouts and measure opponent responses; results are reported in Appendix F. Cournot (tabular). We compare CURB against no intervention and the imperfect-monitoring modification of Calvano et al. [11], in which agents observe a noisy version of their opponents’ quantities rather than the exact joint action. Figure 3(a) shows the CI over training for the nointervention baseline, imperfect monitoring [11], and CURB at λ ∈ {0.1, 0.2, 0.5}. Imperfect monitoring partially reduces collusion, consistent with prior literature [11]. CURB λ=0.5 drives the 8
1.0
Final CI (mean ± SEM)
Collusion Index
1.2
No intervention CURB =0.20 CURB =0.50
1.2 0.8 0.6 0.4 0.2 0.0 0
2
4
6
8
10
Training steps (×106)
12
No intervention (0.88) TV JSD (norm.) JSD (raw)
1.0 0.8 0.6 0.4 0.2 0.0
14
= 0.1
= 0.2
= 0.5
(b) TV vs JSD divergence ablation, n=2
(a) Bertrand Competition n=3
Figure 2: Left: CURB scales to n = 3 agents. Right: TV outperforms JSD variants at matched λ. No intervention Imperfect monitoring CURB = 0.1 CURB = 0.2 CURB = 0.5
1.0 0.8
No intervention CURB = 0.1 CURB = 0.2 CURB = 0.5
1.2
Collusion Index
Collusion Index
1.2
0.6 0.4 0.2
1.0 0.8 0.6 0.4 0.2
0.0
0.0 0.0
0.5
1.0
1.5
2.0
Training steps (×106)
2.5
3.0
0.0
(a) Cournot Competition n=2
0.2
0.4
0.6
Training steps (×106)
0.8
1.0
(b) DQN-Bertrand Competition n=2
Figure 3: CURB transfers to Cournot competition and DQN.
CI to zero and outperforms imperfect monitoring. This demonstrates that CURB transfers across multiple repeated-game environments. Bertrand (DQN) We replace tabular Q-learning with independent DQNs using 3-layer MLPs and replay buffers. Figure 3(b) shows that all CURB settings substantially reduce collusion relative to baseline, indicating the mechanism transfers beyond tabular learning.
7
Discussion & Conclusion
The defection criterion ϕi introduces a tunable parameter that, while requiring domain knowledge about what constitutes cooperation and defection, also provides a useful degree of design flexibility. In many settings, certain joint action profiles may be cooperative yet welfare-neutral, while others are cooperative in appearance but harmful to third parties. Because ϕi partitions the action space explicitly, a designer can target specifically the subset of coordinated behaviors that reduce third-party welfare while grouping all remaining actions. This selectivity is a feature of the framework: rather than penalizing all history-dependent behavior indiscriminately, CURB can be tuned to intervene only against the coordination patterns that cause harm. Limitations. Our formal guarantees apply only to two-player collusion; extending the analysis to n > 2 remains open. Belief injection is empirically effective but currently lacks formal guarantees. The framework targets collusion sustained by punishment dynamics, which prior literature has identified as a prominent mechanism by which algorithmic collusion arises. Whether CURB’s detection signal would remain informative in settings where collusion may be sustained through alternative mechanisms is an open question. Conclusion. We formalized the connection between algorithmic collusion and Simple Penal Codes, showing that non-trivial punishment strategies induce a detectable TV-distance signal in learned policies. Building on this connection, we proposed CURB, a framework that suppresses punishmentbased collusion. Across Bertrand and Cournot competition under both tabular Q-learning and DQN, CURB consistently drove the Collusion Index near zero without modifying the game structure or requiring centralized control. As the risk of algorithmic collusion grows across markets and multiagent systems, the need for principled interventions becomes increasingly pressing. By grounding mitigation in the equilibrium structure of repeated games rather than in the specifics of any one market or platform, CURB offers a step toward general-purpose tools for safeguarding competitive outcomes wherever autonomous agents learn to interact. 9
References [1] Dilip Abreu. On the theory of infinitely repeated games with discounting. Econometrica, 56 (2):383–396, 1988. ISSN 00129682, 14680262. URL http://www.jstor.org/stable/ 1911077. [2] John Asker, Chaim Fershtman, and Ariel Pakes. Artificial intelligence, algorithm design, and pricing. AEA Papers and Proceedings, 112:452–56, May 2022. doi: 10.1257/pandp.20221059. URL https://www.aeaweb.org/articles?id=10.1257/pandp.20221059. [3] Stephanie Assad, Robert Clark, Daniel Ershov, and Lei Xu. Algorithmic pricing and competition: Empirical evidence from the german retail gasoline market. Journal of Political Economy, 132 (3):723–771, 2024. doi: 10.1086/726906. URL https://doi.org/10.1086/726906. [4] Martino Banchio and Andrzej Skrzypacz. Artificial intelligence and auction design. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 30–31, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450391504. doi: 10.1145/3490486.3538244. URL https://doi.org/10.1145/3490486.3538244. [5] Quentin Bertrand, Juan Agustin Duque, Emilio Calvano, and Gauthier Gidel. Self-play qlearners can provably collude in the iterated prisoner’s dilemma. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 3952–3975. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/v267/bertrand25a.html. [6] Gianluca Brero, Eric Mibuari, Nicolas Lepore, and David Parkes. Learning to mitigate ai collusion on economic platforms. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 37892–37904. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ f746974abd33c0015ca583a267dac1fd-Paper-Conference.pdf. [7] Zach Y. Brown and Alexander MacKay. Competition in pricing algorithms. American Economic Journal: Microeconomics, 15(2):109–56, May 2023. doi: 10.1257/mic.20210158. URL https://www.aeaweb.org/articles?id=10.1257/mic.20210158. [8] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolò, and Sergio Pastorello. Algorithmic pricing what implications for competition policy? Review of Industrial Organization, 55 (1):155–171, August 2019. ISSN 1573-7160. doi: 10.1007/s11151-019-09689-3. URL https://doi.org/10.1007/s11151-019-09689-3. [9] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolò, Joseph E. Harrington, and Sergio Pastorello. Protecting consumers from collusive prices due to ai. Science, 370(6520):1040– 1042, 2020. doi: 10.1126/science.abe3796. URL https://www.science.org/doi/abs/10. 1126/science.abe3796. [10] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicolò, and Sergio Pastorello. Artificial intelligence, algorithmic pricing, and collusion. The American Economic Review, 110(10):pp. 3267–3297, 2020. ISSN 00028282, 19447981. URL https://www.jstor.org/stable/ 26966472. [11] Emilio Calvano, Giacomo Calzolari, Vincenzo Denicoló, and Sergio Pastorello. Algorithmic collusion with imperfect monitoring. International Journal of Industrial Organization, 79: 102712, 2021. ISSN 0167-7187. doi: https://doi.org/10.1016/j.ijindorg.2021.102712. URL https://www.sciencedirect.com/science/article/pii/S0167718721000059. [12] Rama Cont and Wei Xiong. Dynamics of market making algorithms in dealer markets: Learning and tacit collusion. Mathematical Finance, 34(2):467–521, 2024. doi: https://doi.org/10. 1111/mafi.12401. URL https://onlinelibrary.wiley.com/doi/abs/10.1111/mafi. 12401. 10
[13] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’06, page 71–78, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595931341. doi: 10.1145/1132516.1132527. URL https: //doi.org/10.1145/1132516.1132527. [14] Sara Fish, Yannai A. Gonczarowski, and Ran I. Shorrer. Algorithmic collusion by large language models. arXiv preprint arXiv:2404.00806, 2024. URL https://arxiv.org/abs/ 2404.00806. [15] Karsten T. Hansen, Kanishka Misra, and Mallesh M. Pai. Frontiers: Algorithmic collusion: Supra-competitive prices via independent algorithms. Marketing Science, 40(1):1–12, January 2021. ISSN 1526-548X. doi: 10.1287/mksc.2020.1276. URL https://doi.org/10.1287/ mksc.2020.1276. [16] Joseph E Harrington. Developing competition law for collusion by autonomous artificial agents†. Journal of Competition Law & Economics, 14(3):331–363, 09 2018. ISSN 1744-6414. doi: 10.1093/joclec/nhy016. URL https://doi.org/10.1093/joclec/nhy016. [17] Jason D. Hartline, Sheng Long, and Chenhao Zhang. Regulation of algorithmic collusion. In Proceedings of the 2024 Symposium on Computer Science and Law, CSLAW ’24, page 98–108, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703331. doi: 10.1145/3614407.3643706. URL https://doi.org/10.1145/3614407.3643706. [18] Jason D. Hartline, Chang Wang, and Chenhao Zhang. Regulation of algorithmic collusion, refined: Testing pessimistic calibrated regret. In Proceedings of the 2025 Symposium on Computer Science and Law, CSLAW ’25, page 108–120, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400714214. doi: 10.1145/3709025.3712217. URL https://doi.org/10.1145/3709025.3712217. [19] Matthias Hettich. Algorithmic collusion: Insights from deep learning. CQE Working Papers 9421, Center for Quantitative Economics (CQE), University of Muenster, Nov 2021. URL https://ideas.repec.org/p/cqe/wpaper/9421.html. [20] Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Dueñez Guzman, Antonio García Castañeda, Iain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, Heather Roff, and Thore Graepel. Inequity aversion improves cooperation in intertemporal social dilemmas. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/ 7fea637fd6d02b8f0adf6f7dc36aed93-Paper.pdf. [21] Justin P. Johnson, Andrew Rhodes, and Matthijs Wildenbeest. Platform design when sellers use pricing algorithms. Econometrica, 91(5):1841–1879, 2023. doi: https://doi.org/ 10.3982/ECTA19978. URL https://onlinelibrary.wiley.com/doi/abs/10.3982/ ECTA19978. [22] Timo Klein. Autonomous algorithmic collusion: Q-learning under sequential pricing. The RAND Journal of Economics, 52(3):538–558, 2021. ISSN 07416261, 17562171. URL http: //www.jstor.org/stable/45419973. [23] Joel Z. Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore Graepel. Multiagent reinforcement learning in sequential social dilemmas. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), São Paulo, Brazil, 2017. URL https://www.ifaamas.org/AAMAS/aamas2017/proceedings/pdfs/ p464.pdf. [24] Ryan Y. Lin, Siddhartha Ojha, Kevin Cai, and Maxwell F. Chen. Strategic collusion of LLM agents: Market division in multi-commodity competitions. arXiv preprint arXiv:2410.00031, 2024. URL https://arxiv.org/abs/2410.00031. 11
[25] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. 2013. URL http://arxiv.org/abs/1312.5602. cite arxiv:1312.5602Comment: NIPS Deep Learning Workshop 2013. [26] Leon Musolff. Algorithmic pricing facilitates tacit collusion: Evidence from e-commerce. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 32–33, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450391504. doi: 10.1145/3490486.3538239. URL https://doi.org/10.1145/3490486.3538239. [27] Ariel Rubinstein. Equilibrium in supergames with the overtaking criterion. Journal of Economic Theory, 21(1):1–9, 1979. ISSN 0022-0531. doi: https://doi.org/10.1016/0022-0531(79)90002-4. URL https://www.sciencedirect.com/science/article/pii/0022053179900024. [28] Jean Tirole. The Theory of Industrial Organization, volume 1 of MIT Press Books. The MIT Press, 1 edition, December 1988. doi: None. URL https://ideas.repec.org/b/mtp/ titles/0262200716.html. [29] U.S. Department of Justice. Justice department sues RealPage for algorithmic pricing scheme that harms millions of American renters. Press release, Office of Public Affairs, August 2024. [30] Ludo Waltman and Uzay Kaymak. Q-learning agents in a cournot oligopoly model. Journal of Economic Dynamics and Control, 32(10):3275–3293, 2008. ISSN 0165-1889. doi: https: //doi.org/10.1016/j.jedc.2008.01.003. URL https://www.sciencedirect.com/science/ article/pii/S0165188908000183. [31] Christopher J. C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3):279–292, 1992. doi: 10.1007/BF00992698. URL https://doi.org/10.1007/BF00992698.
12
A
Q-Learning
Each agent i maintains a Q-function Qi : S × Ai → R and updates it according to Equation 17. ′ t Qi (st , ati ) ← Qi (st , ati ) + α rit + δ max Q (s , a ) − Q (s , a ) (17) i t+1 i t i ′ a ∈Ai
In Equation 17, α ∈ (0, 1) is the learning rate. The greedy policy derived from Qi is πi (s) = arg maxa∈Ai Qi (s, a). During training agents act ε-greedily, selecting a random action with probability ε and the greedy action otherwise.
B
Example Instantiations of the Defection Criterion 1. Path-consistent (when Q0 is known): ϕi (s, a) = 1 a ∈ / Ci (Q0 , t) . Directly tied to Abreu’s definition of deviation. Preferred when Q0 is observable or estimable from a baseline run of standard Q-learning. 2. Nash-deviation (when stage game Nash payoffs are known): ϕi (s, a) = 1 max ri (a, a−i ) ≤ riN ash,G , a−i ∈A−i
where riN ash,G denotes the Nash equilibrium payoff of the stage game G. 3. Relative reward-percentile: h i (1:t) ϕi (st , ati ) = 1 ρt−1 ≥ Q̂1−p ρi , i where ρti = rit −
1 X t rj n−1 j̸=i
(1:t)
is agent i’s reward advantage over opponents at t, and Q̂1−p (ρi ) is the online (1 − p)-th percentile of observed relative advantages up to t. Agent i is classified as having defected when its reward advantage over opponents was unusually large, consistent with having captured excess surplus at opponents’ expense. p ∈ (0, 1) controls the fraction of periods classified as defections.
C
Proofs
C.1
Proof of Proposition 2 and Corollaries
We first establish a lemma characterizing the optimality of punishment paths. C.1.1
Punishment path is a best response
Lemma 1. Let σ(Q0 , Qi , Qj ) be a subgame-perfect equilibrium of G∞ (δ) under Assumptions 1–3. Then for any alternative path Q̃ generated by agent i playing an alternative strategy σ̃i against the other agents’ prescribed post-deviation behavior, vi (Qi ) ≥ vi (Q̃).
(18)
proof: Consider the subgame beginning the period after agent i deviates singly from Q0 . By Definition 1, σ prescribes the continuation path Qi with the other agents playing their Qi -roles. By subgame perfection (Definition 2), σi restricted to this subgame is a best response to σ−i . Since σ̃i is a feasible alternative and σi is optimal, vi (Qi ) ≥ vi (Q̃). 13
C.1.2
Proof of Proposition 2
Define ∆∗t := vi (Q0 ; t+1)−vi (Qi ) for each t ≥ 1. By Proposition 1, the sustainability condition (3) applied to agent i at period t states: 0 ∆i (qi∗,t , q−i (t)) ≤ ∆∗t ,
0 where qi∗,t ∈ arg max ri (a, q−i (t)). a∈Ai
(19)
Since qi∗,t is a stage-game best response and qi0 (t) ∈ Ai is feasible, 0 0 ∆i (qi∗,t , q−i (t)) = ri (qi∗,t , q−i (t)) − ri (q 0 (t)) ≥ 0.
(20)
Hence ∆∗t ≥ 0 for all t. Suppose for contradiction that ∆∗t = 0 for every t. Then (19) and (20) together force 0 0 ∆i (qi∗,t , q−i (t)) = 0 for every t, which means qi0 (t) ∈ arg maxa∈Ai ri (a, q−i (t)) for every t. By 0 0 symmetry (applying the same argument to agent j), qj (t) ∈ arg maxa∈Aj rj (a, q−j (t)) for every t, 0 0 so Q is a stage-game Nash path – contradicting the non-Nash hypothesis on Q . Therefore there exists at least one period t∗ with ∆∗t∗ > 0. Fix such a t∗ and define ∆∗ := ∆∗t∗ > 0. Define the intermediate path Q̃ on periods t ≥ t∗ + 1 as follows: • Agent i plays qi0 (t) (the cooperative on-path action); • Agent j plays according to the punishment-phase distribution πj (· | at−1 ∈ Di ). i By construction, Q̃ is the path that results if agent i deviates at t∗ – triggering the punishment phase – but then, contrary to optimality, continues to play the cooperative action qi0 (·) while j punishes. This is a feasible alternative strategy for i in the post-deviation subgame, so Lemma 1 applies: vi (Qi ) ≥ vi (Q̃).
(21)
Decompose: ∆∗ = vi (Q0 ; t∗ + 1) − vi (Qi ) = vi (Q0 ; t∗ + 1) − vi (Q̃; t∗ + 1) + vi (Q̃; t∗ + 1) − vi (Qi ) . {z } | {z } | pure j-effect
≤0 by (21)
(22) Hence vi (Q0 ; t∗ + 1) − vi (Q̃; t∗ + 1) ≥ ∆∗ > 0.
(23)
On path Q0 , agent i plays qi0 (·) throughout, and agent j plays its cooperation-phase distribution πj (· | Ci ). On path Q̃, agent i still plays qi0 (·) (by construction of Q̃), and agent j plays its punishment-phase distribution πj (· | Di ). Thus Q0 and Q̃ differ only in j’s action distribution. For each s ≥ 1, define hs : Aj → [rmin , rmax ] by hs (aj ) := ri (qi0 (t∗ + s), aj ). Then vi (Q0 ; t∗ + 1) − vi (Q̃; t∗ + 1) =
∞ X
δ s−1 Eaj ∼πj (·|Ci ) [hs (aj )] − Eaj ∼πj (·|Di ) [hs (aj )] . (24)
s=1
For any function h : Aj → [rmin , rmax ] and any distributions µ, ν on Aj , |Eµ [h] − Eν [h]| ≤ (rmax − rmin ) · ∥µ − ν∥T V . (25) P (For any constant c, Eµ [h] − Eν [h] = a (h(a) − c)(µ(a) − ν(a)). P Choose c = (rmax + rmin )/2 min so |h(a) − c| ≤ (rmax − rmin )/2; then |Eµ [h] − Eν [h]| ≤ rmax −r a |µ(a) − ν(a)| = (rmax − 2 rmin )∥µ − ν∥T V .) 14
Let TV := ∥πj (·|Di ) − πj (·|Ci )∥T V . Applying (25) termwise to (24) with µ = πj (·|Ci ), ν = πj (·|Di ): vi (Q0 ; t∗ + 1) − vi (Q̃; t∗ + 1) ≤
∞ X
δ s−1 · (rmax − rmin ) · TV
(26)
s=1
=
rmax − rmin · TV. 1−δ
(27)
Since the left-hand side of (27) is positive by (23), we may drop the absolute value and combine with (23): rmax − rmin ∆∗ ≤ · TV. (28) 1−δ TV ≥
(1 − δ)∆∗ = ε∗ (δ) > 0. rmax − rmin
(29)
Since ∆∗ > 0 and the payoff range rmax − rmin is finite by Assumption 1, ε∗ (δ) ∈ (0, 1]. C.1.3
Proof of Corollary 1
Suppose πj (· | at−1 ∈ Di (Q0 , t)) − πj (· | at−1 ∈ Ci (Q0 , t)) T V = 0. i i Since ε∗ (δ) ∈ (0, 1], we have 0 < ε∗ (δ), so the hypothesis gives ∥πj (· | Di (Q0 , t)) − πj (· | Ci (Q0 , t))∥T V < ε∗ (δ). By the contrapositive of Proposition 2, there exist no paths Qi , Qj ∈ A∞ such that σ(Q0 , Qi , Qj ) is a non-trivial SPC of G∞ (δ) with Qi induced by πj ’s post-deviation behavior. In particular, πj cannot implement any non-trivial punishment path against agent i. Because πj is a stationary policy, its action distribution at any period t depends only on the conditioning event at−1 ∈ Di (Q0 , t) or at−1 ∈ Ci (Q0 , t), not on t itself or on any other feature of the history. i i The TV distance vanishing means πj (· | at−1 ∈ Di (Q0 , t)) = πj (· | at−1 ∈ Ci (Q0 , t)) i i
for all t,
so πj ’s action distribution is identical regardless of whether agent i has defected. Consequently, j’s play following any history in Di (Q0 , t) is statistically indistinguishable from its play along the cooperative path itself, so j takes no action that depends on i’s deviation. Since the induced path Qi is generated entirely by best-response dynamics against πj , and πj exhibits no history-dependence between the cooperative and defection partitions, the induced continuation play cannot diverge from the on-path behavior under Q0 . Hence Qi = Q0 . C.1.4
Proof of Corollary 2
By Proposition 2(i) applied to the path-consistent partition, ∥πjD − πjC ∥T V ≥ ε∗ (δ). By the simple-strategy-profile structure (Definition 1), πj ’s action distribution at period t depends only on the current phase, not on the specific classification ϕi (st , ati ) of the current action beyond its role in phase triggering. Formally, for any event E: πj (· | E, cooperation phase) = πjC ,
(30)
πj (· | E, punishment phase) = πjD .
(31)
Hence, by the law of total probability, πj (· | ϕi = 1) = P (punishment phase | ϕi = 1) · πjD + P (cooperation phase | ϕi = 1) · πjC (32) = (1 − wD ) πjD + wD πjC ,
(33)
where wD := P (cooperation phase | ϕi = 1) ≤ α by Assumption 4. Similarly, πj (· | ϕi = 0) = (1 − wC ) πjC + wC πjD , 15
wC ≤ α.
Bound each distance to the true phase-conditional: ∥πj (· | ϕi = 1) − πjD ∥T V = wD · ∥πjC − πjD ∥T V ≤ wD ≤ α,
(34)
∥πj (· | ϕi = 0) − πjC ∥T V
(35)
= wC · ∥πjD − πjC ∥T V
≤ wC ≤ α.
(As ∥πjD − πjC ∥T V ≤ 1.) By the triangle inequality: ∥πj (· | ϕi = 1) − πj (· | ϕi = 0)∥T V ≥ ∥πjD − πjC ∥T V − ∥πj (· | ϕi = 1) − πjD ∥T V − ∥πj (· | ϕi = 0) − πjC ∥T V (36) ∗ ≥ ε (δ) − 2α. (37) Since α < ε∗ (δ)/2, the right-hand side is strictly positive. C.2
Proof of Proposition 3
(⇒) Suppose ∥πj (· | ϕi = 1) − πj (· | ϕi = 0)∥T V = 0, and suppose σ(Q0 , Qi , Qj ) is any SPC consistent with πj . By the phase-conditional mixture identity (proof of Corollary 2), πj (· | ϕi = 1) = (1 − wD ) πjD + wD πjC ,
(38)
πj (· | ϕi = 0) = (1 − wC ) πjC + wC πjD ,
(39)
where wD , wC ∈ [0, α]. Subtracting and taking TV distance: ∥πj (· | ϕi = 1) − πj (· | ϕi = 0)∥T V = (1 − wD − wC ) · ∥πjD − πjC ∥T V .
(40)
Since wD , wC ≤ α < 1/2, we have 1 − wD − wC > 0. The hypothesis forces ∥πjD − πjC ∥T V = 0. Apply Corollary 1: ∥πjD − πjC ∥T V = 0 implies Qi = Q0 . By symmetry (interchanging i and j in Corollary 1, Qj = Q0 . Hence Q0 = Qi = Qj , and the SPC is trivial. (⇐) Suppose σ(Q, Q, Q) is a trivial SPC consistent with πj . Under Definition 1, the simple strategy profile prescribes path Q regardless of the phase: both the cooperation phase and the punishment phase yield the same prescribed actions. Hence agent j’s action distribution is determined by Q alone, independent of ϕi . Under (T2) the policy πj is stationary and the path Q corresponds to a fixed mapping S → ∆(Aj ) that does not condition on ϕi beyond what Q itself prescribes. Hence πjD = πjC , and by the mixture identity above, ∥πj (· | ϕi = 1) − πj (· | ϕi = 0)∥T V = 0. □ C.3
Proof of Proposition 4
⋆ Let (πj⋆ , π−j ) be a greedy-policy fixed point of the shaped Q-learning dynamics that implements an SPC σ(Q0 , Qi , Qj ).
Suppose for contradiction that TV⋆j := πj⋆ (· | ϕi = 1) − πj⋆ (· | ϕi = 0) T V > 0.
(41)
By Proposition 3, conditional non-invariance implies the SPC is non-trivial: Q0 ̸= Qi or Qj ̸= Q0 . Without loss of generality, assume Q0 ̸= Qi (the case Qj ̸= Q0 follows by symmetry, swapping the roles of i and j). Apply Corollary 2 to get the following TV bound: TV⋆j ≥ ε∗ (δ) − 2α > 0.
(42)
Since πj⋆ is stationary, TV⋆j is independent of the current state. Let Q̄j denote the Q-function of πj⋆ ⋆ against π−j under the unshaped reward rj . Both Q⋆j and Q̄j satisfy Bellman equations under the 16
same policies; their right-hand sides differ only by the constant shaping term −λTV⋆j . Iterating the recursion contributes −λTV⋆j /(1 − δ), giving Q⋆j (s, a) = Q̄j (s, a) −
λ · TV⋆j , 1−δ
∀(s, a) ∈ S × Aj .
(43)
Since the penalty is constant across (s, a), arg maxa Q⋆j (s, a) = arg maxa Q̄j (s, a), so πj⋆ is also greedy with respect to Q̄j . Recall that the state st encodes at−1 . Define SD := {s : ϕi (s) = 1} and SC := {s : ϕi (s) = 0}. i For each s ∈ S, let sC (s) ∈ SC denote the state obtained from s by replacing the ith coordinate with a value consistent with cooperation. Note that for s ∈ SC , sC (s) = s. Define πj′ (s) := πj⋆ (sC (s))
∀s ∈ S.
(44)
By construction, πj′ (sD ) = πj′ (sC (sD )) for all sD ∈ SD , so πj′ is conditionally invariant: ∥πj′ (· | ϕi = 1) − πj′ (· | ϕi = 0)∥T V = 0 i.e., TV′j = 0. ⋆ Let Q̄′j denote the unshaped Q-function of πj′ against π−j . By Assumption 1, both unshaped Q-functions take values in [rmin /(1 − δ), rmax /(1 − δ)], so
Q̄j (s, a) − Q̄′j (s, a) ≤
rmax − rmin , 1−δ
∀(s, a).
(45)
The shaped Q-values: λ · TV⋆j λ(ε∗ (δ) − 2α) ≤ Q̄j (s, a) − , 1−δ 1−δ λ · TV′j Q′j (s, a) = Q̄′j (s, a) − = Q̄′j (s, a). 1−δ
Q⋆j (s, a) = Q̄j (s, a) −
(46) (47)
Subtracting and using (45): λ(ε∗ (δ) − 2α) 1−δ rmax − rmin λ(ε∗ (δ) − 2α) ≥− + 1−δ 1−δ λ(ε∗ (δ) − 2α) − (rmax − rmin ) = . 1−δ
Q′j (s, a) − Q⋆j (s, a) ≥ Q̄′j (s, a) − Q̄j (s, a) +
(48) (49) (50)
For λ > λ∗ = (rmax − rmin )/(ε∗ (δ) − 2α), the numerator of (50) is strictly positive: Q′j (s, a) > Q⋆j (s, a)
∀(s, a) ∈ S × Aj .
(51)
⋆ Recall that Q′j is the shaped Q-function of πj′ against π−j , while Q⋆j is the shaped Q-function of πj⋆ ⋆ ′ against π−j . Inequality (51) therefore states that πj achieves strictly higher shaped value than πj⋆ at every state-action pair, against the same opponent. π′
π⋆
Define the shaped value functions Vj j (s) := Ea∼πj⋆ (s) [Q⋆j (s, a)] and Vj j (s) := Ea∼πj′ (s) [Q′j (s, a)]. From (51), π′
π⋆
Vj j (s) > Vj j (s)
∀s ∈ S.
(52)
⋆ Q-learning at a fixed point against a stationary opponent π−j converges (when it converges) to the π⋆
π
optimal policy under shaped rewards: πj⋆ must satisfy Vj j (s) = maxπj Vj j (s) for every s, where the maximum ranges over all stationary policies. But πj′ is a stationary policy that achieves strictly higher value at every state by (52), contradicting the optimality of πj⋆ . Therefore the supposition TV⋆j > 0 must be false. Hence TV⋆j = 0. 17
C.4
Proof of Proposition 5
Let π Nash = (π1Nash , . . . , πnNash ) denote the stationary stage-game Nash profile, where each πjNash plays a stage-game Nash action independent of state. By Observation 2, πjNash (· | at−1 ∈ Diϕ ) − πjNash (· | at−1 ∈ Ciϕ ) T V = 0 i i for all i, j ∈ N . Therefore the TV penalty in the shaped reward is identically zero under π Nash , and the shaped reward equals the unshaped reward: rjshaped (s, a) = rj (s, a) for all (s, a). Because π Nash is state-independent, the continuation value ∞ X rj (π Nash ) VjNash (s) = δ t E rj (π Nash ) = 1−δ t=0 does not depend on s. Hence the Q-value of action a in state s satisfies Nash QNash + δ · VjNash , (s, a) = rj s, a, π−j j and the only a-dependent term is the immediate reward. Maximizing over a reduces to the stage-game best-response problem: Nash arg max QNash (s, a) = arg max rj s, a, π−j . j a∈Aj
a∈Aj
Nash Since πjNash is by definition a stage-game best response to π−j , we have πjNash (s) ∈ Nash Nash arg maxa Qj (s, a) for all s. Hence π is a greedy-policy fixed point of shaped Q-learning.
D
Algorithm
Algorithm 1 CURB Require: penalty strength λ > λ∗ , history length W , injection period k, injection size m, defection criterion ϕi 1: Initialise Qi for all i ∈ [n]; sliding action history H of length W , initially empty 2: for t = 1, 2, . . . do 3: Each agent i selects ati ε-greedily from Qi (st , ·) 4: Observe rewards rit and next state st+1 5: Push joint action at into H (evicting the oldest entry if |H| = W ) 6: for each agent j ∈ [n] do 7: For each i ̸= j, classify each of i’s actions in H via ϕi into a defective set Di and a cooperative set Ci 8: Compute the lag-1 conditional TV between j’s response distributions: t−1 TVij ∈ Di − π̂j · at−1 ∈ Ci TV t = π̂j · ai i Apply shaped reward r̃jt = rjt − λ · maxi̸=j TVij t 10: Update Qj (st , atj ) ← Qj (st , atj ) + α r̃jt + δ maxa′ Qj (st+1 , a′ ) − Qj (st , atj ) 11: end for 12: if t mod k = 0 then 13: for each agent j ∈ [n] do Inject m synthetic transitions into j’s buffer in which j plays a defective action aj ∈ Dj 14: while opponents continue cooperating. 15: end for 16: end if 17: end for 9:
E
Experiments
This appendix documents the environments, algorithms, hyperparameters, and training scale used for the experiments reported in Section 6. 18
E.1
Environments
Bertrand competition. We use the symmetric Bertrand oligopoly with multinomial-logit demand from Calvano et al. [10]. Each agent i chooses a price pi from a discrete grid of K = 15 values spanning the stage-game Nash and monopoly prices with a 10% markup at each end. Demand follows a logit form with quality ai = 2, price sensitivity µ = 0.25, and zero marginal cost. We use n = 2 for the main experiments and n = 3 for the scaling test. Cournot competition. We use the deterministic Cournot oligopoly from Calvano et al. [11]. Each agent chooses a quantity qi from a discrete grid of K = 15 values spanning the Nash quantity Mono q Nash = a/(n + 1) and = a/(2n) with a = 200 and b = 1. Per-period P monopoly quantity q profit is πi = (a − b j qj ) · qi . Cournot with imperfect monitoring. For comparison against the imperfect-monitoring deterrent of Calvano et al. [11], we additionally implement the Cournot variant in which the demand intercept dt is i.i.d. uniform on {290, 310} and agents observe only the realised market price (not opponent quantities). The state space is the previous-period price discretised into 37 levels. t−1 State encoding. Across all environments the state st is the previous joint action (at−1 1 , . . . , an ) n (or the previous price under imperfect monitoring), giving |S| = K in the standard case.
Reward normalisation. All per-period profits are divided by the per-agent monopoly profit so collusion-index calculations and cross-environment λ values are directly comparable. The collusion index is CI = (π̄ − π Nash )/(π Mono − π Nash ), with CI = 0 at Nash and CI = 1 at full collusion. E.2
Algorithms
Tabular Q-learning. Each agent maintains a Q-table Qi : S × Ai → R updated according to Equation 17. Following Calvano et al. [10], we initialise Qi (s, a) = Ea−i [πi (a, a−i )]/(1 − δ) averaged over opponent actions, which seeds the table with reasonable state-independent value estimates. DQN. For the function-approximation experiments we replace the tabular Q-tables with independent multi-agent DQN: one PyTorch Q-network per agent, with no weight sharing. Each network is a 3-layer MLP with 32 hidden units per layer and ReLU activations, trained with Adam, MSE loss, a hard target-network copy every C = 100 steps, and a replay buffer of size 104 . State observations are the previous-period prices, normalised to [0, 1]. E.3
CURB components
Defection criterion. The TV detector requires a defection indicator ϕi to partition agent i’s past actions into “cooperative” and “defective” subsets. We use the simple median-split: at each timestep, ϕi flags an action as defective if it falls on the deviator side of the rolling-history median (below the median for Bertrand prices; above the median for Cournot quantities). A punishment-direction filter further rejects spurious detections by requiring agent j’s mean action when i is below the median to lie below j’s mean action when i is above the median. TV penalty. The TV detector operates on a rolling window of W = 500 past joint actions with lag-1 conditioning: agent j’s current-period action is conditioned on agent i’s previous action, capturing the temporal causality of punishment. The shaped reward is r̃j = rj − λ · maxi̸=j TVij t , with λ swept over {0.05, 0.1, 0.2, 0.5}. Belief injection. Every Kbelief = 100 environment steps we inject Mbelief = 5 synthetic transitions per agent into the agent’s update target. Each injected transition models a unilateral deviation by j against opponents continuing on the cooperative path, with the analytic stage-game profit as the reward. In the tabular setting this is a direct Q-update; in the DQN setting it is a synthetic entry in the agent’s replay buffer. 19
E.4
Hyperparameters
Table 2 lists the hyperparameters used across all experiments. All values are recorded in the run_config.json of each completed run for reproducibility.
Parameter
Tabular Q
DQN
Learning rate α Discount δ Exploration decay β Convergence threshold tstable Replay buffer size Target-network update C Hidden units (per MLP layer) Batch size Action-grid size K TV rolling-window W Belief-injection interval k Belief-injection size m
0.15 0.95 4×10−6 (n=2), 1.2×10−6 (n=3) 105 — — — — 15 500 100 5
10−3 0.95 4×10−6 — 104 100 32 32 15 500 100 5
Table 2: Hyperparameters used across experiments.
E.5
Training scale
Table 3 summarises the conditions, seed counts, and training horizon for each experiment.
Experiment
Conditions
Seeds
Env steps
Bertrand n=2 Bertrand n=3 DQN-Bertrand Cournot n=2 Platform-design JSD ablation Forced defection
10 (baseline + belief-only + 4 TV-only + 4 CURB) 3 (baseline + 2 CURB) 4 (baseline + 3 CURB) 5 (baseline + IM + 3 CURB) 5 (baseline + PDP + DPDP + 2 CURB) 10 (baseline + 3 TV + 3 JSD-norm + 3 JSD-raw) 2 (baseline + TV-only)
20 20 20 20 20 20 20
3×106 2×107 106 3×106 3×106 3×106 3×106
Table 3: Training scale per experiment. “IM” denotes imperfect monitoring; “PDP” / “DPDP” denote the Price-Directed Prominence baselines.
E.6
Compute resources
Tabular Q-learning experiments run entirely on CPU; we use Python multiprocessing to run seeds in parallel (typically 32 workers per node). A complete Bertrand n=2 sweep (200 seed-condition pairs at 3×106 steps each) finishes in roughly 2 hours on a 32-core node. The Bertrand n=3 sweep, with 2×107 steps per seed, takes approximately 6–8 hours on the same hardware. The DQN-Bertrand sweep uses a single GPU (A100) per seed and completes in under 4 hours per node.
E.7
Reporting
All plotted curves show the mean across seeds with ±1 SEM bands. All tables report the mean ± sample standard deviation across seeds. We report final-CI metrics by averaging the per-step CI over the last 10% of training steps to reduce sensitivity to oscillations near convergence. 20
F
Supplementary Results
F.1
Forced-defection test
TV-only ( = 0.5)
No intervention 1.9
Price
1.8 1.7 1.6 Agent 0 (defector) Agent 1 (responder)
1.5 40
50
60
Step
70
80
90 40
50
60
Step
70
80
90
Figure 4: Forced-defection test where agent 0 is forced to defect at step 50. To verify that the TV penalty suppresses the punishment response we examine trained agents’ behavior when one agent is forced to deviate. Figure 4 shows the resulting price trajectories for the no-intervention baseline and the TV-only condition at λ=0.5. Under no intervention, agent 1 follows agent 0 down, a coordinated drop characteristic of an SPC strategy, and both recover within a few steps. Under TV-only, agent 1 does not respond to the deviation, only agent 0 dips and rebounds alone. This indicates that CURB’s TV penalty specifically eliminates the punishment response that sustains collusive SPC equilibria.
21