More Web Proxy on the site http://driver.im/

Article

A Cascade Model for Externalities in Sponsored Search

Authors:

Mohammad MahdianAuthors Info & Claims

WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics

Pages 585 - 596

https://doi.org/10.1007/978-3-540-92185-1_65

Published: 17 December 2008 Publication History

Abstract

One of the most important yet insufficiently studied issues in online advertising is the externality effect among ads: the value of an ad impression on a page is affected not just by the location that the ad is placed in, but also by the set of other ads displayed on the page. For instance, a high quality competing ad can detract users from another ad, while a low quality ad could cause the viewer to abandon the page altogether.

In this paper, we propose and analyze a model for externalities in sponsored search ads . Our model is based on the assumption that users will visually scan the list of ads from the top to the bottom. After each ad, they make independent random decisions with ad-specific probabilities on whether to continue scanning. We then generalize the model in two ways: allowing for multiple separate blocks of ads, and allowing click probabilities to explicitly depend on ad positions as well. For the most basic model, we present a polynomial-time incentive-compatible auction mechanism for allocating and pricing ad slots. For the generalizations, we give approximation algorithms for the allocation of ads.

References

[1]

Aggarwal, G., Feldman, J., Muthukrishnan, S., Pál, M.: Sponsored search auctions with markovian users. In: Proc. 4th Workshop on Ad Auctions (2008)

[2]

Aggarwal, G., Goel, A., Motwani, R.: Truthful auctions for pricing search keywords. In: Proc. 8th ACM Conf. on Electronic Commerce, pp. 1-7 (2006)

[3]

Athey, S., Ellison, G.: Position auctions with consumer search. Working Paper (September 2007)

[4]

Cary, M., Das, A., Edelman, B., Giotis, I., Heimerl, K., Karlin, A., Mathieu, C., Schwarz, M.: Greedy bidding strategies for keyword auctions. In: Proc. 9th ACM Conf. on Electronic Commerce, pp. 262-271 (2007)

[5]

Clarke, E.: Multipart pricing of public goods. Public Choice 11, 17-33 (1971)

[6]

Craswell, N., Zoeter, O., Taylor, M., Ramsey, B.: An experimental comparison of click position-bias models. In: Proc. 1st Intl. Conf. on Web Search and Data Mining (2008)

[7]

Das, A., Giotis, I., Karlin, A., Mathieu, C.: On the effects of competing advertisements in keyword auctions (May 2008) (unpublished manuscript)

[8]

Edelman, B., Ostrovsky, M., Schwarz, M.: Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review 97(1), 242-259 (2007)

[9]

Ghosh, A., Mahdian, M.: Externalities in online advertising. In: 17th Intl. World Wide Web Conference (2008)

[10]

Groves, T.: Incentives in teams. Econometrica 41, 617-631 (1973)

[11]

Joachims, T., Granka, L., Pan, B., Hembrooke, H., Radlinski, F., Gay, G.: Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search. ACM Transactions on Information Systems (TOIS) 25(2) (2007)

[12]

Lahaie, S.: An analysis of alternative slot auction designs for sponsored search. In: Proc. 8th ACM Conf. on Electronic Commerce, pp. 218-227 (2006)

[13]

Lahaie, S., Pennock, D., Saberi, A., Vohra, R.: Sponsored search auctions. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V. (eds.) Algorithmic Game Theory, ch. 28. Cambridge University Press, Cambridge (2007)

[14]

Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In: Proc. 9th ACM Conf. on Electronic Commerce, pp. 288-294 (2007)

[15]

Muthukrishnan, S., Pál, M., Svitkina, Z.: Stochastic models for budget optimization in search-based advertising. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 131-142. Springer, Heidelberg (2007)

[16]

Varian, H.: Position auctions. Intl. J. of Industrial Organization 25(6), 1163-1178 (2007)

[17]

Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. of Finance 16, 8-37 (1961)

[18]

Wortman, J., Vorobeychik, Y., Li, L., Langford, J.: Maintaining equilibria during exploration in sponsored search auctions. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 119-130. Springer, Heidelberg (2007)

Cited By

Li XWang ZZhu BHe FWang YWang XHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Deep Automated Mechanism Design for Integrating Ad Auction and Allocation in FeedProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657774(1211-1220)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657774
Gao XJasin SNajafi SZhang H(2022)Joint Learning and Optimization for Multi-Product Pricing (and Ranking) Under a General Cascade Click ModelManagement Science10.1287/mnsc.2021.424668:10(7362-7382)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1287/mnsc.2021.4246
Derakhshan MGolrezaei NManshadi VMirrokni V(2022)Product Ranking on Online PlatformsManagement Science10.1287/mnsc.2021.404468:6(4024-4041)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1287/mnsc.2021.4044
Show More Cited By

Recommendations

Correcting vindictive bidding behaviors in sponsored search auctions

In this study, we aim to develop a pricing mechanism that reduces the effects resulted by vindictive advertisers who bid on sponsored search auctions run by search engine providers. In particular, we aim to ensure payment fairness and price stability in ...
Truthful learning mechanisms for multi-slot sponsored search auctions with externalities

Sponsored Search Auctions (SSAs) 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, at the same time, to ...
Revenue guarantees in sponsored search auctions
ESA'12: Proceedings of the 20th Annual European conference on Algorithms

Sponsored search auctions are the main source of revenue for search engines. In such an auction, a set of utility-maximizing advertisers compete for a set of ad slots. The assignment of advertisers to slots depends on bids they submit; these bids may be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics

December 2008

731 pages

ISBN:9783540921844

Editors:
Christos Papadimitriou
Computer Science Division, University of California at Berkeley, Berkeley, USA
,
Shuzhong Zhang
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong,

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 December 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li XWang ZZhu BHe FWang YWang XHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Deep Automated Mechanism Design for Integrating Ad Auction and Allocation in FeedProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657774(1211-1220)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657774
Gao XJasin SNajafi SZhang H(2022)Joint Learning and Optimization for Multi-Product Pricing (and Ranking) Under a General Cascade Click ModelManagement Science10.1287/mnsc.2021.424668:10(7362-7382)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1287/mnsc.2021.4246
Derakhshan MGolrezaei NManshadi VMirrokni V(2022)Product Ranking on Online PlatformsManagement Science10.1287/mnsc.2021.404468:6(4024-4041)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1287/mnsc.2021.4044
Chen CChen HZhao KZhou JHe LDeng HXu JZheng BZhang YXing CZhang ARangwala H(2022)EXTR: Click-Through Rate Prediction with Externalities in E-Commerce Sponsored SearchProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539053(2732-2740)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539053
Tang SYuan JDignum FLomuscio AEndriss UNowé A(2021)Adaptive Cascade Submodular MaximizationProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464102(1299-1307)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464102
Tang SYuan JMookerjee VMelodia TEkici EAbouzeid AChen M(2020)Optimizing ad allocation in mobile advertisingProceedings of the Twenty-First International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3397166.3409139(181-190)Online publication date: 11-Oct-2020
https://dl.acm.org/doi/10.1145/3397166.3409139
Colini-Baldeschi RMestre JSchrijvers OWilkens C(2020)The Ad Types ProblemWeb and Internet Economics10.1007/978-3-030-64946-3_4(45-58)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64946-3_4
Seddighin MSaleh HGhodsi M(2019)Externalities and FairnessThe World Wide Web Conference10.1145/3308558.3313670(538-548)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313670
Berman R(2018)Beyond the Last TouchMarketing Science10.1287/mksc.2018.110437:5(771-792)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1287/mksc.2018.1104
Komiyama JHonda JTakeda A(2017)Position-based multiple-play bandit problem with unknown position biasProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3295222.3295253(5005-5015)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3295222.3295253
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents