TY - GEN

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

AU - Bikhchandani, Sushil

AU - De Vries, Sven

AU - Schummer, James

AU - Vohra, Rakesh V.

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=58649083473&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58649083473&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58649083473

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 864

EP - 873

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -