The Computational Complexity of Truthfulness in Combinatorial Auctions

Details The Computational Complexity of Truthfulness in Combinatorial Auctions The Computational Complexity of Truthfulness in Combinatorial Auctions

2012-02-13

arxiv.org/abs/1202.2789v1

Computer Science

Computer Science and Game Theory

Scientific paper

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 \cite{D11}, and even for truthful-in-expectation mechanisms \cite{DughmiV11}. 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 {\em 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-\epsilon}$-approximation for a constant $\epsilon>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^\gamma$, where $n$ is the number of bidders and $\gamma>0$ some absolute constant, unless $NP \subseteq P/poly$. In addition, we prove computational hardness results for two related problems.

Affiliated with

Also associated with

No associations

Rating

The Computational Complexity of Truthfulness in Combinatorial Auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Computational Complexity of Truthfulness in Combinatorial Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Computational Complexity of Truthfulness in Combinatorial Auctions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684086