Skip to Main content Skip to Navigation

A Truthful Learning Mechanism for Contextual Multi-Slot Sponsored Search Auctions with Externalities

Alessandro Lazaric 1 Nicola Gatti 2 Trov'{o} Francesco 2
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : Sponsored search auctions constitute one of the most successful applications of microeconomic mechanisms. In particular, pay-per-click auctions have been designed to incentivize advertisers to bid their truthful valuations and, at the same time, to assure both the advertisers and the auctioneer a non--negative utility. Nonetheless, when the click-through-rates (CTRs) of the advertisers are unknown to the auction, these mechanisms must be paired with an effective learning algorithm for the estimation of the CTRs. This introduces the critical problem of designing a learning mechanism able to estimate the CTRs as the same time as implementing a truthful mechanism with a revenue loss as small as possible. Previous works showed that in single-slot auctions the problem can be solved using a suitable exploration-exploitation mechanism able to achieve a per-step regret of order $O(T^{-1/3})$ (where $T$ is the number of times the auction is repeated). In this paper we extend these results to the general case of contextual multi-slot auctions with position- and ad-dependent externalities. In particular, we prove novel upper-bounds on the revenue loss w.r.t. to a generalized VCG auction and we report numerical simulations investigating their accuracy in predicting the dependency of the regret on the number of rounds $T$, the number of slots $K$, and the number of advertisements $n$.
Complete list of metadata
Contributor : Alessandro Lazaric Connect in order to contact the contributor
Submitted on : Tuesday, January 24, 2012 - 2:20:43 PM
Last modification on : Thursday, January 20, 2022 - 4:17:20 PM


  • HAL Id : hal-00662549, version 1



Alessandro Lazaric, Nicola Gatti, Trov'{o} Francesco. A Truthful Learning Mechanism for Contextual Multi-Slot Sponsored Search Auctions with Externalities. [Research Report] 2012. ⟨hal-00662549⟩



Les métriques sont temporairement indisponibles