TIME: 1:30-2:20 pm,  January 30, 2007

PLACE: EEB 037

TITLE:  Mechanism Design via Differential Privacy

SPEAKER:  Frank McSherry
          Microsoft Research - Silicon Valley
 
ABSTRACT:
We study the role that privacy mechanisms, which prevent the leakage of
specific information about participants, can play in the design of
mechanisms for strategic agents, which must encourage players to
honestly report information. Privacy properties, in addition to their
own intrinsic virtue, ensure that participants have limited effect on
the outcome of the mechanism, and as a consequence have limited
incentive to lie. More precisely, they are $\epsilon$-dominant strategy,
truthful with high probability mechanisms. Moreover, such mechanisms
permit arbitrary externalities in player utility functions, are
automatically resilient to coalitions, and easily allow repeatability.

We study several special cases of the unlimited supply auction problem,
providing new results for digital goods auctions, attribute auctions,
and auctions with arbitrary structural constraints on the prices. As an
important prelude to developing a privacy-preserving auction mechanism,
we introduce and study a generalization of previous privacy work that
accommodates the high sensitivity of the auction setting, where a single
participant may dramatically alter the optimal fixed price, and a slight
change in the offered price may take the revenue from optimal to zero.