skip to main content
10.1145/2554797.2554834acmconferencesArticle/Chapter ViewAbstractPublication PagesitcsConference Proceedingsconference-collections
research-article

Mechanism design in large games: incentives and privacy

Published: 12 January 2014 Publication History

Abstract

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 or to force participation, rather it only has the power to suggestion outcomes on the basis of voluntary participation. We show that despite these restrictions, recommender mechanisms can implement equilibria of complete information games in settings of incomplete information under the condition that the game is large---i.e. that there are a large number of players, and any player's action affects any other's payoff by at most a small amount.
Our result follows from a novel application of differential privacy. We show that any algorithm that computes a correlated equilibrium of a complete information game while satisfying a variant of differential privacy---which we call joint differential privacy---can be used as a recommender mechanism while satisfying our desired incentive properties. Our main technical result is an algorithm for computing a correlated equilibrium of a large game while satisfying joint differential privacy.
Although our recommender mechanisms are designed to satisfy game-theoretic properties, our solution ends up satisfying a strong privacy property as well. No group of players can learn "much" about the type of any player outside the group from the recommendations of the mechanism, even if these players collude in an arbitrary way. As such, our algorithm is able to implement equilibria of complete information games, without revealing information about the realized types.

References

[1]
E. Azevedo and E. Budish. Strategyproofness in the large as a desideratum for market design. Technical report, University of Chicago, 2011.
[2]
N.I. Al-Najjar and R. Smorodinsky. Pivotal players and the characterization of influence. Journal of Economic Theory, 92(2):318--342, 2000.
[3]
Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In Cynthia Dwork, editor, STOC, pages 609--618. ACM, 2008.
[4]
Yiling Chen, Stephen Chong, Ian A Kash, Tal Moran, and Salil Vadhan. Truthful mechanisms for agents that value privacy. In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 215--232. ACM, 2013.
[5]
Anindya De. Lower bounds in differential privacy. In TCC, pages 321--338, 2012.
[6]
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486--503, 2006.
[7]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC '06, pages 265--284, 2006.
[8]
Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of lp decoding. In STOC, pages 85--94, 2007.
[9]
Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In PODS, pages 202--210, 2003.
[10]
Cynthia Dwork, Moni Naor, and Salil Vadhan. The privacy of the analyst and the power of the state. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 400--409. IEEE, 2012.
[11]
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, pages 51--60. IEEE Computer Society, 2010.
[12]
C. Dwork. Differential privacy: A survey of results. Theory and Applications of Models of Computation, pages 1--19, 2008.
[13]
Cynthia Dwork and Sergey Yekhanin. New efficient attacks on statistical disclosure control mechanisms. In CRYPTO, pages 469--480, 2008.
[14]
Lisa Fleischer and Yu-Han Lyu. Approximately optimal auctions for selling privacy when costs are correlated with data. In EC, pages 568--585, 2012.
[15]
Françoise Forges. An approach to communication equilibria. Econometrica: Journal of the Econometric Society, pages 1375--1385, 1986.
[16]
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman. Privately releasing conjunctions and the statistical query barrier. In STOC '11, pages 803--812, 2011.
[17]
R. Gradwohl and O. Reingold. Fault tolerance in large games. In EC, pages 274--283. ACM, 2008.
[18]
R. Gradwohl and O. Reingold. Partial exposure in large games. Games and Economic Behavior, 68(2):602--613, 2010.
[19]
Arpita Ghosh and Aaron Roth. Selling privacy at auction. In EC, pages 199--208, 2011.
[20]
R. Gradwohl. Privacy in implementation. 2012.
[21]
Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In TCC, pages 339--356, 2012.
[22]
Zhiyi Huang and Sampath Kannan. The exponential mechanism for social welfare: Private, truthful, and nearly optimal. In FOCS, 2012.
[23]
Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS, pages 61--70, 2010.
[24]
Justin Hsu, Aaron Roth, and Jonathan Ullman. Differential privacy for the analyst via private equilibrium computation. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pages 341--350. ACM, 2013.
[25]
N. Immorlica and M. Mahdian. Marriage, honesty, and stability. In SODA, pages 53--62. Society for Industrial and Applied Mathematics, 2005.
[26]
E. Kalai. Large robust games. Econometrica, 72(6):1631--1665, 2004.
[27]
F. Kojima and P.A. Pathak. Incentives and stability in large two-sided matching markets. American Economic Review, 99(3):608--627, 2009.
[28]
F. Kojima, P.A. Pathak, and A.E. Roth. Matching with couples: Stability and incentives in large markets. Technical report, National Bureau of Economic Research, 2010.
[29]
Michael Kearns, Mallesh M Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. arXiv preprint arXiv:1207.4084, 2013.
[30]
Katrina Ligett and Aaron Roth. Take it or leave it: Running a survey when privacy comes at a cost. CoRR, abs/1202.4741, 2012.
[31]
Dov Monderer and Moshe Tennenholtz. k-implementation. In Proceedings of the 4th ACM conference on Electronic commerce, pages 19--28. ACM, 2003.
[32]
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94--103, 2007.
[33]
Dov Monderer and Moshe Tennenholtz. Strong mediated equilibrium. Artificial Intelligence, 173(1):180--195, 2009.
[34]
Kobbi Nissim, Claudio Orlandi, and Rann Smorodinsky. Privacy-aware mechanism design. In EC, pages 774--789, 2012.
[35]
Kobbi Nissim, Rann Smorodinsky, and Moshe Tennenholtz. Approximately optimal mechanism design via differential privacy. In ITCS, pages 203--213, 2012.
[36]
Mallesh Pai and Aaron Roth. Privacy and mechanism design. Sigecom Exchanges, pages 8--29, 2013.
[37]
T. Roughgarden. Intrinsic robustness of the price of anarchy. In STOC, pages 513--522. ACM, 2009.
[38]
T. Roughgarden. The price of anarchy in games of incomplete information. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 862--879. ACM, 2012.
[39]
D.J. Roberts and A. Postlewaite. The incentives for price-taking behavior in large exchange economies. Econometrica, pages 115--127, 1976.
[40]
Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In STOC '10, pages 765--774, 2010.
[41]
Aaron Roth and Grant Schoenebeck. Conducting truthful surveys, cheaply. In EC, pages 826--843, 2012.
[42]
David Xiao. Is privacy compatible with truthfulness? In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 67--86. ACM, 2013.

Cited By

View all
  • (2025)Large-Scale Mechanism Design for Networks: Superimposability and Dynamic ImplementationIEEE Transactions on Mobile Computing10.1109/TMC.2024.349995824:3(1278-1292)Online publication date: Mar-2025
  • (2024)Differentially private no-regret exploration in adversarial Markov decision processesProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702687(235-272)Online publication date: 15-Jul-2024
  • (2024)Nash incentive-compatible online mechanism learning via weakly differentially private online learningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692898(20643-20659)Online publication date: 21-Jul-2024
  • Show More Cited By

Index Terms

  1. Mechanism design in large games: incentives and privacy

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science
    January 2014
    566 pages
    ISBN:9781450326988
    DOI:10.1145/2554797
    • Program Chair:
    • Moni Naor
    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 ACM 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: 12 January 2014

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. differential privacy
    2. equilibrium selection
    3. game theory
    4. mechanism design

    Qualifiers

    • Research-article

    Conference

    ITCS'14
    Sponsor:
    ITCS'14: Innovations in Theoretical Computer Science
    January 12 - 14, 2014
    New Jersey, Princeton, USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Large-Scale Mechanism Design for Networks: Superimposability and Dynamic ImplementationIEEE Transactions on Mobile Computing10.1109/TMC.2024.349995824:3(1278-1292)Online publication date: Mar-2025
    • (2024)Differentially private no-regret exploration in adversarial Markov decision processesProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702687(235-272)Online publication date: 15-Jul-2024
    • (2024)Nash incentive-compatible online mechanism learning via weakly differentially private online learningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692898(20643-20659)Online publication date: 21-Jul-2024
    • (2024)Group Decision-Making among Privacy-Aware AgentsSSRN Electronic Journal10.2139/ssrn.4726578Online publication date: 2024
    • (2024)Scenario-based Adaptations of Differential Privacy: A Technical SurveyACM Computing Surveys10.1145/365115356:8(1-39)Online publication date: 26-Apr-2024
    • (2024)Truthful and privacy-preserving generalized linear modelsInformation and Computation10.1016/j.ic.2024.105225(105225)Online publication date: Sep-2024
    • (2023)Threshold KNN-shapleyProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668762(60429-60467)Online publication date: 10-Dec-2023
    • (2023)Differentially private episodic reinforcement learning with heavy-tailed rewardsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619986(37880-37918)Online publication date: 23-Jul-2023
    • (2023)Multi-task differential privacy under distribution skewProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619139(17784-17807)Online publication date: 23-Jul-2023
    • (2023)Mediated Multi-Agent Reinforcement LearningProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598618(49-57)Online publication date: 30-May-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