We consider the classical mathematical economics problem of Bayesian optimal mechanism design where a principal aims to optimize expected revenue when allocating resources to self-interested agents whose preferences are drawn from a known distribution. In single-parameter settings (i.e., where each agent’s preference is given by a single private value for being served and zero for not being served) this problem is solved, but the solution neither practically applicable nor theoretically generalizable to multi-dimensional settings (i.e., the likely case where an each agent’s preference is given by multiple values for each of multiple services available).

In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. We prove that these mechanisms are approximately optimal in single-dimensional settings; moreover, they do not exhibit many of the impractical properties of optimal mechanisms and they generalize to give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve asymmetric multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 2 to 8.

This is joint work with Shuchi Chawla, David Malec, and Balasubramanian Sivan and will appear in STOC'10.