Database Reference
In-Depth Information
Matching Bids and Search Queries
: In our simplified model, advertisers bid on sets of words, and an advertiser's
bid is eligible to be shown for search queries that have exactly the same set of words as the advertiser's bid. In reality,
Google, Yahoo!, and Microsoft all offer advertisers a feature known as
broad matching
, where an ad is eligible to be
shown for search queries that are inexact matches of the bid keywords. Examples include queries that include a subset
or superset of keywords, and also queries that use words with very similar meanings to the words the advertiser bid
on. For such broad matches, search engines charge the advertiser based on complicated formulas taking into account
how closely related the search query is to the advertiser's bid. These formulas vary across search engines and are not
made public.
Charging Advertisers for Clicks
: In our simplified model, when a user clicks on an advertiser's ad, the advertiser is
charged the amount they bid. This policy is known as a
first-price auction
. In reality, search engines use a more com-
plicated system known as a
second-price auction
, where each advertiser pays approximately the bid of the advertiser
who placed immediately behind them in the auction. For example, the first-place advertiser for a search might pay the
bid of the advertiser in second place, plus one cent. It has been shown that second-price auctions are less susceptible
to being gamed by advertisers than first-price auctions and lead to higher revenues for the search engine.
8.4.5
A Lower Bound on Competitive Ratio for Balance
In this section we shall prove that in the simple case of the Balance Algorithm that we are
considering, the competitive ratio is 3/4. Given
Example 8.8
, we have only to prove that
the total revenue obtained by the Balance Algorithm is at least 3/4 of the revenue for the
optimum off-line algorithm. Thus, consider a situation in which there are two advertisers,
A
1
and
A
2
, each with a budget of
B
. We shall assume that each query is assigned to an ad-
vertiser by the optimum algorithm. If not, we can delete those queries without affecting the
revenue of the optimum algorithm and possibly reducing the revenue of Balance. Thus, the
lowest possible competitive ratio is achieved when the query sequence consists only of ads
assigned by the optimum algorithm.
We shall also assume that both advertisers' budgets are consumed by the optimum al-
gorithm. If not, we can reduce the budgets, and again argue that the revenue of the optimum
algorithm is not reduced while that of Balance can only shrink. That change may force us
to use different budgets for the two advertisers, but we shall continue to assume the budgets
are both
B
. We leave as an exercise the extension of the proof to the case where the budgets
of the two advertisers are different.
Figure 8.3
suggests how the 2
B
queries are assigned to advertisers by the two algorithms.
In (a) we see that
B
queries are assigned to each of
A
1
and
A
2
by the optimum algorithm.
Now, consider how these same queries are assigned by Balance. First, observe that Balance
must exhaust the budget of at least one of the advertisers, say
A
2
. If not, then there would be
some query assigned to neither advertiser, even though both had budget. We know at least
one of the advertisers bids on each query, because that query is assigned in the optimum
algorithm. That situation contradicts how Balance is defined to operate; it always assigns a
query if it can.
