Suppose a search engine has three slots {a, b, c} to sell and there are three advertisers {x, y, z}. Wewill assume the basic advertising valuation model in which: each slot i has clickthough rate of ri;each advertiser j has a value v_j per click; and hence the value of advertiser j for slot i is v_ij = r_i v_j .Suppose the clickthrough rates and advertiser per-click values are as follows: r_a = 11, r_b = 5, r_c = 4 and v_x = 9, v_y = 7, v_z = 4. We will also assume that there is a reserve price of 1 per click for any slot.

(a) How will the slots be allocated and what prices will be charged to each advertiser if the search engine uses the VCG mechanism? Explain your answer.

(b) Now lets consider the generalized second-price (GSP) mechanism. Assume that all advertisersbid truthfully (i.e., state their true per-click values). How will the slots be allocated and whatprices will be charged to each advertiser if the search engine uses the GSP mechanism? Explainyour answer.

(c) As in part (b), assume slots are allocated using the GSP mechanism. For each of the threeadvertisers, explain what their best response would be if the other two advertisers bid truthfully.In other words, describe a per-click bid (it may not be unique) that would give them the highestpayoff if the others bid truthfully. Which advertisers (if any) benefit by not bidding truthfully?Please justify your answer.

(d) Unlike the VCG mechanism, GSP may not induce truthful bidding. However, consider thefollowing claim: no advertiser can improve his utility by bidding greater his true per-click value(and may possibly decrease his utility). Give an informal argument that justifies this claim.