Exponential mechanism privacy and utility

For every $r\in R$, [F2] and monotonicity and addition for $\exp$ from [F6] give $w_D(r)\le e^{\epsilon \mathrm{/}2}{w}_{D^{\mathrm{\prime }}}(r)$; summing gives $Z_D\le e^{\epsilon \mathrm{/}2}{Z}_{D^{\mathrm{\prime }}}$. Applying the same argument with $D,D^{\mathrm{\prime }}$ interchanged gives $Z_{D^{\mathrm{\prime }}}\le e^{\epsilon \mathrm{/}2}{Z}_D$. Since the weights and normalizers are positive, [F6] then yields $(w_D(r)\mathrm{/}{Z}_D)\mathrm{/}(w_{D^{\mathrm{\prime }}}(r)\mathrm{/}{Z}_{D^{\mathrm{\prime }}})\le e^{\epsilon }$. Interchanging $D,D^{\mathrm{\prime }}$ gives the reverse point-mass bound. Summing over any event $A\subseteq R$ gives both $(\epsilon ,0)$ event inequalities, so [F4] proves privacy.

By [F3], the maximizing set is nonempty and its elements each have weight $e^{\epsilon {\mathrm{OPT}}_u(D)\mathrm{/}(2{\mathrm{\Delta }}_u)}$. Let $B$ be the event in the Statement. For each $r\in B$, its defining score inequality, monotonicity and addition for $\exp$ from [F6], and [F5] imply $w_D(r)\le e^{\epsilon {\mathrm{OPT}}_u(D)\mathrm{/}(2{\mathrm{\Delta }}_u)}(\mathrm{\mid }{R}_{\mathrm{OPT}}\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid })e^{-t}$. There are at most $\mathrm{\mid }R\mathrm{\mid }$ such elements, while the normalizer is at least the sum of the maximizing weights, namely $\mathrm{\mid }{R}_{\mathrm{OPT}}\mathrm{\mid }{e}^{\epsilon {\mathrm{OPT}}_u(D)\mathrm{/}(2{\mathrm{\Delta }}_u)}$. Therefore the probability of $B$ is at most $e^{-t}$. If $B$ is empty its probability is zero and the same bound holds.