Natalie Rose Collina
University of Pennsylvania
ncollina@seas.upenn.edu
Bio
Natalie is a fourth-year PhD student in computer science at the University of Pennsylvania, where she is fortunate to be advised by Michael Kearns and Aaron Roth. She works in the intersection of algorithmic game theory and online learning. She is particularly interested in understanding algorithms as a form of commitment, and the strategic implications of these commitments. Her research focuses both on finding optimal algorithms to commit to in general classes of repeated games, as well as applying these insights to areas such as contract theory, trust in machine learning, and algorithmic collusion. It turns out that regret guarantees are very useful in many of these settings, and therefore much of her research also eludicates the powerful strategic properties of no-regret and no-swap-regret algorithms. She co-leads the University of Pennsylvania’s weekly Theory Seminar, and her research has been supported by AWS AI.
Areas of Research
- Machine Learning
Algorithmic Collusion without Threats
There has been substantial recent concern that automated pricing algorithms might learn to “collude,” and hence result in monopoly-like prices in what should be competitive markets. It has long been known that supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors via low pricing if they ever “defect” from a set of supra-competitive prices. Recent work has shown that reinforcement learning algorithms are expressive enough to learn such anti-competitive pricing strategies automatically. But if such threats are the only obstacle to competitive pricing by algorithms, one can imagine a world in which algorithms encoding threats (appropriately defined) are forbidden and audited for. We ask: would preventing explicit threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? In this paper, we show that supra-competitive prices can robustly emerge even when both parties are taking steps to behave reasonably. Since deploying an algorithm is a form of commitment, we study sequential pricing games in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a “no-swap-regret” guarantee (a notion which has previously been used to define competitive pricing algorithms), and then the second mover even approximately optimizes within this now static environment, then monopoly-like prices arise. The result applies even when the second mover is optimizing only within a space of static distributions which are incapable of encoding threats. In fact, there exists a set of algorithms, neither of which encode threats, that form a Nash equilibrium of the pricing game with near-monopoly prices. This suggests that definitions of algorithmic collusion may need to be expanded, to include strategies without explicitly encoded threats.