September 22, 2010: Seminar - Jason D. Hartline: "Multi-dimensional Mechanism Design and Sequential Posted Pricing"

Seminar Announcement

Multi-dimensional Mechanism Design and Sequential Posted Pricing

Jason D. Hartline
Northwestern University
Electrical Engineering and Computer Science
Wednesday September 22, 2010
11:00 AM -- 12:00 noon
1000 SEO Building


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 ?rst 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 (STOC 2010).

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF