Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding

We design the first truthful-in-expectation, constant-factor approximation mechanisms for NP-hard cases of the welfare maximization problem in combinatorial auctions with non-identical items and in combinatorial public projects. Our results apply to bidders with valuations that are nonnegative linear combinations of gross substitutes valuations, a class that encompasses many of the most well-studied subclasses of submodular functions, including coverage functions and weighted matroid rank functions. Our mechanisms have expected polynomial running time and achieve an approximation factor of 1 − 1/e. This approximation factor is the best possible for both problems, even for known and explicitly given coverage valuations, assuming P 6 = NP. Recent impossibility results suggest that our results cannot be extended to a significantly larger valuation class. Both of our mechanisms are instantiations of a new framework for designing approximation mechanisms based on randomized rounding algorithms. The high-level idea of this framework is to optimize directly over the (random) output of the rounding algorithm, rather than the usual (and rarely truthful) approach of optimizing over the input to the rounding algorithm