Differentially Private Resource Allocation
We consider a resource allocation problem with private and shared capacities that are used by multiple parties. The problem is formulated using the input data of all parties. In this formulation, the main issue for the parties is the privacy of their input data and the optimal solutions containing their individual decisions. To address this concern, using the structure of the problem, we decompose the main problem into subproblems where each subproblem is solved by the related party. In this way, we eliminate almost all the data-sharing requirements of the main problem except the linking decision variables defined for the shared resources. To reach the optimal allocation decisions, each party still needs to share its decision variable on the shared resources iteratively. However, this would result in some information leakage regarding their private information and violate the privacy of the parties. To prevent this, we design an epsilon-differentially private algorithm to hold the privacy of the parties. We show that the resulting algorithm is convergent and differentially private. To discuss the trade-off between privacy and optimality, we also give a bound on the expected distance to the optimal solution in terms of number iterations.
Meeting ID: 948 5226 4960