Publication | Closed Access
On the Pseudo-Dimension of Nearly Optimal Auctions
91
Citations
0
References
2015
Year
Mathematical ProgrammingElectronic AuctionEngineeringMachine LearningGame TheoryAlgorithmic LearningMarket Equilibrium ComputationMarket DesignData ScienceSearch CostsAuction TheoryCombinatorial OptimizationMechanism DesignLinear OptimizationEconomicsComputational Learning TheoryMarket MechanismStatistical Learning TheorySimple AuctionsBusinessStatistical InferenceNearly Optimal AuctionsSuch AuctionsOptimal Auctions
This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce t-level auctions to interpolate between simple auctions, such as welfare maximization with reserve prices, and optimal auctions, thereby balancing the competing demands of expressivity and simplicity. We prove that such auctions have small representation error, in the sense that for every product distribution F over bidders’ valuations, there exists a t-level auction with small t and expected revenue close to optimal. We show that the set of t-level auctions has modest pseudo-dimension (for polynomial t) and therefore leads to small learning error. One consequence of our results is that, in arbitrary single-parameter settings, one can learn a mechanism with expected revenue arbitrarily close to optimal from a polynomial number of samples.