Database Reference
In-Depth Information
Figure 8.3
Illustration of the assignments of queries to advertisers in the optimum and Balance algorithms
use
y
as the number of queries assigned to
A
1
and
x
as
B
−
y
. It is our goal to show
y
≥
x
.
That inequality will show the revenue of Balance is at least 3
B/
2, or 3/4th the revenue of
the optimum algorithm.
We note that
x
is also the number of unassigned queries for the Balance Algorithm, and
that all the unassigned queries must have been assigned to
A
2
by the optimum algorithm.
The reason is that
A
1
never runs out of budget, so any query assigned by the optimum al-
gorithm to
A
1
is surely bid on by
A
1
. Since
A
1
always has budget during the running of the
Balance Algorithm, that algorithm will surely assign this query, either to
A
1
or to
A
2
.
There are two cases, depending on whether more of the queries that are assigned to
A
1
by the optimum algorithm are assigned to
A
1
or
A
2
by Balance.
(1) Suppose at least half of these queries are assigned by Balance to
A
1
. Then
y
≥
B/
2, so
surely
y
≥
x
.
(2) Suppose more than half of these queries are assigned by Balance to
A
2
. Consider the
last of these queries
q
that is assigned to
A
2
by the Balance Algorithm. At that time,
A
2
must have had at least as great a budget available as
A
1
, or else Balance would have
assigned query
q
to
A
1
, just as the optimum algorithm did. Since more than half of the
B
queries that the optimum algorithm assigns to
A
1
are assigned to
A
2
by Balance, we
know that when
q
was assigned, the remaining budget of
A
2
was less than
B/
2. There-
fore, at that time, the remaining budget of
A
1
was also less than
B/
2. Since budgets
only decrease, we know that
x < B/
2. It follows that
y > x
, since
x
+
y
=
B
.
We conclude that
y
≥
x
in either case, so the competitive ratio of the Balance Algorithm is
3/4.
