Limitations of randomized mechanisms for combinatorial auctions

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.