Truthful learning mechanisms for multi-slot sponsored search auctions with externalities

DOI10.1016/J.ARTINT.2015.05.012zbMATH Open1346.68157arXiv1405.2484OpenAlexW4229718065MaRDI QIDQ899160FDOQ899160

Authors: Nicola Gatti, Alessandro Lazaric, Marco Rocco, Francesco Trovò 

Publication date: 21 December 2015

Published in: Artificial Intelligence (Search for Journal in Brave)

Abstract: Sponsored search auctions 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 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 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 an optimal mechanism designed with 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 per-step regret (over the auctioneer's revenue) of order $O(T^{-1/3})$ (where T is the number of times the auction is repeated). It is also known that, when truthfulness in expectation is adopted, a per-step regret (over the social welfare) of order $O(T^{-1/2})$ can be obtained. In this paper we extend the results known in the literature to the case of multi-slot auctions. In this case, a model of the user is needed to characterize how the advertisers' valuations change over the slots. We adopt the cascade model that is the most famous model in the literature for sponsored search auctions. We prove a number of novel upper bounds and lower bounds both on the auctioneer's revenue loss and social welfare w.r.t. to the VCG auction and we report numerical simulations investigating the accuracy of the bounds in predicting the dependency of the regret on the auction parameters.

Full work available at URL: https://arxiv.org/abs/1405.2484

Recommendations

• Adopting the cascade model in ad auctions: efficiency bounds and truthful algorithmic mechanisms
• Adaptive Incentive-Compatible Sponsored Search Auction
• Characterizing Truthful Multi-armed Bandit Mechanisms
• Mechanism Design for Multi-slot Ads Auction in Sponsored Search Markets
• Revenue guarantees in sponsored search auctions

zbMATH Keywords

online learningmechanism designsponsored search auctionseconomic paradigms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Algorithmic Game Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some aspects of the sequential design of experiments
• Finite-time analysis of the multiarmed bandit problem
• Title not available (Why is that?)
• Optimal Auction Design
• Title not available (Why is that?)
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Maintaining equilibria during exploration in sponsored search auctions
• Computationally feasible VCG mechanisms
• Game theoretic problems in network economics and mechanism design solutions
• An incentive-compatible multi-armed bandit mechanism
• Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
• Adaptive Incentive-Compatible Sponsored Search Auction

Cited In (8)

• Online joint bid/daily budget optimization of Internet advertising campaigns
• An optimal bidimensional multi-armed bandit auction for multi-unit procurement
• A Differential Privacy Mechanism that Accounts for Network Effects for Crowdsourcing Systems
• A quality assuring, cost optimal multi-armed bandit mechanism for expertsourcing
• Optimal selling mechanisms with crossholdings
• Towards better models of externalities in sponsored search auctions
• Mechanism Design for Multi-slot Ads Auction in Sponsored Search Markets
• Truthful mechanisms with implicit payment computation

This page was built for publication: Truthful learning mechanisms for multi-slot sponsored search auctions with externalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899160)