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