Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder’s values for the items are sampled from a possibly correlated, item-symmetric distribution, allowing different distributions for each bidder. In the second setting, we allow the values of each bidder for the items to be arbitrarily correlated, but assume that the distribution of bidder types is bidder-symmetric. These symmetric distributions include i.i.d. distributions, as well as many natural correlated distributions. E.g., an item-symmetric distribution can be obtained by taking an arbitrary distribution, and “forgetting ” the names of items; this could arise when different members of a bidder population have various sorts of correlations among the items, but the items are “the same ” with respect to a random bidder from the population. For all > 0, we obtain a computationally efficient additive -approximation, when the value distributions are bounded, or a multiplicative (1−)-approximation when the value distributions are unbounded, but satisfy the Monotone Hazard Rate condition, covering a widely studie