An Adaptive Algorithm for Selecting Profitable Keywords for
Search-Based Advertising Services
School of OR&IE
Cornell University
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-to-cost 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%. We also explore extensions to current
search-based advertising services and indicate how to adapt our algorithm to
these settings.
This is joint work with David P. Williamson at Cornell University.