Hardness of Randomized Truthful Mechanisms for Combinatorial Auctions

The problem of combinatorial auctions is one of the basic questions in algorithmic mechanism design: how can we allocate/sell m items to n agents with private valuations of different combinations of items, so that the agents are motivated to reveal their true valuations and the outcome is (at least approximately) optimal in terms of total utility? While approximation algorithms exist for several non-trivial classes of valuations, they typically do not motivate agents to report truthfully. The classical VCG mechanism, although truthful, is not computationally efficient. Thus the main question is whether the requirements of truthfulness and computational efficiency can be combined, or whether they are incompatible.

We identify a class of explicit (succinctly represented) valuations, for which combinatorial auctions without the requirement of truthfulness admit a (1-1/e)-approximation; however, we prove that unless NP \subset P/poly, there is no randomized truthful-in-expectation mechanism providing approximation better than polynomial in the number of agents. (Previous work by Dobzinski already ruled out deterministic and universally truthful mechanisms in the value oracle model.)

Joint work with Shaddin Dughmi and Shahar Dobzinski.