Frequently Asked Questions:
"Towards an Axiomatization of Statistical Privacy and Utility"

General Questions

1. Q: Does your utility axiom cover "matrix-based" perturbations or any privacy mechanism I can come up with?
   A: Our axiom covers any privacy mechanism. Any algorithm (randomized or not) can be represented as a (possibly infinite dimensional) matrix. We present our technical results for finite input spaces (in which case the matrix is finite-dimensional). The results for infinite dimensional spaces are slightly different because topology and measure theory works differently in these situations.
2. Q: Where are all the insights that you promised?
   A: Some of the insights we got from studying these axioms are presented in the paper, but we did not have room to fit all of them in. The purpose of this paper was to demonstrate that some simple axioms can have nontrivial results. We are hoping to produce a document describing some concrete applications soon.
3. Q: What is the difference between "generality" and "Bayesian sufficiency"?
   A: They are the same concept and we will probably use the term "sufficiency" in future work. We were unaware of this connection until it was pointed out by Stephen Fienberg.
4. Q: Does there always exist a maximally general mechanism?
   A: Unfortunately, no. For example, if you take the definition of differential privacy and replace "<=" with "<" then there is no maximally general mechanism. It is basically an issue with (topologically) open/closed sets. A simple analogy is the fact that there is no largest real number strictly less than 1, but there is a largest real number that is less than or equal to 1 (i.e. 1 itself).
5. Q: Are you axiomatizing general purpose utility metrics or application-specific utility metrics?
   A: This paper discusses a general principle for application-specific utility metrics. It turns out that measures of utility that make sense in statistics (expected loss, minimax error, etc.) do not make as much sense in privacy. For example, the slides accompanying this paper show a completely useless mechanism that has lower expected loss than a more informative mechanism. The reason seems to be that in privacy we are free to choose the noise (with a few restrictions) but in statistics the noise is given and we are only free to choose the estimator. Arpita Ghosh, Tim Roughgarden and Mukund Sundararajan ("Universally utility-maximizing privacy mechanisms", STOC '09) were the first to show that you could design an optimal mechanism in terms of expected utility but that you were better off using a different mechanism that provides strictly more information (but not more expected utility) and this let you use the output for several related tasks. In a followup paper, Mangesh Gupte and Mukund Sundararajan ("Universally optimal privacy mechanisms for minimax agents", PODS '10) proved a similar result for minimax error.

Technical Questions

1. Q: Is Assumption 2.21 reasonable?
   A: Yes it is (we get it for free). Many predicates yield the same privacy definition when plugged into Definition 2.0.3. In particular, this is true when we replace "q(a,b)" with "q(a,b) AND q(1-a,1-b)". The properties that q(a,b) needs in order for it to be consistent with the axioms can be expressed in terms of the properties of "q(a,b) AND q(1-a,1-b)". Not surprisingly, it turns out that this latter predicate is easier to work with. So, with no loss of generality this is what we do.