Title: Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

Abstract:
We provide a reduction from revenue maximization to welfare maximization in
multi-dimensional Bayesian combinatorial auctions with arbitrary (possibly
combinatorial) feasibility constraints and independent additive bidders with
arbitrary (possibly combinatorial) demand constraints, appropriately extending
Myerson's single-dimensional result [Myerson81] to this setting. We 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 bid vector v_i is transformed into a virtual bid
vector f_i(v_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 form auctions in settings with arbitrary
feasibility and demand constraints. First, we provide a separation oracle for
determining feasibility of a reduced form auction. 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 approximately
execute both algorithms computationally efficiently given only black box
access to an implementation of the VCG allocation rule, providing two fully
polynomial-time randomized approximation schemes (FPRASs). With high
probability, the separation oracle is correct on all points that are eps-away
from the boundary of the set of feasible reduced forms (in the infinity-norm),
and the decomposition algorithm returns a distribution over virtual VCG
allocation rules whose reduced form is within eps (in the infinity-norm) of
any given feasible reduced form that is eps-away from the boundary.

Our mechanisms run in time polynomial in the number of bidder types and not
type profiles. This running time is always polynomial in the number of
bidders, and scales with the cardinality of the support of each bidder's value
distribution. The running time can be improved to polynomial in both the
number of bidders and number of items in item-symmetric settings by making use
of results from [Daskalakis-W. 12].

Joint work with Yang Cai and Costis Daskalakis.