Algorithmic collusion is unavoidable under rationalizable learning, new paper finds

A new theoretical paper by Hartline, Wang, and Zhang, to appear at ACM EC '26, establishes a sharp separation between offline computation and online learning for a class of equilibria in games. They define an 'information-value-free' correlated equilibrium—one where each player has an action that yields the same payoff as their equilibrium strategy when all others follow theirs. While such equilibria can be computed efficiently offline, the authors prove they are not learnable by any algorithm in a broad class that uses only own-payoff feedback and observes the full history of play.

This result has direct implications for antitrust regulation of algorithmic collusion. Under rationalizable learning—a realistic assumption for AI pricing agents—valuable and implicit information exchange becomes unavoidable. Traditional antitrust rules that prohibit such exchange are therefore incompatible with rationalizable learning. The paper also shows an impossibility result for time-average convergence to Nash equilibrium by a wide class of learning algorithms, further deepening the challenge for regulators trying to prevent collusion without explicitly banning pricing algorithms.