  In this paper 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.
