The computational complexity of truthfulness in combinatorial auctions
The computational complexity of truthfulness in combinatorial auctions
复制标题
组合拍卖中真实性的计算复杂性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
J. Vondrák
中科院分区：
文献类型：
--
作者：
Shahar Dobzinski;J. Vondrák
算法机制设计的一个基本问题是在真实性和计算可追溯性之间是否存在固有的冲突：特别是，组合拍卖的多项式时间真实机制是否可证明在近似比方面比非真实机制弱。这个问题最近在组合拍卖的普遍真实机制[4]中得到了解答，甚至在真实预期机制[4]中也得到了解答。然而，这两个结果都是基于由值神谕给出的估值的信息理论论证，并为简洁描述的估值类的多项式时间真实机制留下了可能性。
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 m1/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.