# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## 3 Max-Case Refinement  
Although \(\sqsubseteq^{\text{avg}},\sqsubseteq^{\text{avg}}_{G}\) provides a strong and precise way of comparing systems, one could argue that average-case vulnerability might underestimate the threat of a system. More precisely, imagine that there is a certain observation \(y\) such that the corresponding posterior \(\delta^{y}\) is highly vulnerable (e.g., the adversary can completely infer the real secret), but \(y\) happens with very small probability \(a_{y}\)In this case, the average-case posterior vulnerability \(V[\pi,C]\) can be relatively small, although \(V(\delta^{y})\) is large for that particular \(y\). If such a scenario is considered problematic, we can naturally quantify leakage using a max-case (called \"worse\"-case in some contexts, although the latter is more ambiguous, \"worse\" can refer to a variety of factors.) variant of posterior vulnerability, where all observations are treated equally regardless of their probability of being produced:  
\[V^{\max}[\pi,C]\ \ :=\ \ \max_{y}V(\delta^{y}) \tag{7}\]  
Under this definition, it can be shown [9] that \(V\) has to be _quasi-convex_ on \(\pi\) (instead of convex), in order to satisfy fundamental properties (such as the data processing inequality). Hence, in the max-case, we no longer restrict to \(g\)-vulnerabilities (which are always convex), but we can use any vulnerability \(V:\mathbb{Q}\mathcal{X}\), where \(\mathbb{Q}\mathcal{X}\) denotes the set of all continuous quasi-convex functions \(\mathbb{D}\mathcal{X}\to\mathbb{R}_{\geq 0}\). Inspired by \(\sqsubseteq^{\text{avg}}_{\mathbb{G}}\), we can now define a corresponding max-case leakage order. **Definition 1**. : _The max-case leakage order is defined as_  
\[A\sqsubseteq^{\max}_{\mathbb{Q}}B\qquad\text{iff}\qquad V^{\max}[\pi,A]\ \geq\ V^{\max}[\pi,B]\qquad\qquad\text{for all }V :\mathbb{Q}\mathcal{X},\pi\colon\mathbb{D}\mathcal{X} \tag{8}\]  
Similarly to its average-case variant, \(\sqsubseteq^{\max}_{\mathbb{Q}}\) provides clear privacy guarantees by explicitly requiring that \(B\) leaks no more than \(A\) for all adversaries (modelled as a vulnerability \(V\)). However, this explicit quantification makes the order hard to reason about and verify. We would thus like to characterize \(\sqsubseteq^{\max}_{\mathbb{Q}}\) by a refinement order that depends only on the structure of the two channels. Given a channel \(C\) from \(\mathcal{X}\) to \(\mathcal{Y}\), we denote by \(\tilde{C}\) the channel obtained by normalizing \(C\)'s columns (if a column consists of only zeroes, it is simply removed.) and then transposing:  
\[\tilde{C}_{y,x}\ \ :=\ \ \frac{C_{x,y}}{\sum_{x}C_{x,y}} \tag{9}\]  
Note that the row \(y\) of \(\tilde{C}\) can be seen as the posterior distribution \(\delta^{y}\) obtained by \(C\) under the uniform prior. Note also that \(\tilde{C}\) is non-negative and its rows sum up to \(1\), so it is a valid channel from \(\mathcal{Y}\) to \(\mathcal{X}\). The average-case refinement order required that \(B\) can be obtained by post-processing \(A\). We define the _max-case refinement_ order by requiring that \(\tilde{B}\) can be obtained by _pre-processing_\(\tilde{A}\). **Definition 2**. : _The max-case refinement order is defined as \(A\sqsubseteq^{\max}B\) iff \(R\tilde{A}=\tilde{B}\) for some channel \(R\)._  
Our goal now is to show that \(\sqsubseteq^{\max}_{\mathbb{Q}}\) and \(\sqsubseteq^{\max}\) are different characterizations of the same order. To do so, we start by giving a \"semantic\" characterization of \(\sqsubseteq^{\max}\) that is, expressing it, not in terms of the channel matrices \(A\) and \(B\), but in terms of the _posterior distributions_ that they produce. Thinking of \([\pi,C]\) as a (\"hyper\") distribution on the posteriors produced by \(\pi\) and \(C\), its support \(supp\left[\pi,C\right]\) is the set of all posteriors produced with non-zero probability. We also denote by \(ch\,S\) the convex hull of \(S\). **Theorem 1**. : _Let \(\pi\colon\mathbb{D}\mathcal{X}\).