Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms

Alireza Fallah (), Ali Makhdoumi (), Azarakhsh Malekian () and Asuman Ozdaglar ()
Additional contact information
Alireza Fallah: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Ali Makhdoumi: Fuqua School of Business, Duke University, Durham, North Carolina 27708
Azarakhsh Malekian: Rotman School of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada
Asuman Ozdaglar: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2024, vol. 72, issue 3, 1105-1123

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

Keywords: Market Analytics and Revenue Management; differential privacy; Bayesian mechanism design; minimax lower bound; optimal data acquisition; local and central differential privacy; data markets (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0014 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:3:p:1105-1123

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().