  Most methods for publishing data with privacy guarantees introduce randomness
into datasets which reduces the utility of the published data. In this paper,
we study the privacy-utility tradeoff by taking maximal leakage as the privacy
measure and the expected Hamming distortion as the utility measure. We study
three different but related problems. First, we assume that the data-generating
distribution (i.e., the prior) is known, and we find the optimal privacy
mechanism that achieves the smallest distortion subject to a constraint on
maximal leakage. Then, we assume that the prior belongs to some set of
distributions, and we formulate a min-max problem for finding the smallest
distortion achievable for the worst-case prior in the set, subject to a maximal
leakage constraint. Lastly, we define a partial order on privacy mechanisms
based on the largest distortion they generate. Our results show that when the
prior distribution is known, the optimal privacy mechanism fully discloses
symbols with the largest prior probabilities, and suppresses symbols with the
smallest prior probabilities. Furthermore, we show that sets of priors that
contain more uniform distributions lead to larger distortion, while privacy
mechanisms that distribute the privacy budget more uniformly over the symbols
create smaller worst-case distortion.
