Ascending auctions for integral (poly)matroids with concave nondecreasing separable values

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


Consider a seller with a fixed set of resources that can produce a variety of bundles from a set E of indivisible goods. Several bidders are interested in purchasing a bundle of such goods. Their utility for a bundle is privately known and represented by an additively separable, nondecreasing and concave function. In the case when the set of feasible bundles forms an integral polymatroid (or its basis), we present an ascending auction which in equilibrium returns the efficient outcome. Formally, given an integral, monotone, submodular function ρ: E & ℕ 0 with ρ(φ) = 0 the integral points of the polymatroid P ρ represent various allocations which the seller can feasibly offer. Buyers j ∈ N have privately known valuations υ j(x j) for x j ∈ P ρ with the property that υ j(x j) = Σ e∈Eυ j e(x j e) where the υ j e(x j e) are nondecreasing and concave. We present an ascending auction running in pseudo-polynomial time in which truthful bidding is an ex post equilibrium and results in the efficient outcome. Our auction strictly generalizes the ascending auction of Demange, Gale, and Sotomayor (1986) applied to scheduling matroids (agents want to schedule several jobs; their due and release dates are common knowledge, but the value of completing a job is private information). For a suitable class of uniform matroids, our auction reduces to the ascending auction of Ausubel (2004) for the allocation of multiple units of a homogeneous good when agents have decreasing marginal values in quantities. Finally, our auction can be applied to the setting of spatially distributed markets considered in Babaioff, Nisan, and Pavlov (2004).

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages10
StatePublished - 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CitySan Francisco, CA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Ascending auctions for integral (poly)matroids with concave nondecreasing separable values'. Together they form a unique fingerprint.

Cite this