Externalities in online advertising
Authors:
Open Access
- 21 April 2008
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 161-168
Abstract
Most models for online advertising assume that an adver- tiser's value from winning an ad auction, which depends on the clickthrough rate or conversion rate of the advertise- ment, is independent of other advertisements served along- side it in the same session. This ignores an important ex- ternality eect : as the advertising audience has a limited attention span, a high-quality ad on a page can detract at- tention from other ads on the same page. That is, the utility to a winner in such an auction also depends on the set of other winners. In this paper, we introduce the problem of modeling ex- ternalities in online advertising, and study the winner de- termination problem in these models. Our models are based on choice models on the audience side. We show that in the most general case, the winner determination problem is hard even to approximate. However, we give an approx- imation algorithm for this problem with an approximation factor that is logarithmic in the ratio of the maximum to the minimum bid. Furthermore, we show that there are some interesting special cases, such as the case where the audi- ence preferences are single peaked, where the problem can be solved exactly in polynomial time. For all these algo- rithms, we prove that the winner determination algorithm can be combined with VCG-style payments to yield truthful mechanisms.Keywords
This publication has 10 references indexed in Scilit:
- Approximating Matches Made in Heaven2009
- Evaluating the accuracy of implicit feedback from clicks and query reformulations in Web searchACM Transactions on Information Systems, 2007
- The Political Economy of "Truth-in-Advertising" Regulation During the Progressive Era2006
- Approximately-strategyproof and tractable multiunit auctionsDecision Support Systems, 2005
- Chapter 3 Domain restrictions2002
- Efficient Design with Interdependent ValuationsEconometrica, 2001
- Multidimensional Mechanism Design for Auctions with ExternalitiesJournal of Economic Theory, 1999
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- Strategic NonparticipationThe RAND Journal of Economics, 1996
- The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation RuleEconometrica, 1991