Math Conditions: General Form

Allocating Expenditures across Keywords in Search Advertising

Authors

1. Özgür Özlük

Department of Decision Sciences

College of Business, San Francisco State University

1600 Holloway Ave

San Francisco, CA 94132 USA

Phone: 415-817-4353

Fax: 415-405-0364

Email:

1. Susan Cholette

Department of Decision Sciences

College of Business, San Francisco State University

1600 Holloway Ave

San Francisco, CA 94132 USA

Phone:415-405-2173

Fax: 415-405-0364

Email:

Author Bios

1. Özgür Özlük is an Assistant Professor of Decision Sciences in the College of Business at San Francisco State University. His research interests are in business applications of mathematical programming, practices of revenue management and spreadsheet engineering. He obtained his Ph.D. in Operations Research from UNC Chapel Hill in 1999. After getting his Ph.D. degree, he spent three years working for an airline scheduling company and at a revenue management consulting firm.

2. Susan Cholette is an Assistant Professor of Decision Sciences in the College of Business at San Francisco State University. Her research interests include supply chain management, especially as applied to the wine industry, and she is currently supervising a federal grant to optimally match wineries to distributors. Prior to her university appointment she served as a project manager for several supply chain management solution providers. She earned her Ph.D. in Operations Research from Stanford University and her B.S.E. in Electrical Engineering from Princeton University.

Allocating Expenditures across Keywords in Search Advertising

Abstract

An increasingly popular venue for advertisers is the keyword advertising on the web pages of search engines. Advertisers bid for keywords, where bid price determines ad placement, which in turn affects the response function, defined as the click –through rate. Advertisers typically have a fixed daily budget that should not be exceeded, so an advertiser must allocate the budget as productively as possible by selecting which keywords to use and then deciding how much to allocate for each keyword. We construct and examine a model for this selection and allocation process.

Keywords

1. Search-based advertising
2. Keyword Advertising
3. Keyword Bidding
4. Internet Marketing
5. Resource Allocation
6. Budget Optimization

Introduction

An increasingly popular venue for advertisers iskeyword advertising on the web pages of search engines such as Google, Yahoo and MSN. Keyword ads, also known assearch-based advertisements, appear side by side with “organic”unsponsored search results, and the advertiser is charged only if a user clicks on the advertisement, taking the user to the advertiser’s webpage. US advertisers are projected to spend nearly $8.3 billion on keyword ads in 2007, nearly a 25% increase from 2006 and a 43% share of all US internet marketing expenditures (eMarketer, 2007).

Search-based advertisements provide national, even worldwide, access to potential consumers. The ability to setup and run campaigns of any size allows one-person businesses to compete side by side with much larger companies. Keyword searches have special appeal for businesses that cater to small, niche markets such as shoes for people with very big feet. Yet keyword advertising is a relatively new medium. The first search based ads appeared in 1998 in Overture, and Google did not adopt the current format until 2001 (Vise and Malseed, 2005). Thus all advertisers are still learning how to take advantage of these opportunities.

Our research focuses on maximizing the value that a firm receives from placing keyword advertisements.Advertisers typically have a fixed daily budget that should not be exceeded, so an advertiser must allocate the budget as productively as possible by selecting which keywords to use and then deciding how much fundingto allocate to each keyword. We construct and examine a model for this selection and allocation process.

Literature Review

Given therecent development and adoption of search-based advertisements, academic publications examining keyword ads are not as common as in other channels. In this section, we survey existing literature on keyword advertising and briefly examine papers concerned with resource allocation in other types of internet advertising and in early generalized advertising research. One of the first operations research papers on advertising, Vidale and Wolfe’s (1957) much cited work formalizes the question of how to best allocate advertising expenditures given a fixed budget. They introduce the concept of a response function by defining a response constant and also discuss the saturation effect.

No shortage ofpapers addressing the resource allocation problem exists by the 1970’s. In addition to presenting their own models, Zoltners and Sinha (1980) provide a detailed overview of 24 other papers that have defined sales response functions. The majority of the functional forms presentedare concave, although a few researchersattempt other techniques, such as developingheuristics for S-shaped response curves.

These prior papers and doubtless many others bemoan the difficulty of collecting accurate data for determining the effectiveness of an ad campaign. Today, this effectiveness can be measured more accurately. The advent of internet advertising allowed for the use of metrics such as impressions generated and clicks recorded. Furthermore, the time needed to collect data and evaluate effectiveness has decreased dramatically. Budget and resource allocation horizons shifted from quarterly or yearly down to daily allocations.

Much of the early internet advertising research is concerned with banner ads, a form that predates keywords. Chatterjee, Hoffman, and Novak, (2003) explore the likelihood of generating clicks, given the placement of banner advertising and a variety of other variables. They determine that earlier placement in a sequence of web pages is more likely to generate clicks and discuss the difference between results for general audience and targeted niche banner ads. Findings for the latter category are likely to be more applicable to keyword advertising.

Mangani (2004) constructs a theoretical model of net revenues obtained from banner advertisements by using simple nonlinear functions. He explores the tradeoffs in using the Cost-per-Impression pricing model against the then-emerging Cost-per-Click paradigm. He introduces the concept of elasticity of access with respect to the quantity of advertising and shows that the optimal budget allocation depends on the relation between these elasticities, a finding akin to our results.

Zhao and Nagurney (2004) consider allocating ad expenditures between several websites. Like Mangani, they also evaluate alternative pricing schemes, even including pricing based on generated revenue, which was a novel approach in 2004. They explain the paradox of why click rates are decreasing as internet usage increasesgiven a concave response function. Although this research does not concern keyword ads specifically, many of their results would appear to be relevant to that venue.

Nakamura and Abe(2005) continue the examination of banner ad placement by constructing a linear programming model that maximizes the clicks for a palette of banner advertisements. They definewebsite categories, such as sports vs. non-sports sites, and investigate how other variables affect the response function. However, their findings are best suited to broadbased advertising and are not as applicable to the niche markets served bykeyword advertising.

Fruchterand Dou (2005) research keyword-activated banner ads. These are ads that will appear only when the user has searched for a relevant keyword. For instance, clothing retailers might be more interested in displaying banner ads on pages selected by consumers who have searched for terms like “fashion.” They assume a concave response function - in particular, they utilize a power function. Theythen formulate the problem as an optimal control problem. Their investigation of keyword-specific banners rather than generalized banners suggests a crossover to research on search-based advertising. Their results suggesting that more generalized advertisements at generic portals yield higher click-through rateswould not seem appropriate to be applied tokeyword ad decision making.

Other authors examine managing internet advertising from the point of view of improving advertising revenues for websites that sell advertising space. Chickering and Heckerman (2003) present a linear programming model created for MSN to optimize revenues from ad sales given the constraint of a fixedquota of space to sell. They use a two stage approach, first implementing a pilot to collect data and refine model parameters and then optimizing scheduling and placement of ads with the objective of maximizing total clicks. The focus of their study remains on banner ads. While some targeting isinvolved in scheduling ads to specific subject areas of the MSN website, the underlying model does not naturally lend itself to search-based advertising with its large and growing number of possible keywords.

Menon and Amiri(2004) likewiseespouse the publisher website’s view and consider how to best schedule the placement of banner ads given a finite amount of space. They interpret this problem as a variant of the bin-packing problem and compare Lagrangian decomposition to a column generation procedure. Once again, the approach is intriguing, but not as applicable to our research question. Additionally, while ads that generate a greater number of clicks for advertisers also increase revenues for the search engines and other websites that sell the space, it should be cautioned that the best solution for a search engine is not necessarily the one that most benefits the advertiser.

Only recently (2006) do we find published researchdedicated to search-based advertising and the aspects of it, such as real time auctions for keywords, which differentiates it from other forms of internet advertising. The following papers all address the specific question of optimizing the value obtained from keyword ads given the constraints of a fixed daily advertising budget. Rusmeivichientong and Williamson (2006) consider selecting from a palette of keywords by using an adaptive approximation algorithm that prioritizes keywords by sorting them based on their profit-to-cost ratio. Selecting from a palette of keywords can be considered analogous to deciding which of the levers of a multi-armed slot machine to pull where the gambler has no initial knowledge about the reward of different levers. One traditional heuristic is to use a greedy algorithm to select the lever with the best payoff from the subset of observed levers (1-)% and to engage in exploration the remaining  % of the trials.Rusmeivichientong and Williamson use simulations to show their algorithm performs better thantypical multi-armed bandit approaches.

Muthukrishnan, Pal and Svitkina (2006) specifically address both the auction nature of keyword bidding and the rampant uncertainties associated with the response functions for keywords. Theypostulate that asearch engine selling keywords can predict probability distributions associated with these keywords and thenattempt to solve the advertiser’s allocation problem through the application of stochastic models. We will utilize some of the assumptions they make, such as lack of interaction between keywords.

The auction method used by Google andmost other search engines to sell keywords to advertisers is also coming to the attention of researchers. This mechanism is the generalized second price auction (GSP), where advertisers do not pay their bid price but that of their competitor one slot below. Edelman, Ostrovsky, and Schwartz (2006) and Cary et al (2007) attempt to determine optimalbidding strategies from a game theoretic standpoint. Generalized second price auctions are non-truthful, and it may behoovebidders not to reveal their valuations ofkeyword ad placements. Zhao and Lukose (2006) show such behavior has been observed in practice, including vindictive bidding. This gaming element of optimizing keyword strategies is beyond the scope of our research effort.

Although both Rusmeivichientong and Williamson (2006) and Muthukrishnan, Pal and Svitkina (2006) present complex solution techniques, Feldman et al (2006) propose an alternative approach to keyword selection and bidding that is likely to be more practical to apply. Theyintroduce the concept of click price curves, where clicks increase as the Cost-per-Click increases. They also show that a simple randomized hybrid of two uniform bid strategies works well and comes close to reaching the theoretical maximum possible clicks. As several of these authors are employed by Google, they have access to auction data to empirically test their strategies.

The arena of search-based advertising is so new that solution approaches, let alone vocabulary terms, have not yet been standardized. In the next few years there will doubtless be a plethora papers on keyword ads offering an even greater variety of models and methodologies. This paper will present one such approach.

An Overview of Keyword Advertising

Keyword advertisingis not implemented identically across all search engines. We primarily consider Google, the dominant player with over a 50% share of the keyword advertisingmarket by several metrics (Karbasfrooshan, 2007). We note that other sites such as Yahoo!, MSN, Ask, and AOL may differ, but we believe that the differences are sufficiently minor so that our research can be generalized to all search engines.

Given a keyword that is bid on by multiple advertisers, asearch engineholds an instantaneous, automated auction to determinewhich of the advertisers currently bidding on thatkeyword are allocated advertising slots.Depending on the strength of the advertiser’s bid relative to other bids for the same keyword, the search engine assigns the advertiser’s ad a position which is continually updated throughout the day, subject to new or revised bids by advertisers.Larger bids result in better placement than smaller ones, although the advertiser usually cannot directly specify the exact ad position. Ads placed higher on the page are more desirable than lower placements. In fact, exact positioning is not known in advance andchanges dynamically as competitors bid for keywords. Indeed, Google’s reports provided to itsadvertisers denote ad position as a non-integer average value (Google, 2007). This average value is calculated over a user-specified report duration and can be as frequently as daily.

When a user of the search engine types the keyword that the advertiser has bid on, the advertiser’s ad is displayed, resulting in an impression at the position the search engine has predetermined. If the user clicks on the ad, the advertiser is charged a fee based on the bid price. While not all clicks may result in sales, the advertiser expects that a portion of the users who click through the displayed adwill make a purchase of the advertised product(s) or that the advertiser will otherwise benefits from the user’s click. Thus the advertiser wishes to maximize this benefit while not spending beyond the budget. Figure 1 illustrates this flow.

Figure 1: Influences on Revenue and Spending for Keyword Searches

While Yahoo’s positioning is based solely on bid price, Google analyzes the traffic for all advertisers competing for the same keyword and gives higher positions to the ads that generate more clicks over those who offer a similar bid price but that generate fewer clicks. In addition to placing ads that have greater draw in a more convenient space for the user, this preferential treatment towards more popular ads has the effect of maximizing Google’s revenues. Our model assumes the advertiser has constructed the ad to be as appealing as possible, so relevance is taken as exogenous to the advertiser’s decision process in this model.

In determining the best strategy for an advertiser, two key factors must be considered: the bid price and the rate at which a search engine user is likely to click on the published ad. The bid price is commonly referred to as the Cost-per-Click (CPC).While in reality for generalized second price auctions actual CPC is less than the bid price, we assume that this difference is negligible and will use these terms interchangeably. Bid prices must be positive and are set by most search enginesto be at least $.05 per click. In this model we focus on bids that are sufficiently large to lead to placement on the first page of the search engine’s results, typically positions 1 to 10, with 1 being the highest.

The rate at which a search engine user is likely to click on the published ad is called as the click-through rate (CTR). Because bid price determines ad placement, CTR is a function of bid price and is assumed to be continually differentiable over the region of interest. There are actually two dynamics in play here;first bid price determinesad position, and then ad positiondetermines click-through rate.Both of these effects are combined into a single monotonically increasing function in our model. Feldman et al(2006) confirm that better positioningyields better CTR rates.

Given these two factors, we define the revenue generated from a keyword and the expenditure on that keywordusing the following multiplicative models:

Revenue = Impressions * CTR * Revenue-per-Click

Spending = Impressions * CTR * Cost-per-Click

Impressions denote how often the ad is displayed and depend on the popularity of the product that the keyword references. Revenue-per-Click accounts for widely diverse values that keywords may generateand is function of the underlying profitability of the product being searched or the likelihood of a user’s click converting into a sale or other value-added action for the advertiser. Impressions and Revenue-per-Click are both assumed to be exogenously determined in our research.

Formal Model: Two Keywords

Suppose that we consider an advertiser with a fixed budget who would like to decide how much to bid on two separate keywords. Then the problem can be defined as follows:

Maximize Revenue = m1 r1f(x) + m2 r2g(y)

subject to

m1 x f(x) + m2 y g(y)≤ B

x , y ≥ 0

where the decision variables are

x : bid price for keyword 1

y : bid price for keyword 2

with

f(x):CTR for keyword 1 given x

g(y):CTR for keyword 2 given y

r1: revenue-per-click for keyword 1

r2: revenue-per-click for keyword 2

m1: number of impressions for keyword 1

m2: number of impressions for keyword 2

B:total advertising budget