SPECIAL TIME: 1:30 -- 2:20 pm,  Tuesday, Jan 20, 2009

PLACE: CSE 503  

SPEAKER: Jason Hartline
         Northwestern University

TITLE: Approximation in Multi-dimensional Mechanism Design


ABSTRACT: 

Over the last decade methodologies from the microeconomics subfield of
mechanism design have been imported into computer science to study the
design of algorithms in economic settings such as the Internet.  Much
of the effort in these studies has been on merging computer science
mindsets of "worst-case" and "poly-time" leaving untouched the most
important open question in economics, i.e., identifying the mechanism
by which a seller facing agents with multi- dimensional preferences
drawn from a known distribution can maximize profit.  In such a
setting there is clearly a mechanism, over the class of all
mechanisms, that achieves the highest expected profit in (Bayes-Nash)
equilibrium.  What is it?

In this talk I will show how, with the notion of approximation, one of
the most important exports form computer science into economics, we
are able to get a succinct, and intuitive description of a
near-optimal mechanism for a multi-item unit-demand pricing problem
(e.g., there are multiple houses for sale, a buyer wants to buy a
house, they have an independently drawn value for each house, given
prices on each house they will choose the one that maximizes their
utility = value - price, how can we price the houses to maximize the
seller's profit).  We give a simple three approximation that is based
heavily on Myerson's (1981) theory of optimal auctions in
single-dimensional settings.