Domination-Avoiding Learning Agents Cannot Collude
For economists and AI safety researchers, it provides a theoretical guarantee that certain learning algorithms avoid collusive outcomes in market settings, addressing a key concern about algorithmic collusion.
The paper proves that a broad class of learning agents, called Domination-Avoiding agents, cannot collude in pricing markets, unlike Q-learning and LLM agents that have been shown to collude. This class includes mean-based and internal-regret-minimizing agents, and they are guaranteed to avoid strategies eliminated by iterated dominance.
An influential paper of Calvano et al. empirically demonstrated that Q-learning agents spontaneously collude when placed as sellers that compete on prices in a natural market model. More recent results of Fish et al. empirically demonstrated that similar collusion happens with commercial LLMs. We formally prove that such collusion can also happen with external-regret-minimizing agents. We identify a very general class of agents, which we term Domination-Avoiding agents, that provably do not collude in such markets. This class contains all Mean-Based agents and all internal-regret-minimizing agents, as well as others such as Multiplicative-Weight agents with variable learning rate and contextual variants thereof. More generally we show that, in any game, this class of agents is guaranteed to jointly learn to almost never play strategies that are eliminated by repeated elimination of purely dominated strategies.