Fair Decisions from Calibrated Scores: Achieving Optimal Classification While Satisfying Sufficiency Etam Benger, Katrina Ligett Abstract Binary classification based on predicted probabilities (scores) is a fundamental task in supervised machine learning. While thresholding scores is Bayes-optimal in the unconstrained setting, using a single threshold generally violates statistical group fairness constraints. Under independence (statistical parity) and separation (equalized odds), such thresholding suffices when the scores already satisfy the corresponding criterion. However, this does not extend to sufficiency: even perfectly group-calibrated scores—including true class probabilities—violate predictive parity after thresholding. In this work, we present an exact solution for optimal binary (randomized) classification under sufficiency, assuming finite sets of group-calibrated scores. We provide a geometric characterization of the feasible pairs of positive predictive value (PPV) and false omission rate (FOR) achievable by such classifiers, and use it to derive a simple post-processing algorithm that attains the optimal classifier using only group-calibrated scores and group membership. Finally, since sufficiency and separation are generally incompatible, we identify the classifier that minimizes deviation from separation subject to sufficiency, and show that it can also be obtained by our algorithm, often achieving performance comparable to the optimum. 1 Introduction and Related Work Making decisions based on predicted probabilities is a central task in machine learning, statistics, and data-driven decision-making. Given a score that estimates the probability of a positive outcome, the Bayes-optimal decision rule in the unconstrained setting is simple: apply a deterministic threshold to the score ( 12 ) . This principle underlies many everyday decisions, from acting on a weather forecast to standard classification pipelines. In high-stakes applications, however, decision making is often subject to fairness constraints. Algorithms increasingly affect outcomes in domains such as college admissions, lending, hiring, healthcare, and criminal justice, where concerns about discrimination and disparate treatment across protected groups are paramount. As a result, a substantial literature has developed around formal notions of fairness in classification, typically expressed as statistical constraints relating a prediction or decision R , a target variable Y , and a protected attribute A . Three prominent criteria of algorithmic fairness are independence, separation, and sufficiency ( 2 ) . Independence (often called demographic parity) requires the decision R to be statistically independent of the protected attribute A . Separation (including equalized odds and equal opportunity ( 10 ) ) requires equality of error rates across groups. Sufficiency (also known as predictive parity or group-calibration) requires that, conditional on the decision outcome, the prevalence of the positive label be the same across groups. These terms capture different fairness notions and are known to be mutually incompatible in general, except in trivial cases ( 6 ; 11 ) . A common feature of these criteria is that, when applied to classification, they typically cannot be satisfied by a single, group-agnostic threshold on the score ( 10 ; 7 ) . Instead, satisfying independence or separation usually requires group-specific decision rules or explicit post-processing that depends on the protected attribute. An important exception arises when the score itself already satisfies the desired criterion: if a score satisfies independence or separation, then thresholding preserves the property, and a single threshold can be used fairly. This convenient property does not extend to sufficiency. Even when a score is perfectly calibrated within each group—including the ideal case where the score equals the true conditional probability P(Y=1|X,A) —applying a single threshold generally produces decisions that violate sufficiency ( 6 ; 5 ) . This phenomenon has been highlighted in both theoretical and empirical studies and plays a central role in well-known case studies such as the COMPAS recidivism risk score ( 1 ) , which takes values between 1 and 10 and is used to make binary decisions such as bail decisions. At the same time, sufficiency has received significant attention in the algorithmic fairness literature ( 2 ) . It is an appealing notion for its compatibility with accuracy (in contrast, in general, achieving independence or separation requires sacrificing accuracy ( 9 ) ) and for its relationship to the notion of calibration. Two main approaches have been proposed to address the problem of sufficiency in decision-making. 5 introduce classifiers that satisfy sufficiency by allowing an algorithm to abstain from making a decision on some instances. 3 show that sufficiency can be achieved without abstentions by suitable post-processing, but their analysis relies on strong assumptions about the score distribution, notably continuity and full support. In contrast, many practical systems operate with discrete, finite-valued scores, for which these assumptions do not hold. Our contributions. In this work, we study binary classification under sufficiency in the practically relevant setting of finite-valued, group-calibrated scores. Our focus is on post-processing methods of classification that take as input only a score and group membership and output a (possibly randomized) binary decision. We give an exact characterization of the set of achievable classifiers under sufficiency and use it to derive optimal fair decision rules. We provide a geometric characterization of the feasible pairs of positive predictive value (PPV) and false omission rate (FOR) attainable by binary classifiers based on a calibrated score. This characterization yields a complete description of the “feasible region” and its boundary. Next, we characterize the intersection of the group-wise feasible regions induced by sufficiency and show how to trace its boundary efficiently. This leads to a simple post-processing algorithm that constructs the optimal sufficient classifier for a wide class of objectives, including loss minimization, using only group-calibrated scores and group membership. Finally, recognizing that sufficiency and separation are generally incompatible, we study classifiers that satisfy sufficiency while minimizing deviation from separation. We show that this objective can be optimized within the same geometric framework and often yields classifiers with performance close to that of the loss-optimal solution. 2 Preliminaries Definition 2.1 (Sufficiency) . Let Y be a target variable and A a protected attribute. A predictor S of Y satisfies sufficiency if Y and A are conditionally independent given S , that is, P(Y\mid S,A)=P(Y\mid S). Intuitively, sufficiency requires that the predictive meaning of a score be the same across groups. This notion is closely related to calibration. Definition 2.2 (Calibration and group-calibration) . Let Y be a binary target variable. A score S\in[0,1] is calibrated with respect to Y if P(Y=1\mid S=s)=s for all s\in\supp S . If A denotes population groups, S is group-calibrated if P(Y=1\mid S=s,A=a)=s for all a\in\supp A and s\in\supp S with P(S=s,A=a)>0 . If S is group-calibrated, then it satisfies sufficiency, and the converse also holds up to a relabeling of S (see, e.g., ( 2 ) ). For nonconstant binary predictors, sufficiency is equivalent to predictive parity, defined next. Definition 2.3 (Predictive parity) . Let Y be binary and R a nonconstant binary predictor. Define the positive predictive value and false omission rate as \displaystyle\ppv(R) \displaystyle:=P(Y=1\mid R=1), \displaystyle\for(R) \displaystyle:=P(Y=1\mid R=0). We say that R satisfies predictive parity if, for all a\in\supp A , \displaystyle P(Y=1\mid R=1,A=a) \displaystyle=\ppv(R), \displaystyle P(Y=1\mid R=0,A=a) \displaystyle=\for(R). 3 Feasibility in the Unconstrained Setting We begin by characterizing the unconstrained setting, ignoring for now the role of A , and later extend the analysis to binary classifiers that satisfy sufficiency. Let Y be a binary target variable and denote by \pi:=P(Y=1) its base rate, or prevalence, and let S be a finite-valued calibrated prediction of Y . We denote the values in \supp S in descending order, 1\geq s_{\mathrm{max}}=s_{1}>\dots>s_{m}=s_{\mathrm{min}}\geq 0 , and write P(s_{i}) for short when S is implicitly understood. The calibration of S implies that \displaystyle\E[S] \displaystyle=\sum_{i\in[m]}P(s_{i})\,s_{i}=\sum_{i\in[m]}P(s_{i})\,P(Y=1|s_{i})=\pi, (1) and to avoid degenerate cases, we assume that m:=|\supp S|>1 , so s_{\mathrm{min}}<\pi0 , any nontrivial feasible pair satisfies q<\pi

k^{*}.\end{cases} (5) A detailed proof is given in Appendix B . Since the scores s_{i} are listed in descending order, the classifier R^{*} acts almost like a threshold: it deterministically predicts 1 for all score bins strictly above s_{k^{*}} and 0 for all score bins strictly below s_{k^{*}} , while possibly returning a randomized prediction on the bin corresponding to s_{k^{*}} . An important consequence of Theorem 3.3 is that R^{*}(S;\mu) becomes a purely deterministic (“hard”) threshold exactly at the values \mu_{k}:=\sum\nolimits_{i\leq k}P(s_{i}) for k\in[m] . In those cases we have R^{*}(S;\mu_{k})=1 iff S\geq s_{k} . Moreover, Theorem 3.3 , together with the convexity argument above, yields an explicit construction of a selection rule—and hence a classifier R(S) —to attain any given pair (p,q)\in\mathcal{C} . Specifically, such a classifier is obtained as an appropriate mixture of R^{*}(\mu) and an independent Bernoulli random variable with parameter \mu , where \mu=(\pi-q)/(p-q) follows from ( 2 ) (for p,q\neq\pi ; otherwise the claim is trivial). 3.2 Boundary of the Feasible Region As discussed above, the star-convexity of \mathcal{C} implies that its structure is fully determined by its boundary. The boundary of \mathcal{C} can therefore be divided into two parts. First, a trivial part consisting of two straight edges at p=\pi and q=\pi , implied by the constraint q\leq\pi\leq p ; these edges are not feasible (except at (p,q)=(\pi,\pi) ), since we require 0<\mu<1 . Second, a nontrivial part, traced by (p^{*}(\mu),q^{*}(\mu)) as \mu ranges over (0,1) . In what follows, we refer to this nontrivial part simply as the boundary of \mathcal{C} and denote it by \partial\mathcal{C} . The simple form of the selection rule in Theorem 3.3 allows for a piecewise characterization of \partial\mathcal{C} . Recall the values \mu_{k}:=\sum\nolimits_{i\leq k}P(s_{i}) , which correspond to the deterministic thresholds on S , and let \mu_{0}:=0 . We partition the interval (0,1) accordingly into m subintervals of the form I_{k}:=(\mu_{k-1},\mu_{k}]\cap(0,1) . Note that k^{*}(\mu) , as defined in Theorem 3.3 —that is, the index of the score bin on which R^{*} may randomize—is constant on each interval I_{k} and equals k . Thus, combining Equation ( 5 ) with Equation ( 4 ), we obtain a simple explicit formula for p^{*}(\mu) on each interval I_{k} : \displaystyle p^{*}(\mu) \displaystyle=\frac{1}{\mu}\left(\sum\nolimits_{i1 , we have c_{k}>0 , since the scores are in strictly descending order. Therefore, p^{*}(\mu) is strictly decreasing in \mu on each I_{k} with k>1 , and, by continuity, it is strictly decreasing on (\mu_{1},1) . In the following sections, in order to account for fairness constraints, we extend the analysis to multiple groups and study the intersection of their respective feasible regions. While parametrizing the boundary by the selection rate \mu was convenient for deriving the preceding formulas, in the multi-group setting the group-wise selection rates may differ. It is therefore more convenient to use p as a common boundary parameter. To this end, we exploit the monotonicity established above and induce a partition of the interval (\pi,s_{\mathrm{max}}) from the partition \{I_{k}\} of (0,1) . For each k>1 , define J_{k}:=p^{*}(I_{k}) . Then J_{k}=[p_{k},p_{k-1}) for 1\pi , the intervals \{J_{k}\} form a partition of (\pi,s_{\mathrm{max}}) . In particular, by the strict monotonicity of p^{*} on (\mu_{1},1) , each J_{k} satisfies I_{k}={p^{*}}^{-1}(J_{k}) . Now, let (p,q)\in\partial\mathcal{C} with p1 . Since the boundary consists of the points (p^{*}(\mu),q^{*}(\mu)) , there exists 0<\mu<1 , such that p=p^{*}(\mu) , and it follows that \mu\in{p^{*}}^{-1}(J_{k})=I_{k} . Therefore, by Equation ( 6 ), \mu=\mu(p)=c_{k}/(p-s_{k}) . Plugging this into Equation ( 2 ) and rearranging the expression gives us a formula for q^{*} in terms of p , instead of \mu : q=q(p)=q^{*}(\mu(p))=\frac{(\pi-c_{k})p-s_{k}\pi}{p-s_{k}-c_{k}}. (7) This analysis brings us to the following characterization of the boundary of the feasible region: Theorem 3.4 . The closure of the nontrivial boundary curve of \mathcal{C} consists of a continuous nondecreasing curve q(p) , defined piecewise by Equation ( 7 ) on each interval J_{k}\subset[\pi,s_{\mathrm{max}}) , together with a vertical segment at (s_{\mathrm{max}},q) for q\in[q(s_{\mathrm{max}}^{-}),\pi] . The proof appears in Appendix C . 1 1 1 Formally, \partial\mathcal{C} excludes the endpoints at p=\pi and q=\pi , which correspond to degenerate classifiers with \mu=0 and \mu=1 , respectively. Nonetheless, working with the closed boundary simplifies the subsequent analysis. More specifically, \partial\mathcal{C} consists of two straight segments at q=s_{\mathrm{min}} and p=s_{\mathrm{max}} , and, if m>2 , a sequence of hyperbolic arcs on each J_{k} with 10\} the effective support of S on the subgroup a . Importantly, we make no assumptions on these supports beyond finiteness: they may coincide across groups or be entirely disjoint. For each subgroup separately, as in the previous section, we denote m^{a}:=|\supp^{a}S| and list the distinct scores in \supp^{a}S in decreasing order, 1\geq s_{\mathrm{max}}^{a}=s^{a}_{1}>\dots>s^{a}_{m^{a}}=s_{\mathrm{min}}^{a}\geq 0 . We are interested in (possibly randomized) binary classifiers R=R(S,A) that take both S and A as input. For each a\in\{0,1\} , this implies the Markov condition P(R|S,Y,A=a)=P(R|S,A=a) , meaning that within each group, the classification depends on S alone. For example, R may represent a college admission decision based on an applicant’s test score and protected attribute. We denote \mu^{a}:=P(R=1|a) , p^{a}=\ppv^{a}(R):=P(Y=1|R=1,a) , and q^{a}=\for^{a}(R):=P(Y=1|R=0,a) , and consider group-specific selection rules P(R|s^{a}_{i},a) . Together with the group-calibration of S , the group-wise Markov property of R establishes a direct analogy with the single-group setting. Specifically, conditioning on a fixed group A=a recovers exactly the same structural conditions as in the unconstrained case. As a result, feasibility can be analyzed separately within each subgroup. Definition 4.1 (Subgroup-Feasibility) . Given a joint distribution P(Y,S,A) , we say that a pair (p^{a},q^{a})\in[0,1]^{2} is subgroup-feasible for a\in\supp A if it is feasible in the sense of Definition 3.1 , given the conditional distribution P(Y,S|a) . The subgroup-feasible region \mathcal{C}^{a}:=\mathcal{C}_{P(Y,S|A=a)} is defined accordingly. 4.1 Sufficiency By Definition 2.1 , R satisfies sufficiency with respect to Y and A if P(Y=1|R,A)=P(Y=1|R) . In our setting, this is equivalent to requiring p^{0}=p^{1}=p and q^{0}=q^{1}=q (see Definition 2.3 ). Therefore, R satisfies sufficiency if (p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1}, making the intersection of the subgroup-feasible regions our main object of interest. By Equation ( 8 ), (p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} iff \displaystyle\max\{\pi^{0},\pi^{1}\}

p_{L}\} l\leftarrow\max\{l\in\{2,\dots,m^{1}\}:p^{1}_{l-1}>p_{L}\} p_{R}\leftarrow\min\{p^{0}_{k-1},\,p^{1}_{l-1},\,p_{\mathrm{max}}\} // we have J_{k,l}=[p_{L},p_{R}) \mathit{roots}_{\Phi}\leftarrow real roots of \Phi_{k,l}(p) in (p_{L},p_{R}) , in increasing order for each p_{R}^{\prime}\in\mathit{roots}_{\Phi}\cup\{p_{R}\} do // and now J_{k,l,i}=[p_{L},p_{R}^{\prime}) a\leftarrow 0 if \Phi_{k,l}\left(\frac{p_{L}+p_{R}^{\prime}}{2}\right)\geq 0 else a\leftarrow 1 // a is the active boundary on J_{k,l,i} Evaluate \mathcal{F} on [p_{L},p_{R}^{\prime}) using a,k,l p_{L}\leftarrow p_{R}^{\prime} end for end while if p_{\mathrm{max}}=\min\{s_{\mathrm{max}}^{0},s_{\mathrm{max}}^{1}\} then Evaluate \mathcal{F} on the vertical segment at p=p_{\mathrm{max}} end if 5 Loss Minimization Under Sufficiency Up to this point, we have characterized all pairs (p,q) attainable as p=\ppv(R):=P(Y=1\mid R=1) and q=\for(R):=P(Y=1\mid R=0) by binary classifiers R=R(S,A) that satisfy predictive parity. Specifically, for such classifiers the group-wise quantities \ppv^{a}(R):=P(Y=1\mid R=1,a) and \for^{a}(R):=P(Y=1\mid R=0,a) coincide with p and q for all groups a . Moreover, Theorem 3.3 together with the star-convexity property yields an explicit description of the corresponding selection rules P(R=1\mid S,A) for each feasible pair (p,q) in the intersection of the group-specific feasible regions. When this intersection is nonempty, a natural remaining question is how to choose among the feasible classifiers. In this section, we address this question by considering classifiers that minimize a given loss function. Let \ell:\{0,1\}^{2}\to\mathbb{R} be a loss function assigning a cost \ell(R,Y) to a prediction R and a true label Y , and write \ell_{ry}:=\ell(r,y) . Without loss of generality, we assume \ell_{00}=\ell_{11}=0 and \ell_{01}+\ell_{10}>0 (otherwise, the labels of R can be flipped). Our goal is to find a classifier R that minimizes the expected loss L:=\E_{R,Y}[\ell(R,Y)] subject to sufficiency. We show that any optimal classifier attains a pair (p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} lying on the boundary of the intersection, and can therefore be found by tracing this boundary using Algorithm 1 . For each a\in\{0,1\} we have \displaystyle\E[\ell(R,Y)|a] \displaystyle=P(R=1|a)\,P(Y=0|R=1,a)\ell_{10} \displaystyle\quad+P(R=0|a)\,P(Y=1|R=0,a)\ell_{01} \displaystyle=\mu^{a}(1-p^{a})\ell_{10}+(1-\mu^{a})q^{a}\ell_{01} \displaystyle=\pi^{a}\ell_{01}+\mu^{a}\ell_{10}-\mu^{a}p^{a}(\ell_{01}+\ell_{10}), where the last equality follows from ( 2 ). Define the aggregate parameters \pi:=P(Y=1)=P(A=0)\pi^{0}+P(A=1)\pi^{1} and \mu:=P(R=1)=P(A=0)\mu^{0}+P(A=1)\mu^{1} . Under sufficiency, that is, when p^{0}=p^{1}=p and q^{0}=q^{1}=q , we get L=\E\big[\E[\ell(R,Y)|A]\big]=\pi\ell_{01}+\mu\ell_{10}-\mu p(\ell_{01}+\ell_{10}). (12) In addition, as in the unconstrained setting, \pi=\mu p+(1-\mu)q , so for a fixed \mu , all feasible pairs (p,q) attained by classifiers with P(R=1)=\mu lie on the same line that passes through (\pi,\pi) . Since \ell_{01}+\ell_{10}>0 , ( 12 ) implies that, for any fixed \mu , the expected loss is minimized by maximizing p . Consequently, the loss-minimizing pair (p,q) must lie on the boundary of the feasible set, which under sufficiency is precisely \partial(\mathcal{C}^{0}\cap\mathcal{C}^{1}) . Finally, for any point (\pi,\pi)\neq(p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} , Equation ( 2 ) gives \mu=(\pi-q)/(p-q) . Substituting this expression into ( 12 ) yields L=\pi\ell_{01}+\frac{\pi-q}{p-q}\big(\ell_{10}-p(\ell_{01}+\ell_{10})\big). (13) Using Algorithm 1 to trace the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} , we can search for the exact minimizer of ( 13 ) on each interval J_{k,l,i} (and the vertical segment at p=p_{\mathrm{max}} , if it exists). As shown in Appendix G , this reduces to solving a quadratic equation and evaluating ( 13 ) at the interval endpoints, as well as at any interior critical points. 6 Minimizing Deviation from Separation Sufficiency and separation (equalized odds) are known to be incompatible, except in trivial cases ( 6 ; 11 ) . Nevertheless, among classifiers that satisfy sufficiency, the extent to which separation is violated can vary. In this section, we adopt the deviation-from-separation measure \Delta_{\mathrm{sep}}(R) introduced in ( 4 ) , and study classifiers that satisfy predictive parity while minimizing \Delta_{\mathrm{sep}}(R) . We show that the optimal classifier is attained on the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} , and can therefore be found using Algorithm 1 . There is no guarantee that a classifier minimizing \Delta_{\mathrm{sep}}(R) is also optimal with respect to any particular loss function. Nevertheless, in practice we find that its accuracy is often comparable to that of the optimal classifier. Importantly, this analysis enables practitioners to explicitly compare the loss-optimal solution with a classifier that minimizes deviation from separation, and to select between these two different objectives based on application-specific considerations. The deviation from separation, measured using total variation divergence, 2 2 2 \operatorname{TV}(P,Q):=\frac{1}{2}\sum\nolimits_{x}|P(x)-Q(x)| . is defined as \Delta_{\mathrm{sep}}(R):=\E_{A,Y}\operatorname{TV}\big(P(R|A,Y),\,P(R|Y)\big). This quantity measures the average discrepancy, across subgroups, between the subgroup-specific and aggregate true positive and false positive rates. In particular, separation—that is, in the binary case, equalized odds—requires these rates to coincide across subgroups, and hence any classifier satisfying equalized odds has \Delta_{\mathrm{sep}}(R)=0 . In Appendix H we show that \Delta_{\mathrm{sep}}(R)=K\left(\frac{1-\mu}{p-\pi}-\frac{\mu(p-\pi)}{\pi(1-\pi)}\right), (14) where K:=2P(A=1)\,P(A=0)\,|\pi^{1}-\pi^{0}|\geq 0 , and \mu and \pi are the aggregate parameters defined above. Differentiating with respect to p while holding \mu fixed yields \frac{d}{dp}\Delta_{\mathrm{sep}}(R)=K\left(-\frac{1-\mu}{(p-\pi)^{2}}-\frac{\mu}{\pi(1-\pi)}\right)\leq 0, which implies that, for any fixed \mu , the deviation from separation is either constant or minimized by maximizing p . Consequently, a feasible pair (p,q) minimizing \Delta_{\mathrm{sep}}(R) must lie on the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} . As in the loss-minimization case, Algorithm 1 can be used to search for the exact minimizer of ( 14 ) along the boundary. Appendix H shows that this reduces to solving a quadratic equation and evaluating \Delta_{\mathrm{sep}}(R) at the endpoints of each interval J_{k,l,i} , as well as at any interior critical points. 7 Example Use Case As a representative use case, we apply our method to the COMPAS recidivism dataset introduced by ProPublica ( 1 ) . The dataset contains discrete risk scores S (deciles) produced by the COMPAS system, together with two-year recidivism outcomes Y , for defendants assessed in Broward County, Florida. The protected attribute A is defined by race, with A=0 denoting Caucasian and A=1 non-Caucasian defendants. The COMPAS scores are known to approximately satisfy sufficiency ( 6 ) , but they are not properly group-calibrated, as the reported scores take values in \{1,\dots,10\} rather than probabilities. To address this, we randomly split the data (stratified by score bin), using 20\% of the samples to estimate the empirical calibration curve P(Y=1|S) and the remaining 80\% to estimate the group-specific score distributions P(S|A) . We then trace the boundaries of the two subgroup-feasible regions, corresponding to the race attribute, using Algorithm 1 . The resulting feasible regions and their intersection are shown in Figure 3 . Figure 3 : COMPAS dataset feasible regions. The dots on the boundaries of the feasible regions correspond to deterministic threshold classifiers, with the leftmost dot representing the rule R=1 iff S\geq 1 and the rightmost dot R=1 iff S\geq 10 . The point that maximizes overall accuracy (marked by a cross) lies almost exactly on the seventh breakpoint of the Caucasian group’s feasible region \mathcal{C}^{0} (blue) and the sixth breakpoint of the non-Caucasian group’s feasible region \mathcal{C}^{1} (orange). The calibrated scores obtained in this way are not necessarily monotone in the original bin ordering, and therefore our results are not directly comparable to the thresholding strategies analyzed in ( 1 ; 6 ) . Using 0 – 1 loss and the objective function derived in Appendix G , we find that the point on the boundary of the intersection that maximizes overall accuracy lies very close to a point corresponding to deterministic classifiers for both groups. However, the induced selection rules differ across groups: for the Caucasian group, the optimal classifier selects all individuals with S\geq 7 , whereas for the non-Caucasian group it selects those with S\geq 6 . This illustrates the necessity of group-specific decision rules in order to satisfy sufficiency. The overall accuracy attained at the fair optimum is 0.677 , which is close to the unconstrained optimum of 0.681 . In this example, the classifier that minimizes the deviation from separation \Delta_{\mathrm{sep}}(R) coincides with the accuracy-maximizing fair classifier. Appendix A Additional Derivations A.1 Mixture \for Using ( 2 ), we have \displaystyle(1-\mu)\for(R^{\eta}) \displaystyle=\pi-\mu\ppv(R^{\eta}) \displaystyle=\pi-\mu\big(\eta p+(1-\eta)\pi\big) \displaystyle=(1-\mu)\pi-\eta\mu p+\eta\mu\pi \displaystyle\underset{*}{=}(1-\mu)\pi-\eta\big(\pi-(1-\mu)q\big)+\eta\mu\pi \displaystyle=(1-\mu)\pi-\eta(1-\mu)\pi+\eta(1-\mu)q \displaystyle=(1-\eta)(1-\mu)\pi+\eta(1-\mu)q, where (*) follows from ( 2 ) applied to R , namely \mu p=\pi-(1-\mu)q . Dividing both sides by (1-\mu) yields \for(R^{\eta})=\eta q+(1-\eta)\pi. A.2 Continuity of p^{*}(\mu) To prove the continuity of p^{*}(\mu) on the entire interval (0,1) , it suffices to verify right continuity at the left endpoints of the subintervals I_{k}=(\mu_{k-1},\mu_{k}] for k>1 . Let \mu\in I_{k+1} for some k1 . By ( 6 ), p=p(\mu)=s_{k}+\frac{c_{k}}{\mu}>s_{k} , since c_{k}>0 . Inverting this relation yields \mu=\frac{c_{k}}{p-s_{k}}. (15) Now, substituting into ( 2 ) gives \pi=\mu p+(1-\mu)q=\frac{c_{k}p+(p-s_{k}-c_{k})q}{p-s_{k}}, so that (p-s_{k}-c_{k})q=(\pi-c_{k})p-s_{k}\pi. Therefore, q=\frac{(\pi-c_{k})p-s_{k}\pi}{p-s_{k}-c_{k}}, which is well defined, since \mu<1 implies p-s_{k}>c_{k} by ( 15 ). Appendix B Proof of Theorem 3.3 Theorem 3.3 (Restated) . Let 0<\mu<1 and define k^{*}=k^{*}(\mu):=\min\{\,k\mid\sum_{i\leq k}P(s_{i})\geq\mu\,\} . Then the pair (p^{*}(\mu),q^{*}(\mu)) is attained by R^{*}=R^{*}(S;\mu) , defined according to P(R^{*}=1|s_{i})=\begin{cases}1&ik^{*}.\end{cases} (16) Proof. From Equations ( 3 ) and ( 4 ) we note that the problem of finding a selection rule that maximizes p for a given \mu is equivalent to the fractional knapsack problem with the constraints \sum\nolimits_{i\in[m]}x_{i}\,P(s_{i})=\mu and x_{i}\in[0,1] for all i\in[m] , and the maximization objective \sum\nolimits_{i\in[m]}x_{i}\,v_{i} , where the item values are given by v_{i}:=s_{i}\,P(s_{i}) . The selection rule P(R^{*}|s_{i}) is exactly the greedy algorithm’s solution to this problem ( 8 ) , as we assumed the scores are in descending order. Finally, from ( 2 ), it follows that for any fixed 0<\mu<1 , q is a strictly decreasing function of p , meaning that q^{*}(\mu) must be attained together with p^{*}(\mu) . ∎ Appendix C Proof of Theorem 3.4 Theorem 3.4 (restated) . The closure of the nontrivial boundary curve of \mathcal{C} consists of a continuous nondecreasing curve q(p) , defined piecewise by ( 7 ) on each interval J_{k}\subset[\pi,s_{\mathrm{max}}) , together with a vertical segment at (s_{\mathrm{max}},q) for q\in[q(s_{\mathrm{max}}^{-}),\pi] . Proof. Let (p,q) lie on the nontrivial boundary of \mathcal{C} . Then there exists \mu\in(0,1) such that (p,q)=(p^{*}(\mu),q^{*}(\mu)) . If \mu\in I_{1}=(0,\mu_{1}] , then c_{1}=0 and ( 6 ) gives p=s_{1}=s_{\mathrm{max}} . Substituting into ( 2 ) and rearranging yields q=q^{*}(\mu)=\frac{\pi-\mu s_{\mathrm{max}}}{1-\mu}. Differentiating with respect to \mu gives \frac{d}{d\mu}q=\frac{-s_{\mathrm{max}}(1-\mu)+\pi-\mu s_{\mathrm{max}}}{(1-\mu)^{2}}=\frac{\pi-s_{\mathrm{max}}}{(1-\mu)^{2}}. Since m>1 and \E[S]=\pi by ( 1 ), we have s_{\mathrm{max}}>\pi , and thus q is strictly decreasing in \mu on I_{1} . At the endpoints, \displaystyle q^{*}(0^{+}) \displaystyle=\frac{\pi-0\cdot s_{\mathrm{max}}}{1-0}=\pi, \displaystyle q^{*}(\mu_{1}) \displaystyle=\frac{\pi-P(s_{1})\,s_{\mathrm{max}}}{1-P(s_{1})}=:q_{1}, where q_{1}<\pi since P(s_{1})>0 and s_{\mathrm{max}}>\pi . Hence the closure of the nontrivial boundary includes the vertical segment (s_{\mathrm{max}},q) for q\in[q_{1},\pi] . If \mu\in I_{k} for some k>1 , then p\in J_{k} by construction, and ( 7 ) gives q=q(p)=\frac{(\pi-c_{k})p-s_{k}\pi}{p-s_{k}-c_{k}}. Differentiating with respect to p yields \frac{d}{dp}q(p)=\frac{(\pi-c_{k})(p-s_{k}-c_{k})-(\pi-c_{k})p+s_{k}\pi}{(p-s_{k}-c_{k})^{2}}=\frac{-c_{k}(\pi-s_{k}-c_{k})}{(p-s_{k}-c_{k})^{2}}, (17) so the sign of \frac{d}{dp}q(p) on J_{k} is determined by \pi-s_{k}-c_{k} . Now, for all k\in[m] , \displaystyle\pi-s_{k}-c_{k} \displaystyle=\sum\nolimits_{i\in[m]}s_{i}P(s_{i})-s_{k}-\sum\nolimits_{ik , it follows that \pi-s_{k}-c_{k}<0 for all k0 for k>1 , ( 17 ) implies that q(p) is strictly increasing on J_{k} for 10 . While the utility of constant classification is debatable, one could still consider constant behavior on part of the population, provided the fairness constraint is satisfied. We now briefly characterize how such degenerate cases fit into our framework. First, we extend the definition of feasibility to include constant classifiers: Definition D.1 (Feasibility with degenerate classifiers) . Given a joint distribution P(Y,S) , we say that a pair (p,q)\in[0,1]^{2} is feasible if there exists a randomized binary classifier R=R(S) with selection rate \mu:=P(R=1)\in[0,1] , such that P(Y=1,R=1)=\mu p and P(Y=1,R=0)=(1-\mu)q . Note that when 0<\mu<1 , the definition above reduces to Definition 3.1 , since \ppv(R)=\frac{1}{\mu}P(Y=1,R=1) and \for(R)=\frac{1}{1-\mu}P(Y=1,R=0) . The identity \pi=\mu p+(1-\mu)q ( 2 ) remains valid even in the extreme cases \mu\in\{0,1\} . Therefore, relying on the standing convention that q\leq\pi\leq p , we obtain that if \mu=0 , then q=\pi and p\in[\pi,1] is arbitrary, whereas if \mu=1 , then p=\pi and q\in[0,\pi] is arbitrary. Geometrically, this implies that allowing degenerate classifiers adds two boundary segments to the feasible region, extending horizontally and vertically from the point (\pi,\pi) . If m=1 , meaning that S is constant, then any classifier R=R(S) is constant as well, and the feasible region consists only of these degenerate edges. If m>1 , however, Theorem 3.4 guarantees the feasibility of the point (s_{\mathrm{max}},q(s_{\mathrm{max}}^{-})) , where s_{\mathrm{max}}>\pi and q(s_{\mathrm{max}}^{-})=\frac{\pi-P(s_{1})s_{\mathrm{max}}}{1-P(s_{1})}<\pi (see Appendix C ). This point does not lie on either degenerate segment, and in fact the structure of \partial\mathcal{C} described in Theorem 3.4 implies that \mathcal{C} has a nonempty interior. When considering sufficiency with degenerate classifiers, we must therefore include the degenerate edges in the intersection analysis. For example, using the notation of Section 4 , suppose that (p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} lies on the horizontal degenerate edge of \mathcal{C}^{0} but in the interior of \mathcal{C}^{1} , so that \mu^{0}=0 and 0<\mu^{1}<1 . Then P(R=1,A=0)=0 , but conditioning on R=0 is valid, and by Definition D.1 we have \displaystyle P(Y=1|R=0,A=0) \displaystyle=\frac{P(Y=1,R=0|A=0)}{P(R=0|A=0)}=\frac{(1-\mu^{0})q}{1-\mu^{0}}=q, \displaystyle P(Y=1|R=0,A=1) \displaystyle=\frac{P(Y=1,R=0|A=1)}{P(R=0|A=1)}=\frac{(1-\mu^{1})q}{1-\mu^{1}}=q. Hence P(Y=1|R=0,A=a)=P(Y=1|R=0)=q for both groups, and sufficiency is satisfied by ( 19 ). By ( 8 ), an intersection between the nontrivial part of \mathcal{C}^{a} and a degenerate edge of \mathcal{C}^{b} occurs if s_{\mathrm{min}}^{a}\leq\pi^{b}\leq s_{\mathrm{max}}^{a} and \pi^{a}\neq\pi^{b} . For instance, if s_{\mathrm{min}}^{1}\leq\pi^{0}<\pi^{1} , then the horizontal degenerate edge of \mathcal{C}^{0} intersects \mathcal{C}^{1} along the segment (p,\pi^{0}) for p\in[\pi^{1},p_{\mathrm{max}}^{1}] , where p_{\mathrm{max}}^{1} is defined as in ( 11 ). Finally, note that once degenerate classifiers are allowed, the intersection \mathcal{C}^{0}\cap\mathcal{C}^{1} is always nonempty, albeit in a trivial way. Assuming \pi^{0}<\pi^{1} , the point (\pi^{1},\pi^{0}) lies simultaneously on the horizontal degenerate edge of \mathcal{C}^{0} and the vertical degenerate edge of \mathcal{C}^{1} . The classifier attaining this point is R=A , which simply predicts the subgroup identity. Interpreted probabilistically, this corresponds to predicting the subgroup base rate for every individual. Appendix E Computing p_{\mathrm{max}} and q_{\mathrm{min}} Assume without loss of generality that \pi^{0}\leq\pi^{1} and that \mathcal{C}^{0}\cap\mathcal{C}^{1}\neq\varnothing . Then ( 9 ) implies that s_{\mathrm{min}}^{1}<\pi^{0} and \pi^{1}p_{\mathrm{max}}^{1} must satisfy q>\pi^{0} , and therefore, by ( 9 ), does not belong to the intersection \mathcal{C}^{0}\cap\mathcal{C}^{1} . Consequently, for all (p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} we have p\leq p_{\mathrm{max}}:=\min\{s_{\mathrm{max}}^{0},p_{\mathrm{max}}^{1}\} , with equality attained on \partial\mathcal{C}^{0} if p_{\mathrm{max}}=s_{\mathrm{max}}^{0} , and on \partial\mathcal{C}^{1} if p_{\mathrm{max}}=p_{\mathrm{max}}^{1} . We next provide an algorithmic way to compute p_{\mathrm{max}}^{1} , based on the piecewise characterization of \partial\mathcal{C}^{1} . Recall that the boundary curve of \mathcal{C}^{1} consists of a constant segment q^{1}(p)\equiv s_{\mathrm{min}}^{1} on J_{m^{1}} , a strictly increasing part on the intervals J_{k} for 1k}s_{i}P(s_{i})}{\sum\nolimits_{i>k}P(s_{i})}. In particular, q^{1}_{m^{1}-1}=s^{1}_{m^{1}}=s_{\mathrm{min}}^{1} , so the intervals J_{k} for 10 . By ( 13 ), the expected loss of a classifier R that attains a pair (\pi,\pi)\neq(p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} is L(p,q):=\E[\ell(R,Y)]=\pi\ell_{01}+\frac{\pi-q}{p-q}\big(\ell_{10}-p(\ell_{01}+\ell_{10})\big), where \pi:=P(A=0)\pi^{0}+P(A=1)\pi^{1} is the aggregate base-rate of Y . Moreover, ( 12 ) implies that the minimum of L(p,q) is achieved on the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} . In this appendix we show how to find the minimizer of L(p,q) using Algorithm 1 . First, we prove a simple property of L on line segments: Proposition G.1 . Let (p_{1},q_{1}) and (p_{2},q_{2}) be the endpoints of a line segment contained in \mathcal{C}^{0}\cap\mathcal{C}^{1} . If the segment is vertical ( p_{1}=p_{2}=p ) or horizontal ( q_{1}=q_{2}=q ), then the minimum of L(p,q) on the segment is attained at one of the endpoints. Proof. Assume first that p_{1}=p_{2}=p . Differentiating ( 13 ) with respect to q gives \displaystyle\frac{dL}{dq}(q) \displaystyle=\big(\ell_{10}-p(\ell_{01}+\ell_{10})\big)\frac{-(p-q)+(\pi-q)}{(p-q)^{2}} \displaystyle=\big(\ell_{10}-p(\ell_{01}+\ell_{10})\big)\frac{\pi-p}{(p-q)^{2}}, whose sign is constant in q . Conversely, if q_{1}=q_{2}=q , differentiating with respect to p gives \displaystyle\frac{dL}{dp}(p) \displaystyle=(\pi-q)\frac{-(\ell_{01}+\ell_{10})(p-q)-\big(\ell_{10}-p(\ell_{01}+\ell_{10})\big)}{(p-q)^{2}} \displaystyle=(\pi-q)\frac{(\ell_{01}+\ell_{10})q-\ell_{10}}{(p-q)^{2}}, whose sign is constant in p . In either case, L(p,q) is monotonic (or constant) along the segment and attains its minimum at an endpoint. ∎ Let (p,q)\in\partial(\mathcal{C}^{0}\cap\mathcal{C}^{1}) . As shown in Section 4.2 , either (p,q)\in J_{k,l,i} for some k,l,i , or it lies on a vertical segment at p=p_{\mathrm{max}} . Assume that (p,q)\in J_{k,l,i} and, without loss of generality, assume that the active boundary on that interval is \partial\mathcal{C}^{0} (otherwise, swap the roles of groups 0 and 1, and interchange k and l ). Then q=q^{0}(p) is given by ( 7 ) and we obtain L(p,q)=L(p)=\pi\ell_{01}+\frac{D^{0}_{k}p+E^{0}_{k}}{(p-\pi^{0})(p-s^{0}_{k})}\big(\ell_{10}-p(\ell_{01}+\ell_{10})\big), where \displaystyle D^{0}_{k} \displaystyle:=\pi-\pi^{0}+c^{0}_{k}, \displaystyle E^{0}_{k} \displaystyle:=(\pi^{0}-\pi)s^{0}_{k}-c^{0}_{k}\pi and k is the respective index of J_{k,l,i} . Differentiating with respect to p yields \frac{dL}{dp}(p)=\frac{F^{0}_{k}p^{2}+G^{0}_{k}p+H^{0}_{k}}{(p-\pi^{0})^{2}(p-s^{0}_{k})^{2}}, where \displaystyle F^{0}_{k} \displaystyle:=(\ell_{01}+\ell_{10})\big(D^{0}_{k}(\pi^{0}+s^{0}_{k})+E^{0}_{k}\big)-\ell_{10}D^{0}_{k}, \displaystyle G^{0}_{k} \displaystyle:=-2(\ell_{01}+\ell_{10})D^{0}_{k}\pi^{0}s^{0}_{k}-2\ell_{10}E^{0}_{k}, \displaystyle H^{0}_{k} \displaystyle:=\big(\ell_{10}D^{0}_{k}-(\ell_{01}+\ell_{10})E^{0}_{k}\big)\pi^{0}s^{0}_{k}+\ell_{10}E^{0}_{k}(\pi^{0}+s^{0}_{k}). Therefore, the minimum of L(p,q) on J_{k,l,i} is attained at one of the endpoints or at a real root of \Psi^{0}_{k}(p):=F^{0}_{k}p^{2}+G^{0}_{k}p+H^{0}_{k} in the interior of J_{k,l,i} . Since Algorithm 1 iterates over all the intervals J_{k,l,i} , it suffices to evaluate L(p,q) at the internal roots of \Psi^{0}_{k}(p) and the right endpoint of each interval, as well as at the left endpoint of the leftmost interval, that is (\max\{\pi^{0},\pi^{1}\},q_{\mathrm{min}}) (see Appendix E for the definition of q_{\mathrm{min}} and an algorithm to compute it). Finally, if p_{\mathrm{max}}=\min\{s_{\mathrm{max}}^{0},s_{\mathrm{max}}^{1}\} , the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} contains a vertical segment at p=p_{\mathrm{max}} , and it is left to evaluate L(p,q) there. By Proposition G.1 , it suffices to evaluate L(p,q) at the endpoints of the vertical segment, namely (p_{\mathrm{max}},q(p_{\mathrm{max}}^{-})) and (p_{\mathrm{max}},\pi^{0}) . The lower endpoint coincides with the right endpoint of the rightmost interval J_{k,l,i} , hence it suffices to check L(p_{\mathrm{max}},\pi^{0}) . Appendix H Minimizing Deviation from Separation The deviation from separation of a classifier R , using total variation divergence, is defined as ( 4 ) \displaystyle\Delta_{\mathrm{sep}}(R) \displaystyle:=\E_{A,Y}\operatorname{TV}\big(P(R|A,Y),\,P(R|Y)\big) \displaystyle=\sum_{a\in\{0,1\}}\sum_{y\in\{0,1\}}P(a)P(y|a)\operatorname{TV}\big(P(R|a,y),\,P(R|y)\big), where \displaystyle\operatorname{TV}\big(P(R|a,y),\,P(R|y)\big) \displaystyle:=\frac{1}{2}\sum_{r\in\{0,1\}}|P(r|a,y)-P(r|y)| \displaystyle=|P(R=1|a,y)-P(R=1|y)|. Let (\pi,\pi)\neq(p,q)\in\mathcal{C}^{0}\cap\mathcal{C}^{1} be attained by R , then for all a\in\{0,1\} , following Bayes’ rule, \displaystyle\tpr(R) \displaystyle:=P(R=1|Y=1)=\frac{P(R=1)}{P(Y=1)}P(Y=1|R=1)=\frac{\mu}{\pi}p, \displaystyle\tpr^{a}(R) \displaystyle:=P(R=1|Y=1,a)=\frac{P(R=1|a)}{P(Y=1|a)}P(Y=1|R=1,a)=\frac{\mu^{a}}{\pi^{a}}p, where we used the equality p^{a}=p , since (p,q) belongs to the intersection of the feasible sets. Similarly, \displaystyle\fpr(R) \displaystyle:=P(R=1|Y=0)=\frac{P(R=1)}{P(Y=0)}P(Y=0|R=1)=\frac{\mu}{1-\pi}(1-p), \displaystyle\fpr^{a}(R) \displaystyle:=P(R=1|Y=0,a)=\frac{P(R=1|a)}{P(Y=0|a)}P(Y=0|R=1,a)=\frac{\mu^{a}}{1-\pi^{a}}(1-p). Therefore, \E_{Y|a}\operatorname{TV}\big(P(R|Y,a),\,P(R|Y)\big)=\pi^{a}p\left|\frac{\mu^{a}}{\pi^{a}}-\frac{\mu}{\pi}\right|+(1-\pi^{a})(1-p)\left|\frac{\mu^{a}}{1-\pi^{a}}-\frac{\mu}{1-\pi}\right|. (20) By ( 2 ), \mu=\frac{\pi-q}{p-q} and \mu^{a}=\frac{\pi^{a}-q}{p-q} , so \displaystyle\mu^{a}=1-\frac{p-\pi^{a}}{p-q}=1-\frac{p-\pi^{a}}{p-\pi}(1-\mu)=\frac{(\pi^{a}-\pi)+\mu(p-\pi^{a})}{p-\pi}. Substituting this expression inside the terms of ( 20 ) gives \displaystyle\pi^{a}p\left|\frac{\mu^{a}}{\pi^{a}}-\frac{\mu}{\pi}\right| \displaystyle=\frac{p}{\pi(p-\pi)}\big|(\pi^{a}-\pi)(\pi-\mu p)\big|, \displaystyle(1-\pi^{a})(1-p)\left|\frac{\mu^{a}}{1-\pi^{a}}-\frac{\mu}{1-\pi}\right| \displaystyle=\frac{1-p}{(1-\pi)(p-\pi)}\big|(\pi^{a}-\pi)\big((1-\pi)-\mu(1-p)\big)\big|. Since \pi-\mu p=(1-\mu)q\geq 0 and (1-\pi)-\mu(1-p)=(1-\mu)(1-q)\geq 0 , these terms can be taken out of the absolute values. Substituting into ( 20 ) and rearranging yields \E_{Y|a}\operatorname{TV}\big(P(R|Y,a),\,P(R|Y)\big)=|\pi^{a}-\pi|\left(\frac{1-\mu}{p-\pi}-\frac{\mu(p-\pi)}{\pi(1-\pi)}\right). Now, the only term that depends on a is |\pi^{a}-\pi| and we define \displaystyle K:=\E_{A}|\pi^{A}-\pi| \displaystyle=P(A=0)|\pi^{0}-\pi|+P(A=1)|\pi^{1}-\pi| \displaystyle=P(A=0)|\pi^{0}-P(A=0)\pi^{0}-P(A=1)\pi^{1}|+P(A=1)|\pi^{1}-P(A=0)\pi^{0}-P(A=1)\pi^{1}| \displaystyle=P(A=0)P(A=1)|\pi^{0}-\pi^{1}|+P(A=1)P(A=0)|\pi^{1}-\pi^{0}| \displaystyle=2P(A=0)P(A=1)|\pi^{0}-\pi^{1}|\geq 0. Therefore, \Delta_{\mathrm{sep}}(R)=K\left(\frac{1-\mu}{p-\pi}-\frac{\mu(p-\pi)}{\pi(1-\pi)}\right). (21) As shown in Section 6 , differentiating with respect to p (holding \mu fixed) we obtain \frac{d}{dp}\Delta_{\mathrm{sep}}(R)=K\left(-\frac{1-\mu}{(p-\pi)^{2}}-\frac{\mu}{\pi(1-\pi)}\right)\leq 0, so for a fixed \mu the deviation from separation is constant or minimized by maximizing p , implying that a minimizer is attained on the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} . Finally, we substitute for \mu=\frac{\pi-q}{p-q} in ( 21 ), so \Delta_{\mathrm{sep}}(R)=\Delta_{\mathrm{sep}}(p,q)=\tilde{K}\frac{\pi(1-p)+q(p-\pi)}{p-q}, (22) where \tilde{K}:=\frac{K}{\pi(1-\pi)}=\frac{2P(A=0)P(A=1)|\pi^{0}-\pi^{1}|}{\pi(1-\pi)}. We now show how the minimizer of \Delta_{\mathrm{sep}}(R) can be found using Algorithm 1 , following the same steps of Appendix G for attaining the loss minimizer. First, similar to the case with expected loss (see Proposition G.1 ), \Delta_{\mathrm{sep}}(R) also behaves nicely on line segments: Proposition H.1 . Let (p_{1},q_{1}) and (p_{2},q_{2}) be the endpoints of a line segment contained in \mathcal{C}^{0}\cap\mathcal{C}^{1} . If the segment is vertical ( p_{1}=p_{2}=p ) or horizontal ( q_{1}=q_{2}=q ), then the minimum of \Delta_{\mathrm{sep}}(p,q) on the segment is attained at one of the endpoints. Proof. Assume first that p_{1}=p_{2}=p . Differentiating ( 22 ) with respect to q gives \frac{d\Delta_{\mathrm{sep}}}{dq}(q)=\tilde{K}\frac{p^{2}-2\pi p+\pi}{(p-q)^{2}} whose sign is constant in q . Conversely, if q_{1}=q_{2}=q , differentiating with respect to p gives \frac{d\Delta_{\mathrm{sep}}}{dp}(p)=-\tilde{K}\frac{q^{2}-2\pi q+\pi}{(p-q)^{2}} whose sign is constant in p . In either case, \Delta_{\mathrm{sep}}(p,q) is monotonic (or constant) along the segment and attains its minimum at an endpoint. ∎ Let (p,q)\in\partial(\mathcal{C}^{0}\cap\mathcal{C}^{1}) . Assume that (p,q)\in J_{k,l,i} and, without loss of generality, assume that the active boundary on that interval is \partial\mathcal{C}^{0} . Substituting q=q^{0}(p) in ( 22 ) we obtain \Delta_{\mathrm{sep}}(p,q)=\Delta_{\mathrm{sep}}(p)=\tilde{K}\frac{\tilde{A}^{0}_{k}p^{2}+\tilde{B}^{0}_{k}p+\tilde{C}^{0}_{k}}{(p-\pi^{0})(p-s^{0}_{k})}, where \displaystyle\tilde{A}^{0}_{k} \displaystyle:=\pi^{0}-\pi-c^{0}_{k}, \displaystyle\tilde{B}^{0}_{k} \displaystyle:=\pi(2c^{0}_{k}-\pi^{0}+s^{0}_{k}+1)-s^{0}_{k}\pi^{0}, \displaystyle\tilde{C}^{0}_{k} \displaystyle:=\pi(s^{0}_{k}\pi^{0}-s^{0}_{k}-c^{0}_{k}). Differentiating with respect to p yields \frac{d\Delta_{\mathrm{sep}}}{dp}(p)=\tilde{K}\frac{\tilde{D}^{0}_{k}p^{2}+\tilde{E}^{0}_{k}p+\tilde{F}^{0}_{k}}{(p-\pi^{0})^{2}(p-s^{0}_{k})^{2}}, where \displaystyle\tilde{D}^{0}_{k} \displaystyle:=-\tilde{A}^{0}_{k}(\pi^{0}+s^{0}_{k})-\tilde{B}^{0}_{k}, \displaystyle\tilde{E}^{0}_{k} \displaystyle:=2\tilde{A}^{0}_{k}\pi^{0}s^{0}_{k}-2\tilde{C}^{0}_{k}, \displaystyle\tilde{F}^{0}_{k} \displaystyle:=\tilde{B}^{0}_{k}\pi^{0}s^{0}_{k}+\tilde{C}^{0}_{k}(\pi^{0}+s^{0}_{k}). The minimum of \Delta_{\mathrm{sep}}(p,q) on J_{k,l,i} is attained at one of the endpoints or at a real root of \tilde{\Psi}^{0}_{k}(p):=\tilde{D}^{0}_{k}p^{2}+\tilde{E}^{0}_{k}p+\tilde{F}^{0}_{k} in the interior of J_{k,l,i} . Since Algorithm 1 iterates over all the intervals J_{k,l,i} , it suffices to evaluate \Delta_{\mathrm{sep}}(p,q) at the internal roots of \tilde{\Psi}^{0}_{k}(p) and the right endpoint of each interval, as well as at the left endpoint of the leftmost interval, that is (\max\{\pi^{0},\pi^{1}\},q_{\mathrm{min}}) (see Appendix E for the definition of q_{\mathrm{min}} and an algorithm to compute it). Finally, if p_{\mathrm{max}}=\min\{s_{\mathrm{max}}^{0},s_{\mathrm{max}}^{1}\} , the boundary of \mathcal{C}^{0}\cap\mathcal{C}^{1} contains a vertical segment at p=p_{\mathrm{max}} , and it is left to evaluate \Delta_{\mathrm{sep}}(p,q) there. By Proposition H.1 , it suffices to evaluate \Delta_{\mathrm{sep}}(p,q) at the endpoints of the vertical segment, namely (p_{\mathrm{max}},q(p_{\mathrm{max}}^{-})) and (p_{\mathrm{max}},\pi^{0}) . The lower endpoint coincides with the right endpoint of the rightmost interval J_{k,l,i} , hence it suffices to check \Delta_{\mathrm{sep}}(p_{\mathrm{max}},\pi^{0}) .