Private Distributed Resource Allocation Without Constraint Violations

Distributed resource allocation problem involves a collaborative effort among agents over a communication network to optimize a separable objective function while respecting interconnected constraints. In this work, we address two critical requirements in distributed resource allocation with linear constraints: preserving privacy in coupling constraints and ensuring constraint satisfaction at all times. To meet these needs, we propose a two-step approach. First, we introduce perturbations to the coupling constraints by applying truncated Laplace noise, guaranteeing rigorous differential privacy while preserving problem feasibility. Second, we reformulate the perturbed problem by incorporating auxiliary variables with a network-dependent linear mapping into the constraints. This reformulation allows us to break down the overall optimization problem into local subproblems. In addition, the reformulated optimization problem admits a closed form for the subgradient with respect to the auxiliary variables, which can be computed locally. Exploiting this fact, we develop private distributed resource allocation algorithms, where the optimal auxiliary variables are searched based on gradient-based methods. With some mild assumptions on the objective function and coupling constraints, we prove the sublinear convergence rate of the proposed algorithm. To demonstrate the effectiveness of our approach, we present numerical results on two sets of problems, showcasing the superior performance of our algorithm.