Learning Multi-item Auctions with (or without) Samples

Understand

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of valuations including unit-demand, additive, constrained additive, XOS, and subadditive.

• We obtain our learning results in two settings.
• The first is the commonly studied setting where sample access to the bidders' distributions over valuations is given, for both regular distributions and arbitrary distributions with bounded support.
• Our algorithms require polynomially many samples in the number of items and bidders.