# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## 6 Application: Comparing DP Mechanisms
### Preliminaries  
We define each family of mechanisms in terms of their channel construction. We assume that mechanisms operate on a set of inputs (denoted by \(\mathcal{X}\)) and produce a set of outputs (denoted \(\mathcal{Y}\)). In this sense, our mechanisms can be seen as oblivious (as in standard DP) or as LDP mechanisms. (We use the term'mechanism' in either sense). We denote by \(M^{\varepsilon}\) a mechanism parametrized by \(\varepsilon\), where \(\varepsilon\) is defined to be the same as \(\text{Priv}_{d}(M)\). For the purposes of comparison, we make sure that we use the best possible \(\varepsilon\) for each mechanism. In order to compare mechanisms, we restrict our input and output domains of interest to sequences of non-negative integers. We assume \(\mathcal{X},\mathcal{Y}\) are finite unless specified. In addition, as we are operating in the framework of \(d\)-privacy, it is necessary to provide an appropriate metric defined over \(\mathcal{X}\); here, it makes sense to use the Euclidean distance metric \(d_{\text{E}}\). **Definition 9**. : _A geometric mechanism is a channel \((\mathcal{X},\mathbb{Z},G^{\varepsilon})\), parametrized by \(\varepsilon\geq 0\) constructed as follows:_  
\[G^{\varepsilon}_{x,y}=\frac{(1-\alpha)\cdot\alpha^{d_{\text{E}}(x,y)}}{1+\alpha} \text{for all }x\in\mathcal{X},y\in\mathbb{Z} \tag{27}\]  
_where \(\alpha=e^{-\varepsilon}\) and \(d_{\text{E}}(x,y)=\|x-y\|\). Such a mechanism satisfies \(\varepsilon\cdot d_{\text{E}}\)-privacy._  
In practice, the truncated geometric mechanism is preferred to the infinite geometric. We define the truncated geometric mechanism as follows. **Definition 10**. : _A truncated geometric mechanism is a channel \((\mathcal{X},\mathcal{Y},TG^{\varepsilon})\), parametrized by \(\varepsilon\geq 0\) with \(\mathcal{X}\subseteq\mathcal{Y}\) constructed as follows:_  
\[TG^{\varepsilon}_{x,y} =\frac{(1-\alpha)\cdot\alpha^{d_{\text{E}}(x,y)}}{1+\alpha} \text{for all }y\
eq\min\mathcal{Y},\max\mathcal{Y} \tag{28}\] \[TG^{\varepsilon}_{x,y} =\frac{\alpha^{d_{\text{E}}(x,y)}}{1+\alpha} \text{for }y=\min\mathcal{Y},\max\mathcal{Y} \tag{29}\]  
_where \(\alpha=e^{-\varepsilon}\) and \(d_{\text{E}}(x,y)=\|x-y\|\). Such a mechanism satisfies \(\varepsilon\cdot d_{\text{E}}\)-privacy._It is also possible to define the 'over-truncated' geometric mechanism whose input space is not entirely included in the output space. **Definition 11**. : _An over-truncated geometric mechanism is a channel \((\mathcal{X},\mathcal{Y},OTG^{\varepsilon})\), parametrized by \(\varepsilon\geq 0\) with \(\mathcal{X}\
ot\subseteq\mathcal{Y}\) constructed as follows:_  
1. _Start with the truncated geometric mechanism_ \((\mathcal{X},\mathcal{X}\cup\mathcal{Y},TG^{\varepsilon})\)_._
2. _Sum up the columns at each end until the output domain is reached._  
_Such a mechanism satisfies \(\varepsilon\cdot d_{E}\)-privacy._  
For example, the set of inputs to an over-truncated geometric mechanism could be integers in the range \([0\dots 100]\), but the output space may have a range of \([0\dots 50]\) or perhaps \([-50\dots 50]\). In either of these cases, the mechanism has to 'over-truncate' the inputs to accommodate the output space. We remark that we do not consider the over-truncated mechanism a particularly useful mechanism in practice. However, we provide results on this mechanism for completeness since its construction is possible, if unusual. **Definition 12**. : _An exponential mechanism is a channel \((\mathcal{X},\mathcal{Y},E^{\alpha})\), parametrized by \(\varepsilon\geq 0\) constructed as follows:_  
\[E^{\alpha}_{x,y} =\lambda_{x}\cdot e^{-\frac{\varepsilon}{2}d_{E}(x,y)} \text{for all }x\in\mathcal{X},y\in\mathcal{Y} \tag{30}\]  
_where \(\lambda_{x}\) are normalizing constants ensuring \(\sum_{y}E^{\alpha}_{x,y}=1\).