About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
EC 2012
Conference paper
The computational complexity of truthfulness in combinatorial auctions
Abstract
One of the fundamental questions of Algorithmic Mechanism Design is whether there exists an inherent clash between truthfulness and computational tractability: in particular, whether polynomial-time truthful mechanisms for combinatorial auctions are provably weaker in terms of approximation ratio than non-truthful ones. This question was very recently answered for universally truthful mechanisms for combinatorial auctions [4], and even for truthful-in-expectation mechanisms [12]. However, both of these results are based on information-theoretic arguments for valuations given by a value oracle, and leave open the possibility of polynomial-time truthful mechanisms for succinctly described classes of valuations. This paper is the first to prove computational hardness results for truthful mechanisms for combinatorial auctions with succinctly described valuations. We prove that there is a class of succinctly represented submodular valuations for which no deterministic truthful mechanism provides an m 1/2-ε-approximation for a constant ε > 0, unless NP = RP (m denotes the number of items). Furthermore, we prove that even truthful-in-expectation mechanisms cannot approximate combinatorial auctions with certain succinctly described submodular valuations better than within n γ, where n is the number of bidders and γ > 0 some absolute constant, unless NP ⊆ P/poly. In addition, we prove computational hardness results for two related problems. © 2012 ACM.