TechTalk – Learning Optimal Auctions from Data
The design of optimal auctions for revenue maximization is a central topic in Economics. Classical optimal auction theory assumes that bidders’ values are drawn from a known distribution. In reality, the source of such prior information is really past data. Cole and Roughgarden (2014) modeled past data as i.i.d. samples from the value distribution and asked: How many samples are sufficient/necessary to learn a near optimal auction? This TechTalk will introduce a unified theory that yields sample-efficient algorithms with optimal sample complexity for auctions with homogeneous goods, and state-of-the-art sample complexity for auctions with heterogeneous goods. Unlike conventional statistical learning theory which focuses on the complexity of hypothesis classes, our new theory relies on the simplicity of data distributions and a monotonicity property of these problems.