Learning Simple Auctions
  We present a general framework for proving polynomial sample complexity
bounds for the problem of learning from samples the best auction in a class of
"simple" auctions. Our framework captures all of the most prominent examples of
"simple" auctions, including anonymous and non-anonymous item and bundle
pricings, with either a single or multiple buyers. The technique we propose is
to break the analysis of auctions into two natural pieces. First, one shows
that the set of allocation rules have large amounts of structure; second,
fixing an allocation on a sample, one shows that the set of auctions agreeing
with this allocation on that sample have revenue functions with low
dimensionality. Our results effectively imply that whenever it's possible to
compute a near-optimal simple auction with a known prior, it is also possible
to compute such an auction with an unknown prior (given a polynomial number of
samples).
