Truthful auctions for pricing search keywords

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Truthful auctions for pricing search keywords

Full text

Pdf (247 KB)

Source

Electronic Commerce archive
Proceedings of the 7th ACM conference on Electronic commerce table of contents

Ann Arbor, Michigan, USA

Pages: 1 - 7

Year of Publication: 2006

ISBN:1-59593-236-4

Authors

Gagan Aggarwal	Google Inc.
Ashish Goel	Stanford University
Rajeev Motwani	Stanford University

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 142, Citation Count: 31

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1134707.1134708 What is a DOI?

ABSTRACT

We present a truthful auction for pricing advertising slots on a web-page assuming that advertisements for different merchants must be ranked in decreasing order of their (weighted) bids. This captures both the Overture model where bidders are ranked in order of the submitted bids, and the Google model where bidders are ranked in order of the expected revenue (or utility) that their advertisement generates. Assuming separable click-through rates, we prove revenue-equivalence between our auction and the non-truthful next-price auctions currently in use.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
	2	E. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
	3	B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. Working paper, http://rwj.berkeley.edu/schwarz/, 2005.
	4	J. Feng, H. Bhargava, , and D. Pennock. Implementing sponsored search in web search engines: computational evaluation of alternative mechanisms. To appear in the Informs Journal on Computing, 2006.
	5	T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
	6	Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
	7	C. Simon and L. Blume. Mathematics for Economics. W.W. Norton & Company, Inc., New York, 1994.
	8	W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

CITED BY 31

	Wei Zhou , Subhajyoti Bandyopadhyay , Hsing Cheng , Praveen Pathak, A Mechanism for On-line Advertisement Placement to Deter Click Fraud, International Journal of Electronic Commerce, v.13 n.2, p.9-28, Number 2 / Winter 2008-9
	Prabhakar Raghavan, The changing face of web search: algorithms, auctions and advertising, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Jon Feldman , S Muthukrishnan , Martin Pal , Cliff Stein, Budget optimization in search-based advertising auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Christian Borgs , Jennifer Chayes , Nicole Immorlica , Kamal Jain , Omid Etesami , Mohammad Mahdian, Dynamics of bid optimization in online advertisement auctions, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007
	Mohammad Mahdian , Hamid Nazerzadeh , Amin Saberi, Allocating online advertisement space with unreliable estimates, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Sébastien Lahaie , David M. Pennock, Revenue analysis of a family of ranking rules for keyword auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Zoe Abrams , Ofer Mendelevitch , John Tomlin, Optimal delivery of sponsored search advertisements subject to budget constraints, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Nicolas S. Lambert , Yoav Shoham, Asymptotically optimal repeated auctions for sponsored search, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA
	Gagan Aggarwal , Nir Ailon , Florin Constantin , Eyal Even-Dar , Jon Feldman , Gereon Frahling , Monika R. Henzinger , S. Muthukrishnan , Noam Nisan , Martin Pál , Mark Sandler , Anastasios Sidiropoulos, Theory research at Google, ACM SIGACT News, v.39 n.2, June 2008
	Sudhir Kumar Singh , Vwani Roychowdhury , Himawan Gunadhi , Behnam Rezaei, Diversification in the internet economy: the role of for-profit mediators, ACM SIGecom Exchanges, v.7 n.3, p.1-24, November 2008
	Tian-Ming Bu , Xiaotie Deng , Qi Qi, Forward looking Nash equilibrium for keyword auction, Information Processing Letters, v.105 n.2, p.41-46, January, 2008
	Rica Gonen , Elan Pavlov, An incentive-compatible multi-armed bandit mechanism, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Yunhong Zhou , Rajan Lukose, Vindictive bidding in keyword auctions, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA
	Hamid Nazerzadeh , Amin Saberi , Rakesh Vohra, Dynamic cost-per-action mechanisms and applications to online advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Gagan Goel , Aranyak Mehta, Online budgeted matching in random input models with applications to Adwords, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.982-991, January 20-22, 2008, San Francisco, California
	Tian-Ming Bu , Xiaotie Deng , Qi Qi, Arbitrage opportunities across sponsored search markets, Theoretical Computer Science, v.407 n.1-3, p.182-191, November, 2008
	Garud lyengar , David Phillips , Cliff Stein, Models of malicious behavior in sponsored search, Proceedings of the 2007 spring simulation multiconference, March 25-29, 2007, Norfolk, Virginia
	Gagan Aggarwal , S. Muthukrishnan , Dávid Pál , Martin Pál, General auction mechanism for search advertising, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Moshe Babaioff , Yogeshwer Sharma , Aleksandrs Slivkins, Characterizing truthful multi-armed bandit mechanisms: extended abstract, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Jason Auerbach , Joel Galenson , Mukund Sundararajan, An empirical analysis of return on investment maximization in sponsored search auctions, Proceedings of the 2nd International Workshop on Data Mining and Audience Intelligence for Advertising, p.1-9, August 24-24, 2008, Las Vegas, Nevada
	Eyal Even Dar , Vahab S. Mirrokni , S. Muthukrishnan , Yishay Mansour , Uri Nadav, Bid optimization for broad match ad auctions, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Thomas Meinl , Benjamin Blau, Web service derivatives, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Ashish Goel , Kamesh Munagala, Hybrid keyword search auctions, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Wei Zhou , Subhajyoti Bandyopadhyay , Hsing Cheng , Praveen Pathak, A Mechanism for On-line Advertisement Placement to Deter Click Fraud, International Journal of Electronic Commerce, v.13 n.2, p.9-28, Number 2 / Winter 2008-9
	David Robert Martin Thompson , Kevin Leyton-Brown, Computational analysis of perfect-information position auctions, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Nikhil R. Devenur , Thomas P. Hayes, The adwords problem: online keyword matching with budgeted bidders under random permutations, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Bobji Mungamuru , Hector Garcia-Molina, Managing the quality of CPC traffic, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Renato D. Gomes , Kane S. Sweeney, Bayes-nash equilibria of the generalized second price auction, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Danny Kuminov , Moshe Tennenholtz, User modeling in position auctions: re-considering the GSP and VCG mechanisms, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Shaddin Dughmi , Tim Roughgarden , Mukund Sundararajan, Revenue submodularity, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA