skip to main content
10.1145/2600057.2602902acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Buying private data without verification

Published: 01 June 2014 Publication History

Abstract

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

References

[1]
Glenn W. Brier. 1950. Verification of Forecasts Expressed in Terms of Probability. Monthly Weather Review 78, 1 (1950), 1--3.
[2]
Yiling Chen, Stephen Chong, Ian A Kash, Tal Moran, and Salil Vadhan. 2013.showarticletitleTruthful mechanisms for agents that value privacy. In Proceedings of the fourteenth ACM conference on Electronic commerce. ACM, 215--232.
[3]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC '06. 265--284.
[4]
Lisa Fleischer and Yu-Han Lyu. 2012. Approximately optimal auctions for selling privacy when costs are correlated with data. In ACM Electronic Commerce (EC). 568--585.
[5]
Arpita Ghosh and Katrina Ligett. 2013. Privacy and coordination: computing on databases with endogenous participation. In ACM Conference on Electronic Commerce. 543--560.
[6]
Arpita Ghosh and Aaron Roth. 2013. Selling privacy at auction. Games and Economic Behavior (2013). Preliminary Version appeared un the Proceedings of the Twelfth ACM Conference on Electronic Commerce (EC 2011).
[7]
Sharad Goel, Daniel M. Reeves, and David M. Pennock. 2009.showarticletitleCollective revelation: A mechanism for self-verified, weighted, and truthful predictions. In Proceedings of the 10th ACM conference on Electronic commerce (EC 2009).
[8]
Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. 2013. Private Matchings and Allocations. arXiv preprint arXiv:1311.2828 (2013).
[9]
Radu Jurca and Boi Faltings. 2006. Minimum payments that reward honest reputation feedback. In Proceedings of the 7th ACM conference on Electronic commerce (EC 2006).
[10]
Radu Jurca and Boi Faltings. 2007. Robust Incentive-Compatible Feedback Payments. In Trust, Reputation and Security: Theories and Practice, Vol. 4452. Springer-Verlag, 204--218.
[11]
Radu Jurca and Boi Faltings. 2008. Incentives for expressing opinions in online polls. In Proceedings of the 9th ACM conference on Electronic commerce (EC 2008).
[12]
Radu Jurca and Boi Faltings. 2009. Mechanisms for making crowds truthful. J. Artif. Int. Res. 34, 1 (March 2009).
[13]
Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. 2014. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science. ACM, 403--410.
[14]
N. Lambert and Y. Shoham. 2008. Truthful surveys. Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2008) (2008).
[15]
Katrina Ligett and Aaron Roth. 2012. Take it or leave it: Running a survey when privacy comes at a cost. In Internet and Network Economics. Springer, 378--391.
[16]
N. Miller, P. Resnick, and R. Zeckhauser. 2005. Eliciting informative feedback: The peer-prediction method. Management Science (2005), 1359--1373.
[17]
Kobbi Nissim, Claudio Orlandi, and Rann Smorodinsky. 2012. Privacy-aware mechanism design. In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 774--789.
[18]
Kobbi Nissim, Salil Vadhan, and David Xiao. 2014. Redrawing the boundaries on purchasing data from privacy-sensitive individuals. In Proceedings of the 5th conference on Innovations in theoretical computer science. ACM, 411--422.
[19]
Mallesh Pai and Aaron Roth. 2013. Privacy and Mechanism Design. Sigecom Exchanges (2013), 8--29.
[20]
A. Papakonstantinou, A. Rogers, E.H. Gerding, and N.R. Jennings. 2011. Mechanism design for the truthful elicitation of costly probabilistic estimates in distributed information systems. Artificial Intelligence 175, 2 (2011), 648--672.
[21]
D. Prelec. 2004. A Bayesian Truth Serum for subjective data. Science 306, 5695 (2004), 462--466.
[22]
Ryan Rogers and Aaron Roth. 2013. Asymptotically Truthful Equilibrium Selection in Large Congestion Games. arXiv preprint arXiv:1311.2625 (2013).
[23]
Aaron Roth and Grant Schoenebeck. 2012. Conducting truthful surveys, cheaply. In ACM Electronic Commerce (EC). 826--843.
[24]
J. Witkowski and D. Parkes. 2012a. A robust Bayesian Truth Serum for small populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012).
[25]
Jens Witkowski and David C. Parkes. 2011. A Robust Bayesian Truth Serum for Small Populations. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012).
[26]
Jens Witkowski and David C. Parkes. 2012b. Peer Prediction without a Common Prior. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012).

Cited By

View all
  • (2024)Counterfactual Explanation of Shapley Value in Data CoalitionsProceedings of the VLDB Endowment10.14778/3681954.368200417:11(3332-3345)Online publication date: 1-Jul-2024
  • (2024)Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple GamesProceedings of the ACM on Management of Data10.1145/36393112:1(1-28)Online publication date: 26-Mar-2024
  • (2024)Privacy Preserving User Energy Consumption Profiling: From Theory to ApplicationIEEE Transactions on Smart Grid10.1109/TSG.2023.331569015:2(2332-2347)Online publication date: Mar-2024
  • Show More Cited By

Index Terms

  1. Buying private data without verification

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    EC '14: Proceedings of the fifteenth ACM conference on Economics and computation
    June 2014
    1028 pages
    ISBN:9781450325653
    DOI:10.1145/2600057
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 June 2014

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. differential privacy
    2. mechanism design
    3. peer prediction

    Qualifiers

    • Research-article

    Conference

    EC '14
    Sponsor:
    EC '14: ACM Conference on Economics and Computation
    June 8 - 12, 2014
    California, Palo Alto, USA

    Acceptance Rates

    EC '14 Paper Acceptance Rate 80 of 290 submissions, 28%;
    Overall Acceptance Rate 664 of 2,389 submissions, 28%

    Upcoming Conference

    EC '25
    The 25th ACM Conference on Economics and Computation
    July 7 - 11, 2025
    Stanford , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)20
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Counterfactual Explanation of Shapley Value in Data CoalitionsProceedings of the VLDB Endowment10.14778/3681954.368200417:11(3332-3345)Online publication date: 1-Jul-2024
    • (2024)Fast Shapley Value Computation in Data Assemblage Tasks as Cooperative Simple GamesProceedings of the ACM on Management of Data10.1145/36393112:1(1-28)Online publication date: 26-Mar-2024
    • (2024)Privacy Preserving User Energy Consumption Profiling: From Theory to ApplicationIEEE Transactions on Smart Grid10.1109/TSG.2023.331569015:2(2332-2347)Online publication date: Mar-2024
    • (2024)Protecting Data Buyer Privacy in Data MarketsIEEE Internet Computing10.1109/MIC.2024.339862628:4(14-20)Online publication date: Jul-2024
    • (2024)Truthful and privacy-preserving generalized linear modelsInformation and Computation10.1016/j.ic.2024.105225(105225)Online publication date: Sep-2024
    • (2023)How Good are Privacy Guarantees? Platform Architecture and Violation of User PrivacySSRN Electronic Journal10.2139/ssrn.4497994Online publication date: 2023
    • (2023)How Good Are Privacy Guarantees? Data Sharing, Privacy Preservation, and Platform BehaviorSSRN Electronic Journal10.2139/ssrn.4333457Online publication date: 2023
    • (2023)Privacy Protection Under Incomplete Social and Data Correlation InformationIEEE/ACM Transactions on Networking10.1109/TNET.2023.325454931:6(2515-2528)Online publication date: Dec-2023
    • (2023)Locally Differentially Private Personal Data Markets Using Contextual Dynamic Pricing MechanismIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.323961520:6(5043-5055)Online publication date: Nov-2023
    • (2023)A Survey of Data Pricing for Data MarketplacesIEEE Transactions on Big Data10.1109/TBDATA.2023.32541529:4(1038-1056)Online publication date: 1-Aug-2023
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media