A Distributed Differentially Private Algorithm for Resource Allocation in Unboundedly Large Settings
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).
Code (0)
등록된 구현이 없습니다.
Tasks
Privacy PreservingSimilar Papers 제목 키워드 기반
Differentially Private Dual Gradient Tracking for Distributed Resource Allocation
This paper investigates privacy issues in distributed resource allocation over directed networks, where each agent holds a private cost function and optimizes its decision subject to a global coupling constraint through …
Private Optimization Without Constraint Violations
We study the problem of differentially private optimization with linear constraints when the right-hand-side of the constraints depends on private data. This type of problem appears in many applications, especially resou…
QoS-Aware Token Scheduling and Private Data Valuation for Multi-Modal Agentic Networks
In agentic systems, human-generated data records anchor the value of AI services. Yet cloud compute pipelines centralize processing on remote servers. Data centralization reduces personal data sovereignty and may potenti…
Image ReconstructionScalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning
This paper introduces the first provably accurate algorithms for differentially private, top-down decision tree learning in the distributed setting (Balcan et al., 2012). We propose DP-TopDown, a general privacy preservi…
Privacy PreservingDifferentially Private ADMM for Distributed Medical Machine Learning
Due to massive amounts of data distributed across multiple locations, distributed machine learning has attracted a lot of research interests. Alternating Direction Method of Multipliers (ADMM) is a powerful method of des…
BIG-bench Machine Learning