Learning in repeated auctions
share
Auction theory historically focused on the question of designing the best way to sell a single item to potential buyers, with the concurrent objectives of maximizing the revenue generated or the welfare created. Those results relied on some prior Bayesian knowledge agents have on each-other and/or on infinite computational power. All those assumptions are no longer satisfied in new markets such as online advertisement: similar items are sold repeatedly, agents are agnostic and try to manipulate each-other. On the other hand, statistical learning theory now provides tools to supplement those missing assumptions in the long run, as agents are able to learn from their environment to improve their strategies. This survey covers the recent advances of learning in repeated auctions, starting from the traditional economical study of optimal one-shot auctions with a Bayesian prior. We will then focus on the question of learning these mechanism from a dataset of the past values of bidders. The sample complexity as well as the computational efficiency of different methods will be studied. We will also investigate online variants where gathering those data has a cost to be integrated ("earning while learning"). In a second step, 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, at their own advantage. At the end of this stand-alone survey (reminders of the different techniques used are provided), we will describe new interesting direction of research on repeated auctions.
READ FULL TEXT