A Distributed Differentially Private Algorithm for Resource Allocation in Unboundedly Large Settings
This work addresses privacy-preserving resource allocation for applications like urban mobility and paper assignment, offering a scalable solution with practical impact.
The paper tackles the problem of resource allocation in large-scale multi-agent systems by introducing PALMA, a decentralized algorithm that provides strong differential privacy guarantees and achieves up to 86% of the non-private optimal matching quality in real-world scenarios.
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 \leq 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).