Theory Seminar: Sampath Kannan (Simons Institute, Berkeley), Collusion in the Age of Algorithmic Agents

Content

Speaker

Sampath Kannan (Simons Institute, Berkeley)

Abstract

Fair competition demands that sellers do not collude with each other in setting prices. But what does this mean? Prior work has shown that two sellers  can set supra-competitive prices and gain supra-competitive revenue by either encoding threats in their behavior, or by not optimizing their own payoffs. Moreover, reinforcement learning algorithms can learn such threat strategies on their own.

Here we show that supra-competitive prices can arise in seemingly innocuous settings, when no threats are being encoded, and each agent is playing optimally. In our model each of the two agents sets a price for a good at each point in time, and the agent setting the lower price sells the good. We show that if one of the agents uses a no-regret algorithm to set prices, and the other aproximately best responds, then both agents can get close to monopolistic profits, rather than the near-zero profit they should get under perfect competition. This suggests that it is non-trivial to define collusion in the age of algorithmic agents.

This talk will be self-contained and introduce the bits of game theory, online learning, and economics needed for understanding it. 

The work is joint with Natalie Collina, Eshwar Arunachaleswaran, Aaron Roth, and Juba Ziani.

Bio

Sampath Kannan is the Henry Salvatori Professor in the Department of Computer and Information Science at the University of Pennsylvania. He is currently on leave from this position and serving as the Associate Director at the Simons Institute for the Theory of Computing at Berkeley.

He obtained his undergraduate degree from the Indian Institute of Technology, Bombay, his Masters from Princeton University, and his Ph.D. from the University of California, Berkeley in 1989. His research interests are in the areas of Program Reliability, Computational Biology, and Algorithmic Game Theory and Fairness.

Sampath served as Associate Dean for Academics in the School of Engineering and Applied Science at Penn between 2006 and 2008 and as Division Director for the Computing and Communication Foundations Division at NSF from 2008 to 2010. He served as Associate Director for Theoretical Computer Science at the Simons Foundation from 2010 to 2013. He was also Chair of Penn’s CIS Department from 2013 to 2017. He  served on the advisory board of DIMACS and on CRA’s CCC Council. Sampath was the founding co-director of the online Master’s program that Penn created in Computer and Information Technology in 2018 targeted at students with no undergraduate background in computer science.

Sampath is a Fellow of the ACM and AAAS and the winner of the SIGACT Distinguished Service Award.