Database Reference
In-Depth Information
8.4.6
The Balance Algorithm with Many Bidders
When there are many advertisers, the competitive ratio for the Balance Algorithm can be
under 3/4, but not too far below that fraction. The worst case for Balance is as follows.
(1) There are
N
advertisers,
A
1
, A
2
, . . . , A
N
.
(2) Each advertiser has a budget
B
=
N
!.
(3) There are
N
queries
q
1
, q
2
, . . . , q
N
.
(4) Advertiser
A
i
bids on queries
q
1
, q
2
, . . . , q
i
and no other queries.
(5) The query sequence consists of
N
rounds. The
i
th round consists of
B
occurrences of
query
q
i
and nothing else.
The optimum off-line algorithm assigns the
B
queries
q
i
in the
i
th round to
A
i
for all
i
.
Thus, all queries are assigned to a bidder, and the total revenue of the optimum algorithm
is
NB
.
However, the Balance Algorithm assigns each of the queries in round 1 to the
N
advert-
isers equally, because all bid on
q
1
, and the Balance Algorithm prefers the bidder with the
greatest remaining budget. Thus, each advertiser gets
B/N
of the queries
q
1
. Now consider
the queries
q
2
in round 2. All but
A
1
bid on these queries, so they are divided equally among
A
2
through
A
N
, with each of these
N
− 1 bidders getting
B/
(
N
− 1) queries. The pattern,
suggested by
Fig. 8.4
, repeats for each round
i
= 3
,
4
, . . .
, with
A
i
through
A
N
getting
B/
(
N
−
i
) queries.
Figure 8.4
Apportioning queries to
N
advertisers in the worst case
However, eventually, the budgets of the higher-numbered advertisers will be exhausted.
That will happen at the lowest round
j
such that
that is,
Euler showed that as
k
gets large, approaches log
e
k
. Using this observation, we can
approximate the above sum as log
e
N
− log
e
(
N
−
j
).