  We provide a reduction from revenue maximization to welfare maximization in
multi-dimensional Bayesian auctions with arbitrary (possibly combinatorial)
feasibility constraints and independent bidders with arbitrary (possibly
combinatorial) demand constraints, appropriately extending Myerson's result to
this setting. We also show that every feasible Bayesian auction can be
implemented as a distribution over virtual VCG allocation rules. A virtual VCG
allocation rule has the following simple form: Every bidder's type t_i is
transformed into a virtual type f_i(t_i), via a bidder-specific function. Then,
the allocation maximizing virtual welfare is chosen. Using this
characterization, we show how to find and run the revenue-optimal auction given
only black box access to an implementation of the VCG allocation rule. We
generalize this result to arbitrarily correlated bidders, introducing the
notion of a second-order VCG allocation rule.
  We obtain our reduction from revenue to welfare optimization via two
algorithmic results on reduced forms in settings with arbitrary feasibility and
demand constraints. First, we provide a separation oracle for determining
feasibility of a reduced form. Second, we provide a geometric algorithm to
decompose any feasible reduced form into a distribution over virtual VCG
allocation rules. In addition, we show how to execute both algorithms given
only black box access to an implementation of the VCG allocation rule.
  Our results are computationally efficient for all multi-dimensional settings
where the bidders are additive. In this case, our mechanisms run in time
polynomial in the total number of bidder types, but not type profiles. For
generic correlated distributions, this is the natural description complexity of
the problem. The runtime can be further improved to poly(#items, #bidders) in
item-symmetric settings by making use of recent techniques.
