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
Y1 - 2008
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 -