Timezone: »

 
Poster
On the Pseudo-Dimension of Nearly Optimal Auctions
Jamie Morgenstern · Tim Roughgarden

Tue Dec 08 04:00 PM -- 08:59 PM (PST) @ 210 C #84
in Poster Session »

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.

[ PDF] 

Author Information

Jamie Morgenstern (University of Pennsylvania)
Tim Roughgarden (Stanford University)

More from the Same Authors