Database Reference
In-Depth Information
The greedy algorithm picks, for each search query, any advertiser who has bid 1 for that
query. The competitive ratio for this algorithm is 1/2, as the following example shows.
EXAMPLE
8.7 Suppose there are two advertisers
A
and
B
, and only two possible queries,
x
and
y
. Advertiser
A
bids only on
x
, while
B
bids on both
x
and
y
. The budget for each ad-
vertiser is 2. Notice the similarity to the situation in
Example 8.1
; the only differences are
the fact that the bids by each advertiser are the same and the budgets are smaller here.
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 al-
gorithm 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
.
□
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.
EXAMPLE
8.8 Consider the same situation as in
Example 8.7
. The Balance Algorithm can
assign the first query
x
to either
A
or
B
, because they both bid on
x
and their remaining
budgets are the same. However, the second
x
must be assigned to the other of
A
and
B
,
because they then have the larger remaining budget. The first
y
is assigned to
B
, since it
has budget remaining and is the only bidder on
y
. The last
y
cannot be assigned, since
B
is
out of budget, and
A
did not bid. Thus, the total revenue for the Balance Algorithm on this
data is 3. In comparison, the total revenue for the optimum off-line algorithm is 4, since it
can assign the
x
s to
A
and the
y
s to
B
. Our conclusion is that, for the simplified adwords
problem of
Section 8.4.3
,
the competitive ratio of the Balance Algorithm is no more than
3/4. We shall see next that with only two advertisers, 3/4 is exactly the competitive ratio,
although as the number of advertisers grows, the competitive ratio lowers to 0.63 (actually
1 − 1
/e
) but no lower.
□
Adwords Aspects not in Our Model
There are several ways in which the real AdWords system differs from the simplified model of this section.