Exercise 2.8 Recall the sponsored search setting of Section 2.6, in which bidder 1' has a valuation \"Uz- per click. There are 34: slots with click-through rates (CTRs) 01 33 0:2 2 -- ~ 2 Cl'k- The social welfare of an assignment of bidders to slots is 2?:1 vim, where 2:;- equals the CTR of the slot to which i is assigned (or 0 if bidder i is not assigned to any slot). Prove that the social welfare is maximized by assigning the bidder with the ith highest valuation to the ith best slot for 3' : 1, 2, . . . , k. Comments on Exercise 2.8: As a hint, here is a proof of a relevant algebraic fact. You will want to incorporate this into your proof. If we have two strings of numbers :11 2 a2 2 - - - 2 an and b1 2 b2 2 . . . on then among all sums of products a1: bi, where a is paired with a different b, we nd the largest sum is (1161 + (12 b2 + - - - + anbn. You can prove this by induction. For the base case lets show that if (:51 2 a2 and in 2 b2, that min + agbz 2 a1b2 + azbl. To do this notice that the difference is nonegative: (1151 + (1252 1'52 a2b1 = 1'51 :5;le + 2b2 (1251 = 1('33'1 b2) {12031 52) (1) = ((11 a2)(b1 b2) 2 0: as both factors are 2 0. Now for the inductive step assume the claim is true for sums of n 1 terms and show it is true for sums of as. terms. Consider the random sum of all)\". terms. If it contains (11 b1, then it remains only to prove that the remaining terms aibj sum up to less than agbz + (13-53 + - - - + ans)... As this sum has in. 1 terms, this follows by assumption. Now assume that 0.151 is not in our sum. Then there are some terms 0.1 b]- and akbl in it. Then (albl '1' (11:55) (albj- + (IR-bl) = ((1.1 Gk)(b1 bi) Z 0 so we may increase the sum by replacing albj- + ak b1 with al b1 + akbj. Our new sum contains albl already, so we have reduced the problem to the previous case