File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1137/1.9781611974331.ch43
 Scopus: eid_2s2.084963542261
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Jointly Private Convex Programming
Title  Jointly Private Convex Programming 

Authors  
Issue Date  2016 
Publisher  Society for Industrial and Applied Mathematics (SIAM). 
Citation  The 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA., 1012 January 2016. In Conference Proceedings, 2016, p. 580599 How to Cite? 
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 multicommodity flow problems, general allocation problems, and multidimensional 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. 
Persistent Identifier  http://hdl.handle.net/10722/232173 
ISBN 
DC Field  Value  Language 

dc.contributor.author  Hsu, J   
dc.contributor.author  Huang, Z   
dc.contributor.author  Roth, A   
dc.contributor.author  Wu, ZS   
dc.date.accessioned  20160920T05:28:13Z   
dc.date.available  20160920T05:28:13Z   
dc.date.issued  2016   
dc.identifier.citation  The 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA., 1012 January 2016. In Conference Proceedings, 2016, p. 580599   
dc.identifier.isbn  9781510819672   
dc.identifier.uri  http://hdl.handle.net/10722/232173   
dc.description.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 multicommodity flow problems, general allocation problems, and multidimensional 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.   
dc.language  eng   
dc.publisher  Society for Industrial and Applied Mathematics (SIAM).   
dc.relation.ispartof  Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2016 Proceedings   
dc.rights  27th Annual ACMSIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.   
dc.title  Jointly Private Convex Programming   
dc.type  Conference_Paper   
dc.identifier.email  Huang, Z: zhiyi@cs.hku.hk   
dc.identifier.authority  Huang, Z=rp01804   
dc.description.nature  Link_to_subscribed_fulltext   
dc.identifier.doi  10.1137/1.9781611974331.ch43   
dc.identifier.scopus  eid_2s2.084963542261   
dc.identifier.hkuros  263131   
dc.identifier.spage  580   
dc.identifier.epage  599   
dc.publisher.place  United States   
dc.customcontrol.immutable  sml 160926   