Truthful approximation mechanisms for restricted combinatorial auctions |
| |
Institution: | 1. Department of IM & IS, School of Management, Fudan University, 200433, Shanghai, China;2. Department of Industrial Economics, School of Management, Fudan University, 200433, Shanghai, China;1. Smith Institute for Political Economy and Philosophy, Chapman University, United States;2. Department of Economics, Simon Fraser University, Canada;3. Department of Economics, Marquette University, United States;1. Department of Electrical Engineering, Technical University of Denmark, Elektrovej 325, DK-2800 Kongens Lyngby, Denmark;2. Department of Economics, Copenhagen Business School, Porcelaenshaven 16 A, Frederiksberg DK-2000, Denmark |
| |
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: | |
本文献已被 ScienceDirect 等数据库收录! |
|