Real-Time Optimisation for Online Learning in Auctions

Lorenzo Croissant · Marc Abeille · ClĂ©ment Calauzènes

Keywords: [ Game Theory and Mechanism Design ] [ Learning Theory ] [ Online Learning / Bandits ]

[ Abstract ]
Thu 16 Jul noon PDT — 12:45 p.m. PDT
Fri 17 Jul midnight PDT — 12:45 a.m. PDT


In display advertising, a small group of sellers and bidders face each other in up to 10^{12} auctions a day. In this context, revenue maximisation via monopoly price learning is a high-value problem for sellers. By nature, these auctions are online and produce a very high frequency stream of data. This results in a computational strain that requires algorithms be real-time. Unfortunately, existing methods, inherited from the batch setting, suffer O(\sqrt(t)) time/memory complexity at each update, prohibiting their use. In this paper, we provide the first algorithm for online learning of monopoly prices in online auctions whose update is constant in time and memory.

Chat is not available.