On The Optimality Of The Exponential Mechanism

In this work, we investigate one of the most renowned tools used in differential privacy, namely the exponential mechanism. We first study the optimality of the error introduced by the exponential mechanism in the average-case scenario, when the input/output universe of the mechanism can be modeled as a graph where each node is associated with a database. By leveraging linear programming theory, we provide some regularity conditions on the graph structure under which the exponential mechanism minimizes the average error. Moreover, we give a toy example in which the optimality is preserved (up to a constant factor) even if these regularity conditions hold only to a certain extent. Finally, we prove the worst-case optimality of the exponential mechanism when it is used to release the output of a sorting function.