243. Privacy-Preserving Resource Allocation: Near-Optimal Algorithms and Public Policy Implications
Invited abstract in session TA-34: Advancements of OR-analytics in statistics, machine learning and data science 2, stream Advancements of OR-analytics in statistics, machine learning and data science.
Tuesday, 8:30-10:00Room: Michael Sadler LG10
Authors (first author is the speaker)
| 1. | Du Chen
|
| Nanyang Business School, Nanyang Technological University | |
| 2. | Geoffrey A. Chua
|
| Nanyang Business School, Nanyang Technological University | |
| 3. | Victor Jose
|
| Operations and Information Management, Georgetown University |
Abstract
Resource allocation is an important and pervasive problem in management science. Recent growth in privacy concerns has made this problem more challenging because decision makers attempting to optimally distribute limited resources may inadvertently leak agents’ private data through the optimal allocation decisions. To address this potential privacy leakage, we develop a generic algorithm called Noisy Dual Mirror Descent (NDMD) that provides privacy guarantees without sacrificing optimality by much. This algorithm applies a noisy mirror descent approach to the dual problem and privatizes the shadow prices in the resource allocation problem, which can then be used to coordinate allocations in the original problem. We show that this proposed algorithm is jointly differentially private (JDP), a tailored concept for allocation problems under the differential privacy (DP) framework. Furthermore, we show that the algorithm can achieve near-optimal convergence rates of suboptimality in the minimax sense. Finally, we demonstrate the use and benefit of this NDMD approach by applying it to an important policy problem; namely, the allocation of Title I US education grants. When compared to a popular DP algorithm that privatizes the raw input data, our approach significantly reduces nationwide misallocation by as much as 52%. We also show that this allocation can significantly mitigate the disproportionate impact of privacy protection on historically disadvantaged and underrepresented
Keywords
- Convex Optimization
- OR/MS and the Public Sector
- Computer Science/Applications
Status: accepted
Back to the list of papers