# A Distributed Differentially Private Algorithm for Resource Allocation in Unboundedly Large Settings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2020.

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

- [LIA: Privacy-Preserving Data Quality Evaluation in Federated Learning Using a Lazy Influence Approximation](https://mlsanity.com/paper/2205.11518/) (2022)

## Abstract (arXiv)

We introduce a practical and scalable algorithm (PALMA) for solving one of the fundamental problems of multi-agent systems -- finding matches and allocations -- in unboundedly large settings (e.g., resource allocation in urban environments, mobility-on-demand systems, etc.), while providing strong worst-case privacy guarantees. PALMA is decentralized, runs on-device, requires no inter-agent communication, and converges in constant time under reasonable assumptions. We evaluate PALMA in a mobility-on-demand and a paper assignment scenario, using real data in both, and demonstrate that it provides a strong level of privacy (varepsilon ≤ 1 and median as low as varepsilon = 0.5 across agents) and high-quality matchings (up to 86% of the non-private optimal, outperforming even the privacy-preserving centralized maximum-weight matching baseline).