Budget constrained bidding in keyword auctions and online knapsack problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Budget constrained bidding in keyword auctions and online knapsack problems

Full text

Pdf (125 KB)

Source

International World Wide Web Conference archive
Proceeding of the 17th international conference on World Wide Web table of contents

Beijing, China

POSTER SESSION: Posters table of contents

Pages 1243-1244

Year of Publication: 2008

ISBN:978-1-60558-085-2

Authors

Yunhong Zhou	HP Labs, Palo Alto, CA, USA
Deeparnab Chakrabarty	Georgia Tech, Atlanta, GA, USA
Rajan Lukose	HP Labs, Palo Alto, CA, USA

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1367497.1367747 What is a DOI?

ABSTRACT

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e., without knowledge) of other bidders' prices and/or click-through-rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.

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	Overture view bids, available until Febuary 2007. http://uv.bidtool.overture.com/d/search/tools/bidtool
	2	Awerbuch, Y. Azar, and S. A. Plotkin. Throughput- competitive on-line routing. In FOCS, pages 32--40, 1993.
	3	Buchbinder, K. Jain, and J. S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. ESA, pages 253--264, 2007.
	4	A. Marchetti-Spaccamela , C. Vercellis, Stochastic on-line knapsack problems, Mathematical Programming: Series A and B, v.68 n.1, p.73-104, Jan. 2, 1995 [doi>10.1007/BF01585758]
	5	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]
	6	Zhou, D. Chakrabarty, and R. Lukose. Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. HP Labs tech report HPL-2008--9, 2008.

CITED BY 3

	Yunhong Zhou , Victor Naroditskiy, Algorithm for stochastic multiple-choice knapsack problem and application to keywords bidding, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Moshe Babaioff , Jason D. Hartline , Robert D. Kleinberg, Selling ad campaigns: online algorithms with cancellations, 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