Database Reference
In-Depth Information
and we could then assign ads to the queries in a way that maximized both the revenue to the
search engine and the number of impressions that each advertiser got. The problem with
off-line algorithms is that most queryers don't want to wait a month to get their search res-
ults.
Thus, we must use an on-line algorithm to assign ads to search queries. That is, when a
search query arrives, we must select the ads to show with that query immediately. We can
use information about the past, e.g., we do not have to show an ad if the advertiser's budget
has already been spent, and we can examine the
click-through rate
(fraction of the time the
ad is clicked on when it is displayed) that an ad has obtained so far. However, we cannot
use anything about future search queries. For instance, we cannot know whether there will
be lots of queries arriving later and using search terms on which this advertiser has made
higher bids.
EXAMPLE
8.1 Let us take a very simple example of why knowing the future could help. A
manufacturer
A
of replica antique furniture has bid 10 cents on the search term “chester-
field” and “sofa.” Both have monthly budgets of $100, and there are no other bidders on
either of these terms. It is the beginning of the month, and a search query “chesterfield” has
just arrived. We are allowed to display only one ad with the query.
The obvious thing to do is to display
B
's ad, because they bid more. However, suppose
there will be lots of search queries this month for “sofa,” but very few for “chesterfield.”
Then
A
will never spend its $100 budget, while
B
will spend its full budget even if we give
the query to
A
. Specifically, if there will be at least 500 more queries for either “sofa” or
“chesterfield,” then there is no harm, and potentially a benefit, in giving the query to
A
. It
will still be possible for
B
to spend its entire budget, while we are increasing the amount
of
A
's budget that will be spent. Note that this argument makes sense both from the point
of view of the search engine, which wants to maximize total revenue, and from the point
of view of both
A
and
B
, who presumably want to get all the impressions that their budgets
allow.
If we could know the future, then we would know how many more “sofa” queries and
how many more “chesterfield” queries were going to arrive this month. If that number is
below 500, then we want to give the query to
B
to maximize revenue, but if it is 500 or
more, then we want to give it to
A
. Since we don't know the future, an on-line algorithm
cannot always do as well as an off-line algorithm.
□
