Private Matchings and Allocations
Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu
[arXiv]
We consider a private variant of the classical allocation problem: given m 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? Specifically, the valuation functions are sensitive information which the agents wish to keep private from arbitrary coalitions of other agents. 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 the standard notion of differential privacy. Informally, the allocation must match agents to preferred goods in order to maximize social welfare, but this preference is exactly what agents wish to keep private! Therefore, we consider the problem under the recently introduced constraint of joint differential privacy: roughly, for any agent i, no coalition of agents excluding i should be able to learn about the valuation function of agent i. We first show that if there are a small number of identical copies of each good, then it is possible to efficiently and accurately solve the maximum weight matching problem while guaranteeing joint differential privacy. We then extend our techniques to the more general allocation problem, when bidder valuations satisfy the gross substitutes condition. Finally, we prove lower bounds demonstrating that the problem cannot be privately solved to non-trivial accuracy without requiring multiple copies of each type of good.