Arpita Ghosh
ABSTRACT
When 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-click competition for conversions cannot: since the value-per-click of an advertiser is proportional to the conversion probability conditional on a click, which depends on the other ads displayed, the private value of an advertiser is no longer one-dimensional, and the GSP mechanism is not adequately expressive. We study the design of expressive GSP-like mechanisms for the simplest form that an advertiser's private value can have in the presence of such externalities- an advertiser's value depends on exclusivity, i.e., whether her ad is shown exclusively, or along with other ads.
Our auctions take as input two-dimensional (per-click) bids for exclusive and nonexclusive display, and have two types of outcomes: either a single ad is displayed exclusively, or multiple ads are simultaneously shown. We design two expressive auctions that are both extensions of GSP- the first auction, GSP2D, is designed with the property that the allocation and pricing are identical to GSP when multiple ads are shown; the second auction, NP2D, is designed to be a next price auction. We show that both auctions have high efficiency and revenue in all reasonable equilibria; further, the NP2D auction is guaranteed to always have an equilibrium with revenue at least as much as the current GSP mechanism. However, we find that unlike with one-dimensional valuations, the GSP-like auctions for these richer valuations do not always preserve efficiency and revenue with respect to the VCG mechanism.
- Abrams, Z., Ghosh, A., and Vee, E. Cost of conciseness in sponsored search auctions. In WINE '07: Proceedings of the 3rd International Workshop on Internet and Network Economics (Berlin, Heidelberg, 2007), Springer-Verlag. Google Scholar
Digital Library
- Aggarwal, G., Feldman, J., and Muthukrishnan, S. Bidding to the top: VCG and equilibria of position-based auctions. In WAOA'06: Proc. Workshop on Approximation and Online Algorithms (2006). Google ScholarDigital Library
- Aggarwal, G., Feldman, J., Muthukrishnan, S., and Pal, M. Sponsored search auctions with markovian users. In WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics (Berlin, Heidelberg, 2008), Springer-Verlag, pp. 621--628. Google ScholarDigital Library
- Athey, S., and Nekipelov, D. Equilibrium and uncertainty in sponsored search auctions. Manuscript (2009).Google Scholar
- Benisch, M., Sadeh, N., and Sandholm, T. A theory of expressiveness in mechanisms. In Proceedings of National Conference on Artificial Intelligence (AAAI) (2008), pp. 07--178. Google ScholarDigital Library
- Cary, M., Das, A., Edelman, B., Giotis, I., Heimerl, K., Karlin, A. R., Mathieu, C., and Schwarz, M. Greedy bidding strategies for keyword auctions. In EC '07: Proceedings of the 8th ACM conference on Electronic commerce (New York, NY, USA, 2007), ACM, pp. 262--271. Google ScholarDigital Library
- Das, A., Giotis, I., Karlin, A., and Mathieu, C. On the effects of competing advertisements in keyword auctions. Unpublished Manuscript, May (2008).Google Scholar
- Edelman, B., Ostrovsky, M., Schwarz, M., Fudenberg, T. D., Kaplow, L., Lee, R., Milgrom, P., Niederle, M., and Pakes, A. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review 97 (2005).Google Scholar
- Ghosh, A., and Mahdian, M. Externalities in online advertising. In WWW '08: Proceeding of the 17th international conference on World Wide Web (New York, NY, USA, 2008), ACM, pp. 161--168. Google ScholarDigital Library
- Ghosh, A., and Sayedi, A. Expressive Auctions for Externalities in Online Advertising. Manuscript, November (2009). http://www.andrew.cmu.edu/user/ssayedir/ext.pdf.Google Scholar
- Giotis, I., and Karlin, A. R. On the equilibria and efficiency of the GSP mechanism in keyword auctions with externalities. In WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics (Berlin, Heidelberg, 2008), Springer-Verlag, pp. 629--638. Google ScholarDigital Library
- Gomes, R., Immorlica, N., and Markakis, E. Externalities in keyword auctions: an empirical and theoretical assessment. In WINE '09: Proceedings of the 5th International Workshop on Internet and Network Economics (2009), Springer-Verlag. Google ScholarDigital Library
- Guruswami, V., Hartline, J., Karlin, A., Kempe, D., Kenyon, C., and McSherry, F. On profit-maximizing envy-free pricing. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (2005), Society for Industrial and Applied Mathematics Philadelphia, PA, USA, pp. 1164--1173. Google ScholarDigital Library
- Jeziorski, P., and Segal, I. What makes them click: Empirical analysis of consumer demand for search advertising. Manuscript (2009).Google Scholar
- Kempe, D., and Mahdian, M. A cascade model for externalities in sponsored search. In WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics (Berlin, Heidelberg, 2008), Springer-Verlag, pp. 585--596. Google ScholarDigital Library
- Muthukrishnan, S. Bidding on configurations in Internet ad auctions. Manuscript (2009).Google Scholar
- Sadeh, N., Hong, J., Cranor, L., Fette, I., Kelley, P., Prabaker, M., and Rao, J. Understanding and capturing people's privacy policies in a people finder application. The Journal of Personal and Ubiquitous Computing (2008). Google ScholarDigital Library
- Salek, M., and Kempe, D. Auctions for share-averse bidders. In WINE '08: Proceedings of the 4th International Workshop on Internet and Network Economics (Berlin, Heidelberg, 2008), Springer-Verlag, pp. 609--620. Google ScholarDigital Library
- Schwartz, B. The paradox of choice: Why more is less. Harper Perennial, 2005.Google Scholar
- Varian, H. Position auctions. International Journal of Industrial Organization 25, 6 (2007), 1163--1178.Google ScholarCross Ref
- Yu, J., and Deng, X. A new ranking scheme of the GSP mechanism with markovian users. In WINE '09: Proceedings of the 5th International Workshop on Internet and Network Economics (2009), Springer-Verlag. Google ScholarDigital Library
Index Terms
- Expressive auctions for externalities in online advertising
Recommendations
Externalities in online advertising
WWW '08: Proceedings of the 17th international conference on World Wide WebMost 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 ...
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 ...
Boosted Second Price Auctions: Revenue Optimization for Heterogeneous Bidders
KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data MiningThe second price auction has been the prevalent auction format used by advertising exchanges because of its simplicity and desirable incentive properties. However, even with an optimized choice of reserve prices, this auction is not revenue optimal when ...
Comments