zbMATH — the first resource for mathematics

Selling privacy at auction. (English) Zbl 1318.91093
Summary: We study markets for private data using differential privacy. We consider a setting in which a data analyst wishes to buy information from a population from which he can estimate some statistic. The analyst wishes to obtain an accurate estimate cheaply, while the owners of the private data experience some cost for their loss of privacy. Agents are rational and we wish to design truthful mechanisms.
We show that such problems can naturally be viewed and solved as variants of multi-unit procurement auctions. We derive auctions for two natural settings:
1. The analyst has a fixed accuracy goal and wishes to minimize his payments.
2. The analyst has a budget and wishes to maximize his accuracy.
In both results, we treat each agent’s cost for privacy as insensitive information. We then show that no individually rational mechanism can compensate individuals for the privacy loss incurred due to their reported valuations for privacy.

91B26 Auctions, bargaining, bidding and selling, and other market models
Full Text: DOI
[1] Blum, A.; Dwork, C.; McSherry, F.; Nissim, K., Practical privacy: the sulq framework, (Proceedings of the twenty-fourth Symposium on Principles of Database Systems, ACM SIGMOD-SIGACT-SIGART, (2005))
[2] Brenner, H.; Nissim, K., Impossibility of differentially private universally optimal mechanisms, (Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS, (2010)) · Zbl 1320.68072
[3] Calzolari, G.; Pavan, A., On the optimality of privacy in sequential contracting, J. Econ. Theory, 130, 1, 168-204, (2006) · Zbl 1141.91391
[4] Chen, N.; Gravin, N.; Lu, P., On the approximability of budget feasible mechanisms, (Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, (2011)) · Zbl 1377.90113
[5] Chen, Y., Chong, S., Kash, I., Moran, T., Vadhan, S., 2011. Truthful mechanisms for agents that value privacy. Manuscript.
[6] Clifford, Stephanie, Web startups offer bargains for users data, N.Y. Times, (May 2010)
[7] Conitzer, V.; Taylor, C.; Wagman, L., Hide and seek: costly consumer privacy in a market with repeat purchases, Marketing Sci., 31, 2, 277-292, (2012)
[8] Dwork, C., Differential privacy: A survey of results, (Proceedings of Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Lecture Notes in Computer Science, vol. 4978, (2008), Springer), 1 · Zbl 1139.68339
[9] Dwork, C.; McSherry, F.; Nissim, K.; Smith, A., Calibrating noise to sensitivity in private data analysis, (Proceedings of the Third Theory of Cryptography Conference, TCC, Lecture Notes in Computer Science, vol. 3876, (2006), Springer), 265 · Zbl 1112.94027
[10] Ensthaler, L.; Giebe, T., How to allocate research (and other) subsidies, (February 2011), Available at SSRN
[11] Feigenbaum, J.; Jaggard, A. D.; Schapira, M., Approximate privacy: foundations and quantification (extended abstract), (Proceedings of the 11th ACM Conference on Electronic Commerce, (2010), ACM), 167-178
[12] Ghosh, A.; Roughgarden, T.; Sundararajan, M., Universally utility-maximizing privacy mechanisms, (Proceedings of the 41st Annual ACM Symposium on Theory of Computing, (2009), ACM New York, NY, USA), 351-360 · Zbl 1304.94060
[13] Gupta, A.; Ligett, K.; McSherry, F.; Roth, A.; Talwar, K., Differentially private combinatorial optimization, (Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, (2010)) · Zbl 1288.94087
[14] Hartline, J.; Karlin, A., Profit maximization in mechanism design, Algorithmic Game Theory, 331, (2007) · Zbl 1151.91418
[15] Hartline, J. D.; Roughgarden, T., Optimal mechanism design and money burning, (Proceedings of the Annual Symposium on Theory of Computing, STOC, (2008)), CiteSeer · Zbl 1231.91117
[16] Kleinberg, J., Papadimitriou, C., Raghavan, P., 2001. On the value of private information. In: Proc. 8th Conf. on Theoretical Aspects of Rationality and Knowledge.
[17] Laudon, K., Markets and privacy, Commun. ACM, 39, 9, 104, (1996)
[18] Lohr, Steve, You want my personal data? reward me for it, N.Y. Times, (July 2010)
[19] McSherry, F.; Talwar, K., Mechanism design via differential privacy, (Proceedings of the 48th Annual Symposium on Foundations of Computer Science, (2007))
[20] Nissim, K.; Smorodinsky, R.; Tennenholtz, M., Approximately optimal mechanism design via differential privacy, (2010), Preprint
[21] Singer, Y., Budget feasible mechanisms, (Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS, (2010))
[22] Xiao, D., Is privacy compatible with truthfulness?, (2011), Cryptology ePrint Archive, 2011/005 · Zbl 1361.68076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.