Access Restriction

Author Dobzinski, Shahar ♦ Vondrk, Jan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Truthful mechanisms ♦ Computational complexity ♦ Submodular functions
Abstract A long-standing open question in algorithmic mechanism design is whether there exist computationally efficient truthful mechanisms for combinatorial auctions, with performance guarantees close to those possible without considerations of truthfulness. In this article, we answer this question negatively: the requirement of truthfulness can impact dramatically the ability of a mechanism to achieve a good approximation ratio for combinatorial auctions. More precisely, we show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that approximates optimal social welfare within a factor of $m^{1/2™ε}$ must use exponentially many value queries, where $\textit{m}$ is the number of items. Furthermore, we show that there exists a class of succinctly represented submodular valuation functions, for which the existence of a universally truthful polynomial-time mechanism that provides an $m^{1/2™ε}-approximation$ would imply $\textit{NP}$ = $\textit{RP}.$ In contrast, ignoring truthfulness, there exist constant-factor approximation algorithms for this problem, and ignoring computational efficiency, the VCG mechanism is truthful and provides optimal social welfare. These are the first hardness results for truthful polynomial-time mechanisms for any type of combinatorial auctions, even for deterministic mechanisms. Our approach is based on a novel direct hardness technique that completely skips the notoriously hard step of characterizing truthful mechanisms. The characterization step was the main obstacle for proving impossibility results in algorithmic mechanism design so far.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-02-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 1
Page Count 19
Starting Page 1
Ending Page 19

Open content in new tab

   Open content in new tab
Source: ACM Digital Library