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
already been used, Ψ 2 = 10×(1− e 1 / 10 ). Recall ( Section 1.3.5 ) the Taylor expansion for e x
= 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
Search WWH ::




Custom Search