Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma
Quentin Bertrand, Juan Agustin Duque, Emilio Calvano, Gauthier Gidel
Abstract
A growing body of computational studies shows that simple machine learning agents converge to cooperative behaviors in social dilemmas, such as collusive price-setting in oligopoly markets, raising questions about what drives this outcome. In this work, we provide theoretical foundations for this phenomenon in the context of self-play multi-agent Q-learners in the iterated prisoner’s dilemma. We characterize broad conditions under which such agents provably learn the cooperative Pavlov (win-stay, lose-shift) policy rather than the Pareto-dominated “always defect” policy. We validate our theoretical results through additional experiments, demonstrating their robustness across a broader class of deep learning algorithms.
BibTeX
@inproceedings{
bertrand2025selfplay,
title={Self-Play \$Q\$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma},
author={Quentin Bertrand and Juan Agustin Duque and Emilio Calvano and Gauthier Gidel},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=q6zwUeWkZL}
}