Abstract

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of bidder valuations including unit-demand, additive, constrained additive, XOS, and subadditive. We achieve our learning results in two settings. The first is the commonly studied setting where sample access to the type distributions of the bidders is provided, for both regular distributions and arbitrary distributions with bounded support. The second is a more general min-max learning setting that we introduce, where we are given approximate type distributions and we seek to compute mechanisms whose revenue is approximately close to optimal simultaneously for all distributions that are close to the ones we were given. All results hold for type distributions satisfying the standard (and necessary) independent across items properties.
 
(Joint work with Yang Cai)