Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms

• 成果类型: Article
• 署名作者: Fallah, Alireza; Makhdoumi, Ali; Malekian, Azarakhsh; Ozdaglar, Asuman
• 署名单位: Massachusetts Institute of Technology (MIT); Duke University; University of Toronto
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0014
• 发表日期: 2024
• 关键词: Supply chain; INFORMATION; MARKETS

摘要

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 Bayesianoptimal mechanism design problem, in which an individual can share their (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 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).