The Convergence of Learning Algorithms in Auction Games
Abstract: Many digital markets, such as display advertising exchanges, are run as repeated first- or second-price auctions and are increasingly automated by learning agents. Recent empirical work shows that simple learning algorithms converge to an equilibrium in such settings, yet the reasons for this convergence remain elusive. We model the equilibrium problem as an infinite-dimensional variational inequality and analyze the associated dynamical system induced by gradient-based learning. We show that known sufficient conditions for convergence do not hold, but are able to prove asyptotic stability of the equilibrium. Our approach establishes a new framework for analyzing the convergence of learning dynamics in these games.
Bio sketch: Martin Bichler is Head of the Department of Computer Science at the Technical University of Munich (TUM) and head of the research group Decision Sciences and Systems. He is affiliated with the TUM School of Management and a core member of the Munich Data Science Institute. Martin received his Master degree from the Technical University of Vienna, and his Doctorate as well as his Habilitation from the Vienna University of Economics and Business. He was a research fellow at UC Berkeley, and a research staff member at the IBM T. J. Watson Research Center, Yorktown Heights, New York. Later, he was a visiting scholar at the University of Cambridge, at HP Labs Palo Alto, at the Department of Economics at Yale University, the Department of Economics at Stanford University, and the Simons Laufer Mathematical Sciences Institute in Berkeley.
Bio sketch: Martin Bichler is Head of the Department of Computer Science at the Technical University of Munich (TUM) and head of the research group Decision Sciences and Systems. He is affiliated with the TUM School of Management and a core member of the Munich Data Science Institute. Martin received his Master degree from the Technical University of Vienna, and his Doctorate as well as his Habilitation from the Vienna University of Economics and Business. He was a research fellow at UC Berkeley, and a research staff member at the IBM T. J. Watson Research Center, Yorktown Heights, New York. Later, he was a visiting scholar at the University of Cambridge, at HP Labs Palo Alto, at the Department of Economics at Yale University, the Department of Economics at Stanford University, and the Simons Laufer Mathematical Sciences Institute in Berkeley.
Practical information
- Informed public
- Registration required
Organizer
- Daniel Kuhn and Andrés Cristi