Let's say that our N advertisers,
A1 through AN.
And let's say each advertiser has the same
budget B and that B is greater than N.
There are going to be N times B
queries that appear in No rounds of B
queries each.
Right so we don't actually
get one query at a time, but
we're going to group them into
end rounds of B queries each.
And here's how the bidding works.
With the queries that come in round
one the bidders are A 1 through A N.
For the queries that appear in round two,
the bidders are A 2 through A N.
For the queries that appear in round i,
the bidders are A i through A N and so on.
Until round N, the queries that appear
in round N, the only bidder is is A N.
And remember,
there are B queries in each round.
And B is also equal to
the budget of each advertiser.
So the optimal algorithm in this case
is to assign the round i
queries to the i advertiser.
That is assign assign all
the round one queries to A1.
Assign all the round two
queries to A two and so on.
So since A one has budget B
all the round one queries,
all the B round queries
are assigned to A one.
A two has budget B,
all the round two queries are assigned
to budget, to, to advertiser A too.
A, Ai has budget B.
All the B A round i queries are assigned
to advertiser Ai and so on.
And since the optimal algorithm
assigns the, all the queries in round
i to advertiser i, it is in fact able to
assign each query to some advertiser.
And so the revenue of the optimal
algorithm is equal to
the number of queries and
that is N times B.
Now, let's see what balance
algorithm does in this case.
now, let's just imagine that these
empty rectangles represent the unspent
budget of each of the advertisers,
A1 through AN.
And as we assign queries
to the advertisers,
they're going to color
these these rectangles.
When the round one queries come in now
it's easy to you know, it's easy to see.
But the balance algorithm is going
to assign an equal number of
round one queries to each
advertiser A1 through AN.
Now since there are actually
B round one phase.
This means that each advertiser is, is
allocated B by N of the round one phase.
And I, I've shown that in this
new coloring on the slideshow.
Now when the round two queries come in
the round two queries the bidders
are advertisers A2 through AN.
A1 doesn't bid for round two queries.
And once again, the balance algorithm
will have find an equal number of
the round two queries to each of
the eligible advertisers A2 through AN.
Now, the number of eligible advertisers,
in this case, is not N, but N minus one.
and, so, the balance algorithm will end
up assigning B by N minus one, round one,
or round two queries to each of
the advertisers A2 through AN.
Now, similarly, when,
the round three queries come in,
valuable advertisers are A3.
Two A N, and
there are N minus two of them, and so
the balance algorithm will end up
assigning B by N minus two queries,
to each of the advertisers,
A three through N.
So, in general, after k rounds,
the allocation advertiser k is
given by the formula shown here.
SK which the al,
allocation to advertiser k is even by sum
one through k b divided
by n minus i plus one.
Okay?
So the allocation to advertiser i is b
by n plus b by n minus one
plus b by n minus two and
so on until b by n minus i plus one.
Now, this process can continue for
a while, but once, after the few rounds,
what's going to happen is that we will,
this sum, or
this allocation, is going to exhaust
the budget of the of the K advertiser.
At some point, Sk is going to exceed B,
which is the total budget that's available
to the kth advertiser and at that point,
we have exhausted the budget of,
not just the kth ad advertiser, but also
all the advertisers k plus 1, k plus 2 and
so on through N because all the,
all the advertisers k plus 1 through N.
Have the same allocations.
So if you can find the smallest k such
that Sk is greater than or equal to B,
then after k rounds we've exhausted
the budgets of all the advertisers k,
k plus 1 through N, and so
we cannot assign any queries to
any advertiser beyond that point.
So, our goal is to find the smallest k.
Such that SK is greater than B.
Now, just look at this,
simple graphic that shows the allocations
to different advertisers.
The allocation to the first advertiser,
S1, is just B by N.
The allocation to the second advertiser,
which is S2,
is B by N plus B by N minus 1.
The allocation at third advertiser,
the sum of the first 3 terms and so on.
The allocation of the K advertiser,
the sum of the first, or
the last K terms of the series.
B / N-
K-
1.
All the way to, B by N.
And we want to find the, the smallest
K such that the sum of the series.
Or is greater than output B.
Now, what you're going to do,
to simplify the problem,
is we're going to divide by B throughout.
And saying that, the allocation going
to the first advertiser is 1 by N.
Ratio of second advertiser is 1,
1 by N minus 1 and so on.
And what's the inte, interested of doing
is that we're interested in finding the,
the, the, the, the,
the radix N such that the sum of the first
k terms is greater than or equal to 1.
So, if we want to find the smallest k
such that 1 by N plus 1 by N minus 1,
and so on through 1 by N minus k minus
1 is greater than or equal to 1.
Now, there's a very famous result
due to Euler that says that,
that for a very large N,
the series 1 plus a half.
Plus, plus one-third and so on.
Some the matter logarithm of, of N.
This is true to a, the small additive
constant, which we will ignore.
'Kay?
Now what we've said is that the,
we want to find the smallest k
such that the sum of the last k
terms of the series is equal to 1.
If the sum of the last k
terms of the series is 1.
Then the sum of the first n minus k
terms of the series must be equal to
N minus 1, since the sum of
the whole series is equal to N.
However, if you just look at the first
n minus k terms of the series,
they are 1 plus half.
And so on, through 1 by N minus k.
And using Euler's assault once again,
the sum of these terms can also
be denoted as line of N minus k.
Okay?
So there's two ways to write the sum of
the first N minus k terms of the series.
As lan N minus k, and as lan N minus 1.
And so it must be the case that lan N
minus 1 is equal to lan of N minus k.
And when I solve that.
I can solve that for k and
that gives me N divided by N minus k is
equal to e or
k is equal to N times 1 minus 1 over e.
So we've in fact,
found the k such that after k rounds.
We've exhausted the budgets of
all advertisers Ak through AN,
and therefore we cannot assign
any queries to any advertiser.
So after the first k rounds, and
k is N times 1 minus 1 by e, we cannot
allocate any query to any advertiser.
And so the allocation or the assignment
of the revenue from the balance algorithm
is given by B times N times 1 minus 1 by
e, since in each round we have B queries.
Now we've also shown that the revenue
of the optimal algorithm is N times B.
And therefore, the competitive ratio of
the balance algorithm is just the ratio of
the revenues of the balance algorithm
to that of the optimal algorithm.
And that's 1 minus 1 over E.
So what we've shown here is an example
of a scenario where the balance
algorithm has a competitive ratio,
1 minus 1 over E.
The actual proof that the balance
algorithm has this competitive ratio, and
can do no worse than one minus one by e,
is outside the scope of this lecture.
And I encourage you to read the,
the actual paper for that proof.
Now, we look at a very simplified
version of the [adverse?] problem.
Where all advertisers had
the same budget B and
all ads had equal expected revenue of one.
Now the general version of,of the problem,
this is not the case.
The general version of the problem all
each advertiser has a different budget.
And, all the bids, each advertise
has a different bid for each ad.
And each ad has a different
expected click-through rate,
yielding a different expected revenue.
Now in, in the general setting like this
the balance algorithm as I've described so
far can actually be quite terrible.
Let's look at an example.
Suppose there are, there's a query q and
there are two advertisers A1 and A2.
And let's say, A, A1's bid is one, and
let's say the result of
the expected revenue.
And and A1's budget is $110.
A2's bid is ten and let's say
the result of the expected revenue and,
the bud, A2's budget is $100.
Now, let's say we see ten
instances of the query q.
When the first instance of the, of the
query q comes in, we'll notice that A1 and
A2 are both advertisers, but we'll notice
A1's balance is much larger than A2's,
because A, A1's budget is 110,
and A2's budget is 100, and so
we end up assigning
the query to advertiser A1.
When the second query comes in,
A1's balance is going to be 109, A2's is
going to be 100, so the second query is
going to go to A1 as well, and so on.
So, in fact,
we will assign all the first ten instances
of the query Q to advertiser A1.
And, therefore, the, revenue of
the in this case is going to be $10.
The optimal algorithm that is
obvious in this case will assign.
All the instances of query Q to
advertiser A2 and will earn $100.
And therefore, the competitive ratio
in this case is 10 divided by 100,
which is 1 over 10.
Which is quite terrible.
So it turns out that we can fix
the balance algorithm to deal with
the fact that advertisers have
different budgets and different bids.
And this is what's called
a generalized balance algorithm.
Suppose for query q and bidder i,
the the, the corresponding bid is xi,
and the, the budget of advertiser i,
is is bi.
Okay?
and, let's say the amount spent so
far by the advertiser is m i.
Now the fraction of the advertiser's
bud-budget left over,
which we'll call f i,
is one divided by m i over b i.
Remember, m i, in this case, is the,
is the, amount that's been spent so
far by the advertiser,.
B i for the advertiser i's total budget.
And therefore,
1 minus m by b i is going by f i.
Be the fraction of the advertisers
i that's left over to be spent.
Now we're going to define this
new term called psi i of q.
And psi i of q is given
by this expression x i.
times 1 minus e vase to negative fi.
'Kay?
And what we're going to do is when query,
query q comes in,
we're going to take each
eligible advertiser i.
And we're going to compute
this function psi i of q.
Which is the product of the bid xi.
And one minus e negative five.
And once we compute that,
we going to allocate the query q
to the bidder i with the largest
of value of psi i of q.
Now I leave,leave the next exercise
to you to show to yourself that in
the case were all the bids are equal,
all the psi i are equal to one and
all the budgets are equal.
Uh,that is all the budgets Bi
are actually equal to a single
budget B ale, ale, ale,
you know, allocating queries
uh,using generalized balance with the
largest value of psi i of q is equivalent
to allocating queries to the advertiser
with the largest unspent balance.
Now the generalized
balance algorithm works in
the general setting when the bids and the
budgets of each advertiser are different.
And in fact, it achieves the same
competitive ratio one minus one over
e that the balance algorithm
achieves in the simpler setting.
So in this lecture, we've looked at
an algorithm called the balance algorithm
and, and the generalized version of it
called the generalized balance algorithm
that, that deals with the adverse problem
in the situation of limited budget and
also has a better comparative
ratio than the greedy algorithm.
Thank you.