Database Reference
In-Depth Information
−
e
−
1
) as long as we can expect that there will be enough queries remaining in the month
to give
A
i
its full budget of ads. This change can cause Balance to perform worse if the
sequence of queries is governed by an adversary who can control the sequence of queries.
Such an adversary can cause the queries
A
i
bid on suddenly to disappear. However, search
engines get so many queries, and their generation is so random, that it is not necessary in
practice to imagine significant deviation from the norm.
8.4.9
Exercises for Section 8.4
EXERCISE
8.4.1 Using the simplifying assumptions of
Example 8.7
,
suppose that there are
three advertisers,
A
,
B
, and
C
. There are three queries,
x
,
y
, and
z
. Each advertiser has a
budget of 2. Advertiser
A
bids only on
x
;
B
bids on
x
and
y
, while
C
bids on
x
,
y
, and
z
. Note
that on the query sequence
xxyyzz
, the optimum off-line algorithm would yield a revenue
of 6, since all queries can be assigned.
!
(a) Show that the greedy algorithm will assign at least 4 of these 6 queries.
!!
(b) Find another sequence of queries such that the greedy algorithm can assign as few
as half the queries that the optimum off-line algorithm assigns on that sequence.
have unequal budgets.
to make the competitive ratio come out as close to 0 as you like.
8.5 Adwords Implementation
While we should now have an idea of how ads are selected to go with the answer to a search
query, we have not addressed the problem of finding the bids that have been made on a giv-
en query. As long as bids are for the exact set of words in a query, the solution is relatively
easy. However, there are a number of extensions to the query/bid matching process that are
not as simple. We shall explain the details in this section.
