Jointly private convex programming
From MaRDI portal
Abstract: In this paper we present an extremely general method for approximately solving a large family of convex programs where the solution can be divided between different agents, subject to joint differential privacy. This class includes multi-commodity flow problems, general allocation problems, and multi-dimensional knapsack problems, among other examples. The accuracy of our algorithm depends on the emph{number} of constraints that bind between individuals, but crucially, is emph{nearly independent} of the number of primal variables and hence the number of agents who make up the problem. As the number of agents in a problem grows, the error we introduce often becomes negligible. We also consider the setting where agents are strategic and have preferences over their part of the solution. For any convex program in this class that maximizes emph{social welfare}, there is a generic reduction that makes the corresponding optimization emph{approximately dominant strategy truthful} by charging agents prices for resources as a function of the approximately optimal dual variables, which are themselves computed under differential privacy. Our results substantially expand the class of problems that are known to be solvable under both privacy and incentive constraints.
Recommendations
Cited in
(7)- Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner
- Private matchings and allocations
- Near optimal jointly private packing algorithms via dual multiplicative weight update
- Scalable and Jointly Differentially Private Packing
- A privacy-preserving method to optimize distributed resource allocation
- Private matchings and allocations
- Adversarial bandits with knapsacks
This page was built for publication: Jointly private convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575620)
