Towards better models of externalities in sponsored search auctions

DOI10.3233/978-1-61499-672-9-1167zbMATH Open1396.91243arXiv1604.04095OpenAlexW3179169617MaRDI QIDQ4576241FDOQ4576241

Authors: Nicola Gatti, Paolo Serafino, Carmine Ventre, Marco Rocco 

Publication date: 12 July 2018

Abstract: Sponsored Search Auctions (SSAs) arguably represent the problem at the intersection of computer science and economics with the deepest applications in real life. Within the realm of SSAs, the study of the effects that showing one ad has on the other ads, a.k.a. externalities in economics, is of utmost importance and has so far attracted the attention of much research. However, even the basic question of modeling the problem has so far escaped a definitive answer. The popular cascade model is arguably too idealized to really describe the phenomenon yet it allows a good comprehension of the problem. Other models, instead, describe the setting more adequately but are too complex to permit a satisfactory theoretical analysis. In this work, we attempt to get the best of both approaches: firstly, we define a number of general mathematical formulations for the problem in the attempt to have a rich description of externalities in SSAs and, secondly, prove a host of results drawing a nearly complete picture about the computational complexity of the problem. We complement these approximability results with some considerations about mechanism design in our context.

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

Recommendations

• Towards better models of externalities in sponsored search auctions
• Externalities among Advertisers in Sponsored Search
• Adopting the cascade model in ad auctions: efficiency bounds and truthful algorithmic mechanisms
• Position auctions with externalities
• Truthful learning mechanisms for multi-slot sponsored search auctions with externalities

zbMATH Keywords

computational complexityapproximation algorithmexternalitiessponsored search auctions

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Approximation algorithms (68W25)

Cited In (5)

• Modeling bounded rationality for sponsored search auctions
• Towards better models of externalities in sponsored search auctions
• Adopting the cascade model in ad auctions: efficiency bounds and truthful algorithmic mechanisms
• Sponsored data: a game-theoretic model with consumer multihoming behaviour
• Externalities among Advertisers in Sponsored Search

This page was built for publication: Towards better models of externalities in sponsored search auctions

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