On ascending Vickrey auctions for heterogeneous objects

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 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 various ascending auctions in the literature.

Joint work with James Schummer and Rakesh V. Vohra