Computationally-feasible truthful auctions for convex bundles

• 成果类型: Article; Proceedings Paper
• 署名作者: Babaioff, Moshe; Blumrosen, Liad
• 署名单位: University of California System; University of California Berkeley; Hebrew University of Jerusalem
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2006.07.002
• 发表日期: 2008
• 页码: 588-620
• 关键词: Mechanism design; auctions; Approximation algorithms

摘要

In many economic settings, like spectrum and real-estate auctions, geometric figures on the plane are for sale. Each bidder bids for his desired figure, and the auctioneer has to choose a set of disjoint figures that maximizes the social welfare. In this work, we design mechanisms that are both incentive compatible and computationally feasible for these environments. Since the underlying algorithmic problem is computationally hard, these mechanisms cannot always achieve the optimal welfare; Nevertheless, they do guarantee a fraction of the optimal solution. We differentiate between two information models-when both the desired figures and their values are unknown to the auctioneer or when only the agents' values are private data. We guarantee different fractions of the optimal welfare for each information model and for different families of figures (e.g., arbitrary convex figures or axis-aligned rectangles). We suggest using a measure on the geometric diversity of the figures for expressing the quality of the approximations that our mechanisms provide. (C) 2006 Elsevier Inc. All rights reserved.