Database Reference
In-Depth Information
We are thus looking for the
j
such that log
e
N
−log
e
(
N
−
j
) = 1, approximately. If we re-
place log
e
N
− log
e
(
N
−
j
) by the equivalent log
e
N/
(
N
−
j
) and exponentiate both sides of
the equation log
e
N/
(
N
−
j
) = 1, we get
N/
(
N
−
j
) =
e
. Solving this equation for
j
, we get
as the approximate value of
j
for which all advertisers are either out of budget or do not bid
on any of the remaining queries. Thus, the approximate revenue obtained by the Balance
Algorithm is that is, the queries of the first
j
rounds. Therefore, the competitive ratio
is or approximately 0.63.
8.4.7
The Generalized Balance Algorithm
The Balance Algorithm works well when all bids are 0 or 1. However, in practice, bids can
be arbitrary, and with arbitrary bids and budgets Balance fails to weight the sizes of the
bids properly. The following example illustrates the point.
EXAMPLE
8.9 Suppose there are two advertisers
A
1
and
A
2
, and one query
q
. The bids on
q
and budgets are:
If there are 10 occurrences of
q
, the optimum off-line algorithm will assign them all to
A
2
and gain revenue 100. However, because
A
1
's budget is larger, Balance will assign all
ten queries to
A
1
for a revenue of 10. In fact, one can extend this idea easily to show that
for situations like this one, there is no competitive ratio higher than 0 that holds for the Bal-
ance Algorithm.
□
In order to make Balance work in more general situations, we need to make two modi-
fications. First, we need to bias the choice of ad in favor of higher bids. Second, we need
to be less absolute about the remaining budget. Rather, we consider the fraction of the
budgets remaining, so we are biased toward using some of each advertiser's budget. The
latter change will make the Balance Algorithm more “risk averse”; it will not leave too
much of any advertiser's budget unused. It can be shown (see the chapter references) that
the following generalization of the Balance Algorithm has a competitive ratio of 1 − 1
/e
=
0
.
63.
• Suppose that a query
q
arrives, advertiser
A
i
has bid
x
i
for this query (note that
x
i
could be 0). Also, suppose that fraction
f
i
of the budget of
A
i
is currently unspent.
