Multi-unit auctions: beyond roberts
Multi-unit auctions: beyond roberts
复制标题
多单位拍卖：超越罗伯茨
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Nisan
中科院分区：
文献类型：
--
作者：
Shahar Dobzinski;N. Nisan
我们展示了激励兼容的多单位拍卖，不是仿射最大化（即，不属于VCG家族），但社会福利近似在1+ε的因子内。对于两个项目的两个投标人拍卖的情况下，我们表明，这些拍卖，被称为分类拍卖，是唯一的可扩展的近似因子优于2。“可扩展”意味着分配不依赖于衡量估值的单位。我们由此推断，任何可扩展的计算效率的激励兼容拍卖的m个项目和n ≥ 2投标人不能近似的社会福利的一个因素内优于2。这与仅在计算约束下就可以达到的任意好的近似值形成对比，并且与实现最优分配的激励相容机制的存在形成对比。
We exhibit incentive compatible multi-unit auctions that are not affine maximizers (i.e., are not of the VCG family) and yet approximate the social welfare to within a factor of 1+ε. For the case of two-item two-bidder auctions we show that these auctions, termed Triage auctions, are the only scalable ones that give an approximation factor better than 2. "Scalable" means that the allocation does not depend on the units in which the valuations are measured. We deduce from this that any scalable computationally-efficient incentive-compatible auction for m items and n ≥ 2 bidders cannot approximate the social welfare to within a factor better than 2. This is in contrast to arbitrarily good approximations that can be reached under computational constraints alone, and in contrast to the existence of incentive-compatible mechanisms that achieve the optimal allocation.