Abstract
We consider a platform's problem of collecting data from privacy sensitiveusers to estimate an underlying parameter of interest. We formulate thisquestion as a Bayesian-optimal mechanism design problem, in which an individualcan share her (verifiable) data in exchange for a monetary reward or services,but at the same time has a (private) heterogeneous privacy cost which wequantify using differential privacy. We consider two popular differentialprivacy settings for providing privacy guarantees for the users: central andlocal. In both settings, we establish minimax lower bounds for the estimationerror and derive (near) optimal estimators for given heterogeneous privacy losslevels for users. Building on this characterization, we pose the mechanismdesign problem as the optimal selection of an estimator and payments that willelicit truthful reporting of users' privacy sensitivities. Under a regularitycondition on the distribution of privacy sensitivities we develop efficientalgorithmic mechanisms to solve this problem in both privacy settings. Ourmechanism in the central setting can be implemented in time $\mathcal{O}(n \logn)$ where $n$ is the number of users and our mechanism in the local settingadmits a Polynomial Time Approximation Scheme (PTAS).