Truthful Learning Mechanisms for Multi–Slot Sponsored Search Auctions with Externalities

Nicola Gatti 1 Alessandro Lazaric 2, 3 Marco Rocco 1 Francesco Trovò 1
3 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 (SSAs) constitute one of the most successful applications of microeconomic mechanisms. In mechanism design, auctions are usually designed to incentivize advertisers to bid their truthful valuations and, at the same time, to guarantee 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 truthful 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 at the same time as implementing a truthful mechanism with a revenue loss as small as possible compared to the mechanism that can exploit the true CTRs. Previous work showed that, when dominant–strategy truthfulness is adopted, in single–slot auctions the problem can be solved using suitable exploration–exploitation mechanisms able to achieve a cumulative regret (on the auctioneer's revenue) of order O(T^(2/3)), where T is the number of times the auction is repeated. It is also known that, when truthfulness in expectation is adopted, a cumulative regret (over the social welfare) of order O(T^(1/2)) can be obtained. In this paper, we extend the results available in the literature to the more realistic case of multi–slot auctions. In this case, a model of the user is needed to characterize how the CTR of an ad changes as its position in the allocation changes. In particular, we adopt the cascade model, one of the most popular models for sponsored search auctions, and we prove a number of novel upper bounds and lower bounds on both auctioneer’s revenue loss and social welfare w.r.t. to the Vickrey–Clarke–Groves (VCG) auction. Furthermore, we report numerical simulations investigating the accuracy of the bounds in predicting the dependency of the regret on the auction parameters.
Type de document :
Article dans une revue
Artificial Intelligence, Elsevier, 2015, 227, pp.93-139
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01237670
Contributeur : Alessandro Lazaric <>
Soumis le : vendredi 4 décembre 2015 - 15:44:16
Dernière modification le : jeudi 12 avril 2018 - 11:14:03
Document(s) archivé(s) le : samedi 29 avril 2017 - 04:17:26

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01237670, version 1

Citation

Nicola Gatti, Alessandro Lazaric, Marco Rocco, Francesco Trovò. Truthful Learning Mechanisms for Multi–Slot Sponsored Search Auctions with Externalities. Artificial Intelligence, Elsevier, 2015, 227, pp.93-139. 〈hal-01237670〉

Partager

Métriques

Consultations de la notice

214

Téléchargements de fichiers

263