Database Reference
In-Depth Information
discuss a greedy algorithm called “Balance” that offers a good competitive ratio. We ana-
lyze this algorithm for a simplified case of the adwords problem.
8.4.1
History of Search Advertising
Around the year 2000, a company called Overture (later bought by Yahoo!) introduced a
new kind of search. Advertisers bid on
keywords
(words in a search query), and when a
user searched for that keyword, the links to all the advertisers who bid on that keyword are
displayed in the order highest-bid-first. If the advertiser's link was clicked on, they paid
what they had bid.
That sort of search was very useful for the case where the search queryer really was look-
ing for advertisements, but it was rather useless for the queryer who was just looking for
information. Recall our discussion in
Section 5.1.1
about the point that unless a search en-
gine can provide reliable responses to queries that are for general information, no one will
want to use the search engine when they are looking to buy something.
Several years later, Google adapted the idea in a system called
Adwords
. By that time,
the reliability of Google was well established, so people were willing to trust the ads they
were shown. Google kept the list of responses based on PageRank and other objective cri-
teria separate from the list of ads, so the same system was useful for the queryer who just
wanted information as well as the queryer looking to buy something.
The Adwords system went beyond the earlier system in several ways that made the se-
lection of ads more complex.
(1) Google would show only a limited number of ads with each query. Thus, while Over-
ture simply ordered all ads for a given keyword, Google had to decide which ads to
show, as well as the order in which to show them.
(2) Users of the Adwords system specified a budget: the amount they were willing to pay
for all clicks on their ads in a month. These constraints make the problem of assigning
ads to search queries more complex, as we hinted at in
Example 8.1
.
(3) Google did not simply order ads by the amount of the bid, but by the amount they ex-
pected to receive for display of each ad. That is, the click-through rate was observed
for each ad, based on the history of displays of that ad. The value of an ad was taken
to be the product of the bid and the click-through rate.
