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

Article

An adaptive algorithm for selecting profitable keywords for search-based advertising services

Authors:

Paat Rusmevichientong,

David P. WilliamsonAuthors Info & Claims

EC '06: Proceedings of the 7th ACM conference on Electronic commerce

Pages 260 - 269

https://doi.org/10.1145/1134707.1134736

Published: 11 June 2006 Publication History

Abstract

Increases in online search activities have spurred the growth of search-based advertising services offered by search engines. These services enable companies to promote their products to consumers based on their search queries. In most search-based advertising services, a company sets a daily budget, selects a set of keywords, determines a bid price for each keyword, and designates an ad associated with each selected keyword. When a consumer searches for one of the selected keywords, search engines then display the ads associated with the highest bids for that keyword on the search result page. A company whose ad is displayed pays the search engine only when the consumer clicks on the ad. If the company's spending has exceeded its daily budget, however, its ads will not be displayed. With millions of available keywords and a highly uncertain clickthru rate associated with the ad for each keyword, identifying the most profitable set of keywords given the daily budget constraint becomes challenging for companies wishing to promote their goods and services via search-based advertising. Motivated by these challenges, we formulate a model of keyword selection in search-based advertising services. We develop an algorithm that adaptively identifies the set of keywords to bid on based on historical performance. The algorithm prioritizes keywords based on a prefix ordering-- sorting of keywords in a descending order of profit-tocost ratio (or "bang-per-buck"). We show that the average expected profit generated by the algorithm converges to near-optimal profits. Furthermore, the convergence rate is independent of the number of keywords and scales gracefully with the problem's parameters. Extensive numerical simulations show that our algorithm outperforms existing methods, increasing profits by about 7%.

References

[1]

G. Aggarwal and J. D. Hartline, "Knapsack Auctions," Workshop on Sponsored Search Auctions, EC 2005.

[2]

R. Agrawal, "The continuum-armed bandit problem," SIAM J. Control and Optimization, vol. 33, pp. 1926--1951, 1995.

Digital Library

[3]

P. Auer, N. Cesa-Bianchi, P. Fischer, "Finite-time Analysis of the Multiarmed Bandit Problem," Machine Learning, pp. 235--256, 2002.

Digital Library

[4]

P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, "Gambling in a rigged casino: The adversarial multi-armed bandit problem," SODA 1995.

Digital Library

[5]

M-F. Balcan, A. Blum, J. D. Hartline, Y. Mansour "Sponsored Search Auction Design via Machine Learning," Workshop on Sponsored Search Auctions, EC 2005.

[6]

J. Chen, D. Liu, A. B. Whinston, "Designing Share Structure in Auctions of Divisible Goods," Workshop on Sponsored Search Auctions, EC 2005.

[7]

B. Dean, M.X. Goemans and J. Vondrak, "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," FOCS 2004, pp. 208--217.

Digital Library

[8]

E. Even-Dar, S. Mannor, and Y. Mansour, "PAC bounds for multi-armed bandit and Markov decision processes," Fifteenth Annual Conference on Computational Learning Theory, pp. 255-270, 2002.

Digital Library

[9]

J. Goodman, "Pay-Per-Percentage of Impressions: An Advertising Method that is Highly Robust to Fraud," Workshop on Sponsored Search Auctions, EC 2005.

[10]

R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: A survey," Annals of Discrete Mathematics, 5:287--326, 1979.

[11]

B. J. Jansen and M. Resnick, "Examining Searcher Perceptions of and Interactions with Sponsored Results," Workshop on Sponsored Search Auctions, EC 2005.

[12]

B. Kitts, P. Laxminarayan, B. LeBlanc, R. Meech, "A Formal Analysis of Search Auctions Including Predictions on Click Fraud and Bidding Tactics," Workshop on Sponsored Search Auctions, EC 2005.

[13]

R. Kleinberg, "Online Decision Problems with Large Strategy Sets," Ph.D. disseration, MIT 2005.

Digital Library

[14]

R. Kleinberg, "Nearly tight bounds for the continuum-armed bandit problem," in NIPS 2005.

[15]

S. R. Kulkarni and G. Lugosi, "Finite-time lower bounds for the two-armed bandit problem," IEEE Trans. Aut. Control, pp. 711--714, 2000.

[16]

T. L. Lai and H. Robbins, "Asymptotically efficient adaptive allocation rules," Advances in Applied Mathematics, vol. 6, pp. 4--22, 1985.

Digital Library

[17]

S. Mannor and J. N. Tsitsiklis, "Lower bounds on the sample complexity of exploration in the multiarmed bandit problem," Sixteenth Annual Conference on Computational Learning Theory, pp. 418-432. Springer, 2003.

[18]

C. Meek, D. M. Chickering, D. B. Wilson, "Stochastic and Contingent-Payment Auctions," Workshop on Sponsored Search Auctions, EC 2005.

[19]

A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani, "Adwords and Generalized Online Matching," FOCS 2005.

Digital Library

[20]

M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge, 2005.

Digital Library

[21]

D. C. Parkes and T. Sandholm,"Optimize-and-Dispatch Architecture for Expressive Ad Auctions," Workshop on Sponsored Search, EC 2005.

[22]

D. Pollard, Convergence of Stochastic Processes, Springer Verlang, 1994.

[23]

S. Sahni, "Approximate Algorithms for the 0/1 Knapsack Problem," Journal of the ACM, 22:115--124, 1975.

Digital Library

[24]

M. Zinkevich, "Online convex programming and generalized infinitisimal gradient ascent," in Proceeding of the 20th International Conference on Machine Learning, pp. 928--936, 2003.

Cited By

Guo ZZhang CLi MKrunz M(2024)Fair Probabilistic Multi-Armed Bandit With Applications to Network OptimizationIEEE Transactions on Machine Learning in Communications and Networking10.1109/TMLCN.2024.34211702(994-1016)Online publication date: 2024
https://doi.org/10.1109/TMLCN.2024.3421170
Phillips JChow YRogers HBlaszczynski A(2024)The search term ‘suicide’ is being used to lead web browsers to online casinosBehaviour & Information Technology10.1080/0144929X.2023.229830743:16(4033-4044)Online publication date: 5-Jan-2024
https://doi.org/10.1080/0144929X.2023.2298307
Majima KKawakami KIshizuka KNakata K(2024)Keyword-Level Bayesian Online Bid Optimization for Sponsored Search AdvertisingOperations Research Forum10.1007/s43069-024-00322-y5:2Online publication date: 22-May-2024
https://doi.org/10.1007/s43069-024-00322-y
Show More Cited By

Index Terms

An adaptive algorithm for selecting profitable keywords for search-based advertising services
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

An empirical analysis of sponsored search performance in search engine advertising
WSDM '08: Proceedings of the 2008 International Conference on Web Search and Data Mining

The phenomenon of sponsored search advertising - where advertisers pay a fee to Internet search engines to be displayed alongside organic (non-sponsored) web search results - is gaining ground as the largest source of revenues for search engines. ...
Bidding for Multiple Keywords in Sponsored Search Advertising: Keyword Categories and Match Types

Although keyword auctions are often studied in the context of a single keyword in the literature, firms generally have to participate in multiple keyword auctions at the same time. Advertisers purchase a variety of keywords that can be categorized as ...
Competitive Poaching in Sponsored Search Advertising and Its Strategic Impact on Traditional Advertising

Traditional advertising, such as TV and print advertising, primarily builds awareness of a firm's product among consumers, whereas sponsored search advertising on a search engine can target consumers closer to making a purchase because they reveal their ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '06: Proceedings of the 7th ACM conference on Electronic commerce

June 2006

342 pages

ISBN:1595932364

DOI:10.1145/1134707

General Chair:
Joan Feigenbaum
Yale University, USA
,
Program Chairs:
John Chuang
University of California Berkeley, USA
,
David M. Pennock
Yahoo! Research, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

EC06

Sponsor:

EC06: ACM Conference on Electronic Commerce

June 11 - 15, 2006

Michigan, Ann Arbor, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
1,597
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo ZZhang CLi MKrunz M(2024)Fair Probabilistic Multi-Armed Bandit With Applications to Network OptimizationIEEE Transactions on Machine Learning in Communications and Networking10.1109/TMLCN.2024.34211702(994-1016)Online publication date: 2024
https://doi.org/10.1109/TMLCN.2024.3421170
Phillips JChow YRogers HBlaszczynski A(2024)The search term ‘suicide’ is being used to lead web browsers to online casinosBehaviour & Information Technology10.1080/0144929X.2023.229830743:16(4033-4044)Online publication date: 5-Jan-2024
https://doi.org/10.1080/0144929X.2023.2298307
Majima KKawakami KIshizuka KNakata K(2024)Keyword-Level Bayesian Online Bid Optimization for Sponsored Search AdvertisingOperations Research Forum10.1007/s43069-024-00322-y5:2Online publication date: 22-May-2024
https://doi.org/10.1007/s43069-024-00322-y
Chen RWu F(2023)Dynamically Interrupting Deadlocks in Game Learning Using Multisampling Multiarmed BanditsIEEE Transactions on Games10.1109/TG.2022.317759815:3(360-367)Online publication date: Sep-2023
https://doi.org/10.1109/TG.2022.3177598
Benamara IViennet E(2023)Contextual Advertising Strategy Generation via Attention and Interaction Guidance2023 IEEE 10th International Conference on Data Science and Advanced Analytics (DSAA)10.1109/DSAA60987.2023.10302533(1-10)Online publication date: 9-Oct-2023
https://doi.org/10.1109/DSAA60987.2023.10302533
Jeong JHong DYoum S(2022)Optimization of the Decision-Making System for Advertising Strategies of Small Enterprises—Focusing on Company ASystems10.3390/systems1004011610:4(116)Online publication date: 6-Aug-2022
https://doi.org/10.3390/systems10040116
Li HYang Y(2022)Keyword targeting optimization in sponsored search advertisingElectronic Commerce Research and Applications10.1016/j.elerap.2022.10120956:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.elerap.2022.101209
Gupta SMishra A(2022)Revenue-maximizing ranking algorithm for advertisers in sponsored search advertising using novel adaptive keyword-weighted approachMultimedia Tools and Applications10.1007/s11042-022-13747-682:8(12043-12064)Online publication date: 17-Sep-2022
https://doi.org/10.1007/s11042-022-13747-6
Dayanik SSezer S(2022)Optimal dynamic multi-keyword bidding policy of an advertiser in search-based advertisingMathematical Methods of Operations Research10.1007/s00186-022-00803-y97:1(25-56)Online publication date: 14-Nov-2022
https://doi.org/10.1007/s00186-022-00803-y
Gupta VRusmevichientong P(2021)Small-Data, Large-Scale Linear Optimization with Uncertain ObjectivesManagement Science10.1287/mnsc.2019.355467:1(220-241)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1287/mnsc.2019.3554
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents