  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 m matroid rank sums (MRS), which encompass most concrete examples of
submodular functions studied in this context, including coverage functions,
matroid weighted-rank functions, and convex combinations thereof. 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 approach leads to
truthful-in-expectation mechanisms, and these mechanisms can be implemented
efficiently when the corresponding objective function is concave. For bidders
with MRS valuations, we give a novel randomized rounding algorithm that leads
to both a concave objective function and a (1-1/e)-approximation of the optimal
welfare.
