skip to main content
10.1145/2764468.2764504acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Private Pareto Optimal Exchange

Published: 15 June 2015 Publication History

Abstract

We consider the problem of implementing an individually rational, asymptotically Pareto optimal allocation in a barter-exchange economy where agents are endowed with goods and preferences over the goods of others, but may not use money as a medium of exchange. Because one of the most important instantiations of such economies is kidney exchange -- where the "input" to the problem consists of sensitive patient medical records -- we ask to what extent such exchanges can be carried out while providing formal privacy guarantees to the participants. We show that individually rational allocations cannot achieve any non-trivial approximation to Pareto optimality if carried out under the constraint of differential privacy -- or even the relaxation of joint-differential privacy, under which it is known that asymptotically optimal allocations can be computed in two sided markets [Hsu et al. STOC 2014]. We therefore consider a further relaxation that we call marginal-differential privacy --which promises, informally, that the privacy of every agent i is protected from every other agent j ≠ i so long as j does not collude or share allocation information with other agents. We show that under marginal differential privacy, it is possible to compute an individually rational and asymptotically Pareto optimal allocation in such exchange economies.

References

[1]
ALCALDE-UNZU, J. AND MOLIS, E. 2009. Exchange of indivisible goods and indifferences: the top trading absorbing sets mechanisms. CORE Discussion Papers 2009062, Universit catholique de Louvain, Center for Operations Research and Econometrics (CORE).
[2]
DWORK, C., MCSHERRY, F., NISSIM, K., AND SMITH, A. 2006. Calibrating noise to sensitivity in private data analysis. In TCC '06. 265--284.
[3]
DWORK, C., ROTHBLUM, G. N., AND VADHAN, S. P. 2010. Boosting and differential privacy. In FOCS. 51--60.
[4]
GUPTA, A., LIGETT, K., MCSHERRY, F., ROTH, A., AND TALWAR, K. 2010. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 1106--1125.
[5]
HE, K. AND MU, X. 2014. Differentially private and incentive compatible recommendation system for the adoption of network goods. In Proceedings of the fifteenth ACM conference on Economics and computation. ACM, 949--966.
[6]
HSU, J., HUANG, Z., ROTH, A., ROUGHGARDEN, T., AND WU, Z. S. 2014a. Private matchings and allocations. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. STOC '14. ACM, New York, NY, USA, 21--30.
[7]
HSU, J., HUANG, Z., ROTH, A., AND WU, Z. S. 2014b. Jointly private convex programming. CoRR abs/1411.0998.
[8]
JARAMILLO, P. AND MANJUNATH, V. 2012. The difference indifference makes in strategy-proof allocation of objects. Journal of Economic Theory 147, 5, 1913--1946.
[9]
KEARNS, M., PAI, M., ROTH, A., AND ULLMAN, J. 2014. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th ACM SIGact Innovations in Theoretical Computer Science (ITCS).
[10]
MCSHERRY, F. AND MIRONOV, I. 2009. Differentially private recommender systems: building privacy into the net. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 627--636.
[11]
MCSHERRY, F. AND TALWAR, K. 2007. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. FOCS '07. IEEE Computer Society, Washington, DC, USA, 94--103.
[12]
NISSIM, K., RASKHODNIKOVA, S., AND SMITH, A. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM, 75--84.
[13]
RAGHAVAN, P. AND THOMPSON, C. D. 1987. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 4, 365--374.
[14]
ROGERS, R. M. AND ROTH, A. 2014. Asymptotically truthful equilibrium selection in large congestion games. In Proceedings of the fifteenth ACM conference on Economics and computation. ACM, 771--782.ROTH, A. E., SONMEZ, T., AND UTKUUNVER, M. 2005. Pairwise kidney exchange. Journal of Economic Theory 125, 2, 151--188.
[15]
SABAN, D. AND SETHURAMAN, J. 2013. House allocation with indifferences: A generalization and a unified view. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce. EC '13. ACM, New York, NY, USA, 803--820.
[16]
SHAPLEY, L. AND SCARF, H. 1974. On cores and indivisibility. Journal of Mathematical Economics 1, 1, 23--37.

Cited By

View all
  • (2017)Efficient Commodity Matching for Privacy-Preserving Two-Party BarteringProceedings of the Seventh ACM on Conference on Data and Application Security and Privacy10.1145/3029806.3029831(107-114)Online publication date: 22-Mar-2017
  • (2017)Towards Privacy-Preserving Multi-party BarteringFinancial Cryptography and Data Security10.1007/978-3-319-70278-0_2(19-34)Online publication date: 19-Nov-2017

Index Terms

  1. Private Pareto Optimal Exchange

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation
    June 2015
    852 pages
    ISBN:9781450334105
    DOI:10.1145/2764468
    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].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 15 June 2015

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. algorithms
    2. differential privacy
    3. mechanism design

    Qualifiers

    • Research-article

    Funding Sources

    • NSF

    Conference

    EC '15
    Sponsor:
    EC '15: ACM Conference on Economics and Computation
    June 15 - 19, 2015
    Oregon, Portland, USA

    Acceptance Rates

    EC '15 Paper Acceptance Rate 72 of 220 submissions, 33%;
    Overall Acceptance Rate 664 of 2,389 submissions, 28%

    Upcoming Conference

    EC '25
    The 25th ACM Conference on Economics and Computation
    July 7 - 11, 2025
    Stanford , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2017)Efficient Commodity Matching for Privacy-Preserving Two-Party BarteringProceedings of the Seventh ACM on Conference on Data and Application Security and Privacy10.1145/3029806.3029831(107-114)Online publication date: 22-Mar-2017
    • (2017)Towards Privacy-Preserving Multi-party BarteringFinancial Cryptography and Data Security10.1007/978-3-319-70278-0_2(19-34)Online publication date: 19-Nov-2017

    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