Allocating Budget Across Portals In Search Engine Advertising

Abstract: As increasingly popular of search engine advertising which displays advertisements alongside the search results in response to user queries, advertisers can issue ads campaigns across different search engines simultaneously for better return of investment and overall clicks. Advertisers typically have a limited budget that should not be overspent, therefore advertisers must decide how to allocate budget across portals by selecting which portal to use and how much expenditure to allocate for each portal in order to gain maximal return of investment. In this paper, we present a model that can be used for this purpose by using profile of search engine in terms of search volume, advertising efforts, conversion rate and average revenue per action of portals. By examining the necessary conditions of optimal solution and conducting elastic analysis we propose budget allocation principles should be followed by advertisers for their ultimate goal. Furthermore we also analysis the situation when response function of advertising efforts is S-shape, we show that, advertisers should concentrate on one portal when budget is small.

Keywords: keyword advertising, search engine advertising, budget allocation, keyword auction, sponsored search

1 Introduction

Internet search engines are indispensable tools for interacting on the web, they not only provide information requested, but also are navigational tools that take users to specific websites. Search engine advertising is a brand new type of business model adopted by internet search engine companies such as Google and Yahoo. It has become a major source of revenue for these companies. Compared with traditional advertisement, search engine advertising is highly targeted and efficiency. Online retailing has been booming since the emergence of this special keyword advertisement. In this regard, search engine advertising is one of the most successful business models both in internet advertising and search engine business. It is an essential tool vital to the success of many businesses. Without it, the search engines as well as the webs would be far different than they are today. The global search engine advertising market is predicted to have a 37 percent compound annual growth rate, to

Supported by the National Natural Science Foundation of China (70601009)

more than $33 billion in 2010, there is not surprising more and more firms start to set up ads campaign on search engine. The basic setup is as follows: when a user poses a query at a search engine, he receives a page of results containing links generated by algorithm of the search engine, together with sponsored links, i.e., advertisements that are placed into positions usually arranged linearly down the page from top to bottom. Most major search engines determine the assignment of ads to positions by running an auction among all advertisers who placed a keyword that matches the query. Advertisers pay nothing to appear on the results page; they only pay the amount they have agreed to (or bid for) when someone actually clicks on their ad and is taken to the landing page on their websites. Generally, ads that appear in a higher position on the page receive more attention and clicks from users than lower ones. Jansen[1] has more detail and basic elements of search engine adverting.

At present, many search engines are running and providing services. The most popular search engine is Google; its advertising program is called AdWords. The next most popular search engines are Yahoo!, MSN Live, Baidu and Ask. A large number of other search engines offering search engine advertising opportunities are available---ranging from Meta search engines that incorporate traffic from numerous other engines and online sources all the way to small, niche search engines that specialize in one or more categories or topics of interest. Though top search engines are the most popular and produce most of the search volume, small search engines are appealing to advertisers. Because popular search engines have quite a bit of competition which brings the bid price higher than their small counterparts. In general, different search engine has different type of user group, e.g., Baidu is the most popular search engine in China and Google is definitely the top one in United States, thus their advertising effort and efficiency are different. Hence, in order to attract as many customers as they can, many advertisers launch advertising campaigns across different search engine portals. The evidence is apparent, type “notebook” in Google and Yahoo!, we can find that HP’s sponsored link appears on both Google and Yahoo. Despite the success of search engine advertising, it is still brand new fields to people include users, advertisers and scholars, especially advertisers. They are still learning how to make use of these opportunities and how to allocate resource so as to achieve the best return of investment.

Our research is standing on the side of advertisers with the purpose to maximize value that a company receives from launching advertisement campaigns across search engine portals with constraint of limited budget. The core issues here are: how to make the decision of how much budget should be allocated to a portal; what are the deterministic factors? How to judge whether a portal is much more profitable than another one? As the best to our knowledge, this is the first piece of work with respect to the above problem. The rest of the paper is organized as follows: Section 2 discuss related work about search engine advertising. Section 3 models and solves the optimal problem of two portals case. Section 4 describes the properties of S-curve response function. Section 5 generalizes the model to multiple portals. Finally, we conclude the effort and discuss further research possibilities in section 6.

2 Related works

With the rapid development and adoption of search based advertisement, academic publications about search engine advertising which also often referred to sponsored search, keyword auction, position auction, search-based ads and search engine marketing are booming. Typically, most of the published works can be labeled into three categories: First one also the most popular spot of sponsored search are standing from the point of view of search engines (auctioneer) with the goal of maximizing revenue of search engines. The most attractive problem considered here is how to allocate advertisers to queries such that certain constraints are satisfied and efficiency is maximized. Zoe[2] proposes an approach based on linear programming formulation which incorporate bidder budgets constraint to optimize ad delivery. Several similar papers considered the effect of budgeted advertisers are in [3-5]. Most of the researches of this filed are done by researcher working in search engine companies. The second researching community is about economic study, they take the angle of game theory to analysis search engine advertising, treat it as an auction and comparing it with traditional auction mechanism. They investigate incentive compatible properties and Nash equilibriums of existing advertising auction systems [6-11] . Through their studies, we can gain better understanding of the role and strategies of search engine providers, users and advertiser. The last academic category of search advertising is standing on the side of advertisers. They propose optimal bidding strategies and resources allocation methods in order to maximize revenue of advertisers [12-17] . Compared with traditional bidding strategies for normalized auction, bidding policies for search advertising are more complicated by involving uncertain internet users, multi keywords, multi search engines, huge competitors and the difficulty of information tracing. Though this research is vital for advertisers, there are few existing works about it. Our work belongs to the third label.

Since our research inherently has strong relation with advertising, it would be helpful to learn from researches about advertising including traditional ads and online ads. Vidale and Wolfe[18] are the first researchers that formulized the problem of how to optimal allocate resources given a limited budget. Response function was first introduced into this area which is widely used later about research of advertising which measured the effect of advertising budget, it has been proved both by theoretical and empirical. Thus, we will use the concept of response function with respect to advertising efforts in our work. Furthermore, many researchers in advertising field believe that response function is concave and monotonically increasing of advertising budget according to Zoltners and Sinha[19] . Typically, response function is used to measure how much goodwill or sales share gained by allocated budget, however, it’s to indicate the ability of converting potential clicks into real clicks in our context. Thus money spent on search engines is the input of response function and advertising effort is the output.

Mangani[20] and Susan[13] are the pioneers who studied issues of internet advertising, they both used the concept of elasticity of access and show that optimal budget allocation fall back on the relations among the elasticity. Our approach is akin to theirs; however, we are on different arenas, we focus on search-based advertisment. Mangani studied the area of banner ads which is predate than search ads. Susan’s work is much closer with ours than Mangani, we all play games on search engine advertising; however, Susan concentrated on allocating expenditures across keywords within a single search engine. Our research stands on a much higher level than Susan’s by taking the average performance of search engine into account rather than single keyword. Both Susan and our results are useful for advertisers. In particular, advertisers can use our work first to determine how much budget should be allocated to a portal and then use Susan’s result to determine how to allocate expenditures across keywords within that portal. Nagurney and Zhao[21] employed the network modeling approach to study the problem of allocating ad expenditures across several websites. By using their model, they were able to quantitatively explain puzzles of why has the click through rate declined even internet users increased and is advertising on more websites really better? They give some criterions on when to use new website for advertising. Compared with their work, we rather focus on search engine advertising than general internet advertising, hence, our work is much more specific.

Search engine advertising is such a rapidly growing arena that academic research is far behind real world business. This situation results in great loss of companies which are participating in the campaigns with little or no knowledge about it. This paper is on the effort to contribute the overall knowledge of search engine advertising and provide decision support for companies that want to advertise across several search engine portals.

3 Two portals model

In this section, we present the two portals model which is much more convenient to analysis, however, without lost of generality. Nowadays, major search engines all implement resemble quality score system like Google to decide position and cost of an advertisement. Actually, quality score not only influence keywords’ rank and actual cost per clicks, but also used to estimating the first page bids, it’s vital for success in search engine advertising, the higher the quality score is, the lower costs and the better ad position it will be. The exact formula of quality score is unknown due to business secret, however, the core components are: historical click through rate, quality of landing page, relevance of the keyword to ads, relevance of keyword to the search query. Search engines believe quality score can significantly improve user experience as well as their revenue. Though quality score is critical to search based ads, we won’t make any further discuss of it in our paper, it belongs to other topic. We assume advertisers have done enough work that makes their quality score as high as possible, therefore, quality score is treated as exogenous variable to the decision process in our model.

Before formulizing our model, several essential parameters must be discussed in advance for a better understanding of it. They are search volume, targeted search queries, advertising effort, average conversion rate and average profit per purchase. Search volume is used to measure popularity of search engines, the larger the search volume a search engine is, the much more welcomed it is. Targeted search queries is the part of search volume matched advertisers’ keyword list within a search engine, it’s the relevance between search engine and advertisement. Advertising effort is a function of budget that can turn potential clicks into real clicks; different search engines have different advertising effort even with the same budget, as mentioned above, we use the concept of response function to present advertising effort, it’s reasonable to assume that response function is concave and monotonically increasing with advertising budget [13, 22] which captures the diminishing return of advertising expenditures. Average conversion rate measures efficiency of a search engine in our context, high conversion rate often leading to high revenue. Typically, conversion rate is the percentage of visitors who take conversion action like making an online purchase or submitting a form to request additional information. It can be calculated by actual data provided by search engines. Average profit per purchase is private information of advertisers thus it can be easily computed. Given the above parameters, we define the revenue generated from a search engine with a fixed budget is:

Revenue=Search volume× Targeted search queries

$\times$ Advertising effort $\times$ Average conversion rate $\times$ Profit per purchase –budget.

3.1 Model formulation

For simplicity and without loss of generality, we consider the scenario of an advertiser which is involving ads campaign across two search engines with a fixed budget. Then his problem is to decide how much budget should be allocated to each search engine so as to maximize revenue. The optimal question can be formulated as follows:

Let G and M represent the separate search engine, $n_G$ and $n_M$ be the search volume of G and M respectively. $n_G$ and $n_M$ can be measured in real time by using a combination of sophisticated traffic monitoring software tools such as WebTrends. Let $h_G$ and $h_M$ denotes the targeted search volume of G and M, then we have

Maximize:

$(n_G h_G f_G(x) r_G + n_M h_M f_M(y) r_M) \times p$ (1) ubject to

$n_{G}h_{G}f_{G}(x)c_{G}(x) + n_{M}h_{M}f_{M}(y)c_{M}(y) \le B$ (2)

x \ge 0, \quad y \ge 0 \tag{3}

Where $f_G(x)$ and $f_M(y)$ denote advertising effort of G and M with allocated budget x and y. $c_G(x)$ and $c_M(y)$ are functions of average cost-per-click respecting to the given budget, they have the similar concave curve as advertising effort function. $r_G$ and $r_M$ are conversion rate of G and M, notice that conversion rate is independent of budget here, however, in real world practice it is much more complicated and it might have relationship with budget. Here it is used to indicate that conversion rate varies from search engines due to different profile and user group of search engines. p is profit of per conversion action. B denotes a fixed budget that advertiser would like to spend. Both f and c are concave and monotonically increasing functions of advertising budget and twice differentially.

3.2 Necessary conditions of maximization

The above optimization is a typical nonlinear maximal problem subject to inequality constraints and nonnegative values of variables [23]. The inequality constraints can be converted to equality constraints by adding Lagrange multipliers $\lambda$ . Thus, the Lagrangian function for the original problem (1) is:

$L = (n_G h_G f_G(x) r_G + n_M h_M f_M(y) r_M) \times p + \lambda (B - n_G h_G f_G(x) c_G(x) - n_M h_M f_M(y) c_M(y)$ (4)

that is, the objective function plus the inner product of the Lagrange multipliers and the difference between fixed budget and the cost functions.

The Kuhn-Tucker conditions are:

$\frac{\partial L}{\partial x} = n_G h_G f_G p \frac{df_G(x)}{dx} - \lambda n_G h_G \left( \frac{df_G(x)}{dx} c_G(x) + \frac{dc_G(x)}{dx} f_G(x) \le 0 \right)$

$\frac{\partial L}{\partial y} = n_M h_M r_M p \frac{df_M(y)}{dy} - \lambda n_M h_M \left( \frac{df_M(y)}{dy} c_M(y) + \frac{dc_M(y)}{dy} f_M(y) \le 0 \right)$

$\frac{\partial L}{\partial x} x + \frac{\partial L}{\partial y} y = 0$

$B - n_G h_G f_G(x) c_G(x) - n_M h_M f_M(y) c_M(y) \ge 0$ (8)

$\lambda (B - n_G h_G f_G(x) c_G(x) - n_M h_M f_M(y) c_M(y)) = 0 \quad (9)$

$x \ge$ , $y \ge 0$ , $\lambda \ge 0$ (10)

These conditions are necessary and sufficient for the optimization of our problem since our objective function is concave and constraint function is convex, however, the optimal problem can’t be explicit solved due to the unknown exact function form of f and c. Fortunately, we are able to explore deeply enough to explain how to allocate budget between search engines with these conditions. For advertisers, they can use historical data to conjecture the formula of f and c, notice that, the formula might be different for different advertisers.

3.3 Exploration and explanation

In this part, we propose some suggestions that are useful for advertisers by exploring the conditions mentioned above.

Theorem 3.1 The advertiser should spend the whole budget for optimization on the condition that f is a concave and monotonically increasing function of advertising budget and twice differentially.

Proof. It can be easily proved in a counterevidence way. Assume that budget is under spent, then (8) should be greater than zero. According to (9) we have $\lambda = 0$ , then in order to satisfy (5) and (6) following formulas must be satisfied:

$n_G h_G r_G p \frac{df_G(x)}{dx} \le 0$ and $n_M h_M r_M p \frac{df_M(y)}{dy} \le 0$ ,

since $n_G h_G r_G p$ and $n_M h_M r_M p$ are positive, thus $\frac{df_G(x)}{dx} \le 0$ and $\frac{df_M(y)}{dy} \le 0$ holds. Recalling that f is a concave and monotonically increasing function, then $\frac{df_G(x)}{dx} > 0$ and $\frac{df_M(y)}{dy} > 0$ , it conflicts with the result

derived from budget is under spent.

There is an exception here, if the goal of advertiser is to maximize profit and cost per click is greater than revenue per click, the budget should not be exhausted in the optimal solution. Advertisers should carefully select keywords that are not too competitive but still popular so as to make sure cost per click is lower than revenue per click. We assume our advertisers are enough sophisticate to insure that. However, with overall clicks as the ultimate optimization given a fixed budget, the exception is free

Theorem 3.2 (5) and (6) must equal zero for the optimal solution.

Proof. Suppose (5) and (6) doesn’t equal zero, then they must be lower than zero. Since (7) and (10) holds, if x > 0 then y > 0 and $\frac{\partial L}{\partial y} > 0$ must be satisfied which

conflicts with (6); if x = 0, then y = 0 must holds for (7) in respect that $\frac{\partial L}{\partial y} < 0$ , in this case, advertiser spend no

budget on both search engines which means he quit the ads campaigns. It violates our assumption too. Therefore

theorem 3.2 holds.

Rewrite (5) and (6) with respect to theorem 3.2 yields:

$r_{G} p f_{G}'(x) = \lambda (f_{G}'(x) c_{G}(x) + f_{G}(x) c_{G}'(x))$ (11)

$r_{M} p f_{M}'(y) = \lambda (f_{M}'(y) c_{M}(y) + f_{M}(y) c_{M}'(y))$ (12)
Then we have,

$\lambda = \frac{r_{G} p f_{G}'(x)}{(f_{G}'(x) c_{G}(x) + f_{G}(x) c_{G}'(x))}$

$= \frac{r_{M} p f_{M}'(y)}{(f_{M}'(y) c_{M}(y) + f_{M}(y) c_{M}'(y))}$ (13)

(13) Indicates that for the optimal budget allocation to each portal, equal ratio of marginal revenue over marginal cost among them must be held. Because $r_G p f_G'(x)$ is the marginal revenue of G, $f_G'(x) c_G(x) + f_G(x) c_G'(x)$ is the marginal cost. Notice that, marginal cost includes two parts: cost of additional clicks received which is $f_G'(x) c_G(x)$ and cost of additional expense per click which is $f_G(x) c_G'(x)$ with regard to additional budget. Portal M has the same situation. It’s derived from the equal marginal utility principle of economic theory.

Sensitivity and elasticity analysis is another important tool in economic theory which can be used for further analysis in our work. Typically, it’s the ratio of percent change in one variable to the percent change in another variable. It can help us to understand the dynamic response of budget and advertising effort. The elasticity of the advertising effort function could be defined as the change in the advertising effort with respect to the change in the budget.

$E_{f_G x}(G) = \frac{df_G(x)}{f_G x} / \frac{dx}{x}$ (14)

Similar we have elasticity of cost function,

$E_{c_G x}(G) = \frac{dc_G(x)}{c_G x} / \frac{dx}{x}$ (15)

Let (14) over (15), we get the elasticity of advertising effort in terms of cost function, this elasticity measures efficiency of search engines.

$E_{f_G c}(G) = \frac{df_G(x)}{f_G x} / \frac{dc_G(x)}{c_G(x)}$ (16)

$E_{f_M c}(M) = \frac{df_M(y)}{f_M y} / \frac{dc_M(y)}{c_M(y)}$ (17)

Rewriting equation (13) with regard to (16) and (17) yields the following:

$\frac{c_G(x)}{r_G}(1 + \frac{1}{E_{f_Gc(G)}}) = \frac{c_M(y)}{r_M}(1 + \frac{1}{E_{f_Mc}(M)})$ (18)

Equation (18) shows the principle of allocating budget between search engines at maximal point. From our analytical results, we can obtain a measure of the advertising budget allocation preference through examining the ratio of cost per click and conversion rate as well as elasticity. We conclude with the following proposition.

Propositions:

• (1) Advertiser should increase (decrease) the ratio of budget allocation to the portal whose conversion rate is higher (lower) than another portal.
• (2) If competition pressure of a portal is much fiercer than other one, that’s average cost per click increases fast as budget increasing in that portal, then advertiser should shift more budget to the portal with lower competition pressure.
• (3) If the efficiency at a particular budget for a portal increases (low cost with great advertising effort) then the ratio of budget for the portal should increases too, vice versa.

Notice that, how much budget should be allocated to a portal has no relationship with gross budget and its search volume. Intuitively, portal with larger search volume should receive more budgets; however, if that portal is extremely competitive then advertiser would exhaust his budget soon with small amount of clicks. Thus, in the case that advertiser allocate budget with their intuition without carefully calculating cost, conversion rate and portal efficiency, he will never success in search ads campaigns.

4 S-shape advertising effort

Though many researchers believe advertising effort is a concave function [13, 22], there still are some scholars consider that S-shape advertising effort would be more

realistic [24, 25]. With S-shape response function, advertising effort is convexity in the low budget range and concave in the high range. The analysis of section 3 is based on the assumption that advertiser have enough budget that advertising effort is locating on the concave portion of S-shape curve. However, for small businesses with little budget and their advertising effort fell into the convexity part, the above result is improper, then we should further examine properties of S-curve response function for optimal budget allocation with small amount of budget.

For simplicity and without loss of generality, we also use two portals scenarios for S-shape analysis. We use the same notations as section 3. Since $f_G(x)$ is S-shape, then there must exist a point $x^i$ i.e. inflection point such that $0 \le x \le x^i$ , $f_G^{"}(x) > 0$ for $x^i < x$ , $f_G^{"}(x) < 0$ and $f_G^{"}(x) = 0$ at $x = x^i$ . Let $x^*$ be the point where marginal advertising effort equals average advertising effort, that is $f_G^{"}(x^*) = f_G(x^*)/x^*$ .

Theorem 4.1 If gross budget is smaller than inflection points of G and M and $f_G(x)$ is strictly greater than $f_M(y)$ within the convex part, then advertiser should allocate the whole budget on portal G.

Proof. If advertiser allocates the whole budget B on portal G, then he receives $f_G(B)$ advertising effort. If advertiser splits B into two parts, e.g. b for G and B-b for M, then he receives $f_G(b) + f_M(B-b)$ advertising effort. Since $f_G(x)$ is strictly greater than $f_M(y)$ , then we have $f_G(b) + f_M(B-b) < f_G(b) + f_G(B-b)$ .

If -b < b < B , according to mean value theorem, we have

$f_G(B) - f_G(b) = f_G^{"}(\varepsilon)(B - b)$ $f_G(B - b) - f_G(0) = f_G^{"}(\theta)(B - b)$

where $b < \varepsilon < B$ and $0 < \theta < B - b$ since $f_G(x)$ is convex and its first order function is monotony increasing, then we have $f_G^{"}(\varepsilon) > f_G^{"}(\theta)$ thus we have $f_G(B) - f_G(b) > f_G^{"}(B - b) - f_G(0)$ . Note that $f_G(0) = 0$ , then we get $f_G(B) > f_G(b) + f_G(B - b)$ . If b < B - b < B, it can be proved by the similar way that $f_G(B) > f_G(b) + f_G(B - b)$ . That is allocate all budget to G generates better advertising effort than split the budget into two portals.

S-curve response function has been well studied in^[24], the optimal solution can be characterized by the point where marginal response equals average response. S-shape response function is much more complicated than concave functions. Due to the length restriction of paper and our limited knowledge of S-shape function, we

won’t make further discussion. We strongly recommend papers [24, 26] as detail references.

5 Multiple portals model

The results of section 3 can be easily extended to multiple portals. Using the same notations as section 3 except the subscript, we use $i=\{1,2,\cdots,N\}$ to index portals, i.e. $f_i(x_i)$ is the advertising effort of portal i with allocated budget $x_i$ . Then, the multiple portals model is

Maximize:

\sum_{i=1}^{N} (n_i h_i f_i(x_i) r_i \times p \tag{19}

Subject to

$\sum_{i=1}^{N} (n_i h_i f_i(x_i) c_i(x_i)) \le B$ (20)

x_i \ge 0 \tag{21}

Conducting the same analysis of section 3, the necessary conditions of optimal solution can be easily educed, thus we get

$\lambda = \frac{r_i p f_i'(x_i)}{(f_i'(x_i)c_i(x_i) + f_i(x_i)c_i'(x_i))}$ (22)

Using the concept of efficiency of portal as section 3, we have similar results like (18), i.e. given two portal (i,j) following formula holds.

$\frac{c_i(x_i)}{r_i} \left(1 + \frac{1}{E_{f_i c}(i)}\right) = \frac{c_j(x_j)}{r_j} \left(1 + \frac{1}{E_{f_j c}(j)}\right)$ (23)

Advertisers can use this technique to decide how to allocate budget across multiple portals, however, in practice it would be costly to monitor and calculate all the parameters if N is large. The tradeoff of additional cost and profit gained by advertising on a new portal should be paid attention to. Theoretically speaking, adding a new portal always produces no less revenue than the former one. It can easily prove by allocating zero budgets to the new one which generate the same revenue as without new portal.

In practice, different search engine often have apparent discrepancies of Search volume and conversion rate. Using the concept of long tail theory, we would be able to divide search engines into “head tail” and “long tail”. Advertisers should carefully deal with “head tail” search engines as well as “long tail” ones. Generally speaking, gigantic search engines of “head tail” like Google may contribute major traffic to advertisers. “Long tail” search engines which bring in significantly less traffic, but they tend to bring in more targeted and higher converting visitors. “Long tail” search engines are

usually more specific than “Head tail” search engines, e.g. vertical search market. In our model, “head tail” and “long tail” search engines might be distinguished by their conversion rate and adverting effort. Theoretically, advertisers might favor “long tail” search engines and invest a larger portion of its budget in them. It can be induced from (23) easily since conversion rate of “long tail” search engines are higher than “head tail”, thus more budget should be placed in order to make the ratios equal.

6 Conclusions and further research

In this paper, using nonlinear programming modeling approach, we have developed an optimal decision model of how to allocate budget across portals in search engine advertising. We pinpointed factors such as the search volume, average click through rate, targeted search queries, average conversion rate and revenue per action. We used the concept of advertising effort to capture average click through rate of search engines.

We show and prove that under the concave response function of adverting effort assumption, the gross budget should be exhausted in optimal solution. Though we can’t solve the problem in an explicit way, we present enough exploration and explanation of budget allocating principle that can be used in practice. Typically, budget should be shifted to portals with higher conversion rate, less competitive and higher efficiency. We define efficiency of search engine by using the concept of sensitive and elasticity. Furthermore, the S-shape response function is included and optimal policy with small budget is presented, we proved that for small business dedicates into single portal is better off than splitting budget into multi portals. Finally, multiple portals model is addressed as well as the impact of “head tail” and “long tail” search engines.

Since search engine advertising is a new and challengeable field, there are several issues that should be explored for further studies. First, our model doesn’t incorporate time factor, budget allocation over time should be an interesting research subject. Second, we assume advertisers place same ads across portals, but in real world, many advertisers play different games of different portal. It would be more difficulty and interesting to solve problem like this. Third, the model can be expanded to include the interactions among portals which are more realistic, that is search engines are not independent. Fourth, we didn’t consider the cost of monitor advertising data which could be vital in practice. Another interesting topic is how to improve quality score of search ads which is considered as exogenous variable in this work; however, incorporating quality score into optimal model is necessary. Therefore, we are looking forward to further explore these interesting and promising fields.

References

• [1] Jansen, B.J, T. Mullen. Sponsored search: An overview of the concept, history, and technology[J]. International Journal of Electronic Business, 2008,6(2): 114-131.

• [2] Zoe, A.O. Optimal delivery of sponsored search advertisements subject to budget constraints[C]// Proceedings of the 8th ACM conference, California, USA: ACM Press, 2007.

• [3] Mehta, A., et al. AdWords and generalized online matching[J]. Journal of the ACM, 2007,54(5):1-19.

• [4] Mahdian, M., H. Nazerzadeh, S. Amin. Allocating online advertisement space with unreliable estimates[C]// Proceedings of the 8th ACM conference, California USA: ACM Press, 2007.

• [5] Abrams, Z., Revenue maximization when bidders have budgets[C]//Proceeding Symposium on Discrete Algorithms, 2006:1074-1082.

• [6] Edelman, B., M. Ostrovsky, M. Schwarz, Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords[J]. American Economic Review, 2007(97): 242-259.

• [7] Varian, H.R., Position auctions[J]. International Journal of Industrial Organization, 2007,25(6): 1163- 1178.

• [8] Zhou, Y, R. Lukose. Vindictive bidding in keyword auctions[C]//Second Work-shop on Sponsored Search Auctions, Ann Arbor, Michigan, 2006.

• [9] Bu, T., X. Deng, Q. Qi. Forward looking Nash equilibrium for keyword auction[J]. Information Processing Letters, 2008,105(2): 41-46.

• [10] Edelman, B, M. Ostrovsky, Strategic bidder behavior in sponsored search auctions[J]. Decision Support Systems, 2007, 43(1):192-198.

• [11] Vorobeychik, Y, D.M. Reeves. Equilibrium analysis of dynamic bidding in sponsored search auctions[J]. International Journal of Electronic Business, 2008,6(2): 172-193.

• [12] Zhou, Y, V. Naroditskiy. Algorithm for stochastic multiple-choice knapsack problem and application to keywords bidding[C]//17th International Conference on World Wide Web 2008, WWW’08, New York, NY 10036-5701, United States: Association for Computing Machinery, 2008:21-25.

• [13] O¨zgu¨r O¨ Zlu¨k, S.C. Allocating expenditures across keywords in search advertising[J]. Journal of Revenue and Pricing Management, 2007,6(4): 347-356.

• [14] Christian, B.J. Dynamics of bid optimization in online advertisement auctions[C]//Proceedings of the 16th international conference, Alberta, Canada: ACM Press, 2007.

• [15] Cary, M., et al. Greedy bidding strategies for keyword auctions[C]//Proceedings of the 8th ACM conference, California, USA: ACM Press, 2007.

• [16] Rusmevichientong, P. and P.W. David. An adaptive algorithm for selecting profitable keywords for searchbased advertising services[C]//Proceedings of the 7th ACM conference, Michigan, USA: ACM Press, 2006.

• [17] Kitts, B, B. Leblanc. Optimal bidding on keyword auctions[J]. Electronic Marktes, 2004,14(3):186-201.

• [18] Vidale, M.L, H.B. Wolfe. An operations research study of sales response to advertising[J]. Operations Research, 1957,5(3):370-381.

• [19] Zoltner, A, P. Sinha. Integer programing models for sales resource allocatoin[J]. Management Science, 1980, 26(3): 242-260.

• [20] Mangani, A. Online adverting: Pay-per-view versus pay-per-click[J]. Journal of Revenue and Pricing Management, 2004, 2(4): 295-302.

• [21] Zhao, L, A. Nagurney. A network modeling approach for the optimizaiton of internet-based advertising strategies and pricing with a quantitative explanation of two paradox[J]. Netnomics, 2005,7(2):97- 114.

• [22] G. E. Fruchter, W.D. Optimal budget allocation over time for keyword ads in Web portals[J]. Journal of optimization theory and applications, 2005,124(1): 157- 174.

• [23] Intriligator, M.D. Mathematical optimization and economic theory, Philadelphia: SIAM, 2002.

• [24] Ambar G. RAO, M.R.R. Optimal budget allocation when response is S-Shaped[J]. Operations Research Letters, 1983, 2(5):225-230.

• [25] Feinberg, F.M. On Continuous-time optimal advertising under S-shaped response[J]. Management Science, 2001, 47(11):1476-1487.

• [26] Rothkopf, M.H. Bidding in simultaneous auctions with a constraint on exposure[J]. Operations Research, 1977, 25(4): 620-629.