Truthful Mechanisms for Agents That Value Privacy

Recent work has constructed economic mechanisms that are both truthful and dierentially private. In these mechanisms,
privacy is treated separately from the truthfulness; it is not incorporated in players’ utility functions (and doing so has been
shown to lead to non-truthfulness in some cases). In this work, we propose a new, general way of modelling privacy in
players’ utility functions. Specifically, we only assume that if an outcome o has the property that any report of player i would
have led to o with approximately the same probability, then o has small privacy cost to player i. We give three mechanisms
that are truthful with respect to our modelling of privacy: for an election between two candidates, for a discrete version of
the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As
the number n of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of n).