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 ).
Search WWH ::




Custom Search