## March 27th : Tim Roughgarden

March 24, 2011 by ilannehama

Title: Revenue Maximization with a Single Sample

Speaker: Tim Roughgarden, Stanford University, http://theory.stanford.edu/~tim/

Abstract:

We design and analyze approximately revenue-maximizing auctions in general single-parameter settings. Bidders have publicly observable attributes, and we assume that the valuations of indistinguishable bidders are independent draws from a common distribution. Crucially, we assume all valuation distributions are a priori unknown to the seller. Despite this handicap, we show how to obtain approximately optimal expected revenue — nearly as large as what could be obtained if the distributions were known in advance—under quite general conditions.

Our most general result concerns arbitrary downward closed single-parameter environments and valuation distributions that satisfy a standard hazard rate condition. We also assume that no bidder has a unique attribute value, which is obviously necessary with unknown and attribute dependent valuation distributions. Here, we give an auction that, for every such environment and unknown valuation distributions, has expected revenue at least a constant fraction of the expected optimal welfare (and hence revenue). A key idea in our auction is to associate each bidder with another that has the same attribute, with the second bidder’s valuation acting as a random reserve price for the first. Conceptually, our analysis shows that even a single sample from a distribution — the second bidder’s valuation — is sufficient information to obtain near-optimal expected revenue, even in quite general settings.

Joint work with peerapong dhangwotnotai and qiqi yan.

### Like this:

Like Loading...

*Related*

on March 28, 2011 at 7:29 pm |Report on AGT semester I: Talks with Agendas « Algorithmic Game-Theory/Economics[…] Roughgarden talked in our group’s Computation and Economics seminar and his agenda was the possibility of designing “distribution-free” mechanisms. The […]