{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T12:44:20Z","timestamp":1751028260180,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T00:00:00Z","timestamp":1540252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["NRI-1317788, CCF-1116892, CCF-1101215, CCF-1101389 and CNS-1065060"],"award-info":[{"award-number":["NRI-1317788, CCF-1116892, CCF-1101215, CCF-1101389 and CNS-1065060"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF CAREER"},{"name":"Google Focused Research Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>\n            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\u2014where the \u201cinput\u201d to the problem consists of sensitive patient medical records\u2014we 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\u2014or even the relaxation of\n            <jats:italic>joint<\/jats:italic>\n            -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\n            <jats:italic>marginal<\/jats:italic>\n            -differential privacy\u2014which promises, informally, that the privacy of every agent\n            <jats:italic>i<\/jats:italic>\n            is protected from every other agent\n            <jats:italic>j<\/jats:italic>\n            \u2260\n            <jats:italic>i<\/jats:italic>\n            so long as\n            <jats:italic>j<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3105445","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T12:16:16Z","timestamp":1540296976000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Private Pareto Optimal Exchange"],"prefix":"10.1145","volume":"6","author":[{"given":"Sampath","family":"Kannan","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jamie","family":"Morgenstern","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Rogers","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jorge Alcalde-Unzu and Elena Molis. 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). Retrieved from http:\/\/EconPapers.repec.org\/RePEc:cor:louvco:2009062.  Jorge Alcalde-Unzu and Elena Molis. 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). Retrieved from http:\/\/EconPapers.repec.org\/RePEc:cor:louvco:2009062."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873691"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602841"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591826"},{"key":"e_1_2_1_7_1","unstructured":"Justin Hsu Zhiyi Huang Aaron Roth and Zhiwei Steven Wu. 2014a. Jointly private convex programming. CoRR abs\/1411.0998 (2014). Retrieved from http:\/\/arxiv.org\/abs\/1411.0998.  Justin Hsu Zhiyi Huang Aaron Roth and Zhiwei Steven Wu. 2014a. Jointly private convex programming. CoRR abs\/1411.0998 (2014). Retrieved from http:\/\/arxiv.org\/abs\/1411.0998."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2012.05.017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554834"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884444"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557090"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602856"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.04.004"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482574"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90033-0"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105445","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:38Z","timestamp":1750217438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,23]]},"references-count":18,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3105445"],"URL":"https:\/\/doi.org\/10.1145\/3105445","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2018,10,23]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}