Abstract
We study a market model where a data analyst uses monetary incentives to procure private data from strategic data subjects/individuals. To characterize individuals’ privacy concerns, we consider a local model of differential privacy, where the individuals do not trust the analyst so privacy costs are incurred when the data is reported to the data analyst. We investigate a basic model where the private data are bits that represent the individuals’ knowledge about an underlying state, and the analyst pays each individual according to all the reported data. The data analyst’s goal is to design a payment mechanism such that at an equilibrium, she can learn the state with an accuracy goal met and the corresponding total expected payment minimized. What makes the mechanism design more challenging is that not only the data but also the privacy costs are unknown to the data analyst, where the costs reflect individuals’ valuations of privacy and are modeled by “cost coefficients.” To cope with the uncertainty in the cost coefficients and drive down the data analyst’s cost, we utilize possible negative payments (which penalize individuals with “unacceptably” high valuations of privacy) and explore interim individual rationality. We design a family of payment mechanisms, each of which has a Bayesian Nash equilibrium where the individuals exhibit a threshold behavior: the individuals with cost coefficients above a threshold choose not to participate, and the individuals with cost coefficients below the threshold participate and report data with quality guarantee. By choosing appropriate parameters, we obtain a sequence of mechanisms, as the number of individuals grows large. Each mechanism in this sequence fulfills the accuracy goal at a Bayesian Nash equilibrium. The total expected payment at the equilibrium goes to zero; i.e., this sequence of mechanisms is asymptotically optimal.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bassily, R., Smith, A.: Local, private, efficient protocols for succinct histograms. In: Proceedings of the Annual ACM on Symposium on Theory of Computing (STOC), Portland, OR, pp. 127–135 (2015)
Cai, Y., Daskalakis, C., Papadimitriou, C.: Optimum statistical estimation with strategic data sources. In: Proceedings of the Conference on Learning Theory (COLT), Paris, France. pp. 280–296. July 2015
Chen, Y., Chong, S., Kash, I.A., Moran, T., Vadhan, S.: Truthful mechanisms for agents that value privacy. In: Proceedings of the ACM Conference on Electronic commerce (EC), Philadelphia, PA. pp. 215–232 (2013)
Chen, Y., Sheffet, O., Vadhan, S.: Privacy games. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 371–385. Springer, Heidelberg (2014). doi:10.1007/978-3-319-13129-0_30
Cummings, R., Ligett, K., Roth, A., Wu, Z.S., Ziani, J.: Accuracy for sale: aggregating data with a variance constraint. In: Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS), Rehovot, Israel. pp. 317–324 (2015)
Dasgupta, A., Ghosh, A.: Crowdsourced judgement elicitation with endogenous proficiency. In: Proceedings of the International Conference on World Wide Web (WWW), Rio de Janeiro, Brazil, pp. 319–330, May 2013
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and minimax bounds: sharp rates for probability estimation. In: Advances Neural Information Processing Systems (NIPS), Lake Tahoe, NV, pp. 1529–1537, December 2013
Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 1–12. Springer, Heidelberg (2006). doi:10.1007/11787006_1
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006). doi:10.1007/11681878_14
Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9(3–4), 211–407 (2014)
Erlingsson, Ú., Pihur, V., Korolova, A.: RAPPOR: randomized aggregatable privacy-preserving ordinal response. In: Proceedings of the ACM SIGSAC Conference on Computer and Communication Security (CCS), Scottsdale, AZ, pp. 1054–1067 (2014)
Fanti, G.C., Pihur, V., Erlingsson, Ú.: Building a RAPPOR with the unknown: privacy-preserving learning of associations and data dictionaries. arXiv:1503.01214 [cs.CR] (2015)
Fleischer, L.K., Lyu, Y.: Approximately optimal auctions for selling privacy when costs are correlated with data. In: Proceedings of the ACM Conference on Electronic Commerce (EC), Valencia, Spain, pp. 568–585 (2012)
Ghosh, A., Ligett, K.: Privacy and coordination: computing on databases with endogenous participation. In: Proceedings of the ACM Conference on Electronic Commerce (EC), Philadelphia, PA, pp. 543–560 (2013)
Ghosh, A., Ligett, K., Roth, A., Schoenebeck, G.: Buying private data without verification. In: Proceedings of the ACM Conference on Economics and Computation (EC), Palo Alto, CA, pp. 931–948 (2014)
Ghosh, A., Roth, A.: Selling privacy at auction. In: Proceedings of the ACM Conference on Electronic Commerce (EC), San Jose, CA, pp. 199–208 (2011)
Hsu, J., Khanna, S., Roth, A.: Distributed private heavy hitters. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 461–472. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31594-7_39
Kairouz, P., Oh, S., Viswanath, P.: Extremal mechanisms for local differential privacy. In: Advances Neural Information Processing Systems (NIPS), Montreal, Canada, pp. 2879–2887, December 2014
Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM J. Comput. 40(3), 793–826 (2011)
Ligett, K., Roth, A.: Take it or leave it: running a survey when privacy comes at a cost. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 378–391. Springer, Heidelberg (2012). doi:10.1007/978-3-642-35311-6_28
Liu, Y., Chen, Y.: Learning to incentivize: eliciting effort via output agreement. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), July 2016, New York, NY
McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), Providence, RI, pp. 94–103 (2007)
Miller, N., Resnick, P., Zeckhauser, R.: Eliciting informative feedback: the peer-prediction method. In: Golbeck, J. (ed.) Computing with Social Trust. Human-Computer Interaction Series, pp. 185–212. Springer, London (2009)
Nissim, K., Vadhan, S., Xiao, D.: Redrawing the boundaries on purchasing data from privacy-sensitive individuals. In: Proceedings of the Conference Innovations in Theoretical Computer Science (ITCS), Princeton, NJ, pp. 411–422 (2014)
Pai, M.M., Roth, A.: Privacy and mechanism design. SIGecom Exch. 12(1), 8–29 (2013)
Roth, A., Schoenebeck, G.: Conducting truthful surveys, cheaply. In: Proceedings of the ACM Conference Electronic Commerce (EC), Valencia, Spain, pp. 826–843 (2012)
Shokri, R.: Privacy games: optimal user-centric data obfuscation. In: Proceedings of the Privacy Enhancing Technologies (PETS), Philadelphia, PA, pp. 299–315 (2015)
Wang, W., Ying, L., Zhang, J.: On the relation between identifiability, differential privacy, and mutual-information privacy. In: Proceedings of the Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, pp. 1086–1092, September 2014
Wang, W., Ying, L., Zhang, J.: A game-theoretic approach to quality control for collecting privacy-preserving data. In: Proceedings of the Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, pp. 474–479, September 2015
Wang, W., Ying, L., Zhang, J.: A minimax distortion view of differentially private query release. In: Proceedings of the Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, pp. 1046–1050, November 2015
Wang, W., Ying, L., Zhang, J.: Buying data from privacy-aware individuals: the effect of negative payments. Technical report, Arizona State University, Tempe, AZ (2016)
Wang, W., Ying, L., Zhang, J.: The value of privacy: strategic data subjects, incentive mechanisms and fundamental limits. In: Proceedings of the Annual ACM SIGMETRICS Conference on Antibes Juan-les-Pins, France, June 2016
Warner, S.L.: Randomized response: a survey technique for eliminating evasive answer bias. J. Amer. Stat. Assoc. 60(309), 63–69 (1965)
Witkowski, J., Bachrach, Y., Key, P., Parkes, D.C.: Dwelling on the negative: incentivizing effort in peer prediction. In: Proceedings of the AAAI Conference on Human Computation and Crowdsourcing (HCOMP), Palm Springs, CA, November 2013
Xiao, D.: Is privacy compatible with truthfulness? In: Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS), Berkeley, CA, pp. 67–86 (2013)
Acknowledegments
This work was supported partially by NSF grant CNS-1618768.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag GmbH Germany
About this paper
Cite this paper
Wang, W., Ying, L., Zhang, J. (2016). Buying Data from Privacy-Aware Individuals: The Effect of Negative Payments. In: Cai, Y., Vetta, A. (eds) Web and Internet Economics. WINE 2016. Lecture Notes in Computer Science(), vol 10123. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-54110-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-662-54110-4_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-54109-8
Online ISBN: 978-3-662-54110-4
eBook Packages: Computer ScienceComputer Science (R0)