Jointly private convex programming

Justin Hsu, Zhiyi Huang, Aaron Roth, Zhiwei Steven Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

We present a general method for approximately solving convex programs defined by private information from agents, when the solution can be naturally partitioned among the agents. This class of problems includes multi-commodity flow problems, general allocation problems, and multi-dimensional knapsack problems, among other examples. The accuracy of our algorithm depends on the number of coupling constraints, which bind multiple agents. On the other hand, our accuracy is nearly independent of the number of variables, and in many cases, actually improves as the number of agents increases. A special case of our result (solving general allocation problems beyond "Gross Substitute" preferences) resolves the main open problem from [Hsu et al. STOC 2014]. We also consider strategic agents who have preferences over their part of the solution. For any convex program in our class that maximizes social welfare, we show how to create an approximately dominant strategy truthful mechanism, approximately maximizing welfare. The central idea is to charge agents prices based on the approximately optimal dual variables, which are themselves computed under differential privacy. Our results substantially broaden the class of problems that are known to be solvable under privacy and/or incentive constraints.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages580-599
Number of pages20
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume1

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Country/TerritoryUnited States
CityArlington
Period1/10/161/12/16

Fingerprint

Dive into the research topics of 'Jointly private convex programming'. Together they form a unique fingerprint.

Cite this