An Ascending Vickrey Auction for Selling Bases of a Matroid
An Ascending Vickrey Auction for Selling Bases of a Matroid
复制标题
销售拟阵底座的升序维克瑞拍卖
DOI：
10.1287/opre.1100.0888
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Vohra
中科院分区：
文献类型：
--
作者：
S. Bikhchandani;S. D. Vries;J. Schummer;R. Vohra
考虑将一捆捆不可分割的商品出售给具有凹效用的买家，这些凹效用在货币和商品上是可加性分离的。我们提出了一个上升拍卖的情况下，卖方被限制出售束的元素形成的基础上的拟阵。它很容易推广到多拟阵。应用包括调度，同质商品的分配和空间分布的市场，等等。我们的上升拍卖诱导买家真实出价，并返回经济有效的基础。与其他这种环境下的递增拍卖不同，我们的拍卖在伪多项式或多项式时间内运行。此外，我们证明了非拟阵独立集系统的上升拍卖的不可能性。
Consider selling bundles of indivisible goods to buyers with concave utilities that are additively separable in money and goods. We propose an ascending auction for the case when the seller is constrained to sell bundles whose elements form a basis of a matroid. It extends easily to polymatroids. Applications include scheduling, allocation of homogeneous goods, and spatially distributed markets, among others. Our ascending auction induces buyers to bid truthfully and returns the economically efficient basis. Unlike other ascending auctions for this environment, ours runs in pseudopolynomial or polynomial time. Furthermore, we prove the impossibility of an ascending auction for nonmatroidal independence set-systems.