Differential Privacy in the Context of Min-Max Optimization Problems

People's profound concern for sharing information due to privacy loss, decreases the accuracy of statistics. Differential privacy provides a mathematical definition of privacy and potentially increases privacy levels while keeping sufficient accuracy. In this research, we implement differentially private mechanisms in the context of min-max functions. First, we evaluate the performance of Laplacian methods, the exponential method and a private version of the sub gradient method, in optimizing a min-max function that generates a convex, piecewise affine optimization problem. We show that the private sub gradient method attains best results under most circumstances. Second, we present an algorithm based on the Johnson-Lindenstrauss transformation, to find a min-max shortest path in a differentially private way. Our research shows that the algorithm maintains a relatively good level of optimality, particularly for large graphs. This paper additionally contains an extended related work section about the applications of differential privacy in economic theory and economic applications.