Jointly differentially private packing

Abstract

I focus my research on differential privacy. Informally, a mechanism is differentially private if the output distribution is insensitive to the change of an individual's data.

Consider a packing problem with $n$ agents and $m$ resources where each agent has different values for different bundles of resources. The value and resource demands of an agent are private. The goal is to allocate bundles to agents so as to maximize the sum of values of all agents subject to the supply constraints of resources.

Firstly, we present an improved $(\epsilon, \delta)$-jointly differentially private algorithm for packing problems. Our algorithm gives a feasible output that is approximately optimal up to an $\alpha n$ additive factor as long as the supply of each resource is at least $\tilde{O}(\sqrt{m} / \alpha \epsilon)$, where $m$ is the number of resources. This improves the previous result by Hsu et al.~(SODA '16), which requires the total supply to be at least $\tilde{O}(m^2 / \alpha \epsilon)$, and only guarantees approximate feasibility in terms of total violation. Further, we complement our algorithm with an almost matching hardness result, showing that $\Omega(\sqrt{m \ln(1/\delta)} / \alpha \epsilon)$ supply is necessary for any $(\epsilon, \delta)$-jointly differentially private algorithm to compute an approximately optimal packing solution. Then, we introduce an alternative approach that runs in linear time, is exactly truthful, can be implemented online, and can be $\epsilon$-jointly differentially private, but requires a larger supply of each resource. Finally, we introduce an scalable $(\epsilon, \delta)$-jointly differentially private algorithm for packing problems. Our algorithm not only achieves the optimal trade-off between the privacy parameter $\epsilon$ and the minimum supply requirement (up to logarithmic factors), but is also scalable in the sense that the running time is linear in the number of agents $n$. Previous algorithms either run in cubic time in $n$, or require a minimum supply per resource that is $\sqrt{n}$ times larger than the best possible.