An ascending vickrey auction for selling bases of a matroid

Sushil Bikhchandani*, Sven De Vries, James Schummer, Rakesh V. Vohra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


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 setsystems.

Original languageEnglish (US)
Pages (from-to)400-413
Number of pages14
JournalOperations Research
Issue number2
StatePublished - Mar 1 2011


  • Auction
  • Combinatorial
  • Matroid
  • Multi-item
  • Polymatroid
  • Vickrey

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'An ascending vickrey auction for selling bases of a matroid'. Together they form a unique fingerprint.

Cite this