Simple and Nearly Optimal Multi-Item Auctions
Simple and Nearly Optimal Multi-Item Auctions
复制标题
简单且近乎最优的多件物品拍卖
DOI：
10.1137/1.9781611973105.41
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Zhiyi Huang
中科院分区：
文献类型：
--
作者：
Yang Cai;Zhiyi Huang
在两个条件下，我们提出了一个多项式时间近似方案（PTAS）的贝叶斯最优多物品多投标人拍卖问题。首先，投标人是独立的，具有附加估值，并且来自同一人群。其次，每个投标人的项目的价值分布是独立的，但不一定相同的单调风险率（MHR）分布。对于非i.i.d.投标人，我们还提供了一个PTAS时，投标人的数量是小。在此之前，我们的工作，即使是一个单一的投标人，只有常数因子近似已知。
我们的机制的另一个吸引人的特点是简单的分配规则。事实上，我们使用的机制是第二价格拍卖与保留价的每一个项目单独，或VCG分配与一些外围项目，需要额外的处理。令人惊讶的是，如此简单的分配规则足以获得近乎最优的收入。
We provide a Polynomial Time Approximation Scheme (PTAS) for the Bayesian optimal multi-item multi-bidder auction problem under two conditions. First, bidders are independent, have additive valuations and are from the same population. Second, every bidder's value distributions of items are independent but not necessarily identical monotone hazard rate (MHR) distributions. For non-i.i.d. bidders, we also provide a PTAS when the number of bidders is small. Prior to our work, even for a single bidder, only constant factor approximations are known.
Another appealing feature of our mechanism is the simple allocation rule. Indeed, the mechanism we use is either the second-price auction with reserve price on every item individually, or VCG allocation with a few outlying items that requires additional treatments. It is surprising that such simple allocation rules suffice to obtain nearly optimal revenue.