(Approximating) Optimal Auctions with Correlated Bidders



Shahar Dobzinski

Monday October 17, 2011
4:00 PM,
5130 Upson Hall



We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We show that one can find in poly time a
deterministic revenue-maximizing auction that guarantees at least 3/5 of the revenue of the best truthful-in-expectation auction. The proof consists of three steps:

(1) Showing that the optimal truthful-in-expectation auction for a constant number of bidders can be computed in polynomial time.
(2) A "derandomization" algorithm that implements every 2-player truthful-in-expectation mechanism as a universally truthful mechanism.
(3) An analysis of three new auctions that have complementary properties.

Joint work with Hu Fu and Bobby Kleinberg.