# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## 3 Max-Case Refinement
If \(A\sqsubseteq^{\max}B\), then the posteriors of \(B\) (under \(\pi\)) are convex-combinations of those of \(A\), that is,_  
\[supp\left[\pi,B\right]\ \ \subseteq\ \ ch\,supp\left[\pi,A\right] \tag{10}\]  
_Moreover, if (A1) holds and \(\pi\) is full support, then \(A\sqsubseteq^{\max}B\)._  
Note that, if (A1) holds for any full-support prior, then it must hold for all priors. Theorem A1 has a nice geometric intuition (cf. Figure 2) that we are going to illustrate in the following example. **Example 5**. : _Consider the following systems._  
\[ \begin{array}{|c|cccc|}\hline A&y_{1}&y_{2}&y_{3}&y_{4}\\ \hline x_{1}&1/3&2/9&2/9&2/9\\ x_{2}&1/9&1/3&2/9&1/3\\ x_{3}&1/9&2/9&1/3&1/3\\ \hline\end{array} \quad \begin{array}{|c|cccc|}\hline B&y_{1}&y_{2}&y_{3}&y_{4} \\ \hline x_{1}&1/3&2/9&2/9&1/9\\ x_{2}&2/9&1/3&2/9&1/9\\ x_{3}&2/9&2/9&1/3&1/9\\ \hline\end{array}  \tag{11}\]  
_Consider the prior \(\pi=(\
icefrac{{1}}{{2}},\
icefrac{{1}}{{4}},\
icefrac{{1}}{{4}})\). The set of the posterior distributions generated by \(A\) under \(\pi\) are:_  
\[ \begin{array}{|c|cccc|}\text{supp}\left[\pi,A\right]=\left\{(3/4,1/8,1/8),(4/9,1/3,2/9),(4/9,2/9,1/3),(2/5,3/10,3/10)\right\}\end{array}  \tag{12}\]  
_while those generated by \(B\) are:_  
\[ \begin{array}{|c|cccc|}\text{supp}\left[\pi,B\right]=\left\{(3/5,1/5,1/5),(4/9,1/3,2/9),(4/9,2/9,1/3),(1/2,1/4,1/4)\right\}\end{array}  \tag{13}\]  
_These posteriors, and the convex hulls that they generate, are illustrated in Figure 2. The pink area is the \(ch\,\text{supp}\left[\pi,A\right]\) and the purple area is the \(ch\,\text{supp}\left[\pi,B\right]\). We can see that \(\text{supp}\left[\pi,B\right]\subseteq ch\,\text{supp}\left[\pi,A\right]\), or, equivalently, \(ch\,\text{supp}\left[\pi,B\right]\subseteq ch\,\text{supp}\left[\pi,A\right]\)._  
We are now ready to give the main result of this section. **Theorem 2**. : _The orders \(\sqsubseteq^{\text{max}}\) and \(\sqsubseteq^{\text{max}}_{\mathbb{Q}}\) coincide._  
Similarly to the average case, \(A\sqsubseteq^{\text{max}}B\) gives us a strong leakage guarantee: can safely replace \(A\) by \(B\), knowing that, for any adversary, the max-case leakage of \(B\) can be no-larger than that of \(A\). Moreover, in case \(A\
ot\sqsubseteq^{\text{max}}B\), we can always find an adversary, modelled by a vulnerability function \(V\), who prefers (wrt the max-case) interacting with \(A\) that with \(B\). Such a function is discussed in Section 5. Finally, we resolve the question of how \(\sqsubseteq^{\text{max}}\) and \(\sqsubseteq^{\text{avg}}\) are related. **Theorem 3**. : \(\sqsubseteq^{\text{avg}}\) _is strictly stronger than \(\sqsubseteq^{\text{max}}\)._  
This result might appear counter-intuitive at first; one might expect \(A\sqsubseteq^{\text{max}}B\) to imply \(A\sqsubseteq^{\text{avg}}B\). To understand why it does not, note that the former only requires that, for each output \(y_{B}\) of \(B\), there exists some output of \(y_{A}\) that is at least as vulnerable, regardless of how likely \(y_{A}\) and \(y_{B}\) are to happen (this is max-case, after all). We illustrate this with the following example. Figure 2: The simplex and the convex hulls of the posterior distributions in Example 5. **Example 6**. : _Consider the following systems:_  
\[ \begin{array}{|c|cccc|}\hline A&y_{1}&y_{2}&y_{3}&y_{4}\\ \hline x_{1}&3/4&0&1/4&0\\ x_{2}&3/4&1/4&0&0\\ x_{3}&0&1/4&1/4&1/2\\ \hline\end{array} \quad \begin{array}{|c|cccc|}\hline B&y_{1}&y_{2}&y_{3}\\ \hline x_{1}&1/2&0&1/2\\ x_{2}&1/2&1/2&0\\ x_{3}&0&1/2&1/2\\ \hline\end{array}  \tag{14}\]  
_Under the uniform prior, the \(y_{1},y_{2},y_{3}\) posteriors for both channels are the same, namely \((1/2,1/2,0)\), \((0,1/2,1/2)\) and \((1/2,0,1/2)\), respectively. Thus, the knowledge that can be obtained by each output of \(B\) can be also obtained by some output of \(A\) (albeit with a different probability). Hence, from Theorem A1, we get that \(A\sqsubseteq^{\max}B\).