# Regulation of Algorithmic Collusion, Refined: Testing Pessimistic Calibrated Regret

arXiv: https://arxiv.org/abs/2501.09740 · HTML: https://mlsanity.com/paper/2501.09740/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2025.

## Built on by (most cited first, 8 of 8)

- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Breaking Algorithmic Collusion in Human-AI Ecosystems](https://mlsanity.com/paper/2511.21935/) (2025)
- [Mitigating Retaliatory Algorithmic Collusion in Repeated Games](https://mlsanity.com/paper/2609.20548/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [Mean-based algorithms: A lower bound and regret](https://mlsanity.com/paper/2606.04931/) (2026)
- [Collusion with Competitive Marginals: Price-Level Audits Are Blind by Construction](https://mlsanity.com/paper/2607.26385/) (2026)
- [When and How Order-Flow Interventions Work After Dealers Adapt](https://mlsanity.com/paper/2610.18158/) (2026)

## Abstract (arXiv)

We study the regulation of algorithmic (non-)collusion amongst sellers in dynamic imperfect price competition by auditing their data as introduced by Hartline et al. [2024]. We develop an auditing method that tests whether a seller's pessimistic calibrated regret is low. The pessimistic calibrated regret is the highest calibrated regret of outcomes compatible with the observed data. This method relaxes the previous requirement that a pricing algorithm must use fully-supported price distributions to be auditable. This method is at least as permissive as any auditing method that has a high probability of failing algorithmic outcomes with non-vanishing calibrated regret. Additionally, we strengthen the justification for using vanishing calibrated regret, versus vanishing best-in-hindsight regret, as the non-collusion definition, by showing that even without any side information, the pricing algorithms that only satisfy weaker vanishing best-in-hindsight regret allow an opponent to manipulate them into posting supra-competitive prices. This manipulation cannot be excluded with a non-collusion definition of vanishing best-in-hindsight regret. We motivate and interpret the approach of auditing algorithms from their data as suggesting a per se rule. However, we demonstrate that it is possible for algorithms to pass the audit by pretending to have higher costs than they actually do. For such scenarios, the rule of reason can be applied to bound the range of costs to those that are reasonable for the domain.