On the Pseudo-Dimension of Nearly Optimal Auctions
On the Pseudo-Dimension of Nearly Optimal Auctions
复制标题
论近乎最优拍卖的伪维度
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
Jamie Morgenstern;Tim Roughgarden
本文开发了一种植根于统计学习理论的一般方法，以从数据中学习近似收入最大化的拍卖，我们引入了T级拍卖，以在简单的拍卖之间进行插入表达和简单性的竞争要求。估值，T级拍卖量很小，预期收入接近最佳我们的结果是，在任意的单参数设置中，可以从多项式数量的样本中学习具有预期收入的最佳收入的机制。
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.