AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Exponential mechanism

Definition

Let $D$ be the finite-support count functions on a nonempty record universe, with add/remove-one-occurrence adjacency. Input a database $D \in D$ , a parameter $ε > 0$ , a nonempty finite database-independent range $R$ , and a real-valued utility $u : D \times R \to R$ with finite positive global utility sensitivity $Δ_{u}$ . For each $r \in R$ , set $w_{D} (r) = \exp ⁣ (\frac{ε u (D, r)}{2 Δ_{u}}), Z_{D} = \sum_{s \in R} w_{D} (s) .$ Output $r \in R$ with probability $w_{D} (r) / Z_{D}$ . Equip $R$ with its power-set sigma-algebra and define $K (D, B) = \sum_{r \in B} w_{D} (r) / Z_{D}$ for each $B \subseteq R$ ; this is the probability kernel from databases to outputs.

Definition references

Global utility sensitivity

The probability-kernel conditions for a randomized mechanism

Dwork and Roth, The Algorithmic Foundations of Differential Privacy, Definition 3.4, printed p. 38.

Vadhan, The Complexity of Differential Privacy, §4.1, Proposition 4.2.

Facts & Assumptions

Given: $ε > 0$ , a nonempty finite set $R$ , a real-valued utility $u$ , and a finite sensitivity $Δ_{u} > 0$ .

[F1]

Utility sensitivity is the attained finite maximum of adjacent-pair score differences over the database-independent finite range.

[F2]

The real exponential is finite on every real input, and exponential positivity gives strictly positive values.

[F3]

Probability measure means a measure of total mass one.

[F4]

The database domain has the power-set sigma-algebra.

[F5]

Probability kernel means each section is a probability measure and each event evaluation is measurable in the source.

Verification

1.1F1F2F3givenconstruct

Since $Δ_{u} > 0$ and each score $u (D, r)$ is real, [F2] makes every weight $w_{D} (r)$ finite and positive. The nonempty finite sum $Z_{D}$ is therefore finite and strictly positive. For $A \subseteq R$ , define $K (D, A) = \sum_{r \in A} w_{D} (r) / Z_{D}$ . This is nonnegative, equals one on $R$ , and is countably additive because a disjoint family of subsets of finite $R$ has only finitely many nonempty members. Thus each section is a probability measure by [F3].

2.1F4F5step 1.1∎

For every $A \subseteq R$ , $D \mapsto K (D, A)$ is measurable because every subset of the database domain is measurable by [F4]. Hence the assignment satisfies both conditions in [F5] and is a probability kernel.

Depends on

Used by

Finite-range private selection Example
Exponential mechanism privacy and utility Theorem

Dependency tree · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy (standard reference, not scraped)
Salil Vadhan, The Complexity of Differential Privacy, 2017 manuscript (standard reference, not scraped)