  We derive the optimal $\epsilon$-differentially private mechanism for a
general two-dimensional real-valued (histogram-like) query function under a
utility-maximization (or cost-minimization) framework for the $\ell^1$ cost
function. We show that the optimal noise probability distribution has a
correlated multidimensional staircase-shaped probability density function.
Compared with the Laplacian mechanism, we show that in the high privacy regime
(as $\epsilon \to 0$), the Laplacian mechanism is approximately optimal; and in
the low privacy regime (as $\epsilon \to +\infty$), the optimal cost is
$\Theta(e^{-\frac{\epsilon}{3}})$, while the cost of the Laplacian mechanism is
$\frac{2\Delta}{\epsilon}$, where $\Delta$ is the sensitivity of the query
function. We conclude that the gain is more pronounced in the low privacy
regime. We conjecture that the optimality of the staircase mechanism holds for
vector-valued (histogram-like) query functions with arbitrary dimension, and
holds for many other classes of cost functions as well.
