Tim Roughgarden - Stanford
Tim Roughgarden from Stanford will present "Data-Driven Optimal Auction Theory".
The traditional economic approach to revenue-maximizing auction design posits a known prior distribution over what bidders are willing to pay, and then solves for the auction that maximizes the seller's expected revenue with respect to this distribution. But where does this distribution come from? One obvious answer is from data, in the form of previous bids by comparable bidders in auctions for comparable items. How much data is necessary and sufficient to determine which auction you should run? This question turns out to be technically interesting already for the problem of approximating the monopoly price of an unknown distribution from samples, for which we prove tight sample complexity bounds. We then use tools from statistical learning theory to tackle the more general problem of learning near-optimal auctions from samples. For classes of auctions that are "not too complex," such as reserve-price-based auctions, we show that a near-optimal auction from the class can be learned from a modest (i.e., polynomial) number of samples.
Includes joint work with Richard Cole, Zhiyi Huang, Yishay Mansour, and Jamie Morgenstern.