A Caltech Library Service

Buying Private Data without Verification

Ghosh, Arpita and Ligett, Katrina and Roth, Aaron and Schoenebeck, Grant (2014) Buying Private Data without Verification. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation. Association for Computing Machinery , New York, pp. 931-948. ISBN 978-1-4503-2565-3.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of designing a survey to aggregate non-verifiable information from a privacy-sensitive population: an analyst wants to compute some aggregate statistic from the private bits held by each member of a population, but cannot verify the correctness of the bits reported by participants in his survey. Individuals in the population are strategic agents with a cost for privacy, ie, they not only account for the payments they expect to receive from the mechanism, but also their privacy costs from any information revealed about them by the mechanism's outcome---the computed statistic as well as the payments---to determine their utilities. How can the analyst design payments to obtain an accurate estimate of the population statistic when individuals strategically decide both whether to participate and whether to truthfully report their sensitive information' We design a differentially private peer-prediction mechanism [Miller et al. 2005] that supports accurate estimation of the population statistic as a Bayes-Nash equilibrium in settings where agents have explicit preferences for privacy. The mechanism requires knowledge of the marginal prior distribution on bits bi, but does not need full knowledge of the marginal distribution on the costs ci, instead requiring only an approximate upper bound. Our mechanism guarantees ε-differential privacy to each agent i against any adversary who can observe the statistical estimate output by the mechanism, as well as the payments made to the n-1 other agents j ≠ i. Finally, we show that with slightly more structured assumptions on the privacy cost functions of each agent [Chen et al. 2013], the cost of running the survey goes to 0 as the number of agents diverges.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Ligett, Katrina0000-0003-2780-6656
Additional Information:© 2014 ACM. Publication Date: June 1, 2014. KL’s work was supported in part by an NSF CAREER award (CNS-1254169), the US-Israel Binational Science Foundation (grant 2012348), the Charles Lee Powell Foundation, a Google Faculty Research Award, and a Microsoft Faculty Fellowship. AR’s work was supported in part by an NSF CAREER award, under NSF grants CCF-1101389 and CNS-1065060, and a Google Focused Research Award.
Funding AgencyGrant Number
US-Israel Binational Science Foundation2012348
Charles Lee Powell FoundationUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
Microsoft Faculty FellowshipUNSPECIFIED
Google Focused Research AwardUNSPECIFIED
Record Number:CaltechAUTHORS:20140804-112502954
Persistent URL:
Official Citation:Ghosh, A., Ligett, K., Roth, A., & Schoenebeck, G. (2014). Buying private data without verification. Paper presented at the Proceedings of the fifteenth ACM conference on Economics and computation, Palo Alto, California, USA.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:47887
Deposited By: Jason Perez
Deposited On:04 Aug 2014 22:06
Last Modified:10 Nov 2021 17:51

Repository Staff Only: item control page