Multi-unit auctions: Beyond Roberts

• 成果类型: Article
• 署名作者: Dobzinski, Shahar; Nisan, Noam
• 署名单位: Weizmann Institute of Science; Hebrew University of Jerusalem
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2014.04.006
• 发表日期: 2015
• 页码: 14-44
• 关键词: Incentive compatibility; Incentive compatible mechanism

摘要

We study environments with m homogenous items and two bidders, where the private information of each bidder consists of a monotone valuation (multi-unit auctions). We analyze ex-post implementable social choice functions where the dominant strategy of a bidder is to reveal his valuation. A result by Green and Laffont [8] implies that an efficient outcome can only be ex-post implemented by VCG payments. However, the VCG mechanism has well-known drawbacks, such as low revenue and computational intractability. Thus we seek alternatives by allowing approximate efficiency instead of full efficiency. We exhibit a new family of auctions: for every epsilon > 0 there exists an ex-post implementable social choice function of this family that is not of the VCG family, yet the value of the selected allocation is always within a multiplicative factor of (1 + epsilon) of the value of efficient allocation. We term these auctions triage auctions. We then proceed to characterizing ex-post implementable social choice functions that are approximately efficient. For the case of two-item two-bidder auctions, we show that triage auctions are the only scalable ex-post implementable social choice functions that always output a solution with value greater than half of the value of the efficient allocation. Scalable means that the allocation does not depend on the units (the currency) in which the valuations are measured. We use the two-item characterization to provide an almost complete description of all scalable ex-post implementable social choice functions for any number of items and show that they usually identify with triage auctions. (C) 2014 Elsevier Inc. All rights reserved.