The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal

In this work we show that for any mechanism design problem with the objective of maximizing social welfare, the exponential mechanism can be implemented as a truthful mechanism while still preserving differential privacy. Our instantiation of the exponential mechanism can be interpreted as a generalization of the VCG mechanism in the sense that the VCG mechanism is the extreme case when the privacy parameter goes to infinity. To our knowledge, this is the first general tool for designing mechanisms that are both truthful and differentially private.

Speaker Details

Zhiyi Huang is a 4th-year PhD student at University of Pennsylvania working with Prof. Sampath Kannan and Prof. Aaron Roth. His primary research interest is algorithmic game theory and algorithm design in general. Recently, his research has been focusing on designing mechanisms that satisfy strong privacy guarantee by combining techniques from mechanism design and differential privacy.

Series:
Microsoft Research Talks
Date:
Speakers:
Zhiyi Huang
Affiliation:
University of Pennsylvania

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks