Impossibility of Differentially Private Universally Optimal Mechanisms

The notion of a universally utility-maximizing privacy mechanism was introduced by Ghosh, Roughgarden, and Sundararajan [Proceedings of STOC, 2009]. These are mechanisms that guarantee optimal utility to a large class of information consumers, simultaneously, while preserving privacy. They demonstrated, quite surprisingly, a case where such a universally utility-maximizing privacy mechanism exists, when the information consumers are Bayesian. This result was later extended by Gupte and Sundararajan [Proceedings of PODS, 2010] to risk-averse consumers. Both positive results deal with mechanisms (approximately) computing a single count query (i.e., the number of individuals satisfying a specific property in a given population). We show that such universally optimal mechanisms do not exist for some natural extensions of count queries, both for Bayesian and risk-averse consumers. For the Bayesian case, we go further and give a characterization of those functions that admit universally optimal mechanisms, showing that a universally optimal mechanism exists, essentially, only for a (single) count query. At the heart of our proof is a representation of a query function by its privacy constraint graph whose edges correspond to values resulting by applying the query function to neighboring databases.