Truthful approximation mechanisms for restricted combinatorial auctions
Ahuva Mu'alem () and
Noam Nisan
Games and Economic Behavior, 2008, vol. 64, issue 2, 612-631
Abstract:
When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness). We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O'Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios.
Keywords: Mechanism; design; Combinatorial; auctions; Multi-unit; auctions; Multi-unit; combinatorial; auctions; Approximation; algorithms (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00050-X
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:64:y:2008:i:2:p:612-631
Access Statistics for this article
Games and Economic Behavior is currently edited by E. Kalai
More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().