Problems Problem 2.1 This problem considers 011111113 single-item auctions, where bidders arrive one-by-one. Assume that the number 11 of bid- ders is known, and that bidder 1 has a private valuation 11;. We consider auctions of the following form. Online Single-Item Auction For each bidder arrival 1' = 1, 2, . . . ,11: if the item has not been sold in a previous iteration, formulate a price p, and then accept a bid 3),; from bidder 1 if p, 0 independent of 11, there is no deterministic online auction that always achieves social welfare at least c times the highest valuation. (c) (H) Assume that bidders bid truthfully. Prove that there is a constant c > 0, independent of 11, and a deterministic online auction with the following guarantee: for every unordered set of 11 bidder valuations, if the bidders arrive in a uniformly random Downloaded from https:!!ww.cambridge.org}core. AMSIKaist Digital Sci Lib, on 16]u|2018 at 12:17:20, subject to the Cambridge Core tem'is of use. available at httpsrfwmvcambri dge.org1'corefterms. httpswdoicrgl'l 0.101?!CE509?8'| 316179309003 Notes, Problems, and Exercises 23 order, then the expected welfare of the auction's outcome is at least c times the highest valuation