  We provide a computationally efficient black-box reduction from mechanism
design to algorithm design in very general settings. Specifically, we give an
approximation-preserving reduction from truthfully maximizing \emph{any}
objective under \emph{arbitrary} feasibility constraints with \emph{arbitrary}
bidder types to (not necessarily truthfully) maximizing the same objective plus
virtual welfare (under the same feasibility constraints). Our reduction is
based on a fundamentally new approach: we describe a mechanism's behavior
indirectly only in terms of the expected value it awards bidders for certain
behavior, and never directly access the allocation rule at all.
  Applying our new approach to revenue, we exhibit settings where our reduction
holds \emph{both ways}. That is, we also provide an approximation-sensitive
reduction from (non-truthfully) maximizing virtual welfare to (truthfully)
maximizing revenue, and therefore the two problems are computationally
equivalent. With this equivalence in hand, we show that both problems are
NP-hard to approximate within any polynomial factor, even for a single monotone
submodular bidder.
  We further demonstrate the applicability of our reduction by providing a
truthful mechanism maximizing fractional max-min fairness. This is the first
instance of a truthful mechanism that optimizes a non-linear objective.
