Hello everyone.
Welcome back to Mining
of Massive Datasets.
We're going to continue our discussion
of the adwords problem with a look at
the BALANCE Algorithm.
The BALANCE Algorithm is a way to deal
with the problem of limited advertiser
budgets in the context
of the adword problem.
To refresh your memory on
what the adword problem is,
we are given a set of bids by
advertisers for search queries.
And a click-through rate for
each advertiser-query pair.
And in addition, a budget for
each advertiser.
The budget could be for a day, or a month,
or a year, or some period like this.
Let's just assume that
it's a daily budget.
Finally, there's a limit on the number
of ads to be displayed with each
search query.
This limit could be one, or two, or three.
Now, we need to respond to each search
query with a set of advertisers such that,
the size of the advertiser set is no
larger than the limits of the number of
ads per query.
Each advertiser who we show has
actually bid on the search query.
And finally, if the ad is shown and
somebody clicks on the ad,
then the advertiser should have
enough budget left over to pay for
the ad when it's actually clicked upon.
So we don't actually want to show ads from
advertisers who don't have a budget to
pay for
the clicks if they do actually happen.
Because that's not a bidding
proposition for us.
So the question is how
do we deal with the,
the issue of limited advertiser budget,
that we don't want to show, or
can not show an ad from an advertiser
whose budget has been exhausted.
Now let's first study the problem
in in a simplified version.
The simplified version that we're going to
look at has only one ad shown for
each query, and
all advertisers have the same budget B.
We're also can assume that all ads
are equally likely to be clicked and
all have the same value of one.
Another way of thinking about this is that
the expected revenue from each ad which is
product of the click-through rate and
the bid is equal to one.
Now, the simplest algorithm is the greedy
algorithm, which we've already looked at.
And the greedy algorithm picks any
advertiser who has bid one for
a query when that query shows up.
And it's easy to show that
the competitive ratio of
the greedy algorithm is actually a half.
But here's a bad scenario for
the greedy algorithm.
Here, here there are two advertisers,
A and B.
And let's say A bids on query x.
B bids on queries x and y.
And both have budgets of $4.
Now, the query stream that comes in is,
x, x, x, x, y, y, y, y.
That's four x's, followed by four y's.
Now when these query queries come in the
greedy algorithm exceeds the first x and
notices that we have both A and
B who have bid for query x.
And let's say the greedy algorithm
arbitrarily assigns query one
to to advertiser B.
And then, the second x comes in, and
let's say the greedy algorithm
assigns that to B as well, and so on.
The greedy algorithm might, for instance
end up assigning all the first four
x queries to advertiser B,
none to advertiser A.
As a result, when the first y query
comes in, B's budget of $4 is
already exhausted and therefore,
no ads can be shown for the y queries.
As a result the greedy algorithms
revenue is is only $4.
Whereas the optimal allocation in
this case, as it's easy to see, is to
show A's ad for the first four queries,
and then B's ad for the next four queries.
And that's the optimal choice and
the optimal algorithm has a revenue of
$8 which is twice the greedy algorithm.
And this is the worst case example that
shows that the greedy algorithm can do
half as well as the optimal algorithm.
Now it's, it's actually quite easy and
straight forward to prove that the greedy
algorithm cannot do worse then, then this,
and the competitive ratio of
the greedy algorithm is exactly half.
And the proof of it is quite similar
to the the proof in the case of
the online bipartite
graph mapping problem,
which we covered in an earlier lecture,
and I leave that to you as an exercise.
The question is, is there an algorithm
that has a competitive ratio of
better than a half for this problem?
And it turns out that there is.
And it's a very simple algorithm
called the balance algorithm.
And the balance algorithm
uses a very simple heuristic.
For each query, it assigns that query to
the advertiser with the largest unspent
budget, or the largest balance.
Hence the name, the balance algorithm.
If there's a tie, for example,
if there's a query, and
there are two advertisers, each of whom
have an equal balance, then the balance
algorithm breaks ties arbitrarily,
but in a deterministic manner.
Let's look at how the balance algorithm
deals with the example that we just saw.
So here, here, again, is our example.
There are two advertisers, A and B.
A bids on query x, and B bids on queries
x and y, and both have budgets of $4.
now, when the first query X comes in the
balance I'll give them to both both A and
B are eligible to be shown for this query
and both have an equal balance of four.
And the balance algorithm has
to break this try arbitrarily.
Let us say the the balance algorithm
assigns this first query to A.
Now the second x comes in and
now notice that
let's write down A's and
B's balances right there.
Notice now that A's balance is three and
B's balance is
four because a dollar of A's budget is
already spent when we showed the first ad.
And so, the algorithm assigns
the second x to the advertiser with
eligible advertiser with the largest
balance, which is B in this case.
And so, that goes to B and
B's balance now becomes three.
Now when the third x comes in
both advertisers are eligible and
once again both balances are equal.
The balance algorithm has to break
the tie, arbitrarily, and let's say B and
gives it to A, when the fourth x
comes in once again it goes to B.
So, they would have a larger balance.
Now, when the first y comes in,
the only other eligible advertiser is B.
A has not bid for query y and so
the query has to go to B, and
B's balance goes down to one.
and, but the next y comes in.
Once again has to B and
B's balance goes down to zero.
And when the last two y's come in,
there's no eligible advertisers, so
we end up not assigning those
query stream advertiser.
In fact, not showing any query for
for those searches, so as a results,
the balance algorithm has a revenue of $6,
because we show six ads.
in, you know, in the balance algorithm.
The optimal algorithm,
as we recall has revenue of $8, and
so the, the competitive ratio
in this case is six by eight.
Which is three-fourths,
which is better than a half, right?
so, and so that's,
that's exactly what what happens here.
The that's a balance showing the optimal
choice, and the competitive ratio is
three-fourths, and in fact it can
be shown that for balance with
two advertisers the competitive ratio
is in fact exactly three fourths.
So we can do no worse than a competitive
ratio of three fourths in this case and
the proof is quite, quite simple,
but quite interesting.
So I'll walk you through it.
So let's analyze the two
advertiser balance scenario.
Let's consider a very simple scenario
with our two advertisers A1 and
A2 both with budget B and
let's assume that the optimal solution
exhausts both advertisers' budget.
In other, in other words the optimal
solution has revenue two B because it
allocates a B amount of budged from A1 and
B amount of budget from A2.
Now, it must be the case that
the balance algorithm exhausts at
least one advertiser's budget.
Because suppose the balance algorithm did
not exhaust at least one advertiser's
budget, then when a query comes in,
then both advertisers are eligible and
at least one of those advertisers
can be can be shown for
that credit and, therefore,
it could do a bit better.
So, it must be the case that the balance
algorithm must exhaust the budget of
at least one advertiser.
Now, assume, without loss of generality,
that balance actually exhausts A2's
budget, but doesn't exhaust A1's budget.
Let's look at this simple visual to
help us understand what's going on here.
And let's say let's assume that these that
these two rectangles
are the present sets of queries.
In this case the blue queries
are the queries that were allocated to,
advertiser A1 in the optimal solution, and
the green rectangle represent the set of
queries that were, assigned to
advertiser A2 in the optimal solution.
Remember that this that there
are B queries of each kind,
since we exhausted both A1's budget and
A2's budget.
And so, there were a total of
two B queries that were allocated
by the optimal solution.
Okay and this is optimal solution.
Let's look at the what happens when
we run the the balance algorithm.
When we run the balance algorithm,
the balance algorithm would assigned for
these in exactly the same
way as the optimal solution.
Let's say that some of the blue
queries that are assigned to
A1 in the optimal solution remained
assigned to A1 in the balanced solution.
But some of the blue queries are instead
assigned to A2 in the balanced solution.
And, some of the green queries assigned
to A2 remain assigned to A2 but
the some of the green queries that
were were originally assigned to
A2 could not be assigned.
And are, in fact,
left unassigned by the balance algorithm.
Okay?
and, in fact, the, the revenue of
the balance algorithm is equal to B,
which is the set of queries that
are assigned to A2, but remember, since we
exhausted A2 's budget, plus y, the set
of queries that-that were assigned to A1.
Right?
So the optimal revenue in this case is 2B.
Since we since the optimal algorithm
assigns B queries to A1 and
B queries to A2, so its revenue is 2B.
The balance revenue is B plus y.
Since the since the balance algorithm
assigns B queries to A2 and
Y queries to A1, and
leaves X queries unassigned.
'Kay.
Now, what we're going to show,
is that we're going to show that y
is greater than or equal to B by 2.
Why are we going to show that?
Well, when, once we're sure that y
is greater than or equal to B by 2,
then we know that the balance of
revenue is at least B plus B by 2,
which is three-fourths
of the optimal revenue.
let's, let's consider two cases.
Case one is when the the balance
algorithm assigns at least
half our B by two queries
of the blue queries to A1.
Okay?
So well, if, if, the balance algorithm
assigns at least B by 2 queries to A1
then we know that the size of
the blue bar is at least B by 2.
And so y is greater than or
equal to B by 2.
And we've shown y is greater than or
equal to B by 2, which is what we
wanted to show in the first place.
Now the second case to consider is that
the balance algorithm assigns less than
B by 2 blue case to to A1.
And therefore since there are total of B
blue queries that are assigned it must
assign more than B by
two blue queries to A2.
Now we have more than b by two blue
queries that are signed to A2,
just look at let's consider the last
blue query, the query right here,
the last blue query that was assigned to,
to A2.
Okay?
When you look at the last blue query there
that was assigned to A2, the balance
algorithm number, both A1 and A2 are
eligible and have bid on the blue queries.
and, but the balance algor, and both,
at this point, have unspent budget.
But the balance algorithm decided
to decide this blue query to A2.
Going by the characteristic of the balance
algorithm, the balance algorithm
assigns the query to the advertiser
with the larger unspent balance.
So at this point, when the blue query
was assigned to A2, it must be the case
that A,
A2's balance was larger than A1's balance.
Okay?
This is just another way of saying
that at this point, the number of
queries assigned to A1 must have been
greater than the number of queries that
were assigned to A2 since both started out
with the same budged in the beginning.
Now, we know that,
at least B, B, this is the,
the, I think B, blue queries
have already been assigned to,
B by two blue queries have already
been assigned to A2 at this point.
Right?
and, since we've said that the number of
queries assigned to A1 at this point has
to be greater than the number of queries
that are assigned to A2 at this point.
It must be the case that the number of
queries assigned to A1 at this point,
which is Y, is also greater than or
equal to B divided by two.
And so
we've shown that Y is greater than or
equal to B divided by two
in the second case as well.
Now, since we've shown
that y is greater than or
equal to B by 2 and we've also, we also
know that balance revenue is B plus y.
Since y is greater than or equal to B by 2
we know that the balance revenues is at,
is greater than or equal to 3B by 2 and
therefore the ratio of
the balance revenue to the optimal
revenue is at least three fourths.
Now, we've analyzed the simple case of
balance with exactly two advertisers and
shown that the competitive ratio is two.
But what happens if there
are more than two advertisers?
What happens if there are a large
number of advertisers?
In the case there are a large number
of advertisers, it's it can be
shown that the competitive ratio of
balance is given by this expression.
One minus one over e where e
is the base of the natural
logarithm 2.718 so on and
that is approximately 0.63.
Notice that this competitive ratio 0.63 is
strictly better than half, which is the
competitive ratio of the greedy algorithm.
So, the balance algorithm does much
better than the greedy algorithm,
in terms of competitive ratio.
Now, interestingly,
although I won't be able to show this in
this lecture no online
algorithm can actually do
better than this competitive ratio of one
minus one by e, for the adverse problem.
But what I'm going to do instead,
is I'm going to show you the worst case
example that gives us this
competitive ratio of 1-1 by e