Differentially Private Selection

In Winter 2026, I took an excellent class on differential privacy taught by Dr. Phyllis Ju. As part of that course, I presented on two papers. The first was on the permute-and-flip mechanism for differentially private selection, as introduced by McKenna and Sheldon [1]. The second was on this method’s equivalence with Report Noisy Max under exponential noise, following Ding, Durfee, Kifer, Rogers, and Zhang [2]. I hope to, at some later point, add a preamble that provides a gentler introduction to differential privacy in general. As of now, these notes assume a bit of background knowledge in the field of differential privacy, and the standard terminology in the field.

Given a database $D$ and a finite set of candidate outputs, each of which comes with a quality score, we would like to release the “best” output — the one with the highest score — while preserving the privacy of individuals in $D$. This is the differentially private selection problem. The classical solution is the exponential mechanism, which samples output $r$ with probability proportional to $\exp(\varepsilon\, q(D, r) / (2\Delta))$. The permute-and-flip mechanism, introduced in 2020, does at least as well as the exponential mechanism on every input, and better on average.

These notes:

1. Set up the private selection problem and the notion of a regular mechanism.
2. Relate it to the exponential mechanism, and to the link between entropy and privacy.
3. Present permute-and-flip and prove its optimality among regular mechanisms.
4. Show its equivalence to Report Noisy Max with exponential noise, via the memoryless property of the exponential distribution.

1. Setup and Notation

Definition 1.1 (Selection mechanism). Let $R$ be a finite set of outputs (the range), with $\lvert R \rvert = n$. A quality score function assigns to each database $D$ and output $r \in R$ a real-valued score $q(D, r) \in \mathbb{R}$. A selection mechanism is a randomized map $M : \mathcal{D} \to R$ that, given a database $D$, returns some output $r \in R$.

Definition 1.2 (Sensitivity). The sensitivity of the quality score function is

Recall that $D$ and $D’$ are neighbors if they differ in the entry of exactly one individual.

Example 1.3 (Pricing). Suppose we survey $4$ people, asking each one all the prices they would be willing to pay for a product. The database is

The set of possible prices (outputs) is $R = \{1, 2, 3, 4, 5\}$. A neighboring database $D’$ differs from $D$ in exactly one person’s response, e.g. replacing person 4’s entry:

We consider two natural quality-score functions.

Score function 1: number of buyers. Define $q_1(D, r)$ as the number of people willing to pay price $r$:

For our database $D$:

The sensitivity is $\Delta_1 = 1$: changing one person’s set of acceptable prices can change the count at any single price by at most $1$.

Score function 2: total profit. Define $q_2(D, r) = r \cdot q_1(D, r)$, the total revenue at price $r$:

The sensitivity is $\Delta_2 = \max_r r \cdot 1 = 5$: at price $r$, changing one person’s response can change the revenue by at most $r$, and the maximum price is $5$.

Note that we do not assume $q$ is monotonic: adding an individual may decrease $q$. For the many score functions that are monotonic — counts and profit among them — the analysis below saves a factor of $2$, and every $2\Delta$ may be replaced by $\Delta$.

2. Regular Mechanisms

To prove optimality, we restrict to mechanisms whose behavior depends on the score vector in a natural way. A mechanism $M$ is called regular if it satisfies the following three properties.

Definition 2.1 (Symmetric). The mechanism depends only on the multiset of quality scores, not on the labeling of outputs. For any permutation $\sigma$ of $R$,

Definition 2.2 (Shift-invariant). The mechanism depends only on the differences between quality scores, not their absolute values. For any constant $c$,

Definition 2.3 (Monotone). For two score vectors $q, q’$ with $q_r \geq q’_r$ and $q_s \leq q’_s$ for all $s \neq r$ (only the score at $r$ improved),

Both the exponential mechanism and permute-and-flip satisfy all three properties.

The objective. As usual in private selection, the goal is to minimize the expected error

subject to the mechanism $M$ being $\varepsilon$-differentially private.

3. The Permute-and-Flip Algorithm

The mechanism is remarkably simple. Given the score vector, we shuffle the outputs, walk through them in the shuffled order, and, for each one, flip a biased coin whose bias grows with the score. We return the first output whose coin comes up heads.

Algorithm (Permute-and-Flip).

Input: database $D$, quality score function $q$, privacy parameter $\varepsilon$, sensitivity $\Delta$, output set $R$.

Output: a differentially private output $r \in R$.

1. Randomly permute the list of outputs $R$.
2. Let $q_\ast = \max_{r \in R} q(D, r)$.
3. For each output $r$ in the permuted order:
   • Flip a coin with heads probability $\exp!\left(\dfrac{\varepsilon\,(q(D, r) - q_\ast)}{2\Delta}\right)$.
   • If heads, return $r$.

Note that the maximizer always has coin probability $1$, so the algorithm always terminates (worst case, at the last position in the shuffle).

4. Connection to the Exponential Mechanism: Entropy and Privacy

4.1 Softmax and the Boltzmann distribution

Consider the softmax (or Boltzmann) distribution over a set of scores $x_1, \ldots, x_n$ at temperature $T$:

In physics this is the Boltzmann distribution; in machine learning it is the softmax. The exponential mechanism uses precisely this distribution with $T = 2\Delta / \varepsilon$.

4.2 Entropy and privacy

The Shannon entropy of the output distribution is

The key intuition is that privacy is roughly a matter of tuning the temperature $T$ so that the entropy $H$ is large enough. When $T$ is large the distribution is close to uniform (high entropy, high privacy); when $T$ is small it concentrates on the maximum score (low entropy, low privacy).

For $n = 5$, say:

• $T \to 0$: the distribution tends to $(1, 0, 0, 0, 0)$, with entropy $H \approx 0$.
• $T$ large: the distribution tends to $(0.2, 0.2, 0.2, 0.2, 0.2)$, with entropy $H \approx \ln 5$.
• Intermediate $T$: something like $(0.6, 0.1, 0.1, 0.1, 0.1)$.

5. Optimality of Permute-and-Flip

We now argue that permute-and-flip is optimal among regular $\varepsilon$-differentially private mechanisms.

5.1 Worst-case scores

The proof proceeds by analyzing the worst case for the quality scores. By monotonicity, the worst case occurs when the scores take the form

Indeed, $q’ - q = 2\Delta\, e_r - \Delta\, \mathbf{1}$; by shift-invariance, adding the constant $\Delta$ to every coordinate does not change the distribution, so this case is identical to $q’ = q + 2\Delta\, e_r$.

5.2 Derivation via tight inequalities

The $\varepsilon$-differential privacy constraint requires, for score vectors $q, q’ = q + 2\Delta\, e_r$ and all $r \in R$,

This gives $\lvert R \rvert$ inequalities. To maximize the probability of selecting the highest-quality output, we

1. Make the inequalities tight for outputs with $q_r < q_\ast$: assign them the lowest probability consistent with differential privacy.
2. Distribute the remaining probability evenly among all outputs achieving $q_\ast$ (by symmetry).

Thus, we can solve the linear program given by the following $n = \lvert R \rvert$ equations:

where $n_\ast = \lvert \{r : q_r = q_\ast\} \rvert$. Iterating the tight inequality $(q_\ast - q_r)/(2\Delta)$ times raises the score at $r$ all the way to $q_\ast$, giving the equivalent closed form

where $\vec{q}^{(r)}$ denotes $\vec{q}$ with its $r$-th entry raised to $q_\ast$.

In general, this optimization can be solved in $O(n \log n)$ time by sorting the scores. Permute-and-flip achieves this optimum in closed form.

5.3 Optimality statement

Theorem 5.1. The permute-and-flip mechanism is optimal among regular $\varepsilon$-differentially private mechanisms. That is, for any regular $\varepsilon$-differentially private mechanism $M’$,

Moreover, permute-and-flip stochastically dominates the exponential mechanism.

Theorem 5.2. $M_{\mathrm{PF}}$ is never worse than $M_{\mathrm{EM}}$: for all $\vec{q} \in \mathbb{R}^n$ and all $t \geq 0$,

5.4 Size of the improvement

The exponential mechanism uses probability proportional to $\exp(\varepsilon\, q(r) / (2\Delta))$, while permute-and-flip effectively uses $\exp(\varepsilon\, q(r) / \Delta)$ in its selection probabilities. Concretely, the expected error of permute-and-flip is approximately $1.2\times$ smaller in the worst case (a gap that narrows as the dataset grows) and, numerically, approximately $2.2\times$ smaller on average.

6. Equivalence with Report Noisy Max

6.1 Report Noisy Max

The Report Noisy Max mechanism adds i.i.d. noise to each quality score and returns the argmax.

Algorithm (Report Noisy Max with exponential noise).

Input: database $D$, quality score function $q$, privacy parameter $\varepsilon$, sensitivity $\Delta$, output set $R$.

Output: a differentially private output $r \in R$.

1. For each output $r \in R$: sample $\eta_r \sim \mathrm{Exp}(\varepsilon / (2\Delta))$ and set $\tilde{q}(r) \gets q(D, r) + \eta_r$.
2. Return $\arg\max_{r \in R} \tilde{q}(r)$.

Here $\mathrm{Exp}(\lambda)$ denotes the exponential distribution with rate $\lambda$.

6.2 Why they are equivalent

The equivalence between permute-and-flip and Report Noisy Max with exponential noise follows from the memoryless property of the exponential distribution. To make this precise, we introduce two intermediate algorithms.

Intermediate algorithm $A$.

1. Compute $q_\ast = \max_i q(D, \omega_i)$.
2. For each $i$: set $v_i = q(D, \omega_i) + \mathrm{Exp}(\varepsilon/(2\Delta))$.
3. Form $S = \{i : v_i \geq q_\ast\}$.
4. Return a uniformly random element of $S$.

Algorithm $A$ adds exponential noise to each score, collects the outcomes whose noisy score reaches the true maximum $q_\ast$, and then selects uniformly at random from this set.

Intermediate algorithm $B$.

1. Compute $q_\ast = \max_i q(D, \omega_i)$.
2. For each $i$: set $\tilde v_i = \min\{q_\ast,\; q(D, \omega_i) + \mathrm{Exp}(\varepsilon/(2\Delta))\}$ and $z_i = \mathrm{Exp}(\varepsilon/(2\Delta))$.
3. Form $S’ = \{i : \tilde v_i = q_\ast\}$.
4. Return $\arg\max_{i \in S’}(\tilde v_i + z_i)$, which equals $\arg\max_{i \in S’} z_i$ since $\tilde v_i = q_\ast$ on $S’$.

Algorithm $B$ truncates each noisy score at $q_\ast$, then adds fresh exponential noise $z_i$ and returns the argmax among the elements that reached the threshold.

Theorem 6.1. Permute-and-flip and Report Noisy Max with exponential noise produce identical output distributions.

Sketch. We chain three equivalences.

(i) Permute-and-flip $\Leftrightarrow$ Algorithm $A$. In Algorithm $A$, the probability that outcome $i$ enters $S$ (i.e. that $v_i \geq q_\ast$) equals $\exp(\varepsilon(q(D, \omega_i) - q_\ast) / (2\Delta))$, which is exactly the coin-flip probability in permute-and-flip. To see this, recall that for $X \sim \mathrm{Exp}(\lambda)$, $\Pr(X > x) = e^{-\lambda x}$. Setting $\lambda = \varepsilon/(2\Delta)$ and $x = q_\ast - q_r$ recovers the flip probability. Returning a uniformly random element of $S$ is equivalent to shuffling and returning the first element that lands in $S$.

(ii) Algorithm $A$ $\Leftrightarrow$ Algorithm $B$. The set $S’ = \{i : \tilde v_i = q_\ast\}$ is exactly $S$ from Algorithm $A$. By the independence of the second noise process from the first, adding fresh exponential noise $z_i$ and taking the argmax is equivalent to picking a uniformly random element of $S’$.

(iii) Algorithm $B$ $\Leftrightarrow$ Report Noisy Max. Algorithm $B$ effectively adds exponential noise to every score and outputs the argmax; it just adds the noise in a conditional way, splitting it into a truncated piece and a fresh piece. This works because of the memoryless property of the exponential: for $X \sim \mathrm{Exp}(\lambda)$ and any $s, t \geq 0$,

Consequently the “chop and add fresh noise” procedure produces the same distribution as the original noise above the threshold. $\square$

7. Summary

The permute-and-flip mechanism is an optimal regular mechanism for $\varepsilon$-differentially private selection. It stochastically dominates the classical exponential mechanism — never worse on any input, roughly $1.2\times$ better in the worst case and $2.2\times$ better on average. Moreover, it is equivalent — as a randomized algorithm — to Report Noisy Max with exponential noise, via the memoryless property of the exponential distribution.

References

[1] R. McKenna and D. Sheldon, “Permute-and-Flip: A New Mechanism for Differentially Private Selection,” Advances in Neural Information Processing Systems (NeurIPS), 2020.

[2] Z. Ding, D. Durfee, D. Kifer, R. M. Rogers, and L. Zhang, “The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise,” arXiv:2105.07260, 2021.