research-article

Truthful Mechanisms for Agents That Value Privacy

Authors:

Salil VadhanAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 4, Issue 3

Article No.: 13, Pages 1 - 30

https://doi.org/10.1145/2892555

Published: 18 March 2016 Publication History

Abstract

Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from truthfulness; it is not incorporated in players’ utility functions (and doing so has been shown to lead to nontruthfulness in some cases). In this work, we propose a new, general way of modeling privacy in players’ utility functions. Specifically, we only assume that if an outcome o has the property that any report of player i would have led to o with approximately the same probability, then o has a small privacy cost to player i. We give three mechanisms that are truthful with respect to our modeling of privacy: for an election between two candidates, for a discrete version of the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As the number n of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of n).

References

[1]

Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. 2005. Practical privacy: The SuLQ framework. In PODS, Chen Li (Ed.). ACM, 128--138.

Digital Library

[2]

Felix Brandt and Tuomas Sandholm. 2008. On the existence of unconditionally privacy-preserving auction protocols. ACM Trans. Inf. Syst. Secur. 11, 2, Article 6 (May 2008), 21 pages.

Digital Library

[3]

Thomas M. Cover and Joy A. Thomas. 1991. Elements of Information Theory (2nd ed.). John Wiley & Sons.

Digital Library

[4]

Irit Dinur and Kobbi Nissim. 2003. Revealing information while preserving privacy. In PODS. ACM, 202--210.

Digital Library

[5]

Yevgeniy Dodis, Shai Halevi, and Tal Rabin. 2000. A cryptographic solution to a game theoretic problem. In CRYPTO (Lecture Notes in Computer Science), Mihir Bellare (Ed.), Vol. 1880. Springer, 112--130.

Digital Library

[6]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC (Lecture Notes in Computer Science), Shai Halevi and Tal Rabin (Eds.), Vol. 3876. Springer, 265--284.

Digital Library

[7]

Cynthia Dwork and Kobbi Nissim. 2004. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO (Lecture Notes in Computer Science), Matthew K. Franklin (Ed.), Vol. 3152. Springer, 528--544.

[8]

Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Now Publishers.

Digital Library

[9]

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. 2010. Boosting and differential privacy. In FOCS. IEEE Computer Society, 51--60.

Digital Library

[10]

Joan Feigenbaum, Aaron D. Jaggard, and Michael Schapira. 2010. Approximate privacy: Foundations and quantification (extended abstract). In ACM Conference on Electronic Commerce, David C. Parkes, Chrysanthos Dellarocas, and Moshe Tennenholtz (Eds.). ACM, 167--178.

Digital Library

[11]

Arpita Ghosh and Aaron Roth. 2011. Selling privacy at auction. In Proceedings of the 12th ACM Conference on Electronic Commerce (EC’11). ACM, New York, NY, 199--208.

Digital Library

[12]

Ronen Gradwohl. 2012. Privacy in Implementation. Working Paper. (November 2012).

[13]

Ronen Gradwohl and Rann Smorodinsky. 2014. Subjective Perception Games and Privacy. arXiv:1409l.1487. (September 2014).

[14]

Zhiyi Huang and Sampath Kannan. 2012. The exponential mechanism for social welfare: Private, truthful, and nearly optimal. In FOCS. IEEE Computer Society, 140--149.

Digital Library

[15]

Sergei Izmalkov, Silvio Micali, and Matt Lepinski. 2005. Rational secure computation and ideal mechanism design. In FOCS. IEEE Computer Society, 585--595.

Digital Library

[16]

Shiva Prasad Kasiviswanathan and Adam Smith. 2008. A note on differential privacy: Defining resistance to arbitrary side information. CoRR abs/0803.3946 (2008).

[17]

Frank McSherry and Kunal Talwar. 2007. Mechanism design via differential privacy. In FOCS. IEEE Computer Society, 94--103.

Digital Library

[18]

Moni Naor, Benny Pinkas, and Reuban Sumner. 1999. Privacy preserving auctions and mechanism design. In ACM Conference on Electronic Commerce. 129--139.

Digital Library

[19]

Kobbi Nissim, Claudio Orlandi, and Rann Smorodinsky. 2012a. Privacy-aware mechanism design. In ACM Conference on Electronic Commerce (EC’12). 774--789.

Digital Library

[20]

Kobbi Nissim, Rann Smorodinsky, and Moshe Tennenholtz. 2012b. Approximately optimal mechanism design via differential privacy. In Innovations in Theoretical Computer Science 2012. 203--213.

Digital Library

[21]

Mallesh M. Pai and Aaron Roth. 2013. Privacy and mechanism design. ACM SIGecom Exchanges 12 (June 2013), 8--29. Issue 1.

Digital Library

[22]

David C. Parkes, Michael O. Rabin, Stuart M. Shieber, and Christopher Thorpe. 2008. Practical secrecy-preserving, verifiably correct and trustworthy auctions. Electronic Commerce Res. Appl. 7, 3 (2008), 294--312.

Digital Library

[23]

David Xiao. 2011. Is privacy compatible with truthfulness? Cryptology ePrint Archive, Report 2011/005. (2011).

[24]

David Xiao. 2013. Is privacy compatible with truthfulness? In ITCS, Robert D. Kleinberg (Ed.). ACM, 67--86.

Digital Library

Cited By

Hoseinpour MHoseinpour MHaghifam MHaghifam M(2024)Privacy-Preserving and Approximately Truthful Local Electricity Markets: A Differentially Private VCG MechanismIEEE Transactions on Smart Grid10.1109/TSG.2023.330117415:2(1991-2003)Online publication date: Mar-2024
https://doi.org/10.1109/TSG.2023.3301174
Lan QSong BLi YLi G(2024)Distributed Differentially Private Ranking AggregationIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.322509611:1(503-513)Online publication date: Feb-2024
https://doi.org/10.1109/TCSS.2022.3225096
Altun OBarlo MDalkıran N(2023)Implementation with a sympathizerMathematical Social Sciences10.1016/j.mathsocsci.2022.12.002121(36-49)Online publication date: Jan-2023
https://doi.org/10.1016/j.mathsocsci.2022.12.002
Show More Cited By

Recommendations

More than Privacy: Adopting Differential Privacy in Game-theoretic Mechanism Design

The vast majority of artificial intelligence solutions are founded on game theory, and differential privacy is emerging as perhaps the most rigorous and widely adopted privacy paradigm in the field. However, alongside all the advancements made in both ...
Is privacy compatible with truthfulness?
ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science

In the area of privacy-preserving data mining, a differentially private mechanism intuitively encourages people to share their data because they are at little risk of revealing their own information. However, we argue that this interpretation is ...
Mechanism design in large games: incentives and privacy
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

We study the problem of implementing equilibria of complete information games in settings of incomplete information, and address this problem using "recommender mechanisms." A recommender mechanism is one that does not have the power to enforce outcomes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 4, Issue 3

Special Issue on EC'13

June 2016

162 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/2905047

Editors:
Vincent Conitzer
Duke University
,
Preston McAfee
Microsoft

Issue’s Table of Contents

Copyright © 2016 ACM.

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2016

Accepted: 01 October 2015

Received: 01 February 2015

Published in TEAC Volume 4, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Sloan Foundation
Google, Inc.
NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
474
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hoseinpour MHoseinpour MHaghifam MHaghifam M(2024)Privacy-Preserving and Approximately Truthful Local Electricity Markets: A Differentially Private VCG MechanismIEEE Transactions on Smart Grid10.1109/TSG.2023.330117415:2(1991-2003)Online publication date: Mar-2024
https://doi.org/10.1109/TSG.2023.3301174
Lan QSong BLi YLi G(2024)Distributed Differentially Private Ranking AggregationIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.322509611:1(503-513)Online publication date: Feb-2024
https://doi.org/10.1109/TCSS.2022.3225096
Altun OBarlo MDalkıran N(2023)Implementation with a sympathizerMathematical Social Sciences10.1016/j.mathsocsci.2022.12.002121(36-49)Online publication date: Jan-2023
https://doi.org/10.1016/j.mathsocsci.2022.12.002
Zou YYang DPan Y(2021)An improved grey Markov chain model with ANN error correction and its application in gross domestic product forecastingJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-21050940:6(12371-12381)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/JIFS-210509
Zhang LZhu TXiong PZhou WYu P(2021)More than PrivacyACM Computing Surveys10.1145/346077154:7(1-37)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3460771
Pal RLi JCrowcroft JLi YLiu MSastry N(2021)Privacy Risk is a Function of Information Type: Learnings for the Surveillance Capitalism AgeIEEE Transactions on Network and Service Management10.1109/TNSM.2020.304670418:3(3280-3296)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2020.3046704
Shahani SVenkateswaran RAbraham J(2021)Cost-based recommendation of parameters for local differentially private data aggregationComputers and Security10.1016/j.cose.2020.102144102:COnline publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1016/j.cose.2020.102144
Biswas SJung KPalamidessi C(2021)An Incentive Mechanism for Trading Personal Data in Data MarketsTheoretical Aspects of Computing – ICTAC 202110.1007/978-3-030-85315-0_12(197-213)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85315-0_12
Dandekar ABasu DBressan S(2020)Differential Privacy at Risk: Bridging Randomness and Privacy BudgetProceedings on Privacy Enhancing Technologies10.2478/popets-2021-00052021:1(64-84)Online publication date: 9-Nov-2020
https://doi.org/10.2478/popets-2021-0005
Cao XBaşar T(2020)Differentially Private Parameter Estimation: Optimal Noise Insertion and Data Owner Selection2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9304375(2887-2893)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1109/CDC42340.2020.9304375
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents