On ascending Vickrey auctions for heterogeneous objects

Sven de Vries, James Schummer*, Rakesh V. Vohra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

77 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)95-118
Number of pages24
JournalJournal of Economic Theory
Volume132
Issue number1
DOIs
StatePublished - Jan 2007

Keywords

  • Combinatorial auctions
  • Duality
  • Primal-dual algorithm
  • Subgradient algorithm
  • Vickrey auctions

ASJC Scopus subject areas

  • Economics and Econometrics

Fingerprint Dive into the research topics of 'On ascending Vickrey auctions for heterogeneous objects'. Together they form a unique fingerprint.

Cite this