We obtain a characterization of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting.
Our characterization is enabled by a novel, constructive proof of Border's theorem [Border 1991], and a new generalization of this theorem to independent (but not necessarily identically distributed) bidders, improving upon the results of [Border 2007, Che-Kim-Mierendor ff 2011]. For a single item and independent (but not necessarily identically distributed) bidders, we show that any feasible reduced form auction can be implemented as a distribution over hierarchical mechanisms. We also give a polynomial-time algorithm for determining feasibility of a reduced form auction, or providing a separation hyperplane from the set of feasible reduced forms. To complete the picture, we provide polynomial-time algorithms to find and exactly sample from a distribution over hierarchical mechanisms consistent with a given feasible reduced form.
All our results generalize to multi-item reduced form auctions for independent, additive bidders. For multiple items, additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders, we give a proper generalization of Border's Theorem, and characterize feasible reduced form auctions as multi-commodity flows in related multi-commodity flow instances. We also show that our generalization holds for a broader class of feasibility constraints, including the intersection of any two matroids.
As a corollary of our results we obtain revenue-optimal, Bayesian Incentive Compatible (BIC) mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles of items, and the bidders are independent. Our mechanisms run in time polynomial in the total number of bidder types (and not type profiles). This running time is polynomial in the number of bidders, but potentially exponential in the number of items. We improve the running time to polynomial in both the number of items and the number of bidders by using recent structural results on optimal BIC auctions in item-symmetric settings [Daskalakis-Weinberg 2011].
