Privacy-aware mechanism design
Kobbi Nissim, Claudio Orlandi, Rann Smorodinsky · 2012
Mechanism design deals with distributed algorithms that are executed with self-interested agents. The designer, whose objective is to optimize some function of the agents private types, needs to construct a computation that takes into account agent incentives which are not necessarily in alignment with the objective of the mechanism. Traditionally, mechanisms are designed for agents who only care about the utility they derive from the mechanism outcome, which often fully or partially discloses their (declared) types. Such mechanisms may become inadequate when agents are privacy-aware, i.e., when their loss of privacy adversely affects their utility. In such cases ignoring privacy-awareness in the design of a mechanism may render it not incentive compatible, and hence inefficient. Interestingly, and somewhat counter-intuitively, Xiao [eprint 2011] has recently showed that this can happen even when the mechanism preserves a strong notion of privacy.