1
00:00:00,370 --> 00:00:01,280
Hello everyone.

2
00:00:01,280 --> 00:00:03,340
Welcome back to Mining
of Massive Datasets.

3
00:00:03,340 --> 00:00:07,250
We're going to continue our discussion
of the adwords problem with a look at

4
00:00:07,250 --> 00:00:08,740
the BALANCE Algorithm.

5
00:00:08,740 --> 00:00:12,640
The BALANCE Algorithm is a way to deal
with the problem of limited advertiser

6
00:00:12,640 --> 00:00:15,310
budgets in the context
of the adword problem.

7
00:00:15,310 --> 00:00:17,750
To refresh your memory on
what the adword problem is,

8
00:00:17,750 --> 00:00:21,538
we are given a set of bids by
advertisers for search queries.

9
00:00:21,538 --> 00:00:25,310
And a click-through rate for
each advertiser-query pair.

10
00:00:25,310 --> 00:00:27,840
And in addition, a budget for
each advertiser.

11
00:00:27,840 --> 00:00:31,550
The budget could be for a day, or a month,
or a year, or some period like this.

12
00:00:31,550 --> 00:00:33,530
Let's just assume that
it's a daily budget.

13
00:00:35,060 --> 00:00:38,040
Finally, there's a limit on the number
of ads to be displayed with each

14
00:00:38,040 --> 00:00:39,020
search query.

15
00:00:39,020 --> 00:00:40,710
This limit could be one, or two, or three.

16
00:00:41,940 --> 00:00:46,890
Now, we need to respond to each search
query with a set of advertisers such that,

17
00:00:46,890 --> 00:00:51,040
the size of the advertiser set is no
larger than the limits of the number of

18
00:00:51,040 --> 00:00:51,790
ads per query.

19
00:00:52,830 --> 00:00:56,270
Each advertiser who we show has
actually bid on the search query.

20
00:00:56,270 --> 00:01:01,230
And finally, if the ad is shown and
somebody clicks on the ad,

21
00:01:01,230 --> 00:01:04,330
then the advertiser should have
enough budget left over to pay for

22
00:01:04,330 --> 00:01:06,670
the ad when it's actually clicked upon.

23
00:01:06,670 --> 00:01:11,110
So we don't actually want to show ads from
advertisers who don't have a budget to

24
00:01:11,110 --> 00:01:13,360
pay for
the clicks if they do actually happen.

25
00:01:13,360 --> 00:01:16,930
Because that's not a bidding
proposition for us.

26
00:01:16,930 --> 00:01:19,100
So the question is how
do we deal with the,

27
00:01:19,100 --> 00:01:22,910
the issue of limited advertiser budget,
that we don't want to show, or

28
00:01:22,910 --> 00:01:27,690
can not show an ad from an advertiser
whose budget has been exhausted.

29
00:01:27,690 --> 00:01:32,110
Now let's first study the problem
in in a simplified version.

30
00:01:32,110 --> 00:01:35,990
The simplified version that we're going to
look at has only one ad shown for

31
00:01:35,990 --> 00:01:39,475
each query, and
all advertisers have the same budget B.

32
00:01:39,475 --> 00:01:42,720
We're also can assume that all ads
are equally likely to be clicked and

33
00:01:42,720 --> 00:01:44,610
all have the same value of one.

34
00:01:44,610 --> 00:01:48,690
Another way of thinking about this is that
the expected revenue from each ad which is

35
00:01:48,690 --> 00:01:51,695
product of the click-through rate and
the bid is equal to one.

36
00:01:51,695 --> 00:01:56,350
Now, the simplest algorithm is the greedy
algorithm, which we've already looked at.

37
00:01:56,350 --> 00:01:59,930
And the greedy algorithm picks any
advertiser who has bid one for

38
00:01:59,930 --> 00:02:01,790
a query when that query shows up.

39
00:02:01,790 --> 00:02:05,400
And it's easy to show that
the competitive ratio of

40
00:02:05,400 --> 00:02:07,400
the greedy algorithm is actually a half.

41
00:02:08,490 --> 00:02:11,420
But here's a bad scenario for
the greedy algorithm.

42
00:02:11,420 --> 00:02:14,890
Here, here there are two advertisers,
A and B.

43
00:02:14,890 --> 00:02:16,860
And let's say A bids on query x.

44
00:02:16,860 --> 00:02:19,120
B bids on queries x and y.

45
00:02:19,120 --> 00:02:20,490
And both have budgets of $4.

46
00:02:20,490 --> 00:02:27,790
Now, the query stream that comes in is,
x, x, x, x, y, y, y, y.

47
00:02:27,790 --> 00:02:30,710
That's four x's, followed by four y's.

48
00:02:30,710 --> 00:02:35,070
Now when these query queries come in the
greedy algorithm exceeds the first x and

49
00:02:35,070 --> 00:02:40,070
notices that we have both A and
B who have bid for query x.

50
00:02:40,070 --> 00:02:45,600
And let's say the greedy algorithm
arbitrarily assigns query one

51
00:02:45,600 --> 00:02:47,540
to to advertiser B.

52
00:02:49,090 --> 00:02:52,330
And then, the second x comes in, and

53
00:02:52,330 --> 00:02:55,580
let's say the greedy algorithm
assigns that to B as well, and so on.

54
00:02:55,580 --> 00:03:00,350
The greedy algorithm might, for instance
end up assigning all the first four

55
00:03:00,350 --> 00:03:02,990
x queries to advertiser B,
none to advertiser A.

56
00:03:02,990 --> 00:03:06,920
As a result, when the first y query
comes in, B's budget of $4 is

57
00:03:06,920 --> 00:03:12,840
already exhausted and therefore,
no ads can be shown for the y queries.

58
00:03:12,840 --> 00:03:17,000
As a result the greedy algorithms
revenue is is only $4.

59
00:03:17,000 --> 00:03:21,180
Whereas the optimal allocation in
this case, as it's easy to see, is to

60
00:03:21,180 --> 00:03:26,320
show A's ad for the first four queries,
and then B's ad for the next four queries.

61
00:03:26,320 --> 00:03:27,851
And that's the optimal choice and

62
00:03:27,851 --> 00:03:31,450
the optimal algorithm has a revenue of
$8 which is twice the greedy algorithm.

63
00:03:32,710 --> 00:03:38,670
And this is the worst case example that
shows that the greedy algorithm can do

64
00:03:38,670 --> 00:03:41,180
half as well as the optimal algorithm.

65
00:03:41,180 --> 00:03:43,570
Now it's, it's actually quite easy and

66
00:03:43,570 --> 00:03:48,680
straight forward to prove that the greedy
algorithm cannot do worse then, then this,

67
00:03:48,680 --> 00:03:51,600
and the competitive ratio of
the greedy algorithm is exactly half.

68
00:03:51,600 --> 00:03:55,820
And the proof of it is quite similar
to the the proof in the case of

69
00:03:55,820 --> 00:03:58,360
the online bipartite
graph mapping problem,

70
00:03:58,360 --> 00:04:02,930
which we covered in an earlier lecture,
and I leave that to you as an exercise.

71
00:04:02,930 --> 00:04:06,980
The question is, is there an algorithm
that has a competitive ratio of

72
00:04:06,980 --> 00:04:08,490
better than a half for this problem?

73
00:04:09,550 --> 00:04:11,320
And it turns out that there is.

74
00:04:11,320 --> 00:04:14,200
And it's a very simple algorithm
called the balance algorithm.

75
00:04:15,380 --> 00:04:19,120
And the balance algorithm
uses a very simple heuristic.

76
00:04:19,120 --> 00:04:22,060
For each query, it assigns that query to

77
00:04:22,060 --> 00:04:26,540
the advertiser with the largest unspent
budget, or the largest balance.

78
00:04:26,540 --> 00:04:29,070
Hence the name, the balance algorithm.

79
00:04:29,070 --> 00:04:31,690
If there's a tie, for example,
if there's a query, and

80
00:04:31,690 --> 00:04:35,580
there are two advertisers, each of whom
have an equal balance, then the balance

81
00:04:35,580 --> 00:04:38,660
algorithm breaks ties arbitrarily,
but in a deterministic manner.

82
00:04:40,000 --> 00:04:45,630
Let's look at how the balance algorithm
deals with the example that we just saw.

83
00:04:45,630 --> 00:04:47,140
So here, here, again, is our example.

84
00:04:47,140 --> 00:04:48,960
There are two advertisers, A and B.

85
00:04:48,960 --> 00:04:53,490
A bids on query x, and B bids on queries
x and y, and both have budgets of $4.

86
00:04:53,490 --> 00:05:00,630
now, when the first query X comes in the
balance I'll give them to both both A and

87
00:05:00,630 --> 00:05:04,770
B are eligible to be shown for this query
and both have an equal balance of four.

88
00:05:04,770 --> 00:05:08,530
And the balance algorithm has
to break this try arbitrarily.

89
00:05:08,530 --> 00:05:15,230
Let us say the the balance algorithm
assigns this first query to A.

90
00:05:16,450 --> 00:05:21,590
Now the second x comes in and
now notice that

91
00:05:21,590 --> 00:05:26,790
let's write down A's and
B's balances right there.

92
00:05:26,790 --> 00:05:31,740
Notice now that A's balance is three and
B's balance is

93
00:05:31,740 --> 00:05:37,520
four because a dollar of A's budget is
already spent when we showed the first ad.

94
00:05:37,520 --> 00:05:42,875
And so, the algorithm assigns
the second x to the advertiser with

95
00:05:42,875 --> 00:05:46,390
eligible advertiser with the largest
balance, which is B in this case.

96
00:05:46,390 --> 00:05:49,800
And so, that goes to B and
B's balance now becomes three.

97
00:05:49,800 --> 00:05:54,130
Now when the third x comes in
both advertisers are eligible and

98
00:05:54,130 --> 00:05:56,200
once again both balances are equal.

99
00:05:56,200 --> 00:05:59,410
The balance algorithm has to break
the tie, arbitrarily, and let's say B and

100
00:05:59,410 --> 00:06:05,300
gives it to A, when the fourth x
comes in once again it goes to B.

101
00:06:05,300 --> 00:06:09,220
So, they would have a larger balance.

102
00:06:09,220 --> 00:06:13,950
Now, when the first y comes in,
the only other eligible advertiser is B.

103
00:06:13,950 --> 00:06:16,770
A has not bid for query y and so

104
00:06:16,770 --> 00:06:20,090
the query has to go to B, and
B's balance goes down to one.

105
00:06:21,140 --> 00:06:23,080
and, but the next y comes in.

106
00:06:23,080 --> 00:06:26,930
Once again has to B and
B's balance goes down to zero.

107
00:06:26,930 --> 00:06:30,660
And when the last two y's come in,
there's no eligible advertisers, so

108
00:06:30,660 --> 00:06:34,030
we end up not assigning those
query stream advertiser.

109
00:06:34,030 --> 00:06:39,790
In fact, not showing any query for
for those searches, so as a results,

110
00:06:39,790 --> 00:06:47,140
the balance algorithm has a revenue of $6,
because we show six ads.

111
00:06:47,140 --> 00:06:50,050
in, you know, in the balance algorithm.

112
00:06:50,050 --> 00:06:54,170
The optimal algorithm,
as we recall has revenue of $8, and

113
00:06:56,260 --> 00:07:00,508
so the, the competitive ratio
in this case is six by eight.

114
00:07:00,508 --> 00:07:05,670
Which is three-fourths,
which is better than a half, right?

115
00:07:07,100 --> 00:07:13,050
so, and so that's,
that's exactly what what happens here.

116
00:07:13,050 --> 00:07:16,575
The that's a balance showing the optimal
choice, and the competitive ratio is

117
00:07:16,575 --> 00:07:20,340
three-fourths, and in fact it can
be shown that for balance with

118
00:07:20,340 --> 00:07:24,535
two advertisers the competitive ratio
is in fact exactly three fourths.

119
00:07:24,535 --> 00:07:29,306
So we can do no worse than a competitive
ratio of three fourths in this case and

120
00:07:29,306 --> 00:07:32,712
the proof is quite, quite simple,
but quite interesting.

121
00:07:32,712 --> 00:07:36,240
So I'll walk you through it.

122
00:07:36,240 --> 00:07:39,430
So let's analyze the two
advertiser balance scenario.

123
00:07:40,740 --> 00:07:44,476
Let's consider a very simple scenario
with our two advertisers A1 and

124
00:07:44,476 --> 00:07:46,990
A2 both with budget B and

125
00:07:46,990 --> 00:07:51,300
let's assume that the optimal solution
exhausts both advertisers' budget.

126
00:07:51,300 --> 00:07:57,751
In other, in other words the optimal
solution has revenue two B because it

127
00:07:57,751 --> 00:08:03,235
allocates a B amount of budged from A1 and
B amount of budget from A2.

128
00:08:03,235 --> 00:08:06,290
Now, it must be the case that
the balance algorithm exhausts at

129
00:08:06,290 --> 00:08:07,730
least one advertiser's budget.

130
00:08:09,240 --> 00:08:13,380
Because suppose the balance algorithm did
not exhaust at least one advertiser's

131
00:08:13,380 --> 00:08:17,160
budget, then when a query comes in,
then both advertisers are eligible and

132
00:08:17,160 --> 00:08:20,360
at least one of those advertisers
can be can be shown for

133
00:08:20,360 --> 00:08:24,040
that credit and, therefore,
it could do a bit better.

134
00:08:24,040 --> 00:08:28,550
So, it must be the case that the balance
algorithm must exhaust the budget of

135
00:08:28,550 --> 00:08:29,650
at least one advertiser.

136
00:08:31,480 --> 00:08:34,240
Now, assume, without loss of generality,

137
00:08:34,240 --> 00:08:39,148
that balance actually exhausts A2's
budget, but doesn't exhaust A1's budget.

138
00:08:41,680 --> 00:08:46,030
Let's look at this simple visual to
help us understand what's going on here.

139
00:08:46,030 --> 00:08:51,620
And let's say let's assume that these that

140
00:08:51,620 --> 00:08:56,570
these two rectangles
are the present sets of queries.

141
00:08:56,570 --> 00:09:01,270
In this case the blue queries
are the queries that were allocated to,

142
00:09:01,270 --> 00:09:06,130
advertiser A1 in the optimal solution, and
the green rectangle represent the set of

143
00:09:06,130 --> 00:09:10,670
queries that were, assigned to
advertiser A2 in the optimal solution.

144
00:09:10,670 --> 00:09:14,210
Remember that this that there
are B queries of each kind,

145
00:09:14,210 --> 00:09:17,580
since we exhausted both A1's budget and
A2's budget.

146
00:09:17,580 --> 00:09:18,490
And so, there were a total of

147
00:09:18,490 --> 00:09:21,320
two B queries that were allocated
by the optimal solution.

148
00:09:22,350 --> 00:09:25,300
Okay and this is optimal solution.

149
00:09:25,300 --> 00:09:29,600
Let's look at the what happens when
we run the the balance algorithm.

150
00:09:29,600 --> 00:09:34,660
When we run the balance algorithm,
the balance algorithm would assigned for

151
00:09:34,660 --> 00:09:37,840
these in exactly the same
way as the optimal solution.

152
00:09:37,840 --> 00:09:40,615
Let's say that some of the blue
queries that are assigned to

153
00:09:40,615 --> 00:09:45,830
A1 in the optimal solution remained
assigned to A1 in the balanced solution.

154
00:09:45,830 --> 00:09:50,250
But some of the blue queries are instead
assigned to A2 in the balanced solution.

155
00:09:50,250 --> 00:09:56,440
And, some of the green queries assigned
to A2 remain assigned to A2 but

156
00:09:56,440 --> 00:10:00,295
the some of the green queries that
were were originally assigned to

157
00:10:00,295 --> 00:10:02,060
A2 could not be assigned.

158
00:10:02,060 --> 00:10:05,390
And are, in fact,
left unassigned by the balance algorithm.

159
00:10:05,390 --> 00:10:06,220
Okay?

160
00:10:06,220 --> 00:10:11,800
and, in fact, the, the revenue of
the balance algorithm is equal to B,

161
00:10:11,800 --> 00:10:15,520
which is the set of queries that
are assigned to A2, but remember, since we

162
00:10:15,520 --> 00:10:21,455
exhausted A2 's budget, plus y, the set
of queries that-that were assigned to A1.

163
00:10:23,780 --> 00:10:26,630
Right?
So the optimal revenue in this case is 2B.

164
00:10:26,630 --> 00:10:31,150
Since we since the optimal algorithm
assigns B queries to A1 and

165
00:10:31,150 --> 00:10:34,320
B queries to A2, so its revenue is 2B.

166
00:10:34,320 --> 00:10:36,640
The balance revenue is B plus y.

167
00:10:36,640 --> 00:10:41,580
Since the since the balance algorithm
assigns B queries to A2 and

168
00:10:41,580 --> 00:10:44,470
Y queries to A1, and
leaves X queries unassigned.

169
00:10:45,560 --> 00:10:47,020
'Kay.

170
00:10:47,020 --> 00:10:48,220
Now, what we're going to show,

171
00:10:48,220 --> 00:10:51,550
is that we're going to show that y
is greater than or equal to B by 2.

172
00:10:51,550 --> 00:10:54,020
Why are we going to show that?

173
00:10:54,020 --> 00:10:56,870
Well, when, once we're sure that y
is greater than or equal to B by 2,

174
00:10:56,870 --> 00:11:00,940
then we know that the balance of
revenue is at least B plus B by 2,

175
00:11:00,940 --> 00:11:02,830
which is three-fourths
of the optimal revenue.

176
00:11:04,910 --> 00:11:07,230
let's, let's consider two cases.

177
00:11:07,230 --> 00:11:12,330
Case one is when the the balance
algorithm assigns at least

178
00:11:13,540 --> 00:11:18,310
half our B by two queries
of the blue queries to A1.

179
00:11:18,310 --> 00:11:19,090
Okay?

180
00:11:19,090 --> 00:11:25,770
So well, if, if, the balance algorithm
assigns at least B by 2 queries to A1

181
00:11:25,770 --> 00:11:31,800
then we know that the size of
the blue bar is at least B by 2.

182
00:11:31,800 --> 00:11:34,320
And so y is greater than or
equal to B by 2.

183
00:11:34,320 --> 00:11:36,290
And we've shown y is greater than or

184
00:11:36,290 --> 00:11:38,710
equal to B by 2, which is what we
wanted to show in the first place.

185
00:11:40,200 --> 00:11:46,040
Now the second case to consider is that
the balance algorithm assigns less than

186
00:11:46,040 --> 00:11:49,660
B by 2 blue case to to A1.

187
00:11:49,660 --> 00:11:54,320
And therefore since there are total of B
blue queries that are assigned it must

188
00:11:54,320 --> 00:11:56,875
assign more than B by
two blue queries to A2.

189
00:11:58,870 --> 00:12:03,210
Now we have more than b by two blue
queries that are signed to A2,

190
00:12:03,210 --> 00:12:08,890
just look at let's consider the last
blue query, the query right here,

191
00:12:08,890 --> 00:12:12,670
the last blue query that was assigned to,
to A2.

192
00:12:12,670 --> 00:12:13,920
Okay?

193
00:12:13,920 --> 00:12:18,610
When you look at the last blue query there
that was assigned to A2, the balance

194
00:12:18,610 --> 00:12:23,619
algorithm number, both A1 and A2 are
eligible and have bid on the blue queries.

195
00:12:24,830 --> 00:12:28,480
and, but the balance algor, and both,
at this point, have unspent budget.

196
00:12:28,480 --> 00:12:33,480
But the balance algorithm decided
to decide this blue query to A2.

197
00:12:33,480 --> 00:12:38,290
Going by the characteristic of the balance
algorithm, the balance algorithm

198
00:12:38,290 --> 00:12:42,940
assigns the query to the advertiser
with the larger unspent balance.

199
00:12:42,940 --> 00:12:47,440
So at this point, when the blue query
was assigned to A2, it must be the case

200
00:12:47,440 --> 00:12:52,838
that A,
A2's balance was larger than A1's balance.

201
00:12:54,860 --> 00:12:55,850
Okay?

202
00:12:55,850 --> 00:12:59,180
This is just another way of saying
that at this point, the number of

203
00:12:59,180 --> 00:13:02,980
queries assigned to A1 must have been
greater than the number of queries that

204
00:13:02,980 --> 00:13:07,030
were assigned to A2 since both started out
with the same budged in the beginning.

205
00:13:08,410 --> 00:13:12,710
Now, we know that,
at least B, B, this is the,

206
00:13:12,710 --> 00:13:15,980
the, I think B, blue queries
have already been assigned to,

207
00:13:17,990 --> 00:13:21,290
B by two blue queries have already
been assigned to A2 at this point.

208
00:13:22,610 --> 00:13:23,740
Right?

209
00:13:23,740 --> 00:13:29,720
and, since we've said that the number of
queries assigned to A1 at this point has

210
00:13:29,720 --> 00:13:33,000
to be greater than the number of queries
that are assigned to A2 at this point.

211
00:13:33,000 --> 00:13:36,900
It must be the case that the number of
queries assigned to A1 at this point,

212
00:13:36,900 --> 00:13:39,670
which is Y, is also greater than or
equal to B divided by two.

213
00:13:41,680 --> 00:13:44,260
And so
we've shown that Y is greater than or

214
00:13:44,260 --> 00:13:46,339
equal to B divided by two
in the second case as well.

215
00:13:47,390 --> 00:13:49,900
Now, since we've shown
that y is greater than or

216
00:13:49,900 --> 00:13:55,300
equal to B by 2 and we've also, we also
know that balance revenue is B plus y.

217
00:13:55,300 --> 00:13:59,660
Since y is greater than or equal to B by 2
we know that the balance revenues is at,

218
00:13:59,660 --> 00:14:02,680
is greater than or equal to 3B by 2 and
therefore the ratio of

219
00:14:02,680 --> 00:14:06,900
the balance revenue to the optimal
revenue is at least three fourths.

220
00:14:06,900 --> 00:14:11,940
Now, we've analyzed the simple case of
balance with exactly two advertisers and

221
00:14:11,940 --> 00:14:14,400
shown that the competitive ratio is two.

222
00:14:14,400 --> 00:14:16,730
But what happens if there
are more than two advertisers?

223
00:14:16,730 --> 00:14:20,150
What happens if there are a large
number of advertisers?

224
00:14:20,150 --> 00:14:23,610
In the case there are a large number
of advertisers, it's it can be

225
00:14:23,610 --> 00:14:28,510
shown that the competitive ratio of
balance is given by this expression.

226
00:14:28,510 --> 00:14:33,750
One minus one over e where e
is the base of the natural

227
00:14:33,750 --> 00:14:39,010
logarithm 2.718 so on and
that is approximately 0.63.

228
00:14:39,010 --> 00:14:43,970
Notice that this competitive ratio 0.63 is

229
00:14:43,970 --> 00:14:47,850
strictly better than half, which is the
competitive ratio of the greedy algorithm.

230
00:14:50,170 --> 00:14:54,540
So, the balance algorithm does much
better than the greedy algorithm,

231
00:14:54,540 --> 00:14:56,380
in terms of competitive ratio.

232
00:14:56,380 --> 00:14:59,030
Now, interestingly,
although I won't be able to show this in

233
00:14:59,030 --> 00:15:02,710
this lecture no online
algorithm can actually do

234
00:15:02,710 --> 00:15:08,910
better than this competitive ratio of one
minus one by e, for the adverse problem.

235
00:15:08,910 --> 00:15:11,850
But what I'm going to do instead,
is I'm going to show you the worst case

236
00:15:11,850 --> 00:15:16,561
example that gives us this
competitive ratio of 1-1 by e