Arpita Ghosh
Mohammad Mahdian
ABSTRACT
Most models for online advertising assume that an advertiser's value from winning an ad auction, which depends on the clickthrough rate or conversion rate of the advertisement, is independent of other advertisements served alongside it in the same session. This ignores an important 'externality effect': as the advertising audience has a limited attention span, a high-quality ad on a page can detract attention 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 externalities in online advertising, and study the winner determination 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 approximation 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 audience preferences are single peaked, where the problem can be solved exactly in polynomial time. For all these algorithms, we prove that the winner determination algorithm can be combined with VCG-style payments to yield truthful mechanisms.
- Aaron Archer and Eva Tardos. Truthful mechanisms for one-parameter agents. In IEEE Symposium on Foundations of Computer Science, pages 482--491, 2001. Google Scholar
Digital Library
- Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. in preparation, 2008.Google Scholar
- W. Gaertner. Domain restrictions. In K. J. Arrow, A. K. Sen, and K. Suzumura, editors, Handbook of Social Choice and Welfare, volume I, chapter 3, pages 131--170. Elsevier Science, 2002.Google ScholarCross Ref
- Z. K. Hansen and M. Law. The political economy of truth-in-advertising regulation in the progressive era. Forthcoming at the Journal of Law and Economics. An earlier version is available as NBER Working Paper No. 11927, 2006.Google Scholar
- Philippe Jehiel and Benny Moldovanu. Strategic non-participation. Rand Journal of Economics, 27(1):84--98, 1996.Google ScholarCross Ref
- Philippe Jehiel and Benny Moldovanu. Efficient design with interdependent valuations. Econometrica, 69(5):1237--59, 2001.Google ScholarCross Ref
- Philippe Jehiel, Benny Moldovanu, and E. Stacchetti. How (not) to sell nuclear weapons. American Economic Review, 86(4):814--829, 1996.Google Scholar
- Philippe Jehiel, Benny Moldovanu, and E. Stacchetti. Multidimensional mechanism design for auctions with externalities. Journal of Economic Theory, 85(2):258--294, 1999.Google ScholarCross Ref
- T. Joachims, L. Granka, Bing Pan, H. Hembrooke, F. Radlinski, and G. Gay. Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search. ACM Transactions on Information Systems (TOIS), 25(2), April 2007. Google ScholarDigital Library
- Anshul Kothari, David C. Parkes, and Subhash Suri. Approximately-strategyproof and tractable multiunit auctions. Decision Support Systems, 39(1):105--121, 2005. Google ScholarDigital Library
- Internet Advertising Bureau. Online lead generation: Standards and guidelines. http://www.iab.net/standards/lead_generation.asp.Google Scholar
- PricewaterhouseCoopers. IAB Internet Advertising Revenue Report, 2006 Full-Year Results. available at http://www.iab.net/resources/adrevenue/pdf/IAB_PwC_2006_Final.pdf, May 2007.Google Scholar
- Y. Sprumont. The division problem with single-peaked preferences: a characterization of the uniform allocation rule. Econometrica, 59(2):509--519, 1991.Google ScholarCross Ref
- J. Håstad. Clique is hard to approximate within n
1-ε. Acta Mathematica, 182:105--142, 1999.Google ScholarCross Ref
- Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Google ScholarDigital Library
- Xiaojin Zhu, Andrew Goldberg, Jurgen Van Gael, and David Andrzejewski. Improving diversity in ranking using absorbing random walks. In Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT), 2007.Google Scholar
Index Terms
- Externalities in online advertising
Recommendations
Expressive auctions for externalities in online advertising
WWW '10: Proceedings of the 19th international conference on World wide webWhen online ads are shown together, they compete for user attention and conversions, imposing negative externalities on each other. While the competition for user attention in sponsored search can be captured via models of clickthrough rates, the post-...
Combinatorial auctions with externalities
AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1Although combinatorial auctions have received a great deal of attention from the computer science community over the past decade, research in this domain has focussed on settings in which a bidder only has preferences over the bundles of goods they ...
Hybrid Advertising Auctions
Facebook and Google offer hybrid advertising auctions that allow advertisers to bid on a per-impression or a per-click basis for the same advertising space. This paper studies the properties of equilibrium and considers how to increase efficiency in ...
Comments