# Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms

arXiv: https://arxiv.org/abs/2201.03968 · HTML: https://mlsanity.com/paper/2201.03968/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 79 references that are in the map.
- First posted on arXiv 10 Jan 2022.

## Builds on (most cited first, 23 of 23)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Differential Privacy: An Economic Method for Choosing Epsilon](https://mlsanity.com/paper/1402.3329/) (2014)
- [Heterogeneous Differential Privacy](https://mlsanity.com/paper/1504.06998/) (2015)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Optimum Statistical Estimation with Strategic Data Sources](https://mlsanity.com/paper/1408.2539/) (2014)
- [Privacy-Preserving Dynamic Personalized Pricing with Demand Learning](https://mlsanity.com/paper/2009.12920/) (2020)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [Differential Privacy in Personalized Pricing with Nonparametric Demand Models](https://mlsanity.com/paper/2109.04615/) (2021)
- [Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals](https://mlsanity.com/paper/1401.4092/) (2014)
- [Optimal Data Acquisition for Statistical Estimation](https://mlsanity.com/paper/1711.01295/) (2017)
- [Buying Private Data without Verification](https://mlsanity.com/paper/1404.6003/) (2014)
- [Learning to Incentivize: Eliciting Effort via Output Agreement](https://mlsanity.com/paper/1604.04928/) (2016)
- [Sequential Peer Prediction: Learning to Elicit Effort using Posted Prices](https://mlsanity.com/paper/1611.09219/) (2016)
- [Prior-free Data Acquisition for Accurate Statistical Estimation](https://mlsanity.com/paper/1811.12655/) (2018)
- [Privacy and Mechanism Design](https://mlsanity.com/paper/1306.2083/) (2013)
- [Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions](https://mlsanity.com/paper/2101.07304/) (2021)
- [Information Design for Congested Social Services: Optimal Need-Based Persuasion](https://mlsanity.com/paper/2005.07253/) (2020)
- [The Privacy Paradox and Optimal Bias-Variance Trade-offs in Data Acquisition](https://mlsanity.com/paper/2105.14262/) (2021)

## Built on by (most cited first, 24 of 24)

- [Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation](https://mlsanity.com/paper/2308.15709/) (2023)
- [Incentives in Private Collaborative Machine Learning](https://mlsanity.com/paper/2404.01676/) (2024)
- [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024)
- [Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learning](https://mlsanity.com/paper/2406.03519/) (2024)
- [Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free](https://mlsanity.com/paper/2305.09668/) (2023)
- [Mean Estimation Under Heterogeneous Privacy Demands](https://mlsanity.com/paper/2310.13137/) (2023)
- [The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning](https://mlsanity.com/paper/2301.13336/) (2023)
- [Crowding Out The Noise: Algorithmic Collective Action Under Differential Privacy](https://mlsanity.com/paper/2505.05707/) (2025)
- [Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression](https://mlsanity.com/paper/2309.10340/) (2023)
- [Personalized Differential Privacy for Ridge Regression](https://mlsanity.com/paper/2401.17127/) (2024)
- [Private Estimation when Data and Privacy Demands are Correlated](https://mlsanity.com/paper/2407.11274/) (2024)
- [Managing Correlations in Data and Privacy Demand](https://mlsanity.com/paper/2509.02856/) (2025)
- [Truthful Generalized Linear Models](https://mlsanity.com/paper/2209.07815/) (2022)
- [Privacy-Aware Data Acquisition under Data Similarity in Regression Markets](https://mlsanity.com/paper/2312.02611/) (2023)
- [Robust Estimation Under Heterogeneous Corruption Rates](https://mlsanity.com/paper/2508.15051/) (2025)
- [High-Probability Bounds For Heterogeneous Local Differential Privacy](https://mlsanity.com/paper/2510.11895/) (2025)
- [Online Linear Regression with Paid Stochastic Features](https://mlsanity.com/paper/2511.08073/) (2025)
- [A Cram'er-von Mises Approach to Incentivizing Truthful Data Sharing](https://mlsanity.com/paper/2506.07272/) (2025)
- [Non-Rival Data as Rival Products: An Encapsulation-Forging Approach for Data Synthesis](https://mlsanity.com/paper/2511.06610/) (2025)
- [Two-Stage Data Synthesization: A Statistics-Driven Restricted Trade-off between Privacy and Prediction](https://mlsanity.com/paper/2602.08657/) (2026)
- [Limits of Personalizing Differential Privacy Budgets](https://mlsanity.com/paper/2605.13503/) (2026)
- [Performative Privacy: When Differential Privacy Maximizes Utility](https://mlsanity.com/paper/2608.28198/) (2026)
- [High-Dimensional Asymptotics and Dataset Selection for Private Transfer Learning](https://mlsanity.com/paper/2610.02578/) (2026)
- [Beyond Second-Order Information: Paid Logistic Regression with Noisy Features](https://mlsanity.com/paper/2610.12919/) (2026)

## Abstract (arXiv)

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 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).