File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Private matchings and allocations

TitlePrivate matchings and allocations
Authors
KeywordsAscending auction
Differential privacy
Gross substitutes
Matching
Issue Date2014
PublisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.sigact.org/stoc.html
Citation
The 4th Annual ACM Symposium on Theory of Computing (STOC 2014), New York, NY., 31 May-3 June 2014. In ACM Symposium on the Theory of Computing Annual Proceedings, 2014, p. 21-30 How to Cite?
AbstractWe consider a private variant of the classical allocation problem: given k goods and n agents with individual, private valuation functions over bundles of goods, how can we partition the goods amongst the agents to maximize social welfare? An important special case is when each agent desires at most one good, and specifies her (private) value for each good: in this case, the problem is exactly the maximum-weight matching problem in a bipartite graph. Private matching and allocation problems have not been considered in the differential privacy literature, and for good reason: they are plainly impossible to solve under differential privacy. Informally, the allocation must match agents to their preferred goods in order to maximize social welfare, but this preference is exactly what agents wish to hide! Therefore, we consider the problem under the relaxed constraint of joint differential privacy: for any agent i, no coalition of agents excluding i should be able to learn about the valuation function of agent i. In this setting, the full allocation is no longer published---instead, each agent is told what good to get. We first show that with a small number of identical copies of each good, it is possible to efficiently and accurately solve the maximum weight matching problem while guaranteeing joint differential privacy. We then consider the more general allocation problem, when bidder valuations satisfy the gross substitutes condition. Finally, we prove that the allocation problem cannot be solved to non-trivial accuracy under joint differential privacy without requiring multiple copies of each type of good. © 2014 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/201109
ISBN
ISSN

 

DC FieldValueLanguage
dc.contributor.authorHsu, Jen_US
dc.contributor.authorHuang, Zen_US
dc.contributor.authorRoth, Aen_US
dc.contributor.authorRoughgarden, Ten_US
dc.contributor.authorWu, SZen_US
dc.date.accessioned2014-08-21T07:13:35Z-
dc.date.available2014-08-21T07:13:35Z-
dc.date.issued2014en_US
dc.identifier.citationThe 4th Annual ACM Symposium on Theory of Computing (STOC 2014), New York, NY., 31 May-3 June 2014. In ACM Symposium on the Theory of Computing Annual Proceedings, 2014, p. 21-30en_US
dc.identifier.isbn978-1-4503-2710-7-
dc.identifier.issn0737-8017-
dc.identifier.urihttp://hdl.handle.net/10722/201109-
dc.description.abstractWe consider a private variant of the classical allocation problem: given k goods and n agents with individual, private valuation functions over bundles of goods, how can we partition the goods amongst the agents to maximize social welfare? An important special case is when each agent desires at most one good, and specifies her (private) value for each good: in this case, the problem is exactly the maximum-weight matching problem in a bipartite graph. Private matching and allocation problems have not been considered in the differential privacy literature, and for good reason: they are plainly impossible to solve under differential privacy. Informally, the allocation must match agents to their preferred goods in order to maximize social welfare, but this preference is exactly what agents wish to hide! Therefore, we consider the problem under the relaxed constraint of joint differential privacy: for any agent i, no coalition of agents excluding i should be able to learn about the valuation function of agent i. In this setting, the full allocation is no longer published---instead, each agent is told what good to get. We first show that with a small number of identical copies of each good, it is possible to efficiently and accurately solve the maximum weight matching problem while guaranteeing joint differential privacy. We then consider the more general allocation problem, when bidder valuations satisfy the gross substitutes condition. Finally, we prove that the allocation problem cannot be solved to non-trivial accuracy under joint differential privacy without requiring multiple copies of each type of good. © 2014 ACM.en_US
dc.languageengen_US
dc.publisherAssociation for Computing Machinery, Inc. The Journal's web site is located at http://www.sigact.org/stoc.html-
dc.relation.ispartofACM Symposium on the Theory of Computing Annual Proceedingsen_US
dc.rightsACM Symposium on the Theory of Computing. Annual Proceedings. Copyright © Association for Computing Machinery, Inc.-
dc.subjectAscending auction-
dc.subjectDifferential privacy-
dc.subjectGross substitutes-
dc.subjectMatching-
dc.titlePrivate matchings and allocationsen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@hku.hken_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.identifier.doi10.1145/2591796.2591826en_US
dc.identifier.scopuseid_2-s2.0-84904329113-
dc.identifier.hkuros234385en_US
dc.identifier.spage21en_US
dc.identifier.epage30en_US
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats