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

Nicola Gatti 1 Alessandro Lazaric 2 Francesco Trov\'{o} 1
2 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : Sponsored search auctions constitute one of the most successful applications of \emph{microeconomic mechanisms}. In mechanism design, auctions are usually 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, in sponsored search auctions, the click--through--rates (CTRs) of the advertisers are often unknown to the auctioneer and thus standard incentive compatible mechanisms cannot be directly applied and 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 compared to an optimal mechanism designed with the true CTRs. 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 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$.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00772624
Contributor : Alessandro Lazaric <>
Submitted on : Thursday, January 10, 2013 - 6:44:12 PM
Last modification on : Tuesday, August 13, 2019 - 11:10:04 AM
Long-term archiving on : Saturday, April 1, 2017 - 3:40:15 AM

File

ec080-gatti.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00772624, version 1

Collections

Citation

Nicola Gatti, Alessandro Lazaric, Francesco Trov\'{o}. A Truthful Learning Mechanism for Contextual Multi--Slot Sponsored Search Auctions with Externalities. EC - 13th ACM Conference on Electronic Commerce, Jun 2012, Valencia, Spain. ⟨hal-00772624⟩

Share

Metrics

Record views

404

Files downloads

526