Adopting the cascade model in ad auctions: efficiency bounds and truthful algorithmic mechanisms
Gabriele Farina, Nicola Gatti
Abstract
Sponsored Search Auctions (SSAs) are one of the most successful applications of microeconomic mechanisms, with a revenue of about $50 billion in the US alone in 2014. However, the problem of designing the best economic mechanism for sponsored search auctions is far from being solved, and given the amounts at stake it is no surprise that it has received growing attention over the past few years. The most common auction mechanism for SSAs is the
Generalized Second Price (GSP). However, the GSP is known not to be
truthful: the agents participating in the auction might have an incentive to report false values, generating economic
inefficiency and suboptimal revenues in turn. Superior, efficient truthful mechanisms, such as the
Vickrey-Clarke-Groves (VCG) auction, are well known in literature. However, while the VCG auction is currently adopted for the strictly related scenario of contextual advertising, e.g., by Google and Facebook, companies are reluctant to extend them to SSAs, fearing prohibitive switching costs. Other than truthfulness, two issues are of paramount importance in designing effective SSAs. First, the choice of the user model; not only does an accurate user model better target ads to users, it also is a critical factor in reducing the inefficiency of the mechanism. Often an antagonist to this, the second issue is the running time of the mechanism, given the performance pressure these mechanisms undertake in the real world. In our work, we argue in favor of adopting the VCG mechanism based on the cascade model with ad/position externalities (APDC-VCG). We study theoretical inefficiency bounds of the GSP and the VCG auction based on another well-known externality model when compared to APDC-VCG, showing that in both cases full-information Nash equilibria for the former models might not exist or be inefficient. We also provide exact, randomized, and approximation algorithms, showing that in real-world settings (based on Yahoo! Webscope A3 dataset with 10 available slots) optimal allocations can be found in less than 1s with up to 1000 ads, and can be approximated by a
maximal-in-its-range algorithm (thus leading to a truthful mechanism) in less than 20ms even with more than 1000 ads with an average efficiency larger than 99%. This shows the practical viability of APDC-VCG in real-wold applications.
Bibtex entry
@article{Farina17:Adopting,
title={Adopting the Cascade Model in Ad Auctions: Efficiency Bounds and Truthful Algorithmic Mechanisms},
author={Farina, Gabriele and Gatti, Nicola},
journal={Journal of Artificial Intelligence Research},
volume={59},
pages={265--310},
year={2017}
}