Article

The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal

Authors:

Zhiyi Huang,

Sampath KannanAuthors Info & Claims

FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

Pages 140 - 149

https://doi.org/10.1109/FOCS.2012.36

Published: 20 October 2012 Publication History

Abstract

In this paper we show that for any mechanism design problem with the objective of maximizing social welfare, the exponential mechanism can be implemented as a truthful mechanism while still preserving differential privacy. Our instantiation of the exponential mechanism can be interpreted as a generalization of the VCG mechanism in the sense that the VCG mechanism is the extreme case when the privacy parameter goes to infinity. To our knowledge, this is the first general tool for designing mechanisms that are both truthful and differentially private.

Cited By

View all

Li ZDing BYao LLi YXiao XZhou J(2024)Performance-Based Pricing for Federated Learning via AuctionProceedings of the VLDB Endowment10.14778/3648160.364816917:6(1269-1282)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.14778/3648160.3648169
Karbasi AVelegkas GYang LZhou FOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Replicability in reinforcement learningProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669387(74702-74735)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669387
Jia FZhang MLiu JKhoussainov BEvans RShpitser I(2023)Incentivising diffusion while preserving differential privacyProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625925(963-972)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625925
Show More Cited By

Recommendations

Privacy-aware mechanism design
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Mechanism design deals with distributed algorithms that are executed with self-interested agents. The designer, whose objective is to optimize some function of the agents private types, needs to construct a computation that takes into account agent ...
Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions
AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

We initiate the study of the social welfare loss caused by corrupt auctioneers, both in single-item and multi-unit auctions. In our model, the auctioneer may collude with the winning bidders by letting them lower their bids in exchange for a (possibly ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

October 2012

770 pages

ISBN:9780769548746

Publisher

IEEE Computer Society

United States

Publication History

Published: 20 October 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li ZDing BYao LLi YXiao XZhou J(2024)Performance-Based Pricing for Federated Learning via AuctionProceedings of the VLDB Endowment10.14778/3648160.364816917:6(1269-1282)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.14778/3648160.3648169
Karbasi AVelegkas GYang LZhou FOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Replicability in reinforcement learningProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669387(74702-74735)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669387
Jia FZhang MLiu JKhoussainov BEvans RShpitser I(2023)Incentivising diffusion while preserving differential privacyProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3625925(963-972)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.5555/3625834.3625925
Jia FZhang MLiu JKhoussainov BAgmon NAn BRicci AYeoh W(2023)Differentially Private Diffusion Auction: The Single-unit CaseProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599056(2724-2726)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599056
Pendurkar SChow CJie LSharon GAgmon NAn BRicci AYeoh W(2023)Bilevel Entropy based Mechanism Design for Balancing Meta in Video GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598887(2134-2142)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598887
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
Dughmi SHartline JKleinberg RNiazadeh R(2021)Bernoulli Factories and Black-box Reductions in Mechanism DesignJournal of the ACM10.1145/344098868:2(1-30)Online publication date: 6-Jan-2021
https://dl.acm.org/doi/10.1145/3440988
Niu LClark A(2021)A Differentially Private Incentive Design for Traffic Offload to Public TransportationACM Transactions on Cyber-Physical Systems10.1145/34308475:2(1-27)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3430847
Epasto AMahdian MMirrokni VZampetakis MLarochelle HRanzato MHadsell RBalcan MLin H(2020)Optimal approximation - smoothness tradeoffs for soft-max functionsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3495947(2651-2660)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3495947
Yang DQu BCudre-Mauroux P(2019)Privacy-Preserving Social Media Data Publishing for Personalized Ranking-Based RecommendationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.284097431:3(507-520)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1109/TKDE.2018.2840974
Show More Cited By

Abstract

Cited By

Recommendations

Privacy-aware mechanism design

Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions

Is privacy compatible with truthfulness?

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations