Foundations and Trends® in Machine Learning > Vol 15 > Issue 3

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

 
Suggested Citation
Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui and Vianney Perchet (2022), "Learning in Repeated Auctions", Foundations and Trends® in Machine Learning: Vol. 15: No. 3, pp 176-334. http://dx.doi.org/10.1561/2200000077

Publication Date: 14 Feb 2022
© 2022 T. Nedelec et al.
 
Subjects
Statistical Learning Theory,  Game theoretic learning,  Algorithmic game theory,  Design and Analysis of Algorithms,  Operations Research
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction: Scope and Motivation
2. Bayesian Mechanism Design
3. Repeated Auctions From a Seller’s Standpoint
4. Adaptive and Strategic Learning Agents
References

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.

DOI:10.1561/2200000077
ISBN: 978-1-68083-938-8
170 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-939-5
170 pp. $145.00
Buy E-book (.pdf)
Table of contents:
1. Introduction: Scope and Motivation
2. Bayesian Mechanism Design
3. Repeated Auctions From a Seller’s Standpoint
4. Adaptive and Strategic Learning Agents
References

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.

 
MAL-077