### Impossibility Results for Truthful Combinatorial Auctions with Submodular ValuationsImpossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Access Restriction
Subscribed

 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

Source: ACM Digital Library