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

Full description

Saved in:
Bibliographic Details
Published in:Journal of economic theory 2007, Vol.132 (1), p.95-118
Main Authors: de Vries, Sven, Schummer, James, Vohra, Rakesh V.
Format: Article
Language:English
Subjects:
Algorithms
Auctions
Bidding
Bids
Combinatorial auctions
Duality
Economic theory
Linear programming
Primal-dual algorithm
Studies
Subgradient algorithm
Vickrey auctions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-0531
1095-7235
DOI:10.1016/j.jet.2005.07.010