Jointly Private Convex Programming
Jointly Private Convex Programming
复制标题
联合私有凸规划
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Zhiwei Steven Wu
中科院分区：
文献类型：
--
作者：
Justin Hsu;Zhiyi Huang;Aaron Roth;Zhiwei Steven Wu
在本文中，我们提出了一个非常一般的方法近似解决一个大家庭的凸规划的解决方案，可以分为不同的代理，联合差分隐私。这门课包括多商品流问题、一般分配问题、多维背包问题等。我们的算法的准确性取决于个体之间的约束条件的数量，但至关重要的是，它几乎独立于原始变量的数量，因此也独立于构成问题的代理的数量。随着问题中代理数量的增加，我们引入的错误通常可以忽略不计。
我们还考虑了代理具有战略性并对解决方案的一部分有偏好的设置。对于任何凸计划在这一类，最大化社会福利，有一个通用的减少，使相应的优化近似优势策略真实的，通过收取代理价格的资源作为一个函数的近似最优的对偶变量，这本身计算下差分隐私。我们的研究结果大大扩展了一类问题，已知是可解决的隐私和激励约束下。
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.