Adaptive Algorithms and Collusion via Coupling

We develop a theoretical model to study strategic interactions between adaptive learning algorithms. Applying continuous-time techniques, we uncover the mechanism responsible for collusion between Artificial Intelligence algorithms documented by recent experimental evidence. We show that spontaneous coupling between the algorithms' estimates leads to periodic coordination on actions that are more profitable than static Nash equilibria. We provide a sufficient condition under which this coupling is guaranteed to disappear, and algorithms learn to play undominated strategies. We apply our results to interpret and complement experimental findings in the literature and to the design of learning-robust strategy-proof mechanisms. We show that ex-post feedback provision guarantees robustness to the presence of learning agents. We fully characterize the optimal learning-robust mechanisms: they are menu mechanisms.Comment: 57 pages, 13 figure