  In the last years we have witnessed the appearance of a variety of strategies
to design optimal location privacy-preserving mechanisms, in terms of
maximizing the adversary's expected error with respect to the users'
whereabouts. In this work, we take a closer look at the defenses created by
these strategies and show that, even though they are indeed optimal in terms of
adversary's correctness, not all of them offer the same protection when looking
at other dimensions of privacy. To avoid "bad" choices, we argue that the
search for optimal mechanisms must be guided by complementary criteria. We
provide two example auxiliary metrics that help in this regard: the conditional
entropy, that captures an information-theoretic aspect of the problem; and the
worst-case quality loss, that ensures that the output of the mechanism always
provides a minimum utility to the users. We describe a new mechanism that
maximizes the conditional entropy and is optimal in terms of average adversary
error, and compare its performance with previously proposed optimal mechanisms
using two real datasets. Our empirical results confirm that no mechanism fares
well on every privacy criteria simultaneously, making apparent the need for
considering multiple privacy dimensions to have a good understanding of the
privacy protection a mechanism provides.
