Databases Reference
In-Depth Information
Adwords Aspects not in Our Model
There are several ways in which the real AdWords system differs from the
simplified model of this section.
Matching Bids and Search Queries: In our simplified model, advertis-
ers 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 complicated 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.
Let the sequence of queries be xxyy. The greedy algorithm is able to allocate
the first two x's to B, whereupon there is no one with an unexpended budget to
pay for the two y's. The revenue for the greedy algorithm in this case is thus 2.
However, the optimum off-line algorithm will allocate the x's to A and the y's
to B, achieving a revenue of 4. The competitive ratio for the greedy algorithm
is thus no more than 1/2. We can argue that on any sequence of queries the
ratio of the revenues for the greedy and optimal algorithms is at least 1/2, using
essentially the same idea as in Section 8.3.3.
2
8.4.4
The Balance Algorithm
There is a simple improvement to the greedy algorithm that gives a competitive
ratio of 3/4 for the simple case of Section 8.4.3. This algorithm, called the
Balance Algorithm, assigns a query to the advertiser who bids on the query and
has the largest remaining budget. Ties may be broken arbitrarily.
