On Optimal Multidimensional Mechanism Design

In his seminal paper, Myerson [1981] provides a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. His design has been generalized to various related settings, but despite much research effort there is no optimal auction known to date for the multiple-item multiple-bidder problem, known in the literature as the “optimal multidimensional mechanism design problem”. We solve this problem when either the number of bidders or the number of items is a constant. In the first setting, we need that the values of each bidder for the items are i.i.d., but allow 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 bidders are i.i.d. For all epsilon 0, we obtain a computationally efficient additive epsilon-approximation, when the value distributions are bounded, or a multiplicative (1-epsilon)-approximation when the value distributions are unbounded, but satisfy the Monotone Hazard Rate condition. When there is a single bidder, we generalize these results to independent but not necessarily identically distributed value distributions, and to independent regular distributions.

(This is joint work with Yang Cai and Matt Weinberg)