On ascending Vickrey auctions for heterogeneous objects

• 成果类型: Article
• 署名作者: de Vries, Sven; Schummer, James; Vohra, Rakesh V.
• 署名单位: Northwestern University; Technical University of Munich
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2005.07.010
• 发表日期: 2007
• 页码: 95-118
• 关键词: Vickrey auctions; combinatorial auctions; Duality; primal-dual algorithm; subgradient algorithm

摘要

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. (c) 2005 Elsevier Inc. All rights reserved.