Limitations of randomized mechanisms for combinatorial auctions

Abstract

We address the following fundamental question in the area of incentive-compatible mechanism design: Are truthful-in-expectation mechanisms compatible with polynomial-time approximation? In particular, can polynomial-time truthful-in-expectation mechanisms achieve a near-optimal approximation ratio for combinatorial auctions with submodular valuations?We prove that this is not the case: There is a constant γ>0 such that there is no randomized mechanism that is truthful-in-expectation - or even approximately truthful-in-expectation - and guarantees an m^-γ-approximation to the optimal social welfare for combinatorial auctions with submodular valuations in the value oracle model. In contrast, a non-truthful (1-1/e)-approximation algorithm is known (Vondrák, 2008), and a truthful-in-expectation (1-1/e)-approximation mechanism was recently developed for the special case of coverage valuations (Dughmi et al., 2011b). We also prove an analogous result for the combinatorial public projects (CPP) problem. Both our results present a significant separation between coverage functions and submodular functions, which does not occur for these problems without strategic considerations.