An Adaptive Algorithm for Selecting Profitable Keywords for Search-Based Advertising Services
Paat Rusmevichientong
Department of Operations Research and Industrial Engineering
Cornell University
Wednesday, May 10, 2006
4:30 - 5:45 PM
Terman Engineering Center, Room 453
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.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html