# Private Matchings and Allocations

arXiv: https://arxiv.org/abs/1311.2828 · HTML: https://mlsanity.com/paper/1311.2828/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2013.

## Built on by (most cited first, 23 of 23)

- [Federated f-Differential Privacy](https://mlsanity.com/paper/2102.11158/) (2021)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Personalization Improves Privacy-Accuracy Tradeoffs in Federated Learning](https://mlsanity.com/paper/2202.05318/) (2022)
- [Differentially Private Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2201.07052/) (2022)
- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learning](https://mlsanity.com/paper/2309.05505/) (2023)
- [Privately Publishable Per-instance Privacy](https://mlsanity.com/paper/2111.02281/) (2021)
- [Private Multi-Task Learning: Formulation and Applications to Federated Learning](https://mlsanity.com/paper/2108.12978/) (2021)
- [Differentially Private Exploration in Reinforcement Learning with Linear Representation](https://mlsanity.com/paper/2112.01585/) (2021)
- [Improved Regret for Differentially Private Exploration in Linear MDP](https://mlsanity.com/paper/2202.01292/) (2022)
- [Adaptive Control of Differentially Private Linear Quadratic Systems](https://mlsanity.com/paper/2108.11563/) (2021)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Differentially Private Condorcet Voting](https://mlsanity.com/paper/2206.13081/) (2022)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Truthful Generalized Linear Models](https://mlsanity.com/paper/2209.07815/) (2022)
- [Learning across Data Owners with Joint Differential Privacy](https://mlsanity.com/paper/2305.15723/) (2023)
- [Differentially Private Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2404.07559/) (2024)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)
- [Differentially Private Online Item Pricing](https://mlsanity.com/paper/2305.11362/) (2023)
- [Differentially Private High Dimensional Bandits](https://mlsanity.com/paper/2402.03737/) (2024)
- [Towards Optimal Differentially Private Regret Bounds in Linear MDPs](https://mlsanity.com/paper/2504.09339/) (2025)
- [Randomized Least Squares Value Iteration itself is Joint Differentially Private](https://mlsanity.com/paper/2606.01952/) (2026)

## Abstract (arXiv)

We 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.