Private matchings and allocations

Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We consider a private variant of the classical allocation problem: given k goods and n agents with private valuation functions over bundles of goods, how can we allocate goods to agents to maximize social welfare? An important special case is when agents desire at most one good, and specify their (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 for a 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 receive. We first show that if there are several identical copies of each good, it is possible to efficiently and accurately solve the matching problem while guaranteeing joint differential privacy. We then consider the more general allocation problem where bidder valuations satisfy the gross substitutes condition. Finally, we prove that the allocation problem cannot be solved to nontrivial accuracy under joint differential privacy without requiring multiple copies of each type of good.

Original languageEnglish (US)
Pages (from-to)1953-1984
Number of pages32
JournalSIAM Journal on Computing
Volume45
Issue number6
DOIs
StatePublished - 2016

Bibliographical note

Funding Information:
The first author was supported in part by NSF Grant CNS-1065060. The third author was supported in part by an NSF CAREER award, NSF Grants CCF-1101389 and CNS-1065060, and a Google Focused Research Award. The fourth author was supported in part by NSF Awards CCF-1016885 and CCF-1215965 and an ONR PECASE Award. The fifth author was supported in part by NSF Grant CCF-1101389.

Keywords

  • Ascending auction
  • Differential privacy
  • Gross substitutes
  • Matching

Fingerprint Dive into the research topics of 'Private matchings and allocations'. Together they form a unique fingerprint.

Cite this