On Optimal Multidimensional Mechanism Design


June 22, 2011


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)


Constantinos Daskalakis

Constantinos (or Costis) Daskalakis is an Assistant Professor of EECS at MIT. He completed his undergraduate studies in Greece, at the National Technical University of Athens, and obtained a PhD in Computer Science from UC Berkeley. After Berkeley he was a postdoctoral researcher in Microsoft Research New England, and since 2009 he has been at the faculty of MIT. His research interests lie in Algorithmic Game Theory and Applied Probability, in particular computational aspects of markets and the Internet, social networks, and computational problems in Biology. Costis has been honored with a 2007 Microsoft Graduate Research Fellowship, the 2008 Game Theory and Computer Science Prize from the Game Theory Society, the 2008 ACM Doctoral Dissertation Award, a NSF Career Award, a 2010 Sloan Foundation Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, and the MIT Ruth and Joel Spira Award for Distinguished Teaching.