Mathematical Modeling Of Competition In Sponsored Search Market

Abstract

Sponsored search mechanisms have drawn much attention from both academic community and industry in recent years since the seminal papers of [13] and [14]. However, most of the existing literature concentrates on the mechanism design and analysis within the scope of only one search engine in the market. In this paper we propose a mathematical framework for modeling the interaction of publishers, advertisers and end users in a competitive market. We first consider the monopoly market model and provide optimal solutions for both ex ante and ex post cases, which represents the long-term and short-term revenues of search engines respectively. We then analyze the strategic behaviors of end users and advertisers under duopoly and prove the existence of equilibrium for both search engines to co-exist from expost perspective. To show the more general ex ante results, we carry out extensive simulations under different parameter settings. Our analysis and observation in this work can provide useful insight in regulating the sponsored search market and protecting the interests of advertisers and end users.

1 Introduction

Internet advertising has become a main source of revenue for primary search engines nowadays. According to the newly-released report by Interactive Advertising Bureau and PricewaterhouseCoopers [1], Internet advertising in the United States reached $22.7 billion in total revenue for the full year of 2009, where sponsored search revenue accounted for 47 percent of the total revenue.

A typical Internet search market consists of three parties: publishers (i.e., search engines), advertisers and end users. In the current age of information explosion, more and more people rely on search engines to pin down their favored products or services. Whenever a query is submitted to the engines by end users, their intents or interests can be potentially captured by the engines through the inputted keywords. These intents of search users can then be sold by search engines to companies who are interested in targeting their products to these users. Nowadays, major search engine operators like Google, Yahoo! and Microsoft display advertisements in the form of sponsored links, which appears alongside the algorithmic links (also known as organic links) in the search results pages. For each keyword, there are usually more than one available advertising slot in the search engine results page. How to effectively allocate these slots and charge the advertisers have been studied and discussed extensively in recent years among people in both academia and industry. Take Google’s AdWords program for example. In this advertising program, advertisers could choose multiple keywords they are interested in, and for each keyword indicate the maximal willingness to pay for each click and the budget to spend over a period of time. Whenever a user clicks on the sponsored link and is re-directed to the advertisers’ site, certain payment is charged by the program until the advertisers’ budget is used up.

Most of the existing works focus on the interaction of the three parties within the scope of only one search engine’s advertising system, and these results and suggestions from researchers did greatly improve the efficiency of mechanism held in major search engine companies. For example, the transition from generalized first price auction to generalized second price auction, from payment per impression to payment per click, from bid-based ranking to quality-based ranking and so on [2, 6]. However, considering there is usually more than one company providing search service in the market, one natural question would be how the market would evolve when there exists competition between multiple search engines. In particular, will all users and advertisers gradually concentrate to one leading engine or will the “inferior” engines still earn enough profits to survive when competing with the leading one? What would be the consequences if one search engine monopolizes the market? Should governments take anti-trust action against potential cooperation among major search engines? These concerns arise from the current situation of high levels of concentration in search engine market: Google is widely considered to possess the leading technology and obtain the largest market shares in most countries and regions, followed by Yahoo! and Microsoft Bing.

This paper aims to formulate a reasonable model to study the competition between two search engine operators and help to address some of the intriguing questions mentioned above. We will consider a three-stage dynamic game model. In stage I, the two operators’ services determine how the market of end users is split. In stage II, the two operators simultaneously determine their prices to advertisers. In stage III, the advertisers choose the operator in which they can obtain highest utility based on the announced prices in stage II. Each operator wants to maximize its revenue subject to the competition for advertisers from the other operator.

The key contributions of the paper are:

To the best of our knowledge, this paper is among the first to model the comprehensive interaction of heterogenous publishers, advertisers and users in a competitive environment. We elaborate the whole process of search engine competition in attracting both users and advertisers. The technical details applied in practical advertising systems, such as the values and budgets of advertisers, are taken into consideration explicitly in our formulation.
We prove the existence of Nash Equilibrium prices when allowing advertisers participate in both advertising systems simultaneously. Moreover, we show the comparative results between the equilibrium prices and monopoly price when only one search engine exists in the market.
We propose two distinct points of view, i.e., the ex ante view and the ex post view, to inspect the long-term and short-term revenues of search engines respectively. Furthermore, for the ex post case, we present the detailed algorithm for calculating the exact allocation results for advertisers. For the ex ante case, we can carry out the simulations to illustrate the comparative results of expected revenues and social welfare under competition and monopoly respectively.

The paper is organized as follows. Section 2 presents the related work. Section 3 formulates the monopoly model and provides solutions for both the ex ante and ex post cases. Based on the monopoly formulation, we analyze the strategic behaviors of end users and advertisers under

duopoly and find the Nash Equilibrium prices of both search engines in Section 4. In Section 5 we compare the results under competition and monopoly via simulation and reveal various factors that affect the revenues and social welfare. We conclude in Section 6 and outline some future research directions.

There are mainly two lines of research work in the sponsored search area. The mainstream of literature focuses on the interaction between advertisers and search engines and aims to understand and devise viable mechanism for the Internet advertising market. There is significant work on the auction mechanism held by major search engines, starting from two seminal works of [13] and [14] which independently investigated the “generalized second-price” (GSP) auction prevailing in major search engines such as Google and Yahoo!. In [20] the authors compared the “direct ranking” method by Overture with the “revenue ranking” method by Google and proposed a truthful mechanism named as “laddered auction”. Considering the non-strategyproofness property of GSP mechanism, [21] analyzed one prevalent strategy of advertisers called “vindictive bidding” in realworld keyword auction. [26] and [27] relaxed the basic assumption of separable click-through rate in [20] and modeled the externality effect among advertisements which appeared in the same search page simultaneously. [28] proposed a new valuation model to absorb the adverse effect of the competing advertisements on the advertiser’s value per click. There is also an abundance of works on proposing more expressive but still scalable mechanism for sponsored search such as [24, 25, 23, 29, 22. In particular, in [29] the advertisers were allowed to submit a two-dimensional bid (b, b’)where b was the bid for exclusive display and b’ for sharing slots with other advertisements. In [22] the authors proposed a truthful hybrid auctions where advertisers can make a per-impression as well as per-click bid and showed that it can generate higher revenue for search engine compared with the pure per-click scheme.

It’s worth pointing out that a few works considered the practical situation where similar keyword auctions are held simultaneously by multiple search engines. For example, in [15] the authors investigated the revenue properties of two search engines with different click-through rates which competed for the same set of advertisers. The study in [16] considered competition between two search engines which differs in their ranking rules: one applied the direct ranking method we mentioned above, and the other applied the revenue ranking method. We assert that this assumption of search engine difference is unrealistic since major engines tend to use the same policy which proves to work efficiently in practice and it is unlikely that certain engine would switch back to the obsolete rules. The Nash equilibrium solution in the former paper of [15] is also not so practical since it requires advertisers to adopt certain randomized strategy. It’s very difficult for individual advertisers to implement such complex strategies which would incur unnecessary maintenance cost.

The other line of work is developed mainly by economists to address the broad issues of search engine competition from social welfare perspective. [4] introduced a quality choice game model where end users choose the search engine with highest quality of search results, and showed that no

^1In the original paper of [16], the authors used the terms of “price-only ranking rule” and “quality-adjusted ranking rule” which has the same meaning.

^2One typical example is that, in May 2002 Google first introduced the revenue ranking approach which proved to be more efficient. And then in 2007, Yahoo! switched from prior direct ranking to revenue ranking rule similar to Google’s [2].

Nash equilibrium exists in this game. Based on this proposition, the author argues that the search engine market would evolve towards monopoly in the absence of necessary regulatory interventions. [5] proposed a duopoly model which has some similarity to our formulation, however, as many of the technical details of the practical advertising system are ignored, it is doubtful whether this can serve as an accurate model to predict the outcome of search engine market. Similarly, [4] faces the same problem that the vague description of participants’ utility may not be strong enough to support the predictive conclusions in the paper.

These two lines of important work have little intersections so far: the mainstream of work concentrates on the technical progress in designing “better” advertising system, and the other line usually involves less technical details (like the budgets of advertisers in practical advertising system) and targets the macro-effect of competitive market. In view of this, we believe that a comprehensive study of the current search engine ecosystem in a competitive way is vital for addressing many of the unresolved issues in this thriving market. Our work manages to narrow the gap between these two directions of research and makes some initial progress in this direction. This observation helps differentiate our work from most of the existing literature.

3 The Monopoly Market Model

In this section we consider the monopoly market first, which serves as a starting point for analyzing the more general competition market. Suppose there is only one search engine in the market servicing a fixed set of end users and providing advertising opportunity for a set of advertisers denoted by I (|I| = m). Assuming all users are homogeneous and each of them tends to generate the same number of impressions (or clicks) for a particular keyword (query). Since we assumes that the search engine owns a fixed number of users, it would be able to supply a fixed number of attentions (in the form of impressions or clicks) for advertisers. For a given interval, let the supply of attentions be S. Each advertiser i ∈ I has two private parameters: value vⁱ denoting i’s maximal willingness to pay for each attention and budget Bⁱ in a given time interval (could be daily, weekly, monthly budget and so on). The search engine needs to determine the optimal price per attention to maximize its revenue³ :

$R = p \cdot \min(S, D(p)) = \min(p \cdot S, pD(p))$

where D(p) is the demand function over price p.

In the following analysis we consider this revenue maximization problem in two different perspectives: the ex ante perspective where the search engine only has an rough estimation to the parameters of participating advertisers, and the ex post perspective where the engine just needs to make decision based on the submitted parameters of advertisers. Although in practice, the advertising systems do determine the prices only after advertisers have submitted their values and budgets, we assert that the ex ante view of revenue to be a natural fit for the search engine’s objective. This is because typically the interaction between search engine and advertisers is not one-shot and would usually last for many rounds. Advertisers can actually adjust their submitted parameters

³ In practice, the optimal price is usually determined automatically by an auction mechanism. Specifically, this automation process can be imagined as an ascending-bid auction [3] where the auctioneer (i.e., the search engine) iteratively raises the price until there is no excessive demand than supply. Considering strategic issues, [19] proposes an asymptotically revenue-maximizing truthful mechanism. For simplicity of analysis, we ignore the detailed implementation of auctions and assume the search engine can solve the revenue-maximizing problem instantaneously.

at any time to achieve better payoff. Thus the ex ante result could provide valuable prediction of the long-term revenue for the search engine, rather than the short-term profit from one particular instance of the ex post case.

3.1 Ex ante case

Assuming the search engine can have a rough estimation of the distribution of advertisers’ values and budgets. For simplicity, we only consider the scenario when the parameters are independent and identically-distributed random variables. To be specific, suppose values are drawn independently from distribution with density function f(v) and CDF F(v) over the range of $[\underline{v}, \overline{v}]$ , and budgets are drawn independently from distribution with density function g(B) and CDF G(B).

After search engine announce the uniform price p, advertiser i would make the deal if only the value $v_i$ is larger than p. The quantity advertiser i could purchase is constrained by the budget $B_i$ . Therefore the expected aggregate demand under price p from all advertisers would be:

$D(p) = \sum_{i \in \mathcal{I}} \frac{E(B_i)}{p} \cdot \text{Prob}\{v_i > p\} = m \cdot \frac{E(B)}{p} [1 - F(p)]$

Rewrite it as:

$p \cdot D(p) = m \cdot E(B) \cdot [1 - F(p)] \tag{1}$

which is a non-increasing function over p.

We can use figure 1 to illustrate the revenue of search engine over price p.

Figure 1: Search Engine Revenue Over Prices (Ex Ante)

Proposition 1. The revenue R is maximized when S = D(p), i.e., when the demand equals the supply.

Proposition 1 can be proved by contradiction. If supply exceeds demand under the current price, the search engine will cut down the price to achieve higher revenue (since $R = p \cdot D(p)$ is non-increasing over price p); if demand exceeds supply, the search engine can raise the price and reach a higher revenue (since $R = p \cdot S$ is monotonically increasing over price p).

Example 1. Assuming $v_i$ is drawn from uniform distribution with positive support on the interval $[\underline{v}, \overline{v}]$ , where $0 \leq \underline{v} < \overline{v}$ and $\Delta v = \overline{v} - \underline{v}$ . Then $1 - F(p) = \frac{\overline{v} - p}{\Delta v}$ . From S = D(p) we have:

$p^* = \frac{m \cdot E(B) \cdot \overline{v}}{m \cdot E(B) + S \cdot \Delta v}$

The intuition is that the more demand (larger m) there is, the higher market clearing price would be; and the more supply (larger S) there is, the lower market clearing price is.

3.2 Ex post case

In practical search engine advertising system, advertisers need to submit their values and budgets to the advertising system. The search engine therefore could determine the optimal price based on the expost variables.

Reorder the index of advertisers such that $v_j \leq v_{j+1}, j = 1, \ldots, m-1$ . Then the aggregate demand can be written as:

$D(p) = \sum_{i \in \mathcal{I}^+(p)} \frac{B_i}{p}$

where we define the set:

$\mathcal{I}^+(p) \triangleq \{i \in \mathcal{I} : v_i > p\}$

Thus $p \cdot D(p) = \sum_{i \in \mathcal{I}^+(p)} B_i$ is a non-increasing function over p since $\mathcal{I}^+(p)$ shrinks as price p increases. By letting demand equal to supply, we have

$p(\mathcal{I}) = \frac{\sum_{i \in \mathcal{I}^+(p)} B_i}{S}$

Notice that the term of price appears in both sides of the equation. Thus in general we cannot derive the closed-form solution for optimal price. Since pD(p) is piece-wise constant and (weakly) decreasing over p, we can illustrate the search engine revenue through examples in figure 2. Here we assume there are four advertisers ordered such that $v_1 \leq v_2 \leq v_3 \leq v_4$ and initially when the price is zero, $\mathcal{I}^+(p) = \mathcal{I} = \{1, 2, 3, 4\}$ . As the price exceeds $v_1$ , advertiser 1 would have no incentive to stay and $\mathcal{I}^+(p)$ becomes $\{2,3,4\}$ . The crossing point of demand and supply shows that the optimal price $p^*$ is located in $[v_1, v_2]$ . To be more exact, $p^*(\mathcal{I}) = (B_2 + B_3 + B_4)/S$ . In figure 2b we also show the other case when there is one advertiser who is indifferent between participating and quitting the ad campaign since the optimal price is equal to its value. In typical search engine systems like Google AdWords, after advertisers input their maximal willingness to pay (i.e., their values) and budgets, the ad system would automatically allocate attentions to advertisers as long as the current price doesn’t exceed their values and the budgets have not been exhausted yet. Thus here for ease of expression we can assume that the indifferent advertiser would continue participating in the ad campaign under the budget constraint. For example, as shown in figure 2b, the optimal price is equal to $v_2$ (satisfying $B_3 + B_4 < v_2 S < B_2 + B_3 + B_4$ ), advertiser 2 would consume the remaining supply of $S - \frac{B_3 + B_4}{v_2}$ and only spent $v_2 S - B_3 - B_4$ which is less than its budget $B_2$ .

(a) Determined Advertisers

(b) Undetermined Advertiser

Figure 2: Search Engine Revenue Over Prices (Ex Post)

We can now show a polynomial step algorithm for search engine to compute the optimal price. By inputting the parameters of advertisers (assuming the indexes of advertisers are re-ordered such that $v_i \leq v_{i+1}$ , $i \in \{1, ..., m-1\}$ ), algorithm 1 would return the value of optimal price. The time complexity of the algorithm is $O(m^2)$ where m is the number of advertisers⁴.

Algorithm 1 Calculate Optimal Price $p^*(\mathcal{I})$

Begin
 1: v_0 = 0;
 2: for i = 1 : m
         sum = 0;
 3:
         for j = i : m
 4:
 5:
              sum + = B_i;
         end for:
 6:
         p = sum/S;
 7:
         if (p \leq v_i)
 8:
              return \max(p, v_{i-1});
 9:
         end if;
10:
11: end for;
12: return v_m;

End

After determining the optimal price $p^*$ , the quantity of attentions allocated to each advertiser i, denoted by $q_i$ , can be easily computed. The search engine would first find the least index of advertiser whose value is larger than or equal to $p^*$ , which is denoted by $j \in \{i \in \mathcal{I} : v_i \geq p^*, v_{i-1} < p^*\}$ (we define $v_0 = 0$ ). If there are no undetermined advertisers, which implies $v_j > p^*$ , the quantity allocated to advertiser i would be $q_i = B_i/p^*$ for $i \geq j$ and $q_i = 0$ otherwise. If undetermined advertiser does exist, which implies $v_j = p^*$ , we have $q_i = B_i/p^*$ for i > j, $q_j = S - \sum_{i=j+1}^m q_i$ , and $q_i = 0$ for i < j. In both cases, the demand equals the supply, i.e., $\sum_{i \in \mathcal{I}} q_i = S$ . This can be summarized in algorithm 2.

The revenue of search engine is:

$R = p^* \cdot S \tag{2}$

The aggregate utility of advertisers is:

$U_A = \sum_{i \in \mathcal{I}^+(p^*)} (v_i - p^*) \frac{B_i}{p^*}$ (3)

Notice that the indifferent advertiser, if exists, would always achieve zero utility since the current price equals its value, thus we don’t need to consider it in the expression.

The social welfare of the advertising system⁵ is:

$SW = R + U_A \tag{4}$

^4The time complexity of the algorithm may be further reduced to O(m) by computing and saving the value of $sum_i \triangleq \sum_{j \in \{i,...,m\}} B_j$ , $i \in \{1,...,m\}$ first, which can be finished in O(m) steps. Then the inner “for” loop in algorithm 1 can be substituted by the stored value of $sum_i$ and the complexity of the algorithm is reduced to O(m). Here for simplicity of exposition, we just show the $O(m^2)$ algorithm.

^5We don’t consider search users’ utility in the expression here.

Algorithm 2 Calculate Allocation $q_i, i \in \mathcal{I}$

Begin

1: sum = 0;
 2: p = p^*;
 3: for j = 1 : m
         if (v_i \geq p)
              break;
 5:
         end if;
 6:
 7: end for;
 8: for i = 1 : (j - 1)
         q_i = 0;
10: end for;
11: for i = (j+1) : m
         q_i = B_i/p;
12:
         sum + = q_i;
13:
14: end for;
15: q_j = S - sum;
End

Lemma 1. The optimal price is non-decreasing over the set of participating advertisers given fixed supply S. That is to say, for any advertisers set $\mathcal{I}_1$ and $\mathcal{I}_2$ , if $\mathcal{I}_1 \subseteq \mathcal{I}_2$ , we have $p^*(\mathcal{I}_1) \leq p^*(\mathcal{I}_2)$ , where $p^*(\mathcal{I})$ is obtained according to algorithm 1.

Proof. We can prove the above lemma by contradiction. For simplicity of notation, we write $p_1 \triangleq p^*(\mathcal{I}_1)$ and $p_2 \triangleq p^*(\mathcal{I}_2)$ and assume that $p_1 > p_2$ .

Since under optimal price, supply must be equal to demand, we have:

$S = \sum_{i \in \mathcal{I}_{1}^{+}(p_{1})} \frac{B_{i}}{p_{1}} + \frac{\alpha B_{l}}{p_{1}} \quad \text{and} \quad S = \sum_{i \in \mathcal{I}_{2}^{+}(p_{2})} \frac{B_{i}}{p_{2}} + \frac{\beta B_{l'}}{p_{2}}$

where $\alpha \in [0, 1]$ , and $\alpha > 0$ if and only if there exists an indifferent advertiser l whose value $v_l$ equals $p_1$ ; Similarly, $\beta \in [0, 1]$ , and $\beta > 0$ if and only if there exists an advertiser l’ such that $v_{l'} = p_2$ .

For any advertiser $i \in \mathcal{I}_1^+(p_1)$ , we have $i \in \mathcal{I}_1 \subseteq \mathcal{I}_2$ and $v_i > p_1 > p_2$ , thus $i \in \mathcal{I}_2^+(p_2)$ , which infers that $\mathcal{I}_1^+(p_1) \subseteq \mathcal{I}_2^+(p_2)$ ; since $v_l = p_1 > p_2$ , we also have $l \in \mathcal{I}_2^+(p_2)$ . Therefore,

$S = \sum_{i \in \mathcal{I}_1^+(p_1)} \frac{B_i}{p_1} + \frac{\alpha B_l}{p_1} \le \sum_{i \in \mathcal{I}_1^+(p_1)} \frac{B_i}{p_1} + \frac{B_l}{p_1} \le \sum_{i \in \mathcal{I}_2^+(p_2)} \frac{B_i}{p_1} < \sum_{i \in \mathcal{I}_2^+(p_2)} \frac{B_i}{p_2} \le \sum_{i \in \mathcal{I}_2^+(p_2)} \frac{B_i}{p_2} + \frac{\beta B_{l'}}{p_2}$

Contradiction to the conclusion that supply should equal demand under optimal price $p_2$ .

Lemma 2. The revenue of search engine is non-decreasing over the set of participating advertisers given fixed supply S. That is to say, for any advertisers set $\mathcal{I}_1$ and $\mathcal{I}_2$ , if $\mathcal{I}_1 \subseteq \mathcal{I}_2$ , we have $R(\mathcal{I}_1) \leq R(\mathcal{I}_2)$ .

Proof. This conclusion can be deducted from lemma 1 immediately:

$R(\mathcal{I}_1) = p^*(\mathcal{I}_1) \cdot S \le p^*(\mathcal{I}_2) \cdot S \le R(\mathcal{I}_2).$

Lemma 3. The optimal price is non-increasing over the supply given the set of participating advertisers $\mathcal{I}$ . That is to say, for any supply $S_1, S_2 \in [0, \infty)$ , if $S_1 > S_2$ , we have $p^*(S_1) \leq p^*(S_2)$ .

Proof. We prove the lemma by contradiction. For simplicity, we write $p_1 \triangleq p^*(S_1)$ and $p_2 \triangleq p^*(S_2)$ and assume that $p_1 > p_2$ .

Since under optimal price, supply equals demand, we get:

$S_1 = \sum_{i \in \mathcal{I}^+(p_1)} \frac{B_i}{p_1} + \frac{\alpha B_l}{p_1}$ and $S_2 = \sum_{i \in \mathcal{I}^+(p_2)} \frac{B_i}{p_2} + \frac{\beta B_{l'}}{p_2}$

For any advertiser $i \in \mathcal{I}^+(p_1)$ , we have $v_i > p_1 > p_2$ , thus $i \in \mathcal{I}^+(p_2)$ , which infers that $\mathcal{I}^+(p_1) \subseteq \mathcal{I}^+(p_2)$ ; since $v_l = p_1 > p_2$ , we also have $l \in \mathcal{I}^+(p_2)$ . Therefore,

$S_1 = \sum_{i \in \mathcal{I}^+(p_1)} \frac{B_i}{p_1} + \frac{\alpha B_l}{p_1} \le \sum_{i \in \mathcal{I}^+(p_1)} \frac{B_i}{p_1} + \frac{B_l}{p_1} \le \sum_{i \in \mathcal{I}^+(p_2)} \frac{B_i}{p_1} < \sum_{i \in \mathcal{I}^+(p_2)} \frac{B_i}{p_2} \le \sum_{i \in \mathcal{I}^+(p_2)} \frac{B_i}{p_2} + \frac{\beta B_{l'}}{p_2} = S_2$

Contradiction to our assumption of $S_1 > S_2$ .

Lemma 4. The revenue of search engine is non-decreasing over the supply given the set of participating advertisers $\mathcal{I}$ . That is to say, for any supply $S_1, S_2 \in [0, \infty)$ , if $S_1 > S_2$ , we have $R(S_1) \geq R(S_2)$ .

Proof. For simplicity, we write $p_1 \triangleq p^*(S_1)$ and $p_2 \triangleq p^*(S_2)$ and from lemma 3 we know that $p_1 < p_2$ .

Since under optimal price, supply equals demand, we get:

$S_1 = \sum_{i \in \mathcal{I}^+(p_1)} \frac{B_i}{p_1} + \frac{\alpha B_l}{p_1}$ and $S_2 = \sum_{i \in \mathcal{I}^+(p_2)} \frac{B_i}{p_2} + \frac{\beta B_{l'}}{p_2}$

For any advertiser $i \in \mathcal{I}^+(p_2)$ , we have $v_i > p_2 > p_1$ , thus $i \in \mathcal{I}^+(p_1)$ , which infers that $\mathcal{I}^+(p_2) \subseteq \mathcal{I}^+(p_1)$ ; since $v_{l'} = p_2 > p_1$ , we also have $l' \in \mathcal{I}^+(p_1)$ . Therefore,

$R(S_2) = p_2 \cdot S_2 = \sum_{i \in \mathcal{I}^+(p_2)} B_i + \beta B_{l'} \le \sum_{i \in \mathcal{I}^+(p_2)} B_i + B_{l'} \le \sum_{i \in \mathcal{I}^+(p_1)} B_i \le \sum_{i \in \mathcal{I}^+(p_1)} B_i + \alpha B_l = R(S_1)$

3.3 Formulated As An Optimization Problem

The revenue maximization problem confronting the monopolistic search engine could also be interpreted as an optimization problem as follows:

$\text{maximize} \quad p \cdot \sum_{i} q_{i} \tag{5}$

subject to $\forall i \in \mathcal{I} : p \cdot q_i \leq B_i$ (6)

$\forall i \in \mathcal{I} : (v_i - p) \cdot q_i \ge 0 \tag{7}$

$\sum_{i} q_i \le S \tag{8}$

$\forall i \in \mathcal{I} : p, q_i \ge 0 \tag{9}$

where the search engine needs to determine its optimal price p and allocation of supply $q_i$ to each advertiser i in objective function 5. Constraint (6) means that each advertiser could not spend more than its budget. Constraint (7) shows that the utility of advertiser must be non-negative, i.e., when the price p exceeds the value $v_i$ , which implies that $q_i$ must be zero, advertiser i would just quit the ad campaign. The total supply to all advertisers is limited by S, which is shown in constraint (8). The last constraint states that all variables (p and $q_i$ , $i \in \mathcal{I}$ ) should be non-negative.

As we have shown in proposition 1 that the maximal revenue can only be obtained when supply equals demand, therefore the above formulation may be further reduced to:

maximize $p \cdot S$ (10)

subject to $\forall i \in \mathcal{I} : p \cdot q_i \leq B_i$ (11)

$\forall i \in \mathcal{I} : (v_i - p) \cdot q_i \ge 0 \tag{12}$

$\sum_{i} q_i = S \tag{13}$

$\forall i \in \mathcal{I} : p, q_i > 0 \tag{14}$

where constraint (13) becomes tight and the objective function is simplified to maximize variable p only. Thus it’s easy to see that the optimal solution for p is unique. Otherwise, if both $p^*$ and $p^{*'}$ maximize the objective function, it must be $p^* \cdot S = p^{*'} \cdot S$ , so $p^* = p^{*'}$ . It remains to be inspected whether the optimal allocation vector of $\vec{q} \triangleq (q_1, q_2, \ldots, q_m)$ for the optimization problem is unique too. We summarize our conclusions in the following proposition.

Proposition 2. In general, for revenue maximization problem (10), the optimal price p is unique, however, there may be multiple optimal solutions for allocation vector $\vec{p}$ .

This can be shown by constructing a simple example as follows: there are two advertisers with $v_1 = 1, v_2 = 2$ and $B_1 = 2, B_2 = 1$ , search engine’s supply is S = 2. Assuming the optimal price $p^*$ is larger than 1, $q_1$ must be zero since $v_1 < p^*$ , then $q_2$ must be 2 according to constraint (13). This would lead to $p \cdot q_2 > 2$ , which contradicts with the budget constraint of $B_2 = 1$ . Now assuming the optimal price $p^* = 1$ , the constraints of the optimization problem would be reduced to $q_1 + q_2 = 2$ and $q_2 \le 1$ , thus the optimal allocation vector could be $\vec{q^*} = (q_1^*, q_2^*) = (2 - q, q), \forall q \in [0, 1]$ .

We now turn to investigate the effect of different optimal solutions to the social welfare. Since in general $R = p \cdot \sum_{i \in \mathcal{I}} q_i$ and $U_A = \sum_{i \in \mathcal{I}} (v_i - p)q_i$ , from equation (4) we get $SW = \sum_{i \in \mathcal{I}} v_i \cdot q_i$ , where the payments between search engine and advertiser are crossed off. If we examine the original social welfare maximization (SWM) problem under the same constraints (11)-(14), we can immediately present a trivial solution as follows: p = 0, $q_m = S$ , $q_i = 0$ for $i \in \mathcal{I} \setminus \{m\}$ , i.e., letting the advertiser with the highest value acquire all the supply exclusively. Now the maximal social welfare would be $SW_{max} = v_m \cdot S$ . However, this solution is infeasible since it induces zero profit to the search engine. An alternative problem the search engine may be interested in is to maximize the social welfare while maintaining the optimal revenue it has achieved in (10). In other words, we need to pick out one among the multiple optimal allocations of (10) to maximize the social welfare. We call it as the constrained social welfare maximization (C-SWM) problem henceforth. This following theorem gives the solution to the C-SWM problem.

Theorem 1. Among all optimal solutions to the profit maximization problem (10), algorithm 1 and 2 yield the one which maximizes the social welfare, i.e., the solution to the constrained social welfare maximization (C-SWM) problem.

Proof. Denote the optimal price and allocation induced by algorithms as $p^*$ and $q_1^*, \ldots, q_m^*$ , and assuming there is another allocation vector $\hat{q}_1, \ldots, \hat{q}_m$ satisfying the constraints (11)-(14). Assuming advertiser j has the cutting-off value such that $v_i \geq p^*$ for $i \geq j$ and $v_i < p^*$ for i < j. Therefore from constraint (12), we must have $q_i^* = \hat{q}_i = 0$ for all i < j. According to algorithm 2, $q_i^* = \frac{B_i}{p^*}$ for all i > j and $q_j^* = S - \sum_{i=j+1}^m q_i$ . Due to the constraint (12), for all i > j, it must be $\hat{q}_i \leq \frac{B_i}{p^*} = q_i^*$ . Hence we can assume that $\hat{q}_i = q_i^* - \delta_i$ , where $\delta_i \geq 0$ for all i > j. Then the social welfare under either allocation is:

$\begin{split} SW_1 &= \sum_{i \in \mathcal{I}} v_i \cdot q_i^* \\ &= \sum_{i = j+1}^m v_i \cdot q_i^* + v_j \cdot (S - \sum_{i = j+1}^m q_i^*) \\ SW_2 &= \sum_{i \in \mathcal{I}} v_i \cdot \hat{q}_i \\ &= \sum_{i = j+1}^m v_i \cdot (q_i^* - \delta_i) + v_j \cdot [S - \sum_{i = j+1}^m (q_i^* - \delta_i)] \\ &= SW_1 + \sum_{i = j+1}^m \delta_i \cdot (v_j - v_i) \end{split}$

Since $\delta_i \geq 0$ and $v_j \leq v_i$ for i > j, we have $SW_2 \leq SW_1$ . Therefore $q_1^*, \ldots, q_m^*$ maximizes the social welfare over all possible optimal allocations of (10).

4 The Duopoly Market Model

In this section we switch from the monopoly model to the competitive model with more than one search engine. Considering the likely situation where there is one leading search company and one major competitor in the market (for example, Google and Yahoo! in the United States), we describe a duopoly model where one search engine has an advantage over the other. We formulate their competition as a three-stage dynamic game and solve it from the ex post perspective as follows.

4.1 Competition for End Users in Stage I

In Stage I search engines would choose different strategies for attracting end users with different tastes. The user bases they attract in this Stage would be the decisive factor for determining their supply of user attentions to advertisers in subsequent stages.

We assume that there are two horizontally and vertically differentiated search engines $\mathcal{J} = \{1, 2\}$ providing search results to users and selling ad opportunity to advertisers.

Here horizontal difference means the different design of their home pages and diversity of extra services such as email, news and other applications. Different users may have different tastes and preferences and hence be attracted by different search engines.

Vertical difference means the quality of searching results. The higher the quality is, the better users and advertisers would feel. We assume that search engine 1 possesses the leading technology to match ads to search queries and can provide better service for both users and advertisers than search engine 2.

In terms of horizontal difference, the canonical Hotelling’s model of spatial competition [7] provides an appealing framework to address the equilibrium in characteristic space. The behaviors of providers could then be rationalized as the best-response strategies of players in a location game. The dynamics of the game can be described as follows: each provider chooses a location in the characteristic space which denotes the specific feature of service it provides to users. And each user is characterized by an address reflecting his individual preference of ideal features search engines should provide. Searching at engine j ∈ J involves quadratic transportation cost⁶ for a user if engine j is not located in his ideal position. Users would choose search engine which provides better search results and also induces as low transportation cost as possible.

Assuming that a continuum of users are spread uniformly with unit density on the circumference of a unit circle. The address of user is denoted by t ∈ [0, 1). Without loss of generality, let search engine 1 locate at x¹ = 0⁷ and search engine 2 x² ∈ [0, 1), as shown in figure 3.

Figure 3: Users in Circular Domain

Assuming search engine 1 can provide higher quality results for users than search engine 2. Then the utility of the user searching in either engine would be as follows:

$u_1(t) = \zeta_1 q - C(t, x_1) = q - \min\{t^2, (1-t)^2\}$ (15)

$u_2(t) = \zeta_2 q - C(t, x_2) = \zeta_1 q - (t - x_2)^2$ (16)

where ζ ∈ [0, 1] denotes the comparative “disability” of search engine 2 to provide the best search result to users; q is the positive payoff users perceive when certain information is returned by the search engine for a particular query; C(t, x^j ) is the transportation cost incurred when there is some distance between user’s address t and search engine j’s location x^j .

Let u1(ξ) = u2(ξ) we can find the location of users who are indifferent between searching in two

⁶Actually in the seminar paper of Hotelling [7] the author assumed the linear transportation cost, which resulted in no equilibrium results. Later literatures on Hotelling’s model usually modified this assumption to the quadratic transportation cost which ensures existence of equilibrium. Here we followed this line of revised model as applied in recent papers such as [8, 9]. Interesting readers may further refer to the excellent survey of [10] for a comprehensive discussion and review of different variants of the Hotelling’s model.

⁷Since it is a circle, engine 1 can also be regarded as locating at the ending point x¹ = 1.

engines:

$\xi_1 = \frac{(1-\zeta)q + x_2^2}{2x_2}$

$\xi_2 = \frac{1-x_2^2 - (1-\zeta)q}{2(1-x_2)}$

Then the market share of search engine 2 is

$n_2(x_2) = \xi_2 - \xi_1 = \frac{1}{2} \left[ 1 - \frac{(1-\zeta)q}{x_2(1-x_2)} \right]$

and search engine 1 obtains the remaining market share: $n_1 = 1 - n_2$ . By applying the first-order condition $\frac{dn_2}{dx_2} = 0$ , we have $x_2^* = \frac{1}{2}$ , i.e., the maximum differentiation.

Letting $x_2 = \frac{1}{2}$ we have

$n_1 = \frac{1}{2} + 2(1 - \zeta)q$

$n_2 = \frac{1}{2} - 2(1 - \zeta)q$

As we can see, when two search engines provide the same quality of service ( $\zeta = 1$ ), they will divide the market share equally. The less quality search engine 2 provides, the less market share it can hold.

Since the impression number for a particular keyword in a search engine is proportional to the users it attracts: the more users see the advertisement, the more impressions the ad would receive in general. To be aligned with the monopoly case in previous section, here we assume the total supply is still S and the supply of each search engine is denoted by:

$S_1 = S \cdot \frac{n_1}{n_1 + n_2} = S \cdot n_1$ $S_2 = S \cdot \frac{n_2}{n_1 + n_2} = S \cdot n_2$

Since $n_1 \geq n_2$ , we have also $S_1 \geq S_2$ .

4.2 Competition for Advertisers in Stage II and III

Search engines compete for advertisers in the last two stages to maximize their revenues subject to the supply constraint $(S_1, S_2)$ determined in Stage I. In Stage II, search engines determine their optimal prices $(p_1, p_2)$ for charging advertisers; and consequently in Stage III, advertisers would choose their favorite search engine for advertisements based on the previously announced prices. Facing the new advertiser sets in Stage III, search engines may want to revert to the second stage and revise their optimal prices, and consequently, advertisers would make necessary adjustment in the third stage. Therefore, Stage II and III would alternate dynamically until it reaches certain stable state. we will discuss this dynamic process in details in the following section.

For advertiser $i \in \mathcal{I}$ , the utility of participating in the ad campaign in either search engine is:

$\pi_1^i = \max\{(v_i - p_1)\frac{B_i}{p_1}, 0\}$ (17)

$\pi_2^i = \max\{(v_i \rho_i - p_2) \frac{B_i}{p_2}, 0\}$ (18)

where $\rho_i \in [0,1]$ is called discount factor denoting advertiser i’s perceived “disability” of search engine 2 to convert the impressions to clicks (or sales of products). We assume that search engine 1 owns better technology and is able to match users’ interest with the most suitable ads, hence can generate a higher click-through rate (users’ probability of clicking after seeing the ads) or conversion rate (users’ probability of purchase the product or service after clicking the ads) than search engine 2. So in general advertisers would evaluate each impression in search engine 1 higher than in engine 2. For simplicity of notation, we have normalized the discount factor of per-impression value in search engine 1 as unity. In practical market, advertisers can be roughly classified into two categories: brand advertisers and performance advertisers [11]. Brand advertisers usually have higher $\rho$ since they aim to promote the brand awareness among users and hence the relative technology disadvantage in search engine 2 would have less effect on their values for each attention/impression. However, for performance advertisers who care more on the click-through rate or conversion rate, the technology disadvantage would affect their values for each impression more and therefore result in lower values of $\rho$ . To be more exact, we let the expectation $E(\rho)$ of discount factor serve as the cutting-off value for two types of advertisers, i.e., advertisers with higher $\rho$ than $E(\rho)$ is defined as brand advertisers and the others are performance advertisers in our model.

By letting $\pi_1^i \geq \pi_2^i$ we can derive the condition under which advertiser i would choose search engine 1:

$\rho_i \leq \frac{p_2}{p_1}$

Assuming that advertisers are re-ordered according to $\rho_i$ . Then the division of advertisers can be depicted in figure 4 where $\mathcal{I}_1(p_1, p_2) = \{i \in \mathcal{I} : \rho_i \leq \frac{p_2}{p_1}\}$ denotes the set of advertisers who prefer search engine 1 and $\mathcal{I}_2(p_1, p_2) = \{i \in \mathcal{I} : \rho_i > \frac{p_2}{p_1}\}$ the set of advertisers preferring engine 2.

Figure 4: The Division of Advertisers

After initial price $p_1$ and $p_2$ are set in the market, the advertisers set is divided into $\mathcal{I}_1$ and $\mathcal{I}_2$ . Then each search engine can compute its optimal price $p_1^*(\mathcal{I}_1)$ and $p_2^*(\mathcal{I}_2)$ independently as the monopoly case and price ratio $\frac{p_2^*(\mathcal{I}_2)}{p_1^*(\mathcal{I}_1)}$ gets updated. If it happens that the new price ratio divides the advertisers set into $\mathcal{I}_1$ and $\mathcal{I}_2$ , we say this is a Nash equilibrium (NE) price pair as $(p_1^{NE}, p_2^{NE})$ and neither search engine has incentive to deviate unilaterally. Otherwise, the process will iterate until the prices become stable.

Defining first the set of advertisers who participate the advertising campaign as follows.

$\mathcal{I}_{1}^{+}(p_{1}, p_{2}) \triangleq \{i \in \mathcal{I} : \rho_{i} \leq \frac{p_{2}}{p_{1}}, v_{i} \geq p_{1}\}$ (19)

$\mathcal{I}_{2}^{+}(p_{1}, p_{2}) \triangleq \{i \in \mathcal{I} : \rho_{i} > \frac{p_{2}}{p_{1}}, \rho_{i}v_{i} \geq p_{2}\}$ (20)

We now give the formal definition of NE price pair.

Definition 1. A price pair of $(p_1, p_2)$ is called a Nash equilibrium price pair if $p_1 = p^*(\mathcal{I}_1^+(p_1, p_2))$ and $p_2 = p^*(\mathcal{I}_2^+(p_1, p_2))$ where $p^*(\mathcal{I})$ is computed according to algorithm 1.

It’s easy to see that under the NE price pair $(p_1, p_2)$ , for any advertiser $i \in \mathcal{I}_1^+$ or $i \in \mathcal{I}_2^+$ , it would have no incentive to switch to the other search engine; for advertiser $i \in \mathcal{I}_1 \setminus \mathcal{I}_1^+$ , since $\rho_i \leq \frac{p_2}{p_1}$ and $v_i < p_1$ , it holds that $\rho_i v_i < p_2$ , thus i would not switch to engine 2 which generates zero utility according to equation (17); for advertiser $i \in \mathcal{I}_2 \setminus \mathcal{I}_2^+$ , since $\rho_i > \frac{p_2}{p_1}$ and $\rho_i v_i < p_2$ , we have $v_i < p_1$ so i have no incentive to switch to engine 1. Thus the NE price pair would induce a stable state to the competition system.

Proposition 3. None-zero NE price pairs may not exist.

A simple counter-example to illustrate proposition 3 is when there is only one advertiser in the system. No matter which search engine this advertiser chooses, the price in the other search engine would be zero since it attracts no advertisers. Then the advertiser would have incentive to join the other search engine due to the zero price. However, once the advertiser switches, the price in the other search engine would become positive and price in the original engine decreases to zero. Thus the advertiser would keep switching between two search engines and no stable prices can be reached.

Proposition 4. If NE price pair $(p_1^{NE}, p_2^{NE})$ exists, it must be $p_1^{NE} \ge p_2^{NE}$ .

Proof. Assuming $p_1^{NE} < p_2^{NE}$ , then since $\frac{p_2^{NE}}{p_1^{NE}} > 1$ , we have $\mathcal{I}_2^+(p_1, p_2) = \varnothing$ . Therefore $p_2^{NE} = 0$ and $p_1^{NE} < 0$ . However, it cannot be the case since rational search engine would never set negative prices.

Proposition 5. In the stable state, search engine 2 cannot make higher revenue than engine 1.

Proof. Since $R_1 = p_1^{NE} \cdot S_1$ and $R_2 = p_2^{NE} \cdot S_2$ , from proposition 4 and $S_1 \geq S_2$ , it’s easy to see that $R_1 \geq R_2$ .

Denote $\nu$ as the price ratio $\frac{p_2}{p_1}$ which determines advertisers’ preferences, we define the optimal price ratio as:

$f(\nu) = \frac{p_2^*(\mathcal{I}_2(\nu))}{p_1^*(\mathcal{I}_1(\nu))}$

where $p^*(\mathcal{I})$ is obtained according to algorithm 1. If the advertiser partitions generated by $\nu$ are the same as those generated by the optimal price ratio $f(\nu)$ , then the partitions are stable and the optimal prices become NE price pair. The problem reduces to find the fixed points which satisfy $f(\nu^*) = \nu^*$ . Notice that $f(\nu)$ is piece-wise constant and its value changes at $\nu = \rho_i$ , $i \in \{1, ..., m\}$ .

From the definitions of $\mathcal{I}_1$ and $\mathcal{I}_2$ we see that as $\nu$ increases, the preferred set of $\mathcal{I}_1$ would expand while $\mathcal{I}_2$ shrinks. According to lemma 1, we know that $p_1^*$ would increase while $p_2^*$ decreases. Therefore $f(\nu)$ should be a non-increasing function of $\nu$ .

We can now show the dynamics of function $f(\nu)$ in figure 5. In this example we assume there are five advertisers re-ordered by their values of $\rho$ such that $\rho_i \leq \rho_{i+1}$ , $i \in \{1, 2, 3, 4\}$ . Similarly, there may be two different scenarios for the location of fixed point $v^*$ : (a) $v^* \in (\rho_i, \rho_{i+1})$ , $i \in \{1, \ldots, m-1\}$ as shown in figure 5a, and (b) $v^* = \rho_i$ , $i \in \{1, \ldots, m\}$ as shown in figure 5b.

For case (a), the optimal $\nu^*$ divides the advertisers set into exactly two subsets, and all advertisers with strict preferences over certain search engine are aggregated to one of the subsets. The market would become stable after each search engine sets their optimal price. For case (b), however, there

Figure 5: Division of Advertisers Set by their Preferences

is one special advertiser who would keep switching from one search engine to the other. To illustrate it, assuming the index of this special advertiser is l which satisfies the following condition:

$\frac{p_2^*(\{l, l+1, \dots, m\})}{p_1^*(\{1, 2, \dots, l-1\})} > \rho_l > \frac{p_2^*(\{l+1, \dots, m\})}{p_1^*(\{1, 2, \dots, l\})}$

The first inequality above implies that advertiser l prefers search engine 1 if l has already joined the system of search engine 2, while the second inequality implies that he would prefer engine 2 if he is associated with engine 1. Therefore, advertiser l would keep switching between two search engines. In this case, we call advertiser l as the undetermined advertiser.

The undetermined advertiser problem arises from our assumption that advertisers can only purchase service from one engine. This resembles the classic oscillation problem in the multi-path routing when all traffic is aggregated to the least congested path [17]. Similar to the “splittable” model in [18] where network users are permitted to route traffic fractionally over many paths, we can also make the following assumption for our model:

Assumption 1. Splittable Budgets: We assume advertisers can arbitrarily split their budgets and invest them into both search engines to maximize their utility.

Under this splittable assumption, the dynamics of undetermined advertiser l’s strategic behavior could be interpreted as follows: assuming starting from the initial state where advertiser l has joined engine 1, and is facing a lower price ratio $(\frac{p_2}{p_1} < \rho_l)$ which indicates him to invest more on engine 2; then l would try to split his budget into two parts: $(1 - \alpha)B_l$ goes to engine 1 and the rest of $\alpha B_l$ goes to engine 2, with $\alpha \in [0, 1]$ . As advertiser l invests more and more budgets on engine 2, i.e., $\alpha$ keeps growing from zero to one, the price ratio $\frac{p_2}{p_1}$ would keep rising until at certain $\alpha^* \in (0, 1)$ it equals $\rho_l$ and advertiser l would have no incentive to invest more on engine 2.

It remains to be shown whether the price ratio above would increase “smoothly” as $\alpha$ increases and whether there always exists $\alpha^*$ for the undetermined advertiser to divide his budget. We summarize our conclusion in the following theorem.

Theorem 2. Assuming that there exists an undetermined advertiser l and this advertiser can purchase service from both search engines. In particular, advertiser l can arbitrarily split his budget into $(1-\alpha)B_l$ and $\alpha B_l$ with $\alpha \in [0,1]$ , where the former is invested to engine 1 and the latter to engine 2. Then there must exist $p_1^*$ , $p_2^*$ and $\alpha^* \in [0,1]$ such that $\frac{p_2^*}{p_1^*} = \rho_l$ .

^8To be more exact, we need to guarantee that there are no discontinuous points. Otherwise, the optimal $\alpha^*$ may not exist.

Proof. Denote $\mathcal{I}_1 \triangleq \{1, 2, \dots, l-1\}$ and $\mathcal{I}_2 \triangleq \{l+1, l+2, \dots, m\}$ . By previous analysis we know that advertisers in $\mathcal{I}_1$ would always be associated with engine 1 and advertisers in $\mathcal{I}_2$ be associated with engine 2. It remains to be shown the effect of advertiser l’s splitting decision on the price ratio. Define first that $p_1^0 = p_1^*(\mathcal{I}_1)$ , $p_1^1 = p_1^*(\mathcal{I}_1 \cup \{l\})$ and $p_1^{\alpha} = p_1^*(\mathcal{I}_1 \cup \alpha\{l\})$ where $\alpha\{l\}$ denotes that advertiser l participates in search engine 1, but with fractional budget of $\alpha B_i$ ; similarly, we define $p_2^0 = p_2^*(\mathcal{I}_2)$ , $p_2^1 = p_2^*(\mathcal{I}_2 \cup \{l\})$ and $p_2^{\alpha} = p_2^*(\mathcal{I}_2 \cup \alpha\{l\})$ .

To prove that $\frac{p_2^{\alpha}}{p_1^{1-\alpha}}$ changes continuously from $\frac{p_2^0}{p_1^1}$ to $\frac{p_2^1}{p_1^0}$ as $\alpha$ increases from zero to one, we first present lemma 5 as follows.

Lemma 5. Given a monopolistic search engine and the advertisers set $\mathcal{I}$ . Assuming all parameters of the ad system, including engine’s supply, advertisers’ values and budgets, are definite except the budget $B_i$ of certain advertiser $i \in \mathcal{I}$ , then the optimal price $p^*(\mathcal{I})$ can be regarded as a function over the variable $B_i \geq 0$ . Furthermore, the function is continuous and non-decreasing as $B_i$ increases.

Proof. Since from algorithm 1, for each realization of $B_i$ , we can compute a definite value of optimal price, the optimal price can therefore be regarded as a function of $B_i$ .

The property of non-decreasing (or weakly increasing) is easy to see by contradiction. Assuming for $B_i$ the optimal price is $p_1$ and for $B_i + \delta$ ( $\delta > 0$ ) the optimal price is $p_2$ with $p_2 < p_1$ . Then $p_1$ would be the optimal solution for formulation in (10)-(14) and we let $\vec{q^*}$ be one of the binding optimal allocations. After we increase advertiser i’s budget to $B_i + \delta$ , the previous solution combination $(p_1, \vec{q^*})$ would still satisfy the constraints of the revised optimization problem since $p_1 \cdot q_i^* \leq B_i \leq B_i + \delta$ and all other conditions remain unchanged. Since $p_2$ is the optimal solution for the revised problem which maximizes the objective function of $p \cdot S$ , we have $p_2 \cdot S \geq p_1 \cdot S$ , thus, $p_2 \geq p_1$ . This contradicts with our previous assumption of $p_2 < p_1$ .

We now turn to prove the property of continuity. Let $p^*(B_i)$ denote the optimal price under budget $B_i$ and $p^*(B_i+\varepsilon)$ the optimal price under budget $B_i+\varepsilon$ where $\varepsilon$ is any small real number. As shown in figure 2, for arbitrary budget $B_i \in [0, \infty)$ , there exist two different scenarios for computing the optimal price: (a) all advertisers are determined; (b) there is one undetermined advertiser. We will discuss these two cases separately as follows.

Case (a): $v_l < p^* < v_{l+1}$ , $l \in \{0, 1, \ldots, m-1\}$ (let $v_0 = 0$ ). We further consider two cases for the index of advertiser i whose budget $B_i$ is the variable: (i) $i \leq l$ ; (ii) i > l. For type (i), since $p^*(B_i) = (B_{l+1} + B_{l+2} + \cdots + B_m)/S$ , the change of $B_i$ would not affect the value of optimal price, therefore, we have $\lim_{\varepsilon \to 0} p^*(B_i + \varepsilon) = p^*(B_i)$ ; For type (ii), since advertiser i is in the participating set, the change of $B_i$ does affect the optimal price. Assuming $\varepsilon$ is small enough such that $|\varepsilon| < \min\{(p^* - v_l) \cdot S, (v_{l+1} - p^*) \cdot S\}$ . This condition guarantees that $p^*(B_i + \varepsilon) = p^*(B_i) + \varepsilon/S$ is still in the interval of $(v_l, v_{l+1})$ . Therefore, $\lim_{\varepsilon \to 0} p^*(B_i + \varepsilon) = p^*(B_i) + \lim_{\varepsilon \to 0} \varepsilon/S = p^*(B_i)$ . Case (b): $p^* = v_l$ , $l \in \{1, \ldots, m\}$ and $B_{l+1} + \cdots + B_m \leq v_l \cdot S \leq B_l + B_{l+1} + \cdots + B_m$ where

Case (b): $p^* = v_l$ , $l \in \{1, ..., m\}$ and $B_{l+1} + \cdots + B_m \leq v_l \cdot S \leq B_l + B_{l+1} + \cdots + B_m$ where advertiser l would only consume part of his budget under price $v_l$ . For i < l, the change of $B_i$ would not affect $p^*$ , so we only need to consider the case for $i \geq l$ . We now consider three possible scenarios for $v_l \cdot S$ :

(i) $B_{l+1} + \cdots + B_m < v_l \cdot S < B_l + B_{l+1} + \cdots + B_m$ . Assuming $\varepsilon$ is small enough such that $|\varepsilon| < \min\{v_l \cdot S - (B_{l+1} + \cdots + B_m), B_l + B_{l+1} + \cdots + B_m - v_l \cdot S\}$ . This condition guarantees that after $B_i$ has changed $\varepsilon$ , $v_l \cdot S$ is still in the interval of $(B_{l+1} + \cdots + B_m + \varepsilon, B_l + B_{l+1} + \cdots + B_m + \varepsilon)$ , which means that $\lim_{\varepsilon \to 0} p^*(B_i + \varepsilon) = \lim_{\varepsilon \to 0} v_l = v_l = p^*(B_i)$ ;

(ii) $v_l \cdot S = B_{l+1} + \cdots + B_m$ . When $\varepsilon$ is negative, it will be equivalent to the above case (i) and therefore we have $\lim_{\varepsilon \to 0^-} p^*(B_i + \varepsilon) = \lim_{\varepsilon \to 0^-} v_l = p^*(B_i)$ ; when $\varepsilon$ is positive, it will be equivalent to case (a) and therefore $\lim_{\varepsilon \to 0^+} p^*(B_i + \varepsilon) = p^*(B_i) + \lim_{\varepsilon \to 0^+} \varepsilon/S = p^*(B_i)$ ;
(iii) $v_l \cdot S = B_l + B_{l+1} + \dots + B_m$ . When $\varepsilon$ is negative, it will be equivalent to case (a) and therefore $\lim_{\varepsilon \to 0^-} p^*(B_i + \varepsilon) = p^*(B_i) + \lim_{\varepsilon \to 0^-} \varepsilon/S = p^*(B_i)$ ; when $\varepsilon$ is positive, it will be equivalent to the above case (i) and therefore we have $\lim_{\varepsilon \to 0^+} p^*(B_i + \varepsilon) = \lim_{\varepsilon \to 0^+} v_l = p^*(B_i)$ .

Therefore now we can conclude that for any $B_i \in [0, \infty)$ , it always holds that $\lim_{\varepsilon \to 0} p^*(B_i + \varepsilon) = p^*(B_i)$ . So $p^*(B_i)$ is a continuous function over $B_i \in [0, \infty)$ .

From lemma 5 we see that $p_2^{\alpha}$ is continuous and weakly increasing function of $\alpha$ and $p_1^{1-\alpha}$ is continuous and weakly decreasing function of $\alpha$ , thus the price ratio $\frac{p_2^{\alpha}}{p_1^{1-\alpha}}$ is continuous and weakly increasing from $\frac{p_2^0}{p_1^1}$ to $\frac{p_2^1}{p_1^0}$ as $\alpha$ rises from zero to one. Thus there must exist an optimal $\alpha^* \in [0,1]$ such that $\frac{p_2^{\alpha^*}}{p_1^{1-\alpha^*}} = \rho_l \in (\frac{p_2^0}{p_1^1}, \frac{p_2^1}{p_1^0})$ .

4.3 Comparison of Competition and Monopoly

After showing the existence of Nash equilibrium prices under a relaxed assumption, we can apply this NE outcome to predict the revenue and social welfare in the duopoly environment, and compare them with the corresponding results when one search engine monopolize the market. These comparative results would be instructive in practice considering the attempt of cooperation among large search companies such as Google and Yahoo!.⁹

We now turn to compare the prices under competition and monopoly. The main results are given in the following theorem.

Theorem 3. The equilibrium price in search engine 1 (or engine 2) under competition is no less (or larger) than the optimal price when engine 1 monopolizes the market.

Proof. Assuming all discount factors are randomly drawn in the range of $(\overline{\rho}, \underline{\rho})$ . According to equation (1) and proposition 1, the monopoly price $p^*$ satisfies the following condition:

$p^* \cdot S = m \cdot E(B) \cdot [1 - F(p^*)] \tag{21}$

Now we divide the total supply arbitrarily into $S_1 = \alpha S$ and $S_2 = (1 - \alpha)S$ , $\alpha \in [0, 1]$ for search engine 1 and 2. Suppose the optimal prices are $p_1$ and $p_2$ respectively and there are $m_1$ advertisers attracted by engine 1 and $m_2$ advertisers by engine 2 where $m_1 + m_2 = m$ , by applying equation (1) and proposition 1 we get the following equations for both search engines,

$p_1 \cdot \alpha S = m_1 \cdot E(B) \cdot [1 - F(p_1)] \tag{22}$

$p_2 \cdot (1 - \alpha)S = \sum_{i \in \mathcal{I}_2} E(B) \cdot \text{Prob}\{\rho_i v_i > p_2\}$ (23)

^9In June 2008, Google and Yahoo! announced an advertising cooperation agreement which was later on forced to be abandoned due to antitrust concern of government regulators. See the article “Antitrust Concerns Kill Yahoo-Google Ad Deal,” CNET, November 5, 2008 (http://news.cnet.com/8301-1023\_3-10082800-93.html).

since in equilibrium p2/p¹ = ν ∗ and for each advertiser i ∈ I² it holds that ρⁱ ≥ ν ∗ , we can derive that:

$Prob\{\rho_i v_i > p_2\} = Prob\{\rho_i v_i > \nu^* p_1\} \ge Prob\{v_i > p_1\} = 1 - F(p_1)$

Now the equation (23) would become:

$\nu^*(1-\alpha) \cdot p_1 S \ge m_2 \cdot E(B) \cdot [1 - F(p_1)] \tag{24}$

Summing over conditions (22) and (24), we have

$[\alpha + \nu^*(1 - \alpha)] \cdot p_1 S \ge m \cdot E(B) \cdot [1 - F(p_1)]$ (25)

Since ν ^∗ ≤ 1, we have α + ν ∗ (1 − α) ≤ α + (1 − α) = 1. Defining the following function first,

$h(p) \triangleq \frac{1 - F(p)}{p}$

which is strictly decreasing over p. Then by comparing conditions (21) and (25), we get

$h(p_1) \le \frac{[\alpha + \nu^*(1 - \alpha)] \cdot S}{m \cdot E(B)} \le \frac{S}{m \cdot E(B)} = h(p^*)$

we can infer that p¹ ≥ p ∗ .

Since from proposition 4 we have p¹ ≥ p² and 1 − F(p) is a monotonic decreasing function of p, equation (22) would become:

$p_2 \cdot \alpha S \le p_1 \cdot \alpha S \le m_1 \cdot E(B) \cdot [1 - F(p_2)] \tag{26}$

And since ρⁱ ≤ 1 for any i ∈ I2, we know that:

$Prob\{\rho_i v_i > p_2\} \le Prob\{v_i > p_2\} = 1 - F(p_2)$

thus equation (23) would become:

$p_2 \cdot (1 - \alpha)S \le m_2 \cdot E(B) \cdot [1 - F(p_2)]$ (27)

Summing over inequalities (26) and (27), we get

$p_2 S \le m \cdot E(B) \cdot [1 - F(p_2)]$

So we have:

$h(p_2) \ge \frac{S}{m \cdot E(B)} = h(p^*)$

which infers that p² ≤ p ∗ .

So in general, we have that p² ≤ p ^∗ ≤ p1.

One natural question to the duopoly market is that whether the company acting as a follower would merge with the leading company in the market. To answer it, we follow the conventional way of analyzing the total revenue and social welfare under competition and monopoly. At first glance, it seems that allowing the search engine with better technology to monopolize the market would generate higher total revenue and social welfare since it can provide better service for both advertisers and end users. However, it turns out the answer depends on the specific parameters of participants in the market. We summarize the comparison results of total revenue and social welfare under competition and monopoly in the following theorem.

Theorem 4. Whether monopoly would bring in higher total revenue and social welfare than competition depends on the specific parameters of advertisers in the advertising systems.

We can prove this theorem by constructing the counter-examples 2 and 3 as follows.

Example 2. Suppose there are two advertisers $\{1,2\}$ participating in the advertising system. The value, budget and discount factor of each advertiser are as follows: $v_1 = 1$ , $B_1 = 2$ , $\rho_1 = 1$ and $v_2 = 4$ , $B_2 = 2$ , $\rho_2 = 0$ . The total supply of advertising opportunity is S = 1.

Under monopoly, the optimal price $p^* = 2$ and the maximal revenue is $R(p^*) = p^* \cdot S = 2$ . For any $p < p^*$ , the corresponding revenue would be $R(p) = p \cdot S < p^* \cdot S = 2$ ; for any $p > p^*$ , since $v_1 < p$ which means advertiser 1 would not attend the system, R(p) is upper bounded by the budget of advertiser 2, i.e., $R(p) \le B_2 = 2$ . This analysis proves the optimality of $p^*$ and $R(p^*)$ .

Under competition, advertiser 1 would choose engine 2 since $\rho_1 = 1$ and advertiser 2 would choose the other engine since $\rho_2 = 0$ . We equally divide the supply into two parts: $S_1 = S_2 = 0.5$ . Now in engine 1, the optimal price is $p_1 = 4$ and $R_1 = p_1 \cdot S_1 = 2$ ; in engine 2, the optimal price is $p_2 = 1$ and $R_2 = p_2 \cdot S_2 = 0.5$ . And the price ratio $p_2/p_1 = 0.25$ is less than $\rho_1$ and greater than $\rho_2$ . Therefore in this example, the competition would bring in even higher total revenue $(R_1 + R_2 = 0.5)$

Example 3. There are still two advertisers in the system, with the following parameters: $v_1 = 2$ , $B_1 = 0.75$ , $\rho_1 = 0$ and $v_2 = 4$ , $B_2 = 0.25$ , $\rho_2 = 1$ . The total supply of advertising opportunity is still S = 1.

Under monopoly, the optimal price $p^* = 1$ and the allocation vector is $(q_1, q_2) = (0.75, 0.25)$ . Thus the social welfare would be $SW = v_1q_1 + v_2q_2 = 2.5$ .

Under competition, advertiser 1 would choose engine 1 since $\rho_1 = 0$ and advertiser 2 would choose the other engine since $\rho_2 = 1$ . We still divide the supply into $S_1 = S_2 = 0.5$ . Now in engine 1, the optimal price is $p_1 = 1.5$ and the social welfare $SW_1 = v_1q_1 = v_1S_1 = 0.75$ ; in engine 2, the optimal price is $p_2 = 0.5$ and $SW_2 = v_2q_2 = v_2S_2 = 2$ . And the price ratio $p_2/p_1 = 1/3$ is greater than $\rho_1$ and less than $\rho_2$ .

Therefore in this example, the competition would bring in even higher social welfare $(SW_1 + SW_2 = 2.75)$ than the monopoly (SW = 2.5).

Theorem 4 shows that there is no common conclusion on whether the existence of an inferior company (or product) in the market would raise or drive down the social welfare (or total revenue). Our observation here based on the particular search engine competition model coincides with the finding in the recent paper [12] that the viability of differentiated services scheme depends on the specific characteristics of users in the system. The services provided by search engine 1 and engine 2 can be regarded as the 1st and 2nd class services in [12] where the 1st class is usually charged higher price than the 2nd (analogous to our proposition that $p_1^{NE} \geq p_2^{NE}$ ).

Recall that our conclusions above are based on the ex post perspective which includes all possible instances of the competitive market. To show the more general ex ante results under common parameter setting of participants, we conduct the simulation in the next section.

5 Simulation Results and Observations

2.5) than the monopoly $(R(p^*) = 2)$ .

In this section we present some simulation results showing the effects of different parameters in our model. There are four major criteria we would like to explore in the model:

(a.1) Prices: We would like to compare the equilibrium prices of both engines with the monopoly price if there is only one search engine dominates the market. In the following section we denote (p1, p2) as the duopoly prices and p^M as the monopoly price.
(a.2) Revenues: It would be intriguing to study the comparative results of total revenues under competition and monopoly. The gap between revenues under competition and monopoly would serve as a signal of whether the leading company would like to propose a merger or acquisition to its competitor. A huge gap would infer that reaching certain cooperation agreement between the two competitors would significantly promote the revenues for both companies.
(a.3) Aggregate Utility of Advertisers: We compare the aggregate utility of advertisers to see whether monopoly would be detrimental to the interest of advertisers, and if so, how severe the loss would be. In particular, we examine the aggregate utility for brand advertisers who benefits from the relatively lower price of the inferior search engine in the duopoly market.
(a.4) Social Welfare: Social welfare can be regarded as the realized value of advertisers and is the benchmark for addressing the interest of the community as a whole. Under competition, the social welfare is computed according to the following equation:

$SW = \sum_{i \in \mathcal{I}_1} v_i q_i + \sum_{i \in \mathcal{I}_2} \rho_i v_i q_i. \tag{28}$

where qⁱ is amount of supply allocated to advertiser i.

In the following, we carry out a set of simulation to investigate the comparative results under different parameter settings. For each simulation setting, we randomly generate 5000 instances of parameters and calculate the average value of each criterion. The expected values from ex ante perspective can then be approximated by the average values of large amounts of ex post instances.

(1). Baseline Setting:

We consider two search engines equally dividing the market and the total supply is normalized to unity. Thus the supply of either search engine is S¹ = S² = 0.5. Advertisers’ values are uniformly distributed over (18, 20), and their budgets are also drawn from uniform distribution with expectation E(B) = 4. Discount factors of advertisers are uniformly distributed over (0.5, 0.9). Therefore there would be expectedly one half of advertisers with discount factors larger than the average value E(ρ) = 0.7, which we define as the brand advertisers.

The simulation results under baseline setting are presented in figure 6. We can make the following observations from figure 6(a)-(d):

As the number of advertisers increases, the prices, revenues and social welfare would all get raised except the aggregate utility of advertisers. This is because as more advertisers participate, the demand for the limited supply would get boosted, which would finally drive up the unit price per supply and raise the revenue of search engines. As the price rises, the utility of advertisers would keep decreasing as seen in figure 6(c). The social welfare can still be improved since when more advertisers appears, only those advertisers with higher values can stay and be allocated with certain amount of supply. Thus the realized values of advertisers would be larger and the social welfare get enhanced.

Figure 6: Baseline Setting

1. After the number of advertisers reaches about five, the growth of prices and revenues seems saturated: more advertisers would not bring evident enhancement in prices and revenues. This can be derived from our parameter setting: E(B)/E(v) = 4/19 ≈ 0.2 is the approximate amount of demand for each advertiser, and since the total supply is one, in expectation it would be sufficient for five advertisers to consume all the supply.
1. Figure 6(a) corresponds with theorem 3 that the monopoly price is smaller than the duopoly price p¹ of engine 1 and larger than price p² of engine 2. We further notice that the monopoly price is actually very close to p¹ but p² is much smaller than p1. This is because the monopoly engine and engine 1 in competition face advertisers with the same distribution of values. Recall that value is the maximal willingness to pay for advertisers, thus when there are too many advertisers competing with each other, the price would approach the maximal possible value, which is 20 according to the distribution range. However, for search engine 2, the actual values of advertisers are the original values discounted by ρ. The lower ρ is, the larger the gap between p¹ and p² would be.
1. Figure 6(b) shows that revenue of search engine 1 is larger than that of engine 2. This can be easily deducted since the revenue of each engine is R¹ = p¹ ·S1, R² = p² ·S² and we have p¹ > p2, S¹ = S2. As we have mentioned, the monopoly price p^M is approximately equal to p1. Therefore the monopoly revenue can be denoted as follows:

$R_{M} = p_{M} \cdot S \approx p_{1} \cdot S = p_{1} \cdot S_{1} + p_{1} \cdot S_{2}$

$= R_{1} + \frac{p_{1}}{p_{2}} R_{2} = R_{1} + \frac{R_{2}}{\rho^{*}} > R_{1} + R_{2}$ (29)

where ρ ∗ is the discount factor of the indifferent advertisers which is always less than one. This inequality explains the gap between total revenue under competition and monopoly in figure 6(b).

1. The utility of advertisers depends on two factors: the value and the price. Compared with the monopoly, under competition a portion of advertisers could enjoy a relatively lower price which would result in higher utility; at the same time, due to the effect of ρ, the values of advertisers in engine 2 get discounted which would cause lower utility. When the positive factor of lower price dominate the negative factor of lower value, the utility under competition would be greater and vice versa. Since in our baseline setting we set a relatively large ρ, the negative factor would be small and advertisers in engine 2 can benefit from the lower price. This conjecture can be verified in figure 6(c). Since in average brand advertisers account for half of all advertisers, in monopoly the utility of brand advertisers is always half of the utility of all advertisers as shown in figure 6(c). However, under competition the brand advertisers would benefit more than the rest advertisers since they have higher discount factors which means lower negative effect on values but confronting a lower price in engine 2.
1. Figure 6(d) indicates that the social welfare under competition is lower than that under monopoly since the realized values in equation (28) get discounted due to the factor ρ.

(2). Effect of Supplies

We now change the supplies to S¹ = 0.9 and S² = 0.1 while all other parameters remain the same. The simulation results are presented in figure 7.

In this setting one search engine plays the leading role in the market and the follower can only take a small fraction of market share. This assumption is more realistic considering the current dominant position of Google in most areas of the world. Figure 7(a) shows little difference with the corresponding price curves in figure 6(a) since all prices approach the maximal possible value when there are sufficient number of advertisers in the market. Since the supply of engine 2 decreases, the revenue of engine 2 which is denoted by $R_2 = p_2 \cdot S_2$ would also drop. According to equation (29), the gap of the total revenues is $R_M - (R_1 + R_2) \approx (\frac{1}{\rho^*} - 1)R_2$ . Therefore when $R_2$ is small, the gap would also be negligible. This is verified by figure 7(b). This result also demonstrates that even when the follower takes a small portion of market share and provides service of relatively lower quality, it can still make nontrivial profit through competition and survive in the market. In figure 7(c), the gain of aggregate utility under competition is tiny compared with that under monopoly since engine 2 can only provide limited supply (10% of the total supply) and only very few of advertisers can take advantage of it. Figure 7(d) shows that the loss of social welfare under competition is very small since only 10% of the total supply is of lower quality, i.e., the second term in equation (28) is insignificant.

(3). Effect of Discount Factors

We now turn to investigate the effect of technology gap between two search engines. Let the discount factors be drawn uniformly on (0.1, 0.5) and all other parameters are the same as the baseline setting.

As figure 8(a) shows, the equilibrium price $p_1$ of engine 1 and the monopoly price $p_M$ are still close to the maximal value of advertisers and $p_2$ approaches the maximal discounted value $\rho v$ . As $\rho$ decreases, the price of engine 2 also diminishes compared with $p_2$ in figure 6(a) and 7(a).

Since the revenue $R = p \cdot S$ and from above analysis we know $p_1$ has little change and $p_2$ diminishes, the revenue $R_1$ of engine 1 would stay almost the same while $R_2$ reduces as shown in figure 8(b). Since we have also mentioned that the gap between the total revenues approximates to $R_M - (R_1 + R_2) \approx (\frac{1}{\rho^*} - 1)R_2$ , when $\rho$ is small, the gap would become larger. This can be easily seen by comparing the corresponding revenue curves in figure 6(b) and figure 8(b).

The aggregate utilities of advertisers in monopoly are the same in figure 6(c) and figure 8(c); however, the aggregate utilities under competition in figure 8(c) is much smaller than those in figure 6(c) due to the negative effect of $\rho$ on advertisers’ values. In figure 8(c) we see that there is certain intersection between utility under competition and monopoly. When there are only a few of advertisers, the prices are still low and the main factor affecting utility is the value. Under competition the existence of $\rho$ would drive down advertisers’ values and thereby results in lower aggregate utility. As the number of advertisers increases, the monopoly price $p_M$ would approach the maximal value $v_{max} = 20$ and the aggregate utility would gradually reduce to zero. However, even when $p_1$ and $p_M$ approach 20, the rest of advertisers whose discount factors are larger than the equilibrium price ratio $\rho^* = p_2/p_1$ can still obtain nontrivial utility which can be approximated as $(\bar{\rho}v - p_2)S_2 \approx (\bar{\rho}v - \rho^*v)S_2$ ( $\bar{\rho}$ denotes the average value of advertisers with discount factors larger than the price ratio $\rho^*$ ).

^10In the United States around 72 percent of the total search volumes are conducted on Google while Yahoo and Bing jointly account for about 25 percent. Source from “Top 20 Sites & Engines,” Hitwise, May 20, 2010 (http://www.hitwise.com/us/datacenter/main/dashboard-10133.html). In some other countries like France, UK and Germany, Google even possessed a market share of over 90 percent. Source from the article “Google’s Market Share in Your Country,” March 13, 2009 (http://googlesystem.blogspot.com/2009/03/googles-market-share-in-your-country.html).

Figure 7: When Supplies Change To S¹ : S² = 9 : 1

Figure 8(d) displays the hug gap between social welfare under competition and monopoly. Since half of the supply (S² = 0.5) is allocated to advertisers with discount factors less than 0.5, the realized values in equation (28) would become significantly smaller than social welfare under monopoly.

6 Conclusion and Future Work

We propose an analytical framework to model the interaction of publishers, advertisers and users under monopoly and duopoly scenarios. For monopoly market, we can give the analytical results of price and revenue for both ex ante and ex post case. For duopoly market, we formulate a threestage dynamic game to model the search engines’ competition for both users and advertisers and prove the existence of Nash equilibrium from ex post perspective. To see the long-term effect of competition from ex ante perspective, we carry out computer simulations for different settings of participants’ parameters. The comparative results of revenues and social welfare under competition and monopoly are then presented and discussed extensively in the paper. Our analysis could provide some insight in regulating the search engine market and protecting the interests of advertisers and

Figure 8: When ρ Belongs to (0.1, 0.5)

end users. Although the cooperation between search engines can probably bring more total revenues, advertisers and users may be averse to such plan which eliminates their freedom to choose from diverse services provided by different search companies.

There are several possible ways to extend our work. Throughout our paper, we implicitly assume that advertisers would reveal their true parameters such as values and budgets to the search engines. Since our framework is by no means strategy-proof, how would rational advertisers’ strategies affect our conclusions would be an interesting question for further investigation. Another non-trivial problem is how to associate our analytical result of revenue from one particular keyword with the practical revenue of an industrial search company which gathers from numerous keywords queried by end users everyday. Besides, to be in line with the practical advertising system nowadays, we will consider incorporating the quality factor of advertisement for the revenue-ranking rule as well as the generalized second-price auction prevailing in major search engines. Finally, it would be intriguing to extend our model for multiple search engines scenario besides the basic duopoly scenario.

References

[1] Interactive Advertising Bureau, “IAB Internet Advertising Revenue Report,” April 7, 2010. Available Online: http://www.iab.net/media/file/IAB-Ad-Revenue-Full-Year-2009.pdf.
[2] B. Jansen and T. Mullen, “Sponsored Search: An Overivew of the Concept, History, and Technology,” Int. J. Electronic Business Vol. 6, No. 2, pages 114 - 131, 2008.
[3] L. Ausubel, “An Efficient Ascending-Bid Auction for Multiple Objects,” American Economic Review 94(5), pages 1452 - 1475, Dec 2004.
[4] R. Pollock, “Is Google The Next Microsoft? Competition, Welfare and Regulation in Internet Search,” Cambridge Working Papers in Economics, April 2009.
[5] G. Sapi and I. Suleymanova, “Beef Up Your Competitor: A Model of Advertising Cooperation Between Internet Search Engines,” DIW Berlin Discussion Paper No. 870, March 2009.
[6] S. Lahaie, D. Pennock, A. Saberi, R. Vohra, “Sponsored Search Auctions,” Chapter 28 of Algorithm Game Theory, Cambridge University Press, pages 699 - 715, Sep 2007.
[7] H. Hotelling, “Stability in Competition,” Economic Journal 39, pages 41 57, 1929.
[8] S. Anderson, J. Goeree and R. Ramer, “Location, Location, Location,” Journal of Economic Theory 77, pages 102 - 127, 1997.
[9] M. Frutos, H. Hamoudi, X. Jarque, “Equilibrium Existence In The Circle Model with Linear Quadratic Transport Cost,” Regional Science and Urban Economics 29, pages 605 - 615, 1999.
[10] S. Brenner, “Determinants of Product Differentiation: A Survey,” Humboldt University, Mimeo, 2001.
[11] M. Benisch, N. Sadeh, T. Sandholm, “Methodology for Designing Reasonably Expressive Mechanisms with Application to Ad Auctions,” IJCAI-09, pages 46 - 52, 2009.
[12] C. Chau, Q. Wang, D. Chiu, “On the Viability of Paris Metro Pricing for Communication and Service Networks,” IEEE INFOCOM 2010, pages 1 - 9, March 2010.
[13] B. Edelman, M. Ostrovsky, M. Schwarz, “Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords,” American Economic Review 97(1), pages 242 - 259, March 2007.
[14] H. Varian, “Position Auctions,” International Journal of Industrial Organization 25, pages 1163 - 1178, 2007.
[15] I. Ashlagi, D. Monderer, M. Tennenholtz, “Competing Ad Auctions,” Fourth Workshop on Ad Auctions, Chicago, July 2008.
[16] D. Liu, J. Chen, A. Whinston, “Competing Keyword Auctions,” Fourth Workshop on Ad Auctions, Chicago, July 2008.
[17] J. He and J. Rexford, “Towards Internet-wide Multipath Routing,” IEEE Network Magazine 22(2), pages 16 - 21, March 2008.
[18] T. Roughgarden and E. Tardos, “How Bad Is Selfish Routing?” ´ JACM 49(2), pages 236 259, 2002.
[19] C. Borgs, J. Chayes, N. Immorlica, M. Mahdian, A. Saberi, “Multi-unit Auctions with Budgetconstrained Bidders,” EC’05, Vancouver, June 2005.
[20] G. Aggarwal, A. Goel, R. Motwani, “Truthful Auctions for Pricing Search Keywords,” EC’06, Michigan, June 2006.
[21] Y. Zhou, R. Lukose, “Vindictive Bidding in Keyword Auctions,” EC’07, Minnesota, August 2007.
[22] A. Goel, K. Munagala, “Hybrid Keyword Search Auctions,” WWW’09, Madrid, April 2009.
[23] D. Martin, J. Gehrke, J. Halpern, “Toward Expressive and Scalable Sponsored Search Auction,” International Conference on Data Engineering, pages 237 - 246, 2008.
[24] E. Dar, M. Kearns, J. Wortman, “Sponsored Search with Contexts,” WINE 2007, pages 312 317, 2007.
[25] Z. Abrams, A. Ghosh, E. Vee, “Cost of Conciseness in Sponsored Search Auctions,” WINE 2007, pages 326 - 334, 2007.
[26] D. Kempe, M. Mahdian, “A Cascade Model for Externalities in Sponsored Search,” Fourth Workshop on Ad Auctions, Chicago, July 2008.
[27] G. Aggarwal, J. Feldman, S. Muthukrishnan, M. P´al, “Sponsored Search Auctions with Markovian Users,” Fourth Workshop on Ad Auctions, Chicago, July 2008.
[28] A. Das, I. Giotis, A. Karlin, C. Mathieu, “On the Effects of Competing Advertiserments in Keyword Auctions,” EC’08, Chicago, July 2008.
[29] A. Ghosh, A. Sayedi, “Expressive Auctions for Externalities in Online Advertising,” WWW 2010, Raleigh, April 2010.