Database Reference
In-Depth Information
Let Ψ
i
=
x
i
(1 −
e
−f
i
). Then assign
q
to the advertiser
A
i
such that Ψ
i
is a maximum.
Break ties arbitrarily.
EXAMPLE
8.10 Consider how the generalized Balance Algorithm would work on the data
of
Example 8.9
.
For the first occurrence of query
q
,
Ψ
1
= 1 × (1 −
e
−
1
)
since
A
1
has bid 1, and fraction 1 of
A
1
's budget remains. That is,
Ψ
1
= 1 − 1
/e
= 0
.
63
On the other hand, Ψ
2
= 10 × (1 −
e
−
1
) = 6
.
3. Thus, the first
q
is awarded to
A
2
.
The same thing happens for each of the
q
s. That is, Ψ
1
stays at 0.63, while Ψ
2
decreases.
However, it never goes below 0.63. Even for the 10th
q
, when 90% of
A
2
's budget has
= 1 +
x
+
x
2
/
2! +
x
3
/
3! + · · ·. Thus,
or approximately,
e
−
1
/
10
= 0
.
905. Thus, Ψ
2
= 10 × 0
.
095 = 0
.
95.
□
We leave unproved the assertion that the competitive ratio for this algorithm is 1−1
/e
.
We also leave unproved an additional surprising fact: no on-line algorithm for the adwords
problem as described in this section can have a competitive ratio above 1 − 1
/e
.
8.4.8
Final Observations About the Adwords Problem
The Balance Algorithm, as described, does not take into account the possibility that the
click-through rate differs for different ads. It is simple to multiply the bid by the click-
through rate when computing the Ψ
i
, and doing so will maximize the expected revenue. We
can even incorporate information about the click-through rate for each ad on each query for
which a nonzero amount has been bid. When faced with the problem of allocating a partic-
ular query
q
, we incorporate a factor that is the click-through rate for that ad on query
q
,
when computing each of the Ψs.
Another issue we must consider in practice is the historical frequency of queries. If, for
example, we know that advertiser
A
i
has a budget sufficiently small that there are sure to be
enough queries coming later in the month to satisfy
A
i
's demand, then there is no point in
boosting Ψ
i
if some of
A
i
's budget has already been expended. That is, maintain Ψ
i
=
x
i
(1