An Ascending Vickrey Auction for Selling Bases of a Matroid

• 成果类型: Article
• 署名作者: Bikhchandani, Sushil; de Vries, Sven; Schummer, James; Vohra, Rakesh V.
• 署名单位: University of California System; University of California Los Angeles; Universitat Trier; Northwestern University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0888
• 发表日期: 2011
• 页码: 400-413
• 关键词: commodities; objects

摘要

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.