Databases Reference
In-Depth Information
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.
2
8.4.5
A Lower Bound on Competitive Ratio for Balance
In this section we shall prove that in the simple case of the Balance Algorithm
that we are considering, the competitive ratio is 3/4. Given Example 8.8, we
have only to prove that the total revenue obtained by the Balance Algorithm is
at least 3/4 of the revenue for the optimum off-line algorithm. Thus, consider a
situation in which there are two advertisers, A
1
and A
2
, each with a budget of
B. We shall assume that each query is assigned to an advertiser by the optimum
algorithm. If not, we can delete those queries without affecting the revenue of
the optimum algorithm and possibly reducing the revenue of Balance. Thus, the
lowest possible competitive ratio is achieved when the query sequence consists
only of ads assigned by the optimum algorithm.
We shall also assume that both advertisers' budgets are consumed by the
optimum algorithm. If not, we can reduce the budgets, and again argue that
the revenue of the optimum algorithm is not reduced while that of Balance can
only shrink. That change may force us to use different budgets for the two
advertisers, but we shall continue to assume the budgets are both B. We leave
as an exercise the extension of the proof to the case where the budgets of the
two advertisers are different.
Figure 8.3 suggests how the 2B queries are assigned to advertisers by the
two algorithms. In (a) we see that B queries are assigned to each of A
1
and A
2
by the optimum algorithm. Now, consider how these same queries are assigned
by Balance. First, observe that Balance must exhaust the budget of at least one
of the advertisers, say A
2
. If not, then there would be some query assigned to
neither advertiser, even though both had budget. We know at least one of the
advertisers bids on each query, because that query is assigned in the optimum
algorithm. That situation contradicts how Balance is defined to operate; it
always assigns a query if it can.
Thus, we see in Fig. 8.3(b) that A
2
is assigned B queries. These queries
could have been assigned to either A
1
or A
2
by the optimum algorithm. We
