1
00:00:00,610 --> 00:00:05,065
Let's say that our N advertisers,
A1 through AN.

2
00:00:05,065 --> 00:00:10,260
And let's say each advertiser has the same
budget B and that B is greater than N.

3
00:00:10,260 --> 00:00:14,300
There are going to be N times B
queries that appear in No rounds of B

4
00:00:14,300 --> 00:00:16,060
queries each.

5
00:00:16,060 --> 00:00:18,430
Right so we don't actually
get one query at a time, but

6
00:00:18,430 --> 00:00:21,340
we're going to group them into
end rounds of B queries each.

7
00:00:24,360 --> 00:00:25,580
And here's how the bidding works.

8
00:00:26,930 --> 00:00:31,820
With the queries that come in round
one the bidders are A 1 through A N.

9
00:00:31,820 --> 00:00:38,050
For the queries that appear in round two,
the bidders are A 2 through A N.

10
00:00:38,050 --> 00:00:43,460
For the queries that appear in round i,
the bidders are A i through A N and so on.

11
00:00:43,460 --> 00:00:50,190
Until round N, the queries that appear
in round N, the only bidder is is A N.

12
00:00:50,190 --> 00:00:53,580
And remember,
there are B queries in each round.

13
00:00:53,580 --> 00:00:56,980
And B is also equal to
the budget of each advertiser.

14
00:00:59,290 --> 00:01:01,780
So the optimal algorithm in this case

15
00:01:02,830 --> 00:01:08,100
is to assign the round i
queries to the i advertiser.

16
00:01:08,100 --> 00:01:14,960
That is assign assign all
the round one queries to A1.

17
00:01:16,150 --> 00:01:19,586
Assign all the round two
queries to A two and so on.

18
00:01:19,586 --> 00:01:23,267
So since A one has budget B
all the round one queries,

19
00:01:23,267 --> 00:01:26,207
all the B round queries
are assigned to A one.

20
00:01:26,207 --> 00:01:27,320
A two has budget B,

21
00:01:27,320 --> 00:01:32,634
all the round two queries are assigned
to budget, to, to advertiser A too.

22
00:01:32,634 --> 00:01:35,130
A, Ai has budget B.

23
00:01:35,130 --> 00:01:39,590
All the B A round i queries are assigned
to advertiser Ai and so on.

24
00:01:40,900 --> 00:01:46,200
And since the optimal algorithm
assigns the, all the queries in round

25
00:01:46,200 --> 00:01:50,680
i to advertiser i, it is in fact able to
assign each query to some advertiser.

26
00:01:50,680 --> 00:01:53,370
And so the revenue of the optimal
algorithm is equal to

27
00:01:53,370 --> 00:01:55,460
the number of queries and
that is N times B.

28
00:01:56,870 --> 00:01:59,240
Now, let's see what balance
algorithm does in this case.

29
00:02:00,280 --> 00:02:05,910
now, let's just imagine that these
empty rectangles represent the unspent

30
00:02:05,910 --> 00:02:09,480
budget of each of the advertisers,
A1 through AN.

31
00:02:09,480 --> 00:02:12,060
And as we assign queries
to the advertisers,

32
00:02:12,060 --> 00:02:15,130
they're going to color
these these rectangles.

33
00:02:15,130 --> 00:02:22,470
When the round one queries come in now
it's easy to you know, it's easy to see.

34
00:02:22,470 --> 00:02:26,140
But the balance algorithm is going
to assign an equal number of

35
00:02:26,140 --> 00:02:30,470
round one queries to each
advertiser A1 through AN.

36
00:02:30,470 --> 00:02:36,110
Now since there are actually
B round one phase.

37
00:02:36,110 --> 00:02:43,220
This means that each advertiser is, is
allocated B by N of the round one phase.

38
00:02:43,220 --> 00:02:46,410
And I, I've shown that in this
new coloring on the slideshow.

39
00:02:49,960 --> 00:02:52,620
Now when the round two queries come in

40
00:02:52,620 --> 00:02:56,960
the round two queries the bidders
are advertisers A2 through AN.

41
00:02:56,960 --> 00:02:59,640
A1 doesn't bid for round two queries.

42
00:02:59,640 --> 00:03:03,679
And once again, the balance algorithm
will have find an equal number of

43
00:03:03,679 --> 00:03:08,270
the round two queries to each of
the eligible advertisers A2 through AN.

44
00:03:08,270 --> 00:03:13,542
Now, the number of eligible advertisers,
in this case, is not N, but N minus one.

45
00:03:13,542 --> 00:03:19,040
and, so, the balance algorithm will end
up assigning B by N minus one, round one,

46
00:03:19,040 --> 00:03:22,791
or round two queries to each of
the advertisers A2 through AN.

47
00:03:24,010 --> 00:03:25,100
Now, similarly, when,

48
00:03:25,100 --> 00:03:28,518
the round three queries come in,
valuable advertisers are A3.

49
00:03:28,518 --> 00:03:31,461
Two A N, and
there are N minus two of them, and so

50
00:03:31,461 --> 00:03:36,026
the balance algorithm will end up
assigning B by N minus two queries,

51
00:03:36,026 --> 00:03:39,289
to each of the advertisers,
A three through N.

52
00:03:41,476 --> 00:03:44,275
So, in general, after k rounds,

53
00:03:44,275 --> 00:03:48,810
the allocation advertiser k is
given by the formula shown here.

54
00:03:48,810 --> 00:03:54,968
SK which the al,
allocation to advertiser k is even by sum

55
00:03:54,968 --> 00:03:59,940
one through k b divided
by n minus i plus one.

56
00:03:59,940 --> 00:04:03,350
Okay?
So the allocation to advertiser i is b

57
00:04:03,350 --> 00:04:06,990
by n plus b by n minus one
plus b by n minus two and

58
00:04:06,990 --> 00:04:14,040
so on until b by n minus i plus one.

59
00:04:14,040 --> 00:04:18,660
Now, this process can continue for
a while, but once, after the few rounds,

60
00:04:18,660 --> 00:04:22,420
what's going to happen is that we will,
this sum, or

61
00:04:22,420 --> 00:04:27,479
this allocation, is going to exhaust
the budget of the of the K advertiser.

62
00:04:28,480 --> 00:04:33,370
At some point, Sk is going to exceed B,
which is the total budget that's available

63
00:04:33,370 --> 00:04:37,750
to the kth advertiser and at that point,
we have exhausted the budget of,

64
00:04:37,750 --> 00:04:44,010
not just the kth ad advertiser, but also
all the advertisers k plus 1, k plus 2 and

65
00:04:44,010 --> 00:04:49,500
so on through N because all the,
all the advertisers k plus 1 through N.

66
00:04:49,500 --> 00:04:51,300
Have the same allocations.

67
00:04:51,300 --> 00:04:56,230
So if you can find the smallest k such
that Sk is greater than or equal to B,

68
00:04:56,230 --> 00:05:01,430
then after k rounds we've exhausted
the budgets of all the advertisers k,

69
00:05:01,430 --> 00:05:03,340
k plus 1 through N, and so

70
00:05:03,340 --> 00:05:07,430
we cannot assign any queries to
any advertiser beyond that point.

71
00:05:07,430 --> 00:05:09,460
So, our goal is to find the smallest k.

72
00:05:09,460 --> 00:05:11,650
Such that SK is greater than B.

73
00:05:11,650 --> 00:05:12,760
Now, just look at this,

74
00:05:12,760 --> 00:05:16,300
simple graphic that shows the allocations
to different advertisers.

75
00:05:16,300 --> 00:05:20,620
The allocation to the first advertiser,
S1, is just B by N.

76
00:05:20,620 --> 00:05:24,370
The allocation to the second advertiser,
which is S2,

77
00:05:24,370 --> 00:05:27,450
is B by N plus B by N minus 1.

78
00:05:27,450 --> 00:05:31,640
The allocation at third advertiser,
the sum of the first 3 terms and so on.

79
00:05:31,640 --> 00:05:35,725
The allocation of the K advertiser,
the sum of the first, or

80
00:05:35,725 --> 00:05:38,109
the last K terms of the series.

81
00:05:38,109 --> 00:05:38,673
B / N-
K-

82
00:05:38,673 --> 00:05:39,262
1.

83
00:05:39,262 --> 00:05:41,243
All the way to, B by N.

84
00:05:41,243 --> 00:05:48,239
And we want to find the, the smallest
K such that the sum of the series.

85
00:05:49,480 --> 00:05:50,770
Or is greater than output B.

86
00:05:53,450 --> 00:05:55,233
Now, what you're going to do,

87
00:05:55,233 --> 00:05:58,804
to simplify the problem,
is we're going to divide by B throughout.

88
00:05:58,804 --> 00:06:05,553
And saying that, the allocation going
to the first advertiser is 1 by N.

89
00:06:05,553 --> 00:06:08,970
Ratio of second advertiser is 1,
1 by N minus 1 and so on.

90
00:06:09,990 --> 00:06:14,850
And what's the inte, interested of doing
is that we're interested in finding the,

91
00:06:14,850 --> 00:06:16,000
the, the, the, the,

92
00:06:16,000 --> 00:06:22,630
the radix N such that the sum of the first
k terms is greater than or equal to 1.

93
00:06:22,630 --> 00:06:27,320
So, if we want to find the smallest k
such that 1 by N plus 1 by N minus 1,

94
00:06:27,320 --> 00:06:32,300
and so on through 1 by N minus k minus
1 is greater than or equal to 1.

95
00:06:32,300 --> 00:06:37,480
Now, there's a very famous result
due to Euler that says that,

96
00:06:37,480 --> 00:06:41,488
that for a very large N,
the series 1 plus a half.

97
00:06:41,488 --> 00:06:46,256
Plus, plus one-third and so on.

98
00:06:46,256 --> 00:06:50,530
Some the matter logarithm of, of N.

99
00:06:52,250 --> 00:06:55,570
This is true to a, the small additive
constant, which we will ignore.

100
00:06:56,660 --> 00:06:58,230
'Kay?

101
00:06:58,230 --> 00:07:03,900
Now what we've said is that the,
we want to find the smallest k

102
00:07:03,900 --> 00:07:09,100
such that the sum of the last k
terms of the series is equal to 1.

103
00:07:09,100 --> 00:07:13,600
If the sum of the last k
terms of the series is 1.

104
00:07:13,600 --> 00:07:18,860
Then the sum of the first n minus k
terms of the series must be equal to

105
00:07:22,114 --> 00:07:25,950
N minus 1, since the sum of
the whole series is equal to N.

106
00:07:27,200 --> 00:07:31,360
However, if you just look at the first
n minus k terms of the series,

107
00:07:31,360 --> 00:07:34,230
they are 1 plus half.

108
00:07:34,230 --> 00:07:37,920
And so on, through 1 by N minus k.

109
00:07:40,070 --> 00:07:42,760
And using Euler's assault once again,

110
00:07:42,760 --> 00:07:47,250
the sum of these terms can also
be denoted as line of N minus k.

111
00:07:50,640 --> 00:07:51,890
Okay?

112
00:07:51,890 --> 00:07:58,026
So there's two ways to write the sum of
the first N minus k terms of the series.

113
00:07:58,026 --> 00:08:02,170
As lan N minus k, and as lan N minus 1.

114
00:08:02,170 --> 00:08:08,540
And so it must be the case that lan N
minus 1 is equal to lan of N minus k.

115
00:08:08,540 --> 00:08:11,290
And when I solve that.

116
00:08:11,290 --> 00:08:16,780
I can solve that for k and
that gives me N divided by N minus k is

117
00:08:16,780 --> 00:08:22,040
equal to e or
k is equal to N times 1 minus 1 over e.

118
00:08:23,760 --> 00:08:30,070
So we've in fact,
found the k such that after k rounds.

119
00:08:30,070 --> 00:08:35,610
We've exhausted the budgets of
all advertisers Ak through AN,

120
00:08:35,610 --> 00:08:39,190
and therefore we cannot assign
any queries to any advertiser.

121
00:08:39,190 --> 00:08:41,350
So after the first k rounds, and

122
00:08:41,350 --> 00:08:46,259
k is N times 1 minus 1 by e, we cannot
allocate any query to any advertiser.

123
00:08:47,420 --> 00:08:53,330
And so the allocation or the assignment
of the revenue from the balance algorithm

124
00:08:53,330 --> 00:09:01,230
is given by B times N times 1 minus 1 by
e, since in each round we have B queries.

125
00:09:01,230 --> 00:09:06,390
Now we've also shown that the revenue
of the optimal algorithm is N times B.

126
00:09:07,780 --> 00:09:12,220
And therefore, the competitive ratio of
the balance algorithm is just the ratio of

127
00:09:12,220 --> 00:09:16,720
the revenues of the balance algorithm
to that of the optimal algorithm.

128
00:09:16,720 --> 00:09:18,210
And that's 1 minus 1 over E.

129
00:09:21,090 --> 00:09:25,220
So what we've shown here is an example
of a scenario where the balance

130
00:09:25,220 --> 00:09:28,340
algorithm has a competitive ratio,
1 minus 1 over E.

131
00:09:29,510 --> 00:09:33,190
The actual proof that the balance
algorithm has this competitive ratio, and

132
00:09:33,190 --> 00:09:37,620
can do no worse than one minus one by e,
is outside the scope of this lecture.

133
00:09:40,270 --> 00:09:44,210
And I encourage you to read the,
the actual paper for that proof.

134
00:09:47,730 --> 00:09:51,950
Now, we look at a very simplified
version of the [adverse?] problem.

135
00:09:51,950 --> 00:09:56,620
Where all advertisers had
the same budget B and

136
00:09:56,620 --> 00:10:00,540
all ads had equal expected revenue of one.

137
00:10:00,540 --> 00:10:04,140
Now the general version of,of the problem,
this is not the case.

138
00:10:04,140 --> 00:10:09,060
The general version of the problem all
each advertiser has a different budget.

139
00:10:09,060 --> 00:10:13,550
And, all the bids, each advertise
has a different bid for each ad.

140
00:10:13,550 --> 00:10:16,580
And each ad has a different
expected click-through rate,

141
00:10:16,580 --> 00:10:18,800
yielding a different expected revenue.

142
00:10:18,800 --> 00:10:22,350
Now in, in the general setting like this
the balance algorithm as I've described so

143
00:10:22,350 --> 00:10:24,760
far can actually be quite terrible.

144
00:10:24,760 --> 00:10:26,110
Let's look at an example.

145
00:10:26,110 --> 00:10:30,170
Suppose there are, there's a query q and
there are two advertisers A1 and A2.

146
00:10:31,210 --> 00:10:33,450
And let's say, A, A1's bid is one, and

147
00:10:33,450 --> 00:10:35,800
let's say the result of
the expected revenue.

148
00:10:35,800 --> 00:10:39,060
And and A1's budget is $110.

149
00:10:39,060 --> 00:10:45,559
A2's bid is ten and let's say
the result of the expected revenue and,

150
00:10:45,559 --> 00:10:48,490
the bud, A2's budget is $100.

151
00:10:48,490 --> 00:10:52,360
Now, let's say we see ten
instances of the query q.

152
00:10:52,360 --> 00:10:57,160
When the first instance of the, of the
query q comes in, we'll notice that A1 and

153
00:10:57,160 --> 00:11:02,040
A2 are both advertisers, but we'll notice
A1's balance is much larger than A2's,

154
00:11:02,040 --> 00:11:07,340
because A, A1's budget is 110,
and A2's budget is 100, and so

155
00:11:07,340 --> 00:11:11,300
we end up assigning
the query to advertiser A1.

156
00:11:11,300 --> 00:11:15,850
When the second query comes in,
A1's balance is going to be 109, A2's is

157
00:11:15,850 --> 00:11:19,730
going to be 100, so the second query is
going to go to A1 as well, and so on.

158
00:11:19,730 --> 00:11:20,450
So, in fact,

159
00:11:20,450 --> 00:11:25,280
we will assign all the first ten instances
of the query Q to advertiser A1.

160
00:11:26,390 --> 00:11:31,780
And, therefore, the, revenue of
the in this case is going to be $10.

161
00:11:31,780 --> 00:11:36,680
The optimal algorithm that is
obvious in this case will assign.

162
00:11:36,680 --> 00:11:41,040
All the instances of query Q to
advertiser A2 and will earn $100.

163
00:11:41,040 --> 00:11:46,750
And therefore, the competitive ratio
in this case is 10 divided by 100,

164
00:11:46,750 --> 00:11:47,580
which is 1 over 10.

165
00:11:47,580 --> 00:11:49,740
Which is quite terrible.

166
00:11:49,740 --> 00:11:53,800
So it turns out that we can fix
the balance algorithm to deal with

167
00:11:53,800 --> 00:11:56,990
the fact that advertisers have
different budgets and different bids.

168
00:11:56,990 --> 00:11:59,130
And this is what's called
a generalized balance algorithm.

169
00:12:03,150 --> 00:12:09,490
Suppose for query q and bidder i,
the the, the corresponding bid is xi,

170
00:12:10,490 --> 00:12:15,410
and the, the budget of advertiser i,
is is bi.

171
00:12:16,880 --> 00:12:18,100
Okay?

172
00:12:18,100 --> 00:12:23,560
and, let's say the amount spent so
far by the advertiser is m i.

173
00:12:23,560 --> 00:12:27,508
Now the fraction of the advertiser's
bud-budget left over,

174
00:12:27,508 --> 00:12:30,720
which we'll call f i,
is one divided by m i over b i.

175
00:12:30,720 --> 00:12:35,200
Remember, m i, in this case, is the,
is the, amount that's been spent so

176
00:12:35,200 --> 00:12:36,640
far by the advertiser,.

177
00:12:36,640 --> 00:12:39,200
B i for the advertiser i's total budget.

178
00:12:39,200 --> 00:12:42,900
And therefore,
1 minus m by b i is going by f i.

179
00:12:42,900 --> 00:12:47,270
Be the fraction of the advertisers
i that's left over to be spent.

180
00:12:48,980 --> 00:12:53,400
Now we're going to define this
new term called psi i of q.

181
00:12:53,400 --> 00:12:57,700
And psi i of q is given
by this expression x i.

182
00:12:57,700 --> 00:13:02,219
times 1 minus e vase to negative fi.

183
00:13:02,219 --> 00:13:04,070
'Kay?

184
00:13:04,070 --> 00:13:07,550
And what we're going to do is when query,
query q comes in,

185
00:13:07,550 --> 00:13:10,310
we're going to take each
eligible advertiser i.

186
00:13:10,310 --> 00:13:14,250
And we're going to compute
this function psi i of q.

187
00:13:14,250 --> 00:13:17,356
Which is the product of the bid xi.

188
00:13:17,356 --> 00:13:21,470
And one minus e negative five.

189
00:13:21,470 --> 00:13:24,630
And once we compute that,
we going to allocate the query q

190
00:13:24,630 --> 00:13:30,050
to the bidder i with the largest
of value of psi i of q.

191
00:13:30,050 --> 00:13:34,770
Now I leave,leave the next exercise
to you to show to yourself that in

192
00:13:34,770 --> 00:13:38,560
the case were all the bids are equal,
all the psi i are equal to one and

193
00:13:38,560 --> 00:13:39,778
all the budgets are equal.

194
00:13:39,778 --> 00:13:45,660
Uh,that is all the budgets Bi
are actually equal to a single

195
00:13:45,660 --> 00:13:50,365
budget B ale, ale, ale,
you know, allocating queries

196
00:13:50,365 --> 00:13:56,120
uh,using generalized balance with the
largest value of psi i of q is equivalent

197
00:13:56,120 --> 00:13:59,889
to allocating queries to the advertiser
with the largest unspent balance.

198
00:14:02,960 --> 00:14:06,330
Now the generalized
balance algorithm works in

199
00:14:06,330 --> 00:14:10,630
the general setting when the bids and the
budgets of each advertiser are different.

200
00:14:10,630 --> 00:14:14,870
And in fact, it achieves the same
competitive ratio one minus one over

201
00:14:14,870 --> 00:14:17,759
e that the balance algorithm
achieves in the simpler setting.

202
00:14:18,950 --> 00:14:23,620
So in this lecture, we've looked at
an algorithm called the balance algorithm

203
00:14:23,620 --> 00:14:26,920
and, and the generalized version of it
called the generalized balance algorithm

204
00:14:26,920 --> 00:14:31,470
that, that deals with the adverse problem
in the situation of limited budget and

205
00:14:31,470 --> 00:14:35,140
also has a better comparative
ratio than the greedy algorithm.

206
00:14:35,140 --> 00:14:35,640
Thank you.