Title: The Exponential Mechanism for Social Welfare: Private,
Truthful, and Nearly Optimal
Abstract: 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 in.nity. To our knowledge, this is the .rst
general tool for designing mechanisms that are both truthful and
differentially private.