Exercise 3.4 Consider the following extension of the sponsored search setting described in Section 2.6. Each bidder i now has a publicly known quality 51'? in addition to a private valuation v.1- per click. As usual, each slot 3' has a CTR 0553-} and 0:1 2 0:2 - - - Z Oik- ch assume that if bidder 1'. is placed in slot j, then the probability of a click is ier}. Thus bidder i. derives value viicrj from the jth slot. Describe the welfaremaximizing allocation rule in this general ized sponsored search set-ting. Prove that this rule is monotone. Give an explicit formula for the perclick payment. of each bidder that ex tends this allocation rule to a DSIC mechanism. 18 Mechanism Design Basics 2.6.3 What We Want ls there an ideal sponsored search auction? Our desiderata are: (l) (2) DSIC. That is, truthful bidding should be a dominant strategy, and never leads to negative utility. Social welfare maximization. rI'hat is, the assignment of bidders to slots should maximize 2:121 1.153,, where 33, now denotes the CTR of the slot to which i. is assigned (or 0 if I". is not assigned to a slot). Each slot can only be assigned to one bidder, and each bidder gets only one slot. Computational efciency. The running time should be polyno~ mial (or even nearlinear) in the size of the input 1:1,... ,1)\". Remember that zillions of these auctions need to be run every davl