We design an expected polynomial time, truthful in expectation, (1 − 1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our results apply to bidders with valuations that are matroid rank sums (MRS), which encompass most concrete examples of submodular functions studied in this context, including coverage functions and matroid weighted-rank functions. Our approximation factor is the best possible, even for known and explicitly given coverage valuations, assuming P = NP . Ours is the first truthful-in-expectation and polynomial-time mechanism to achieve a constant-factor approximation for an NP -hard welfare maximization problem in combinatorial auctions with heterogeneous goods and restricted valuations. Our mechanism is an instantiation of a new framework for designing approximation mechanisms based on randomized rounding algorithms. A typical such algorithm first optimizes over a fractional relaxation of the original problem, and then randomly rounds the fractional solution to an integral one. With rare exceptions, such algorithms cannot be converted into truthful mechanisms. The high-level idea of our mechanism design framework is to optimize directly over the (random) output of the rounding algorithm, rather than over the input to the rounding algorithm. This * A full version of this paper is available at
REF present a general framework that also looks at the fractional relaxation of the problem.
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions
STOC '11
Computer Science Mathematics