Permute-and-Flip: A new mechanism for differentially private selection

Introduction

The exponential mechanism is one of the most fundamental mechanisms for differential privacy. It addresses the important problem of differentially private selection, or selecting an item from a set of candidates that approximately maximizes some objective function. The exponential mechanism was introduced soon after differential privacy itself, and has remained the dominant mechanism for private selection since.

The exponential mechanism is simple, easy to implement, runs in linear time, has good theoretical and practical performance, and solves an important problem. It can be used directly as a competitive mechanism for computing simple statistics like medians or modes . Furthermore, it is an integral part of several more complex differentially private mechanisms for a range of tasks, including linear query answering , heavy hitter estimation , synthetic data generation , dimensionality reduction , linear regression , and empirical risk minimization .

In this work, we propose the permute-and-flip mechanism as an alternative to the exponential mechanism for the task of differentially private selection. It enjoys the same desirable properties of the exponential mechanism stated above, and its expected error is never higher, but can be up to two times lower than that of the exponential mechanism. Furthermore, we show that in reasonable settings no better mechanism exists: the permute-and-flip mechanism is Pareto optimal, and, if $\epsilon\geq\log(\frac{1}{2}(3+\sqrt{5}))\approx 0.96$, is optimal in a reasonable sense “overall”.

The permute-and-flip mechanism serves as a drop-in replacement for the exponential mechanism in existing and future mechanisms, and immediately offers utility improvements. The utility improvements of up to $2\times$ over the state-of-the-art will impact practical deployments of differential privacy, where choosing the right privacy-utility trade-off is already a challenging social choice .

Preliminaries

A dataset $D$ is a collection of individual data coming from the universe of all possible datasets $\mathcal{D}$. We say datasets $D$ and $D^{\prime}$ are neighbors, denoted $D\sim D^{\prime}$, if they differ in the data of a single individual.

Differential privacy is a mathematical privacy definition, and a property of a mechanism, that guarantees the output of the mechanism will not differ significantly (in a probabilistic sense) between any two neighboring datasets.

A randomized mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{R}$ is $\epsilon$-differentially private, if and only if:

for all neighboring datasets $D\sim D^{\prime}$ and all possible subsets of outcomes $S\subseteq\mathcal{R}$.

The sensitivity of a function is an important quantity to consider when designing differentially private mechanisms, which measures how much a function can change between two neighboring datasets.

2 Private Selection

Monotonicity: If $q_{r}\leq q^{\prime}_{r}$ and $q_{s}\geq q^{\prime}_{s}$ for all $s\neq r$, then

Informally, a symmetric mechanism is one where the quality scores can be permuted arbitrarily without affecting the distribution of outcomes. This avoids pathologies where a mechanism can appear to do well for a particular quality score vector, but only because it has a built-in bias towards certain outcomes. Similarly, a shift-invariant mechanism is one where a constant can be added to all quality scores without changing the distribution of outcomes. A mechanism is monotonic if increasing one quality score while decreasing others will increase the probability on that outcome, and decrease the probability on all other outcomes. A mechanism that satisfies all of these criteria is called regular.

Mechanisms that are not regular have undesirable pathologies. Thus, we restrict our attention to regular mechanisms in this work. Beyond regularity, the main criteria we use to evaluate a mechanism is the error random variable:

where $q_{*}=\max_{r\in\mathcal{R}}q_{r}$ is the optimal quality score.

3 Exponential Mechanism

The exponential mechanism is a mechanism that is both classical and state-of-the-art for the task of differentially private selection.

It is well-known that the exponential mechanism is $\epsilon$-differentially private, and it is easy to show that it also satisfies the regularity conditions in Definition 3. In addition, it is possible to bound the error of the exponential mechanism, both in expectation and in probability:

Permute-and-Flip Mechanism

In this section, we propose a new mechanism, $\mathcal{M}_{PF}$, which we call the “permute-and-flip” mechanism. Just like the exponential mechanism, it is simple, easy to implement, and runs in linear time. It is stated formally in Algorithm 1. The mechanism works by iterating through the set of candidates $\mathcal{R}$ in a random order. For each item, it flips a biased coin, and returns that item if the coin comes up heads. The probability of heads is an exponential function of the quality score, which encourages the mechanism to return results with higher quality scores. The mechanism is guaranteed to terminate with a result because if $q_{r}=q_{*}$, then the probability of heads is $1$.

The Permute-and-Flip mechanism $\mathcal{M}_{PF}$ is regular and $\epsilon$-differentially private.

Proofs of all results appear in the supplement; in addition, the main text will contain some proof sketches. The proof of this theorem uses Proposition 2 (below) and a direct analysis of the probability mass function of $\mathcal{M}_{PF}$. Note that the condition in Proposition 2 can be immediately verified to hold (with equality) when $q_{r}\leq q_{*}-2\Delta$ by observing that $p_{r}$ in Algorithm 1 changes by exactly $\exp(\epsilon)$ when $q_{r}$ increases by $2\Delta$, and by a short argument conditioning on the random permutation. The proof using the pmf also handles the case when increasing $q_{r}$ by $2\Delta$ causes item $r$ to have maximum score.

We now describe the principles underlying the permute-and-flip mechanism and intuition behind its derivation. To define a mechanism, we must specify the value of $\Pr[\mathcal{M}(\vec{q})=r]$ for every $(\vec{q},r)$ pair. Intuitively, we would like to place as much probability mass as possible on the items with the highest score, and as little mass as possible on other items, subject to the constraints of differential privacy. For regular mechanisms, these constraints simplify greatly:

for all $(\vec{q},r)$, where $\vec{e}_{r}$ is the unit vector with a one at position $r$.

The proof (in the supplement) argues that it is only necessary to compare $\vec{q}$ to the quality-score vector with $q^{\prime}_{r}=q_{r}+\Delta$ and $q^{\prime}_{s}=q_{s}-\Delta$ for all $s\neq r$, which, by monotonicity, is the worst-case neighbor of $\vec{q}$. By shift-invariance, the mechanism is identical when $q^{\prime}_{r}=q_{r}+2\Delta$ and $q^{\prime}_{s}=q_{s}$, or $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}=\vec{q}+2\Delta\vec{e}_{r}$, which leads to the constraint in the theorem.

This theorem allows allows us to reason about only one constraint for every $(\vec{q},r)$ pair, instead of infinitely many. Ideally we would like to distribute probability to items as unevenly as possible, which would make these constraints tight (satisfied with equality). However, we can see by examining the overall numbers of constraints and variables that we cannot make all of them tight. For each score vector $\vec{q}$, there are: (1) $n=|\mathcal{R}|$ free variables (the probabilities of the mechanism run on $\vec{q}$), (2) $n$ inequality constraints (Proposition 2), and (3) one additional constraint that the probabilities sum to one. This is a total of $n$ inequality constraints and one equality constraint per $n$ variables. On average, we expect at most $n-1$ of the inequality constraints to be tight, leading to $n$ linear constraints that are satisfied with equality for each group of $n$ variables.

The following recurrence for $\Pr[\mathcal{M}(\vec{q})=r]$ defines a mechanism by selecting certain constraints to be satisfied with equality:

The privacy constraint is tight whenever $q_{r}\leq q_{*}-2\Delta$ (Case 1). When $q_{r}$ is one of the maximum scores (Case 2, $q_{r}=q_{*}$), the sum-to-one constraint is used instead, in conjunction with symmetry; here, $n_{*}$ is the number of quality scores equal to $q_{*}$.

The only difference is Case 1, which is obtained by unrolling Case 1 of the original recurrence $(q_{*}-q_{r})/2\Delta$ times so that the $r$th score becomes exactly $q_{*}$. The advantage is that the new expression is well defined for vectors that are not on the $2\Delta$-lattice.

Equation 6 defines a mechanism. In principle, it also gives a way to compute the probabilities of the mechanism for any fixed $\vec{q}$. The most direct approach to calculate these probabilities uses dynamic programming and takes exponential time. A smarter algorithm based on an analytic expression for the solution to the recurrence runs in $O(n^{2})$ time (Appendix E), but is still unacceptably slow compared to the linear time exponential mechanism. Remarkably, it is not necessary to explicitly compute the probabilities of this mechanism, as the permute-and-flip mechanism solves this recurrence relation. As a result, we can simply run the simple linear-time Algorithm 1 and avoid computing the mechanism probabilities directly.

$\mathcal{M}_{PF}$ solves the recurrence relation in Equation 6.

Case 2 is satisfied because $\mathcal{M}_{PF}$ is symmetric and a valid probability distribution. For Case 1, let $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}=\vec{q}+(q_{*}-q_{r})\vec{e}_{r}$ and consider applying $\mathcal{M}_{PF}$ to both $\vec{q}$ and $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}$. In each case, the coin-flip probabilities are the same for all items except $r$, and the probability of selecting any given permutation is the same. The ratio $\Pr[\mathcal{M}_{PF}(\vec{q})=r]/\Pr[\mathcal{M}_{PF}(\vec{q}\mkern 2.0mu\vphantom{q}^{\prime})=r]$ can be shown to be exactly $p_{r}/p^{\prime}_{r}$, where p_{r}=\exp{\big{(}\frac{\epsilon}{2\Delta}(q_{r}-q_{*})\big{)}} is the coin-flip probability with $\vec{q}$ and $p^{\prime}_{r}=1$ is the coin-flip probability with $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}$. The ratio is exactly \exp{\big{(}\frac{\epsilon}{2\Delta}(q_{r}-q_{*})\big{)}}, as required by Case 1. ∎

Comparison with Exponential Mechanism

In this section, we compare the permute-and-flip and exponential mechanisms, both algorithmically and in terms of the error each incurs. One (unconventional) way to sample from the exponential mechanism is stated in Algorithm 2. This is a rejection sampling algorithm: an item is repeatedly sampled uniformly at random from the set $\mathcal{R}$ with replacement and returned with probability p_{r}=\exp{\big{(}\frac{\epsilon}{2\Delta}(q_{r}-q_{*})\big{)}}. For the permute-and-flip mechanism, an item is repeatedly sampled uniformly at random from the set $\mathcal{R}$ without replacement and returned with the same probability. Sampling without replacement is mathematically equivalent to iterating through a random permutation, and hence Algorithm 3 is equivalent to Algorithm 1. These implementations are not recommended in practice, but are useful to illustrate connections between the two mechanisms.

Intuitively, sampling without replacement is better, because items that are not selected, which are likely to have low scores, are eliminated from future consideration. In fact, in Theorem 2 we prove that the permute-and-flip mechanism is never worse than the exponential mechanism in a very strong sense. Specifically, we show that the expected error of permute-and-flip is never larger than the exponential mechanism, and the probability of the error random variable exceeding $t$ is never larger for permute-and-flip (for any $t$). This is a form of stochastic dominance , and suggests it is always preferable to use permute-and-flip over the exponential mechanism, no matter what the risk profile is.

As a direct consequence of Theorem 2, the permute-and-flip mechanism inherits the theoretical guarantees of the exponential mechanism (Proposition 1).

To further compare the two mechanisms, it is instructive to compare their expected errors for a particular class of score vectors. In particular, we examine score vectors that are worst cases for both mechanisms. This analysis will reveal that permute-and-flip can be up to $2\times$ better than the exponential mechanism, and that the upper bounds on expected error in Proposition 1 and Corollary 1 are within a factor of four of being tight.

The worst-case expected errors are found by maximizing Equations 7 and 8 over $p\in(0,1]$.

Figure 1(a) shows the expected error of both mechanisms using Equations 7 and 8 for $n=3$ and $p\in(0,1]$. The error of $\mathcal{M}_{PF}$ is always lower than that of $\mathcal{M}_{EM}$, as expected by Theorem 2. At the two extremes ($p=0$ and $p=1$), the expected error of both mechanisms is exactly , because: (1) when $p=1$, all scores are equal to the maximum, and (2) when $p\rightarrow 0$, the total probability assigned to items with non-maximum scores vanishes. The maximum error for each mechanism occurs somewhere in the middle, typically near $p=\frac{1}{n}$. In fact, by substituting $p=\frac{1}{n}$ into Equation 8, we obtain:

The ratio is always between one and two, and approaches two in the limit at $p\rightarrow 0$ (larger $\epsilon$).

The required $p$ to achieve a fixed ratio decreases with $n$, and the ratio converges to one for all $p>0$ as $n$ goes to infinity. This behavior is well-explained by the algorithmic comparison earlier in this section: as $n$ goes to infinity, the probability of sampling the same low-scoring item multiple times becomes negligible, so sampling without replacement ($\mathcal{M}_{PF}$) becomes essentially identical to sampling with replacement ($\mathcal{M}_{EM}$).

These results are for a particular class of (worst-case) quality-score vectors and not necessarily indicative of what will happen in applications. In our experiments with real quality-score vectors (Section 6) we observe ratios close to two for the values of $\epsilon$ that provide reasonable utility. We have never observed a ratio greater than two for any $\vec{q}$, and it is an open question whether this is possible. In practice, we can and do realize significant improvements even for large $n$.

Figure 1(c) compares the worst-case expected errors of $\mathcal{M}_{EM}$ and $\mathcal{M}_{PF}$ as a function of $n$ by numerically maximizing over $p$ in Equations 7 and 8 for different values of $n$ and $\epsilon=\Delta=1$. For reference, we also plot the analytic upper and lower bounds from Proposition 1, Corollary 1, and Proposition 5. The ratio of worst-case expected error between $\mathcal{M}_{EM}$ and $\mathcal{M}_{PF}$ is largest at $n=2$, and it decays towards $1$ as $n$ increases. Again, this is explained by the algorithmic similarities between the two mechanisms as $n\to\infty$.

Optimality of Permute-and-Flip

Pareto optimality is a desirable property that differentiates permute-and-flip from the exponential mechanism. However, there are many Pareto optimal mechanisms, so we would like additional assurance that permute-and-flip is in some sense the “right” one. To achieve this, we show that it is optimal in some reasonable “overall” sense. In particular, it minimizes the expected error averaged over a representative set of quality score vectors, as long as $\epsilon$ is sufficiently large.

For all regular mechanisms $\mathcal{M}$ and all $\epsilon\geq\log{(\frac{1}{2}(3+\sqrt{5}))}$,

This theorem is proved by analyzing a linear program (LP) that describes the behavior of an optimal regular mechanism on the $2\Delta$-lattice, using the linear constraints described in Section 3.1 to enforce privacy and regularity, and the linear objective from the theorem. The result holds for the bounded lattice with $q_{*}=0$ and all scores at most $k$ lattice points away from zero. Boundedness is required to have a finite number of variables and constraints. The restriction that $q_{*}=0$ is without loss of generality: by shift-invariance, a regular mechanism is completely defined by its behavior on vectors with $q_{*}=0$.

As shown in Figure 2(a) and Figure 2(b), the optimality ratio for permute-and-flip is equal to one above the threshold, as expected. Furthermore, it barely exceeds one even when $\epsilon$ is below the threshold: the largest measured value is about $1.01$. The ratio grows slowly with $k$ (Figure 2(b)) and shows no strong dependence on $n$ (Figure 2(a)). For the exponential mechanism (Figure 2(c)), the optimality ratio is much more significantly larger than one, and generally increases with $\epsilon$, approaching two for larger $k$ and $\epsilon$. Interestingly, the optimality ratio approaches one for both mechanisms as $\epsilon\rightarrow 0$.

Experiments

We now perform an empirical analysis of the permute-and-flip mechanism. Our aim is to quantify the utility improvement from permute-and-flip relative to the exponential mechanism for different values of $\epsilon$ on real-world problem instances. We use five representative data sets from the DPBench study: HEPTH, ADULTFRANK, MEDCOST, SEARCHLOGS, and PATENT and consider the tasks of mode and median selection. In each case, the candidates are the 1024 bins of a discretized domain. For each task, we construct the quality score vector and then analytically compute the expected error for a range of different $\epsilon$ for both the permute-and-flip and exponential mechanisms using their probability mass functions. Below we summarize our experimental findings; additional experimental results can be found in Appendix G.

For mode selection, the quality function is the number of items in the bin, which has sensitivity one. Figure 3(a) shows expected error as a function of $\epsilon$ for the HEPTH data set. Note that expected error is plotted on a log scale, while $\epsilon$ is plotted on a linear scale, and we truncate the plot when the expected error falls below one. The ratio of the expected error of the exponential mechanism to that of permute-and-flip ranges from one (for smaller $\epsilon$) to two (for larger $\epsilon$). For the range of $\epsilon$ that provide reasonable utility, the improvement is closer to two. For example, at $\epsilon=0.04$, the ratio is $1.84$. The expected error of $\mathcal{M}_{PF}$ at this value of $\epsilon$ is about $5.4$, and $\mathcal{M}_{EM}$ would need about $1.27$ times larger privacy budget to achieve the same utility.

Median.

For median selection, the quality function is the (negated) number of individuals that must be added or removed to make a given bin become the median, which is also a sensitivity one function . Figure 3(b) again shows the expected error as a function of $\epsilon$ for the HEPTH data set. Again, the ratio of expected errors ranges from one (for smaller $\epsilon$) to two (for larger $\epsilon$). For the range of $\epsilon$ that provide reasonable utility, the improvement is closer to two. For example, at $\epsilon=0.01$, the ratio is $1.93$. The expected error of $\mathcal{M}_{PF}$ at this value of $\epsilon$ is about $13.7$, and $\mathcal{M}_{EM}$ would need about $1.19$ times larger privacy budget to achieve the same utility.

In Figures 3(a) and 3(b), the expected errors of $\mathcal{M}_{EM}$ and $\mathcal{M}_{PF}$ become approximately parallel lines as $\epsilon$ increases. Because the plots use linear scale for $\epsilon$ and logarithmic scale for expected error this means that the error of both mechanisms behaves approximately as $c\exp(-\epsilon)$ for some $c$. Additionally, $\mathcal{M}_{PF}$ offers an asymptotically constant multiplicative improvement in expected error (a factor of two) and an additive savings of $\epsilon$. For the range of $\epsilon$ that demonstrate the most reasonable privacy-utility tradeoffs, this additive improvement is a meaningful fraction of the privacy budget.

In Figure 3(c) we plot the expected error of $\mathcal{M}_{EM}$ and $\mathcal{M}_{PF}$ on all five data sets. For each dataset, we use the value of $\epsilon$ where $\mathcal{M}_{EM}$ gives a expected error of $50$. This allows us to plot all datasets on the same scale for some $\epsilon$ that gives a reasonable tradeoff between privacy and utility. The improvements are significant, and close to a factor of two for all data sets.

Related Work

The exponential mechanism and the problem of differentially private selection have been studied extensively in prior work .

The most common alternative to the exponential mechanism for the private selection problem is report noisy max , which adds noise to each quality score and outputs the item with the largest noisy score. While we did not compare directly to this mechanism, our initial findings (Appendix F) indicate that it is competitive with the exponential mechanism, but neither mechanism Pareto dominates the other — report noisy max is better for some quality score vectors, while the exponential mechanism is better for others. Several other mechanisms have been proposed for the private selection problem that may work better under different assumptions and special cases .

A generalization of the exponential mechanism was proposed in that can effectively handle quality score functions with varying sensitivity. This technique works by defining a new quality score function that balances score and sensitivity and then running the exponential mechanism, and is therefore also compatible with the permute-and-flip-mechanism. The exponential mechanism was also studied in , where the focus was to improve the privacy analysis for a composition of multiple sequential executions of the exponential mechanism. They also show that the analysis can be improved in some cases by using a measure of the range of the score function instead of the sensitivity (though in commonly-used score functions the range and sensitivity usually coincide). This improvement is orthogonal to our approach, and it is straightforward to extend the analysis of the permute-and-flip mechanism in a similar way.

A new mechanism for private selection from private candidates was studied in . Instead of assuming the quality functions have bounded sensitivity, it is assumed that the quality functions are themselves differentially private mechanisms. This relaxed assumption is appealing for many problems where the traditional exponential mechanism does not apply, like hyperparameter optimization.

The optimality of the exponential mechanism was studied in , where the authors considered linear programs for computing mechanisms that are optimal on average (similar to our Theorem 3). They restricted attention to scenarios where the input/output universe of the mechanism is a graph, and each node is associated with a database. They argued that the optimal mechanism should satisfy privacy constraints with equality for connected nodes in this graph, and showed that the exponential mechanism was optimal up to a constant factor of two in this setting.

Other works have carefully analyzed privacy constraints to construct optimal mechanisms for other tasks and privacy definitions, including predicate counting queries , information theoretic quantities , and generic low-sensitivity functions .

Conclusions and Open Questions

In this work we proposed permute-and-flip, a new mechanism for differentially private selection that can be seen as a replacement for the exponential mechanism. For every set of scores, the expected error of the permute-and-flip mechanism is not higher than the expected error of exponential mechanism, and can be lower by a factor of two; we observe factors close to two in real-world settings. Furthermore, we prove that the permute-and-flip mechanism is optimal in a fairly strong sense overall. Improving the exponential mechanism by a factor between one and two has the potential for wide-reaching impact, since it is one of the most important primitives in differential privacy.

We focused primarily on the utility improvements offered by permute-and-flip in this work. In some cases, permute-and-flip may also offer runtime improvement. Specifically, if $q_{*}$ is known a-priori, then permute-and-flip can potentially terminate early without evaluating all $n$ quality scores. Identifying situations where this potential benefit can be realized and provide meaningful improvement is an interesting open question.

We demonstrated meaninful improvement over the exponential mechanism for simple tasks like median and mode estimation. It would be interesting to apply permute-and-flip to more advanced mechanisms that use the exponential mechanism, and quantify the improvement there.

Our overall optimality result restricts to score vectors on the bounded $2\Delta$-lattice. It would be interesting to understand more fully the nature of optimal mechanisms on more general domains or with other ways of averaging or aggregating over score vectors.

Broader Impact

Our work fits in the established research area of differential privacy, which enables the positive societal benefits of gleaning insight and utility from data sets about people while offering formal guarantees of privacy to individuals who contribute data. While these benefits are largely positive, unintended harms could arise due to misapplication of differential privacy or misconceptions about its guarantees. Additionally, difficult social choices are faced when deciding how to balance privacy and utility. Our work addresses a foundational differential privacy task and enables better utility-privacy tradeoffs within this broader context.

Acknowledgements

We would like to thank Gerome Miklau and the anonymous reviewers for their helpful comments to improve the paper. This work was supported by the National Science Foundation under grants CNS-1409143, IIS-1749854, IIS-1617533, and by DARPA and SPAWAR under contract N66001-15-C-4067.

References

We begin by deriving two different expressions for the probability mass function of $\mathcal{M}_{PF}$, which we will reference in other proofs throughout the supplement.

The probability mass function (pmf) of $\mathcal{M}_{PF}$ can be expressed as:

where $\pi$ is a permutation and p_{r}=\exp{\big{(}\frac{\epsilon}{2\Delta}(q_{r}-q_{*})\big{)}}.

Let $X_{s}$ be the event that the $s$th coin is heads, and let $\pi$ be a random permutation. The events $X_{s}$ are independent. The $r$th item is selected if $X_{r}$ is true, and $X_{s}$ is false for all $s$ that come before $r$ in the permutation $\pi$, that is:

An equivalent expression for the probability mass function of $\mathcal{M}_{PF}$ is:

Let $X_{s}$ again denote the event that the $s$th coin is heads. Let $\pi$ be a random permutation and let $Y_{s}$ be the event $X_{s}\cap(\pi(s)<\pi(r))$, or “the $s$th coin is heads and appears before the $r$th coin in the random permuation”. Note that the events $X_{r}$ and $Y_{s}$ are independent for $r\neq s$.

By independence and the inclusion-exclusion principle:

We now split the event $\bigcap_{s\in S}Y_{S}$, or “all coins in $S$ appear before $r$ and are heads”, into the conjunction of the events “all coins in $S$ appear before $r$” and “all coins in $S$ are heads”, and continue as:

Appendix B Proofs for Section 3: Permute-and-Flip Mechanism

In this section, we first prove Proposition 2, which gives simplifed sufficient conditions for privacy for a regular mechanism. We then use Proposition 2 to prove Theorem 1, which establishes the privacy of permute-and-flip. Finally, we prove Proposition 3, which shows that permute-and-flip satisfies the recurrence used in the derivation.

Let $\mathcal{M}$ be a regular mechanism satisfying:

Using this assumption together with the regularity of $\mathcal{M}$, we obtain:

Thus, we conclude that $\mathcal{M}$ is differentially-private, as desired. This completes the proof. ∎

Before proving Theorem 1, we will argue regularity.

We will establish the three conditions: symmetry, shift-invariance, and monotonicity.

Symmetry: Consider $p_{r}$ as defined in the definition of $\mathcal{M}_{PF}$, and let $\vec{p}\mkern 2.0mu\vphantom{p}^{\prime}=\Pi\vec{p}$ denote the same vector on the permuted quality scores. Now note that every permutation is equally likely for both $\vec{p}$ and $\vec{p}\mkern 2.0mu\vphantom{p}^{\prime}$, and that the only difference is that $p_{r}=p^{\prime}_{\pi(r)}$. Hence $\Pr[\mathcal{M}(\vec{q})=r]=\Pr[\mathcal{M}(\Pi\vec{q})=\pi(r)]$, which implies $\mathcal{M}$ is symmetric as desired.

Shift-invariance: $\mathcal{M}_{PF}$ is shift-invariant because on only depends on $\vec{q}$ through $q_{r}-q_{*}$. Adding a constant to $\vec{q}$ does not change $q_{r}-q_{*}$.

Monotonicity: Monotonicity follows from the pmf of the mechanism:

Assume without loss of generality that $q_{*}=0$ and note that $p_{r}=\exp{(\frac{\epsilon}{2\Delta}q_{r})}$. Clearly, the expression above is monotonically increasing in $p_{r}$ (and hence $q_{r}$) and monotonically decreasing in $p_{s}$ (and hence $q_{s}$). Hence $\mathcal{M}_{PF}$ satisfies the monotonicity property.

Because $\mathcal{M}_{PF}$ is symmetric, shift-invariant, and monotonic, it is regular. ∎

Lemma 3 established regularity. It remains to argue that $\mathcal{M}_{PF}$ is differentially-private. Let $\vec{q}$ and $r$ be arbitrary. By Proposition 2, it suffices to show that

Assume without loss of generality that $\max_{s\neq r}q_{s}=0$, so that $q_{r}$ is a maximum score if and only if $q_{r}\geq 0$. Let $f_{r}(\vec{q})=\log\Pr[\mathcal{M}_{PF}(\vec{q})=r]$. Then is enough to show that $\frac{\partial}{\partial q_{r}}f_{r}(\vec{q})\leq\frac{\epsilon}{2\Delta}$ for all $\vec{q}$, since

The final equality is justified because, by the definition of the pmf for $\mathcal{M}_{PF}$, the function $f_{r}(\vec{q})$ is continuous. Furthermore, there is at most one point of non-differentiability of the partial derivative (at $t=0$, when the $r$th score becomes equal to the maximum), so, if needed, the integral can be split into two parts about $t=0$. This integral is bounded by $\epsilon$ as long the partial derivative $\frac{\partial f_{r}}{\partial q_{r}}$ is bounded by $\frac{\epsilon}{2\Delta}$.

Using the expression for the probability mass function of $\mathcal{M}_{PF}$ from Lemma 2, we have:

We will show using this formula that $\frac{\partial f_{r}}{\partial q_{r}}$ is always bounded by $\frac{\epsilon}{2\Delta}$. We examine the cases when $q_{r}<0$ and $q_{r}\geq 0$ separately.

Case 1: $q_{r}<0$. In this case, observe that p_{s}=\exp\big{(}\frac{\epsilon}{2\Delta}q_{s}\big{)} does not depend on $q_{r}$ for $s\neq r$. Therefore, differentiating the formula for $f_{r}(\vec{q})$ gives

Case 2: $q_{r}\geq 0$. In this case, because $q_{r}$ is the maximum score, we have p_{s}=\exp\big{(}\frac{\epsilon}{2\Delta}(q_{s}-q_{r})\big{)} for all $r$. We therefore proceed by differentiating $f_{r}(\vec{q})$ using this expression for $p_{s}$:

Equivalently, by multiplying both sides by $\Pr[\mathcal{M}_{PF}(\vec{q})=r]$ and rearranging, we would like to show:

Substituting the expression for $\Pr[\mathcal{M}_{PF}(\vec{q})=r]$ and simplifying, the expression on the left-hand side above becomes:

The final equality can be seen directly by multiplying out $\prod_{s\in\mathcal{R}\setminus\{r\}}(1-p_{s})$ or (equivalently) via the inclusion-exclusion formula. The final expression is the probability that the coins for all $s\in\mathcal{R}\setminus\{r\}$ are “tails”, and is clearly non-negative, as desired.

When the quality function is monotonic in the sense that adding an individual to the dataset can only increase $q_{r}$ (and not decrease it), $\mathcal{M}_{PF}$ offers $\frac{\epsilon}{2}$-differential privacy. The proof is largely the same, but the worst-case neighbor from Proposition 2 now occurs when $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}=\vec{q}+\Delta\vec{e}_{r}$.

Because $\mathcal{M}_{PF}(\vec{q})$ is a valid probability distribution for all $\vec{q}$, and it is symmetric, it must satisfy case $2$ of the recurrence relation.

Note that the pmf of $\mathcal{M}_{PF}$ is:

where $p_{r}=\exp{(\frac{\epsilon}{2\Delta}(q_{r}-q_{*}))}$ and $p^{\prime}_{r}=\exp{(\frac{\epsilon}{2\Delta}(q_{*}-q_{*}))}=1$. By comparing terms, it is clear that

Hence, $\mathcal{M}_{PF}$ solves case $1$ of the recurrence relation. This completes the proof.

Appendix C Proofs for Section 4: Comparison with Exponential Mechanism

In this section, we first prove Theorem 2, which shows that the permute-and-flip error is no worse than the exponential mechanism for any score vector. We then prove Proposition 4 and Proposition 5, which analyze the worst-case expected errors of the two mechanisms and give tight lower bounds on expected error as the number of items $n$ increases.

We first prove two lemmas. The first lemma establishes a monotonicity property for the factor of the pmf from Lemma 1 excluding $p_{r}$, i.e., the function $g_{r}(\vec{q})$ such that $\Pr[\mathcal{M}_{PF}(\vec{q})=r]=p_{r}\cdot g_{r}(\vec{q})$. The second lemma gives a useful fact about partial sums of a non-decreasing sequence.

If $q_{r}\leq q_{s}$, then $g_{r}(\vec{q})\leq g_{s}(\vec{q})$, where

Recall that p_{r}=\exp{\big{(}\frac{\epsilon}{2\Delta}(q_{r}-q_{*})\big{)}}. Note that if $q_{r}\leq q_{s}$ then $1-p_{r}\geq 1-p_{s}$. We will show that $g_{s}(\vec{q})-g_{r}(\vec{q})\geq 0$.

Above, (a) breaks the sum up into permutations where $r$ precedes $s$ and vice versa. Step (b) cancels common terms (those that do not contain $1-p_{r}$ or $1-p_{s}$). Step (c) makes the dependence on $1-p_{r}$ and $1-p_{s}$ explicit. Step (d) rearranges terms and uses a variable replacement on the second sum (replacing $r$ with $s$). Step (e) uses the fact that both terms are non-negative. ∎

Then for all $s=\{1,\dots,n\}$, the following holds

Let $m$ be any index satisfying $f_{m}\leq 0$ and $f_{m+1}\geq 0$. If $t\leq m$, the claim is clearly true, as it is a sum of non-positive terms. If $t>m$, we have $\sum_{r=1}^{s}f_{r}\leq\sum_{r=1}^{n}f_{r}=0$. In either case the partial sum is non-positive, and the claimed bound holds. ∎

We will prove the probability statement first, after which the expected error result will follow easily. Assume without loss of generality (by symmetry) that $q_{1}\leq q_{2}\leq\dots\leq q_{n}$. Let $f_{r}(\vec{q})=\Pr[\mathcal{M}_{PF}(\vec{q})=r]-\Pr[\mathcal{M}_{EM}(\vec{q})=r]$ and let $s$ denote the largest index satisfying $q_{s}\leq q_{*}-t$. Then $\Pr[\mathcal{E}(\mathcal{M}_{PF},\vec{q})\geq t]-\Pr[\mathcal{E}(\mathcal{M}_{EM},\vec{q})\geq t]=\sum_{r=1}^{s}f_{r}(\vec{q})$ and our goal is to show:

for all $s\in\{1,\dots,n\}$. We first argue that $f_{r}$ monotonically increases with $q_{r}$, i.e., $f_{1}\leq f_{2}\leq\dots\leq f_{n}$.

Note that $f_{r}(\vec{q})$ can be expressed as $p_{r}[g_{r}(\vec{q})-h_{r}(\vec{q})]$, where

Further, notice that the sequence $h_{r}$ (as $r$ ranges from 1 to $n$) is constant-valued, while, from Lemma 4, we know that $g_{r}$ is also non-decreasing. Thus the sequence $g_{r}-h_{r}$ is also non-decreasing. This, together with the fact that $p_{r}$ is non-negative and also non-decreasing, we know that $f_{r}$ is non-decreasing. This fact together with Lemma 5 shows $\sum_{r=1}^{s}f_{r}(\vec{q})\leq 0$, as desired.

The ordering of expected errors now follows directly. Specifically, the expected error can be expressed in terms of the (complementary) cumulative distribution function as:

We have already shown that $\Pr[\mathcal{E}(\mathcal{M}_{PF},\vec{q})\geq t]\leq\Pr[\mathcal{E}(\mathcal{M}_{EM},\vec{q})\geq t]$. Thus:

C.2 Proofs for Worst-Case Error Analysis

Assume without loss of generality that $q_{*}=0$ and note that $p_{r}=\exp{(\frac{\epsilon}{2\Delta}q_{r})}$.

The (negative) expected error of $\mathcal{M}_{EM}$ can be expressed as:

Our goal is to show this is minimized when $p_{1}=\cdots=p_{n-1}$. We procede by way of contradiction. Assume WLOG $p_{1}<p_{2}$. We will argue that we can replace $p_{1}$ and $p_{2}$ with new values that decrease the objective. First write the negative expected error as a function of $p_{1}$ and $p_{2}$, treating everything else as a constant.

We will show that $f(\frac{p_{1}+p_{2}}{2},\frac{p_{1}+p_{2}}{2})<f(p_{1},p_{2})$.

Above, the inequality follows from the strict convexity of $p\log{(p)}$. Thus, $f(p_{1},p_{2})$ is not a minimum, which is a contradiction.

Plugging in $p_{n}=1$ and $p_{r}=p$ for $r<n$, we obtain:

The (negative) expected error of $\mathcal{M}_{PF}$ can be expressed as:

where $a,b,c,d,e\geq 0$. We proceed in cases, by showing that we can always find new values for $p_{1}$ and $p_{2}$ that reduces $f$

Case 1: $p_{1}\log{(p_{1})}<p_{2}\log{(p_{2})}$

The second term in the sum is (strictly) less by the assumption of case 1. Every other term is strictly less because $p_{1}<p_{2}$, which implies $(1-p_{1})>(1-p_{2})$ or equivalently $-(1-p_{1})<-(1-p_{2})$.

Case 2: $p_{1}\log{(p_{1})}\geq p_{2}\log{(p_{2})}$

Set $p_{1}=p_{2}\leftarrow\frac{p_{1}+p_{2}}{2}$.

Consider breaking up the sum into two pieces; i.e., $f(p_{1},p_{2})=f_{A}(p_{1},p_{2})+f_{B}(p_{1},p_{2})$ where:

Above, the first step follows from linearity, and the second step follows from the convexity of $p\log{(p)}$ and non-negativeness of the linear term. The fourth step uses the assumption that $p_{1}\log{(p_{1})}\geq p_{2}\log{(\vec{p}_{2})}$ (Case 2), and the fact that $a(1-p_{1})+b>a(1-p_{2})+b$ and $\log{(p_{2})}<0$.

Above, the first step follows from linearity, and the second step follows from the fact that the area of a square is always larger than the area of a rectangle with the same perimeter.

We have shown that $f_{A}$ and $f_{B}$ are both reduced, so $f$ as a whole is also reduced.

To derive the expected error for a quality score vector of this form, we use a simple probabilistic argument. There are $n-1$ items with probability $p$ coins, and one item with a probability $1$ coin. The probability of selecting an item corresponding to a probability $p$ coin is $\sum_{i=1}^{n}\frac{1}{n}(1-(1-p)^{i-1})$ where the index of the sum represents the location of the probability $1$ item in the permutation and $1-(1-p)^{i-1}$ is the probability that at least one of the probability $p$ coins before position $i$ comes up heads. Using the formula for a geometic series, this simplifies to $1-\frac{1-(1-p)^{n}}{np}$. Thus, recalling that $c=\frac{2\Delta}{\epsilon}\log{(p)}$, the expected error can be expressed as:

Let $c=-\frac{2\Delta}{\epsilon}\log{(n)}$ and note that $p=\frac{1}{n}$ in Equation 8. Plugging in $p$ to Equation 8 and simplifying, we obtain:

Appendix D Proofs for Section 5: Optimailty of Permute-and-Flip

In this section we prove Proposition 6, about Pareto optimality of permute-and-flip, and Theorem 3, about “overall” optimality.

Note that the expected error of the mechanism can be expressed as:

Let $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}=\vec{q}+(q_{*}-q_{r})\vec{e}_{r}$. By the differential privacy and regularity of $\mathcal{M}$ and the recursive construction of $\mathcal{M}_{PF}$, we know:

Combining the above with the assumption of the Lemma, we obtain:

Note that $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}_{r}=\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}_{*}$. We proceed by way of induction:

Induction Step: Assume Lemma 6 holds when $n^{\prime}_{*}=k+1$. We will show that Lemma 6 holds for $n^{\prime}_{*}=k$.

Case 1: $\Pr[\mathcal{M}(\vec{q}\mkern 2.0mu\vphantom{q}^{\prime})=s]\geq\Pr[\mathcal{M}_{PF}(\vec{q}\mkern 2.0mu\vphantom{q}^{\prime})=s]$ for all $s$ such that $q^{\prime}_{s}<q^{\prime}_{*}$.

Case 2: $\Pr[\mathcal{M}(\vec{q}\mkern 2.0mu\vphantom{q}^{\prime})=s]<\Pr[\mathcal{M}_{PF}(\vec{q}\mkern 2.0mu\vphantom{q}^{\prime})=s]$ for some $s$ such that $q^{\prime}_{s}<q_{*}$.

Applying the induction hypothesis Lemma 6 using $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}$ (now with $n^{\prime}_{*}=k+1$), we see that the claim must be true for $n^{\prime}_{*}=k$, as desired.

For the above optimality criteria, the best mechanism can be obtained by solving a simple linear program. The variables of the linear program correspond to the probabilities the mechanism assigns to different $(\vec{q},r)$ pairs, and the constraints are those required for differential privacy and regularity (which are all linear).

Denote the optimization variables as $x_{r}(\vec{q}):=\Pr[\mathcal{M}(\vec{q})=r]$ for all $\vec{q}\in Q$ and all $r\in\mathcal{R}$. Then the linear program for the optimal regular mechanism can be expressed as:

The first constraint enforces differential privacy for a regular mechanism as in Proposition 2, where $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}$ is the worst-case neighbor of $\vec{q}$. We assumed the maximum entry of every score vector is zero, which is without loss of generality due to shift invariance. To ensure that $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}$ has maximum entry zero, we use separate expressions for $\vec{q}\mkern 2.0mu\vphantom{q}^{\prime}$ depending on whether or not $q_{r}=0$:

The second constraint ensures the mechanism is symmetric, and the final two constraints ensure the mechanism corresponds to a valid probability distribution.

To measure how close to optimal permute-and-flip is for $\epsilon$ below the threshold, we can solve this linear program numerically, and compare the solution to permute-and-flip. Observe that the linear program has a large number of redundant variables from the symmetry constraint (e.g., $x_{1}(-2,-8,0)=x_{3}(0,-8,-2)$). These variables can be grouped into equivalence classes, and the redundant ones can be eliminated, keeping only a single one from each equivalence class. This drastically reduces the number of variables and also allows us to eliminate the symmetry constraints. Using this trick, the resulting linear program is significantly smaller, but the size still grows quickly with $n$ and $k$, and is only feasible to solve for relatively small $n$ and $k$.

Our goal is to show that $\mathcal{M}_{PF}$ solves the linear program. To do so, we will consider the following relaxation of the linear program:

There is exactly one constraint per optimization variable (excluding non-negativity constraints).

The first set of constraints corresponds to a subset of the privacy constraints from the original, corresponding only to $(\vec{q},r)$ pairs with $q_{r}<0$. In addition, we performed substitutions of the form

where $\vec{q}-q_{r}\vec{e}_{r}$ is the quality score vector obtained by setting $q_{r}=0$.

The sum-to-one and symmetry constraints are merged into a single constraint when $q_{r}=0$, and other symmetry constraints are dropped.

These constraints correspond exactly to the ones in the recurrence defining $\mathcal{M}_{PF}$ in Section 3.1. This means that $\mathcal{M}_{PF}$ satisfies these constraints with equality, by construction. Furthermore, since $\mathcal{M}_{PF}$ is feasible in the full LP (because it is a private, regular mechanism), if $\mathcal{M}_{PF}$ is optimal for the relaxed LP it is also optimal for the full LP.

Constructing a dual optimal solution

We can show that $\mathcal{M}_{PF}$ is optimal by constructing a corresponding optimal solution to the dual linear program:

Because there is exactly one constraint for each optimization variable, we have used the same indexing scheme for the dual variables. Note that the non-negativity constraints apply only to $(\vec{q},r)$ pairs with $q_{r}<0$.

To prove optimality, the dual solution and $\mathcal{M}_{PF}$ should satisfy complementary slackness: for each positive primal variable, the corresponding dual constraint should be tight. However, all primal variables are positive. Therefore, all dual constraints must be tight. By treating dual constraints as equalities, we obtain a recurrence for $y$ similar to the one used to derive $\mathcal{M}_{PF}$:

Like the recurrence for $\mathcal{M}_{PF}$, this recurrence is well-founded and defines a unique dual solution $y$. The order of evaluation is reversed for the dual variables, and the base case occurs when $n_{*}=1$ (rather than $n_{*}=n$). We will now argue that, whenever \epsilon\geq\log{\big{(}\frac{1}{2}(3+\sqrt{5})\big{)}}, the resulting dual solution is feasible. This, together with complementary slackness, which is satisfied by construction, implies that $\mathcal{M}_{PF}$ and $y$ are optimal solutions to the primal and dual programs, respectively.

Let $y$ solve the recurrence above for \epsilon\geq\log{\big{(}\frac{1}{2}(3+\sqrt{5})\big{)}}. To show that $y$ is feasible, we will argue inductively that these finer-grained bounds hold:

Note that Equation 11 includes the dual feasibility constraints.

We prove Equations 10 and 11 by induction on the $n_{*}$, the number of zero (i.e., maximum) entries of $\vec{q}$. For the base case, when $n_{*}=1$, $y_{r}(q)=-q_{r}$, so Equations 10 and 11 hold.

Now let $\vec{q}$ be a score vector with $n_{*}>1$ entries equal to zero, and assume that Equations 10 and 11 hold for all score vectors with fewer than $n_{*}$ zeros. By Case 1 of the recurrence, for $r$ such that $q_{r}=0$, we have

In the second line, we used the fact that $y_{r}(\vec{q}-2\Delta t\vec{e}_{r})\leq-(\vec{q}-2\Delta t\vec{e}_{r})_{r}=2\Delta t$, which follows from Equation 11 by the induction hypothesis, since $\vec{q}-2\Delta t\vec{e}_{r}$ is a score vector with $n_{*}-1$ zeros. In the third line, we used the fact that $\sum_{t=1}^{\infty}t\exp(-t\epsilon)\leq 1$ whenever \epsilon\geq\log{\big{(}\frac{1}{2}(3+\sqrt{5})\big{)}}, which is stated and proved in Lemma 7 below.

since, again by Equation 11 and the induction hypothesis, each term of the sum is non-nonegative.

We have now established that Equation 10 holds for all score vectors with $n_{*}$ or fewer zeros, which we use to prove that Equation 11 holds under the same conditions. By Case 2 of the recurrence, when $q_{r}<0$ we have

In the second line, we used, from Equation 10 that $y_{s}(\vec{q})\geq-\frac{2\Delta}{n_{*}}$. Similarly, we have

This completes the inductive proof, and establishes that the dual solution $y$ is feasible. This in turn completes the proof that $\mathcal{M}_{PF}$ is optimal.

If \epsilon\geq\log{\big{(}\frac{1}{2}(3+\sqrt{5})\big{)}}, then $\sum_{k=1}^{\infty}k\exp{(-k\epsilon)}\leq 1$.

Making the substitution $\exp{(\epsilon)}=1+z$, we have:

The solution to the quadratic equation $1+z=z^{2}$ is the golden ratio, $\phi=\frac{1}{2}(1+\sqrt{5})$, so the inequality holds whenever $z\geq\phi$, or whenever \epsilon\geq\log{(1+\phi)}=\log{\big{(}\frac{1}{2}(3+\sqrt{5})\big{)}}. ∎

Appendix E Dynamic Programming Algorithm

In this section, we derive an efficient $O(n^{2})$ dynamic programming algorithm to calculate the probabilities. Recall the expression for the pmf from Lemma 2:

To evaluate the probabilities efficiently, we can break up the sum into groups where $|S|=k$. Then, using dynamic programming, we can calculate these sums efficiently and use them to compute the desired probabilities.

And note that $S(k,r)$ satisfies the recurrence:

$S(k,r-1)$ is the sum over subsets not including $r$, and $p_{r}S(k-1,r-1)$ is the sum over subsets including $r$. Using the above recursive formula together with the base cases $S(0,r)=1$ and $S(k,0)=0$, we can compute $S(k,r)$ for all $(k,r)$ in $O(n^{2})$ time.

$S(k,n)$ is then the sum over all subsets of size $k$. Let $T(k,r)$ denote the sum over all size $k$ subsets not including r:

and note that $T(k,r)$ satisfies the recurrence:

with $T(0,r)=1$. $T(k,r)$ can also be calculated in $O(n^{2})$ time. The final answer is then:

which can be computed in $O(n)$ time for each $r$. Thus, the overall time complexity of this dynamic programming procedure is $O(n^{2})$.

Appendix F Report Noisy Max

A popular alternative to the exponential mechanism for private selection is report noisy max, which works by adding Laplace noise with scale $\frac{2\Delta}{\epsilon}$ to the score for each candidate, then returns the candidate with the largest noisy score.

Reasoning about report noisy max analytically and exactly is challenging, and we are not aware of a simple closed form expression for its probability mass function. To compute the probability of returning a particular candidate, we must reason about the probability that one random variable (the noisy score for that candidate) is larger than $n-1$ other random variables (the scores for other candidates), which in general requires evaluating a complicated integral. Specifically, let $f(x)$ denote the probability density function of $\text{Lap}(\frac{2\Delta}{\epsilon})$ and let $F(x)$ denote its cumulative density function.

If we consider quality score vectors of the form $\vec{q}=(c,\dots,c,0)$, the expression simplies to:

Due to symmetry, the expected error can be expressed as:

While it is not obvious how to simplify this expression further, we can readily evaluate the integral numerically to obtain the expected error. Doing so allows us to compare report noisy max with the exponential mechanism and permute-and-flip. Figure 4 plots the expected error of report noisy max alongside the exponential mechanism and permute-and-flip for quality score vectors of the form $\vec{q}=(c,c,0)$. It shows that report noisy max is better than the exponential mechanism when $c$ is closer to but is worse when $c$ is much smaller than . We made similar observations for different values of $n$ as well. Thus, we conclude that neither one Pareto dominates the other. On the other hand, permute-and-flip is always better than both mechanisms for all $c$. Note that in contrast to Figure 1(a), we plot $c$ on the x-axis instead of p=\exp{\big{(}\frac{\epsilon}{2\Delta}c\big{)}}, because it is not clear if report noisy max only depends on $c$ through $p$.

This comparison covers a particular class of quality score vectors which allow for a simple and tractable exact comparison. Further comparison with report noisy max would be an interesting future direction.

Appendix G Extra Experiments