论文标题
最佳和差异私人数据获取：中央和本地机制
Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms
论文作者
论文摘要
我们考虑了平台从隐私敏感用户收集数据以估计感兴趣的基本参数的问题。我们将这个问题提出为贝叶斯最佳的机制设计问题，其中一个人可以共享她（可验证的）数据以换取货币奖励或服务，但同时却具有（私人）异质性隐私成本，我们使用差异隐私进行了量化。我们考虑两个流行的差别隐私设置，以为用户提供隐私保证：中央和本地。在这两种设置中，我们为估计误差建立了Minimax下限，并为用户的给定异质隐私损失水平得出（接近）最佳估计器。在此特征的基础上，我们将机制设计问题提出了估计器和付款的最佳选择，这些估计器和付款将引起用户隐私敏感性的真实报告。在规律性条件下，我们开发了有效的算法机制来解决这两个隐私设置中的问题。我们在中央设置中的机制可以在及时实现$ \ MATHCAL {O}（n \ log n）$，其中$ n $是用户数量，而我们在本地设置中的机制则可以接受多项式时间近似方案（PTA）。
We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy cost which we quantify using differential privacy. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. In both settings, we establish minimax lower bounds for the estimation error and derive (near) optimal estimators for given heterogeneous privacy loss levels for users. Building on this characterization, we pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities. Under a regularity condition on the distribution of privacy sensitivities we develop efficient algorithmic mechanisms to solve this problem in both privacy settings. Our mechanism in the central setting can be implemented in time $\mathcal{O}(n \log n)$ where $n$ is the number of users and our mechanism in the local setting admits a Polynomial Time Approximation Scheme (PTAS).
