On Ascending Vickrey Auctions for Heterogeneous Objects, Journal of Economic Theory
We construct an ascending auction for heterogeneous objects by applying a primal-dual algorithm to a linear program that represents the efficient-allocation problem for this setting. The auction assigns personalized prices to bundles, and asks bidders to report their preferred bundles in each round. A bidder's prices are increased when he belongs to a "minimally undersupplied" set of bidders. This concept generalizes the notion of "overdemanded" sets of objects introduced by Demange, Gale, and Sotomayor (1986) for the one-to-one assignment problem. Under a submodularity condition, the auction implements the Vickrey-Clarke-Groves outcome; we show that this type of condition is somewhat necessary to do so. When classifying the ascending-auction literature in terms of their underlying algorithms, our auction fills a gap in that literature. We relate our results to the recent work of Ausubel and Milgrom (2002).
Sven de Vries, James Schummer, Rakesh Vohra
de Vries, Sven, James Schummer, and Rakesh Vohra. 2007. On Ascending Vickrey Auctions for Heterogeneous Objects. Journal of Economic Theory. 132(1): 95-118.