An Ascending Vickrey Auction for Selling Bases of a Matroid

Sushil Bikhchandani, Sven de Vries (), James Schummer () and Rakesh V. Vohra ()
Additional contact information
Sven de Vries: FB IV--Mathematik, Universität Trier, 54286 Trier, Germany
James Schummer: Department of Managerial Economics and Decision Sciences, Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Rakesh V. Vohra: Department of Managerial Economics and Decision Sciences, Kellogg School of Management, Northwestern University, Evanston, Illinois 60208

Operations Research, 2011, vol. 59, issue 2, 400-413

Abstract: 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.

Keywords: matroid; Vickrey; multi-item; combinatorial; auction; polymatroid (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1100.0888 (application/pdf)

Related works:
Working Paper: An Ascending Vickrey Auction for Selling Bases of a Matroid (2005)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:2:p:400-413

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().