CaltechAUTHORS
  A Caltech Library Service

Truthful approximation mechanisms for restricted combinatorial auctions

Mu'alem, Ahuva and Nisan, Noam (2008) Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior, 64 (2). pp. 612-631. ISSN 0899-8256. https://resolver.caltech.edu/CaltechAUTHORS:MUAgeb08

[img]
Preview
PDF - Accepted Version
See Usage Policy.

205Kb
[img] PDF
Restricted to Caltech community only
See Usage Policy.

205Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:MUAgeb08

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://doi.dx.org/10.1016/j.geb.2007.12.009DOIUNSPECIFIED
Additional Information:Copyright © 2008 Elsevier Inc. Received 20 April 2006. Published November 2008. Available online 29 February 2008. We thank Daniel Lehmann, Ron Lavi, Shahar Dobzinski, and Liad Blumrosen for helpful comments and Gil Kalai for an early discussion. Special Issue in Honor of Michael B. Maschler, Games and Economic Behavior Volume 64, Issue 2, November 2008.
Subject Keywords:Mechanism design; Combinatorial auctions; Multi-unit auctions; Multi-unit combinatorial auctions; Approximation algorithms
Issue or Number:2
Record Number:CaltechAUTHORS:MUAgeb08
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:MUAgeb08
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13158
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:02 Feb 2009 23:47
Last Modified:03 Oct 2019 00:35

Repository Staff Only: item control page