Learning in Repeated Auctions
By Thomas Nedelec, ENS Paris Saclay and Criteo AI Lab, France, thomas.nedelec@polytechnique.edu | Clément Calauzènes, Criteo AI Lab, France, c.calauzenes@criteo.com | Noureddine El Karoui, Work done while at UC, Berkeley, USA, and Criteo AI Lab, France, nkarouiprof@gmail.com | Vianney Perchet, Criteo AI Lab, France, vianney.perchet@normalesup.org
Abstract
Online auctions are one of the most fundamental facets of the modern economy and power an industry generating hundreds of billions of dollars a year in revenue. Auction theory has historically focused on the question of designing the best way to sell a single item to potential buyers, with the concurrent objectives of maximizing revenue generated or welfare created. Theoretical results in this area have typically relied on some prior Bayesian knowledge agents were assumed to have on each other. This assumption is no longer satisfied in new markets such as online advertising: similar items are sold repeatedly, and agents are unaware of each other or might try to manipulate each other. On the other hand, statistical learning theory now provides tools to supplement those missing pieces of information given enough data, as agents can learn from their environment to improve their strategies.
This monograph covers recent advances in learning in repeated auctions, starting from the traditional economic study of optimal one-shot auctions with a Bayesian prior. We then focus on the question of learning optimal mechanisms from a dataset of bidders’ past values. The sample complexity as well as the computational efficiency of different methods will be studied. We will also investigate online variants where gathering data has a cost to be accounted for, either by sellers or buyers (“earning while learning”). Later in the monograph, we will further assume that bidders are also adaptive to the mechanism as they interact repeatedly with the same seller. We will show how strategic agents can actually manipulate repeated auctions, to their own advantage. A particularly interesting example is that of reserve price improvements for strategic buyers in second price auctions.
All the questions discussed in this monograph are grounded in real-world applications and many of the ideas and algorithms we describe are used every day to power the Internet economy.
Learning in Repeated Auctions
Online auctions are one of the most fundamental facets of the modern economy and power an industry generating hundreds of billions of dollars a year in revenue. Online auction theory has historically focused on the question of designing the best way to sell a single item to potential buyers relying on some prior knowledge agents were assumed to have on each other. In new markets, such as online advertising, however, similar items are sold repeatedly, and agents are unaware of each other or might try to manipulate each other, making the assumption invalid. Statistical learning theory now provides tools to supplement those missing pieces of information given enough data, as agents can learn from their environment to improve their strategies.
This book is a comprehensive introduction to the learning techniques in repeated auctions. It covers everything from the traditional economic study of optimal one-shot auctions, through learning optimal mechanisms from a dataset of bidders’ past values, to showing how strategic agents can actually manipulate repeated auctions to their own advantage. The authors explore the effects of different scenarios and assumptions throughout while remaining grounded in real-world applications. Many of the ideas and algorithms described are used every day to power the Internet economy.
This book provides students, researchers and practitioners with a deep understanding of the theory of online auctions and gives practical examples of how to implement in modern-day internet systems.
