Year: 2020

Abstract:
Fairness of machine learning algorithms has been of increasing interest. In order to suppress or eliminate discrimination in prediction, various notions as well as approaches to impose fairness have been proposed. However, in different scenarios, whether or not the chosen notion of fairness can always be attained, even if with unlimited amount of data, is not well addressed. In this paper, focusing on the Equalized Odds notion of fairness, we consider the attainability of this criterion, and furthermore, if attainable, the optimality of the prediction performance under various settings. In particular, for classification with a deterministic prediction function of the input, we give the condition under which Equalized Odds can hold true; if randomized prediction is acceptable, we show that under mild assumptions, fair classifiers can always be derived. Moreover, we prove that compared to enforcing fairness by post-processing, one can always benefit from exploiting all available features during training and get better prediction performance while remaining fair. However, for regression tasks, Equalized Odds is not always attainable if certain conditions on the joint distribution of the features and the target variable are not met. This indicates the inherent difficulty in achieving fairness in certain cases and suggests a broader class of prediction methods might be needed for fairness.

heading: 1 INTRODUCTION
text: As machine learning models become widespread in automated decision making systems, apart from the efficiency and accuracy of the prediction, their potential social consequence also gains increasing attention. To date, there is ample evidence that machine learning models have resulted in discrimination against certain groups of individuals under many circumstances, for instance, the discrimination in ad delivery when searching for names that can be predictive of the race of individual (Sweeney, 2013); the gender discrimination in job-related ads push (Datta et al., 2015); stereotypes associated with gender in word embeddings (Bolukbasi et al., 2016); the bias against certain ethnicities in the assessment of recidivism risk (Angwin et al., 2016).
The call for accountability and fairness in machine learning has motivated various (statistical) notions of fairness. The Demographic Parity criterion (Calders et al., 2009) requires the independence between prediction (e.g., of a classifier) and the protected feature (sensitive attributes of an individual, e.g., gender, race). Equalized Odds (Hardt et al., 2016), also known as Error-rate Balance (Chouldechova, 2017), requires the output of a model be conditionally independent of protected feature(s) given the ground truth of the target. Predictive Rate Parity (Zafar et al., 2017a), on the other hand, requires the actually proportion of positives (negatives) in the original data for positive (negative) predictions should match across groups (well-calibrated).
On the theoretical side, results have been reported regarding relationships among fairness notions. It has been independently shown that if base rates of true positives differ among groups, then Equalized Odds and Predictive Rate Parity cannot be achieved simultaneously for non-perfect predictors (Kleinberg et al., 2016; Chouldechova, 2017). Any two out of three among Demographic Parity, Equalized Odds, and Predictive Rate Parity are incompatible with each other (Barocas et al., 2017). At the interface of privacy and fairness, the impossibility of achieving both Differential Privacy (Dwork et al., 2006) and Equal Opportunity (Hardt et al., 2016) while maintaining non-trivial accuracy is also established (Cummings et al., 2019).
In practice, one can broadly categorize computational procedures to derive a fair predictor into three types: pre-processing approaches (Calders et al., 2009; Dwork et al., 2012; Zemel et al., 2013; Zhang et al., 2018; Madras et al., 2018; Creager et al., 2019; Zhao et al., 2020), in-processing approaches (Kamishima et al., 2011; Pérez-Suay et al., 2017; Zafar et al., 2017a;b; Donini et al., 2018; Song et al., 2019; Mary et al., 2019; Baharlouei et al., 2020), and post-processing approaches (Hardt et al., 2016; Fish et al., 2016; Dwork et al., 2018). In accord with the fairness notion of interest, a pre-processing approach first maps the training data to a transformed space to remove discriminatory information between protected feature and target, and then pass on the data to make prediction. In direct contrast, a post-processing approach treats the off-the-shelf predictor(s) as uninterpretable black-box(es), and imposes fairness by outputting a function of the original prediction. For inprocessing approaches, various kinds of regularization terms are proposed so that one can optimize the utility function while suppressing the discrimination at the same time. Approaches based on estimating/bounding causal effect between the protected feature and final target have also been proposed (Kusner et al., 2017; Russell et al., 2017; Zhang et al., 2017; Nabi & Shpitser, 2018; Zhang & Bareinboim, 2018; Chiappa, 2019; Wu et al., 2019).
Focusing on the Equalized-Odds criterion, although various approaches have been proposed to impose the fairness requirement, whether or not it is always attainable is not well addressed. The attainability of Equalized Odds, namely, the existence of the predictor that can score zero violation of fairness in the large sample limit, is an asymptotic property of the fairness criterion. This characterizes a completely different kind of violation of fairness compared to the empirical error bound of discrimination in finite-sample cases. If utilizing a “fair” predictor which is actually biased, the discrimination would become a snake in the grass, making it hard to detect and eliminate. Actually, as we illustrate in this paper, Equalized Odds is not always attainable for regression and even classification tasks, if we use deterministic prediction functions. This calls for alternative definitions in the same spirit as Equalized Odds that can always be achieved under various circumstances. Our contributions are mainly:
• For regression and classification tasks with deterministic prediction functions, we show that Equalized Odds is not always attainable if certain (rather restrictive) conditions on the joint distribution of the features and the target variable are not met.
• Under mild assumptions, for binary classification we show that if randomized prediction is taken into consideration, one can always derive a non-trivial Equalized Odds classifier.
• Considering the optimality of performance under fairness constraint(s), when exploiting all available features, we show that the predictor derived via an in-processing approach would always outperform the one derived via a post-processing approach (unconstrained optimization followed by a post-processing step).

heading: 2 PRELIMINARIES
text: In this section, we first illustrate the difference between prediction fairness and procedure fairness, and then, we present the formal definition of Equalized Odds (Hardt et al., 2016).

heading: 2.1 HIERARCHY OF FAIRNESS
text: Before presenting the formulation of fairness, it is important to see the distinction between different levels of fairness when discussing fair predictors. When evaluating the performance of the proposed fair predictor, it is a common practice to compare the loss (with respect to the utility function of choice, e.g., accuracy for binary classification) computed on target variable and the predicted value. There is an implicit assumption lying beneath this practice: the generating process of the data, which is just describing a real-world procedure, is not biased in any sense (Danks & London, 2017). Only when we treat the target variable (recorded in the dataset) as unbiased can we justify the practice of loss evaluation and the conditioning on target variable when imposing fairness (as we shall see in the definition of Equalized Odds in Equation 1).
One may consider a music school admission example. The music school committee would decide if they admit a student to the violin performance program based on the applicant’s personal information, educational background, instrumental performance, and so on. When evaluating whether or not
the admission is “fair”, there are actually two levels of fairness. First, based on the information at hand, did the committee evaluate the qualification of applicants without bias (How committee evaluate the applicants)? And second, is committee’s procedure of evaluating applicants’ qualification reasonable (How other people view the evaluation procedure used by the committee)?
In this paper, we consider prediction fairness, namely, assuming the data recorded is unbiased, the prediction (made with respect to current reality) itself should not include any biased utilization of information. The fairness with respect to the data generating procedure as well as the potential future influence of the prediction are beyond the scope of this paper.

heading: 2.2 EQUALIZED-ODDS FAIRNESS
text: Hardt et al. (2016) proposed Equalized Odds which requires conditional independence between prediction and protected feature(s) given ground truth of the target. Let us denote the protected feature byA, with domain of valueA, additional (observable) feature(s) byX , with domain of value X , target variable by Y , with domain Y , (not necessarily fair) predictors by Ŷ , and fair predictors by Ỹ . Equalized-Odds fairness requires
Ỹ ⊥ A | Y. (1) For classification tasks, one can conveniently use the probability distribution form:
∀a ∈ A, t, y ∈ Y : P (Ỹ = t | A = a, Y = y) = P (Ỹ = t | Y = y), (2) or more concisely, PỸ |AY (t | a, y) = PỸ |Y (t | y). (3)
For better readability, we also use the formulation in Equation 3 in cases without ambiguity. In the context of binary classification (Y = {0, 1}), Equalized Odds requires that the True Positive Rate (TPR) and False Positive Rate (FPR) of each certain group match population positive rates. Throughout the paper, without loss of generality we assume there is only one protected feature for the purpose of simplifying notation. However, considering the fact that the protected feature can be discrete (e.g., race, gender) or continuous (e.g., the ratio of ethnic group in the population for certain district of a city), we do not assume discreteness of the protected feature. Due to the space limit, we will focus on the illustration and implication of our results and defer all the proofs to the appendix.

heading: 3 FAIRNESS IN REGRESSION MAY NOT BE ATTAINED
text: In this section we consider the attainability of Equalized Odds for regression tasks, namely, whether or not it is possible to find a predictor that is conditionally independent from the protected feature given true value of the target. For linearly Gaussian cases, one can attain Equalized Odds by constraining zero partial correlation between the prediction and the protected feature given target variable (Woodworth et al., 2017). Various regularization terms have also been proposed to suppress discrimination when predicting a continuous target (Berk et al., 2017; Mary et al., 2019). However, whether or not one can always achieve 0-discrimination for regression, even if with an unlimited amount of data, is not clear yet.
If “fair” predictors are deployed without carefully checking the attainability of fairness, the discrimination would become a hidden hazard, making it hard to detect and eliminate. Actually as we will show in this section, even in the simple setup of linearly correlated continuous data, Equalized Odds is not always attainable.

heading: 3.1 UNATTAINABILITY OF EQUALIZED ODDS IN LINEAR NON-GAUSSIAN REGRESSION
text: As stated in Section 2.1, in this paper we consider prediction fairness, and therefore any possible bias introduced by the data generating procedure itself is beyond the scope of the discussion. Consider the situation where the data is generated as following (H is not measured in the dataset):
X = qA+ EX ,
H = bA+ EH ,
Y = cX + dH + EY ,
(4)
where (A,EX , EH , EY ) are mutually independent. In fact, if at most one of EX and E := EY + dEH is Gaussian, then any linear combination of A and X with non-zero coefficients will not be conditionally independent fromA given Y , meaning that it is not possible to achieve Equalized-Odds fairness. Let Z be a linear combination of A and X , i.e., Z = αA + βX = (α + qβ)A + βEX , with linear coefficients α and β, where β 6= 0. In Theorem 3.1, we present the general result in linear non-Gaussian cases, where one cannot achieve the conditional independence between Z and A given Y . Theorem 3.1. (Unattainability of Equalized Odds in the Linear Non-Gaussian Case) Assume that feature X has a causal influence on Y , i.e., c 6= 0 in Equation 4, and that the protected feature A and Y are not independent, i.e., qc + bd 6= 0. Assume pEX and pE are positive on R. Let f1 := log pA, f2 := log pEX , and f3 := log pE . Further assume that f2 and f3 are third-order differentiable. Then if at most one of EX and E is Gaussian, Z is always conditionally dependent on A given Y .
From Theorem 3.1, we see that in linear non-Gaussian cases, any non-zero linear combination of the feature (which is a deterministic function of the input) will not satisfy Equalized Odds. One may wonder whether Equalized Odds can be achieved by nonlinear regression, instead of a linear model. Although a proof with general nonlinear models is rather complicated, our simulation results in Section 5.1 strongly suggest that the unattainability of Equalized Odds persists in nonlinear regression cases.
In light of the unattainability of Equalized Odds for prediction with deterministic functions of A and X , it is desirable to develop general, nonlinear prediction algorithms to produce a probabilistic prediction (i.e., with a certain type of randomness in the prediction). One possible way follows the framework of Generative Adversarial Networks (GANs) (Goodfellow et al., 2014): we use random standard Gaussian noise, in addition to A and X , as input, such that the output will have a specific type of randomness. The parameters involved are learned by minimizing prediction error and enforcing Equalized Odds on the “randomized” output at the same time. Given that this approach is not essential to illustrate the claims made in this paper and that theoretical properties of such nonlinear regression algorithms with randomized output are not straightforward to establish, this is left as future work.

heading: 4 FAIRNESS IN CLASSIFICATION
text: In this section, we consider the attainability of Equalized Odds for binary classifiers (with a deterministic or randomized prediction function), and furthermore, if attainable, the optimality of performance under the fairness criterion. Admittedly, as is already pointed out by Woodworth et al. (2017), we generally cannot have 0-discriminatory predictors with a finite number of samples; instead, one should consider imposing δ-discrimination in practice (δ is the violation of Equalized Odds). However, this does not guarantee nor rule out the possibility of attaining 0-discrimination on population when the sample size goes to infinity.

heading: 4.1 CLASSIFICATION WITH DETERMINISTIC PREDICTION
text: We begin with considering cases when the classification is performed by a deterministic function of the input. In particular, we derive the condition under which Equalized Odds can possibly hold true. Theorem 4.1. Assume that the protected feature A and Y are dependent and that their joint probability P (A, Y ) (for discreteA) or joint probability density p(A, Y ) (for continuousA) is positive for every combination of possible values of A and Y . Further assume that Y is not fully determined by A, and that there are additional featuresX that are not independent of Y . Let the output of the classifier Ỹ be a deterministic function f : A×X → Y . Let S(t)A := {a | ∃x ∈ X s.t. f(a, x) = t}, and S
(t) X|a := {x | f(a, x) = t}. Equalized Odds holds true if and only if the following two conditions
are satisfied:
(i) ∀t ∈ Y : S(t)A = A, (ii) ∀t ∈ Y, ∀a, a′ ∈ A (for continuous X , replace summation with integration accordingly):
Σ x∈S(t) X|a PX|AY (x | a, y) = Σx∈S(t) X|a′ PX|AY (x | a′, y).
Let us take a look at the two conditions. Condition (i) says that within each class determined by the classification function f , A should be able to take all possible values in A. While condition (i) is already pretty restrictive, condition (ii) specifies an even stronger constraint on the relation between the conditional probability PX|AY (x|a, y) (or the conditional probability density pX|AY (x|a, y) for continuous X) and the set S(t)X|a (which is determined by the function f ). By definition S (t) X|a has following properties: (1) for any fixed value of a ∈ A, if t 6= t′, then S(t)X|a ⋂ S (t′) X|a = ∅; (2) for any fixed value of a ∈ A, ⋃t∈Y S (t) X|a = X . Condition (ii) says that the set S (t) X|a and the conditional distribution PX|AY (x|a, y) are coupled in some specific way so that they happen to satisfy the specified equality.
In special cases when X ⊥ A | Y , if f is a function of only X , condition (ii) would always hold true. In general situations, if there does not exist any subsets Ka,Ka′ ⊆ X for different values of a, a′ ∈ A such that Σx∈KaPX|AY (x|a, y) = Σx∈Ka′PX|AY (x|a′, y), then condition (ii) can never hold true (i.e., we cannot find a deterministic function f(A,X) that satisfies Equalized Odds). Generally speaking, in order to score a better classification accuracy, one would like to make PỸ |A,X(t|a, x) as close as possible to PY |A,X(y|a, x), and if the set S (t) X|a and PX|AY (x|a, y) are not strictly coupled, condition (ii) would be violated.

heading: 4.2 CLASSIFICATION WITH RANDOMIZED PREDICTION
text: In this section, we consider cases when randomized prediction is acceptable, namely, the classifier would output class labels with certain probabilities. We first derive the relation between positive rates (TPR and FPR) of binary classifiers before and after the post-processing step, i.e., Ŷopt (the unconstrainedly optimized classifier) and Ỹpost (the fair classifier derived by post-processing Ŷopt), and show that under mild assumptions, one can always derive a non-trivial Equalized-Odds (on population level) Ỹpost via a post-processing step. Then, from the ROC feasible area perspective, we prove that post-processing approaches are actually equivalent to in-processing approaches but with additional “pseudo” constraints enforced. Therefore, using the same loss function, post-processing approaches can perform no better than in-processing approaches.

heading: 4.2.1 THE POST-PROCESSING STEP
text: The post-processing step of a predictor Ŷ (here we drop the subscript if without ambiguity) only utilizes the information in the joint distribution (A, Y, Ŷ ). A fair predictor Ỹpost derived via a postprocessing step, for instance, the shifted decision boundary (Fish et al., 2016), the derived predictor (Hardt et al., 2016), or the (monotonic) joint loss optimization over decoupled classifiers (Dwork et al., 2018), is then fully specified by a (possibly randomized) function of (A, Ŷ ). This implies the conditional independence Ỹpost ⊥ Y | A, Ŷ . Since we can denote the positive rates of Ŷ as PŶ |AY (1|a, y)1, positive rates of Ỹ (here we drop the subscript for readability) as PỸ |AY (1|a, y), the relation between positive rates of binary classifiers before and after a post-processing step would satisfy (for every a ∈ A, u, y ∈ Y):
PỸ |AY (1|a, y) = Σu∈Y β(u)a PŶ |AY (u|a, y), where β(u)a := P (Ỹ = 1 | A = a, Ŷ = u). (5) Notice that Equation 5 is just a factorization of probability under the conditional independence (between Ỹpost and Y given A and Ŷ ). Therefore, post-processing an existing predictor boils down to optimizing parameters (for discrete A) or functions (for continuous A) β(u)a .

heading: 4.2.2 ROC FEASIBLE AREA
text: On the Receiver Operator Characteristic (ROC) plane, a two-dimensional plane with horizontal axis denoting FPR and vertical axis denoting TPR, the performance of any binary predictor Ŷ (not
1Recall that PŶ |AY (u|a, y) = P (Ŷ = u | A = a, Y = y). When u = 1, PŶ |AY (1|a, y) = P (Ŷ = 1 | A = a, Y = y) represents positive rates of Ŷ ; When u = 0, PŶ |AY (0|a, y) = P (Ŷ = 0 | A = a, Y = y) represents positive rates of 1− Ŷ (the classifier that flips the prediction of Ŷ ).
Under review as a conference paper at ICLR 2021
0.00 0.25 0.50 0.75 1.00 P (eY = 1 | A, Y = 0) 0.0
0.2
0.4
0.6
0.8
1.0
P (e Y
= 1
|A ,Y
= 1) ≠(
eY §in)
(a) Discrete protected feature (b) Continuous protected feature
0.00 1.00
0. 0
1. 0
ε
a(bY )
<latexit sha1_base64="0V4dtXGOs+2OJOGy4KVFxXE5roY=">AAACAXicbVDLSsNAFJ3UV42vqAtBN8Ei1E1JRPCxKrhxI1SwD2lKuZlO26EzSZiZKCUEF+KXuBIUxK3gT7jyR1w7fSy09cCFwzn3cu89fsSoVI7zZWRmZufmF7KL5tLyyuqatb5RkWEsMCnjkIWi5oMkjAakrKhipBYJAtxnpOr3zgZ+9YYIScPgSvUj0uDQCWibYlBaalpbXgc4h2YCad67pS3SBZVcp/tNK+cUnCHsaeKOSa64/ZD7vrv4KDWtT68V4piTQGEGUtZdJ1KNBISimJHU9GJJIsA96JC6pgFwIhvJ8IHU3tNKy26HQleg7KH6eyIBLmWf+7qTg+rKSW8g/ufVY9U+biQ0iGJFAjxa1I6ZrUJ7kIbdooJgxfqaABZU32rjLgjASmdmmjoFd/LnaVI5KLiHhZNLHccpGiGLdtAuyiMXHaEiOkclVEYYpegRPaMX4954Ml6Nt1FrxhjPbKI/MN5/AB0dmh4=</latexit>
P ( e Y
= 1
|A ,Y
= 1)
<latexit sha1_base64="cCJh62l4ZHE9IIFCD7kRF0oYRZM=">AAACDHicbVDLSgMxFM3UV62vqjvdhBahgpQZEXyAUHHjRqhgX7SlZDK3bWjmQZJRylBcCa78FFeCgujSH3Dlj7g203ah1QMXTs65l9x77IAzqUzz00hMTc/MziXnUwuLS8sr6dW1svRDQaFEfe6Lqk0kcOZBSTHFoRoIIK7NoWL3TmO/cgVCMt+7VP0Ami7peKzNKFFaaqUzxVzjmjmgGHcgqg3wMbZww2UOPtnBtfi13Upnzbw5BP5LrDHJFjZus18352/FVvqj4fg0dMFTlBMp65YZqGZEhGKUwyDVCCUEhPZIB+qaesQF2YyGtwzwllYc3PaFLk/hofpzIiKulH3X1p0uUV056cXif149VO2DZsS8IFTg0dFH7ZBj5eM4GOwwAVTxviaECqZ3xbRLBKFKx5dK6RSsyZv/kvJu3trLH17oOI7QCEm0iTIohyy0jwroDBVRCVF0hx7QE3o27o1H48V4HbUmjPHMOvoF4/0bz22bsg==</latexit>
P (eY = 1 | A, Y = 0)
<latexit sha1_base64="YiqR1N6yVb2IKH3hJ0hQyObye40=">AAACDHicbVDJSgNBEO2JW4zbqDe9NAlCBAkzIriAEPHiRYhgNpIQenoqSZOehe4eJQzBk+DJT/EkKIge/QFP/ohnO8tBow8KXr9XRVc9J+RMKsv6NBJT0zOzc8n51MLi0vKKubpWkkEkKBRpwANRcYgEznwoKqY4VEIBxHM4lJ3u6cAvX4GQLPAvVS+EhkfaPmsxSpSWmma6kK1fMxcU4y7E1T4+xjaue8zFJzu4ql/WdtPMWDlrCPyX2GOSyW/cZr5uzt8KTfOj7gY08sBXlBMpa7YVqkZMhGKUQz9VjySEhHZJG2qa+sQD2YiHt/TxllZc3AqELl/hofpzIiaelD3P0Z0eUR056Q3E/7xapFoHjZj5YaTAp6OPWhHHKsCDYLDLBFDFe5oQKpjeFdMOEYQqHV8qpVOwJ2/+S0q7OXsvd3ih4zhCIyTRJkqjLLLRPsqjM1RARUTRHXpAT+jZuDcejRfjddSaMMYz6+gXjPdvzeebsQ==</latexit>
a(1 bY )
<latexit sha1_base64="5T9cTBbeWBj/jFSlpct+pasK9EQ=">AAACBXicbVDJSgNBEO2JW4zbqDdzaQxCPBhmRHA5Bbx4ESKYRZIQajqdpEn3zNDdo4QhiAfxUzwJCuJRP8KTP+LZznLQxAcFj/eqqKrnhZwp7ThfVmJmdm5+IbmYWlpeWV2z1zdKKogkoUUS8EBWPFCUM58WNdOcVkJJQXiclr3u6cAvX1OpWOBf6l5I6wLaPmsxAtpIDTtda4MQ0Iihn3XxHq7dsCbtgI6v+rsNO+PknCHwNHHHJJPfus98356/Fxr2Z60ZkEhQXxMOSlVdJ9T1GKRmhNN+qhYpGgLpQptWDfVBUFWPh0/08Y5RmrgVSFO+xkP190QMQqme8EynAN1Rk95A/M+rRrp1VI+ZH0aa+mS0qBVxrAM8SAQ3maRE854hQCQzt2LSAQlEm9xSKZOCO/nzNCnt59yD3PGFieMEjZBEabSNsshFhyiPzlABFRFBd+gRPaMX68F6sl6tt1FrwhrPbKI/sD5+ALtymuQ=</latexit>
0.00 1.00
0. 0
1. 0
a(bY )
<latexit sha1_base64="0V4dtXGOs+2OJOGy4KVFxXE5roY=">AAACAXicbVDLSsNAFJ3UV42vqAtBN8Ei1E1JRPCxKrhxI1SwD2lKuZlO26EzSZiZKCUEF+KXuBIUxK3gT7jyR1w7fSy09cCFwzn3cu89fsSoVI7zZWRmZufmF7KL5tLyyuqatb5RkWEsMCnjkIWi5oMkjAakrKhipBYJAtxnpOr3zgZ+9YYIScPgSvUj0uDQCWibYlBaalpbXgc4h2YCad67pS3SBZVcp/tNK+cUnCHsaeKOSa64/ZD7vrv4KDWtT68V4piTQGEGUtZdJ1KNBISimJHU9GJJIsA96JC6pgFwIhvJ8IHU3tNKy26HQleg7KH6eyIBLmWf+7qTg+rKSW8g/ufVY9U+biQ0iGJFAjxa1I6ZrUJ7kIbdooJgxfqaABZU32rjLgjASmdmmjoFd/LnaVI5KLiHhZNLHccpGiGLdtAuyiMXHaEiOkclVEYYpegRPaMX4954Ml6Nt1FrxhjPbKI/MN5/AB0dmh4=</latexit>
a0(bY )
<latexit sha1_base64="c89/nHUAw9xg7yu8XDX4xfETNTg=">AAACAnicbVDLSsNAFJ3UV62vqBvRTbCIdVMSEXysCm7cCBXsQ5pQbqbTduhMEmYmSgnVjf6JK0FB3Io/4cofce30sdDWAxcO59zLvff4EaNS2faXkZqanpmdS89nFhaXllfM1bWyDGOBSQmHLBRVHyRhNCAlRRUj1UgQ4D4jFb9z2vcr10RIGgaXqhsRj0MroE2KQWmpbm64LeAc6gns9nLuDW2QNqjkqrdXN7N23h7AmiTOiGQLmw/Z77vzj2Ld/HQbIY45CRRmIGXNsSPlJSAUxYz0Mm4sSQS4Ay1S0zQATqSXDD7oWTtaaVjNUOgKlDVQf08kwKXscl93clBtOe71xf+8WqyaR15CgyhWJMDDRc2YWSq0+nFYDSoIVqyrCWBB9a0WboMArHRomYxOwRn/eZKU9/POQf74QsdxgoZIoy20jXLIQYeogM5QEZUQRrfoET2jF+PeeDJejbdha8oYzayjPzDefwCDTJpP</latexit>
P (eY = 1 | A, Y = 0)
<latexit sha1_base64="YiqR1N6yVb2IKH3hJ0hQyObye40=">AAACDHicbVDJSgNBEO2JW4zbqDe9NAlCBAkzIriAEPHiRYhgNpIQenoqSZOehe4eJQzBk+DJT/EkKIge/QFP/ohnO8tBow8KXr9XRVc9J+RMKsv6NBJT0zOzc8n51MLi0vKKubpWkkEkKBRpwANRcYgEznwoKqY4VEIBxHM4lJ3u6cAvX4GQLPAvVS+EhkfaPmsxSpSWmma6kK1fMxcU4y7E1T4+xjaue8zFJzu4ql/WdtPMWDlrCPyX2GOSyW/cZr5uzt8KTfOj7gY08sBXlBMpa7YVqkZMhGKUQz9VjySEhHZJG2qa+sQD2YiHt/TxllZc3AqELl/hofpzIiaelD3P0Z0eUR056Q3E/7xapFoHjZj5YaTAp6OPWhHHKsCDYLDLBFDFe5oQKpjeFdMOEYQqHV8qpVOwJ2/+S0q7OXsvd3ih4zhCIyTRJkqjLLLRPsqjM1RARUTRHXpAT+jZuDcejRfjddSaMMYz6+gXjPdvzeebsQ==</latexit>
P ( e Y
= 1
|A ,Y
= 1)
<latexit sha1_base64="cCJh62l4ZHE9IIFCD7kRF0oYRZM=">AAACDHicbVDLSgMxFM3UV62vqjvdhBahgpQZEXyAUHHjRqhgX7SlZDK3bWjmQZJRylBcCa78FFeCgujSH3Dlj7g203ah1QMXTs65l9x77IAzqUzz00hMTc/MziXnUwuLS8sr6dW1svRDQaFEfe6Lqk0kcOZBSTHFoRoIIK7NoWL3TmO/cgVCMt+7VP0Ami7peKzNKFFaaqUzxVzjmjmgGHcgqg3wMbZww2UOPtnBtfi13Upnzbw5BP5LrDHJFjZus18352/FVvqj4fg0dMFTlBMp65YZqGZEhGKUwyDVCCUEhPZIB+qaesQF2YyGtwzwllYc3PaFLk/hofpzIiKulH3X1p0uUV056cXif149VO2DZsS8IFTg0dFH7ZBj5eM4GOwwAVTxviaECqZ3xbRLBKFKx5dK6RSsyZv/kvJu3trLH17oOI7QCEm0iTIohyy0jwroDBVRCVF0hx7QE3o27o1H48V4HbUmjPHMOvoF4/0bz22bsg==</latexit>
ε a(1 bY )
<latexit sha1_base64="5T9cTBbeWBj/jFSlpct+pasK9EQ=">AAACBXicbVDJSgNBEO2JW4zbqDdzaQxCPBhmRHA5Bbx4ESKYRZIQajqdpEn3zNDdo4QhiAfxUzwJCuJRP8KTP+LZznLQxAcFj/eqqKrnhZwp7ThfVmJmdm5+IbmYWlpeWV2z1zdKKogkoUUS8EBWPFCUM58WNdOcVkJJQXiclr3u6cAvX1OpWOBf6l5I6wLaPmsxAtpIDTtda4MQ0Iihn3XxHq7dsCbtgI6v+rsNO+PknCHwNHHHJJPfus98356/Fxr2Z60ZkEhQXxMOSlVdJ9T1GKRmhNN+qhYpGgLpQptWDfVBUFWPh0/08Y5RmrgVSFO+xkP190QMQqme8EynAN1Rk95A/M+rRrp1VI+ZH0aa+mS0qBVxrAM8SAQ3maRE854hQCQzt2LSAQlEm9xSKZOCO/nzNCnt59yD3PGFieMEjZBEabSNsshFhyiPzlABFRFBd+gRPaMX68F6sl6tt1FrwhrPbKI/sD5+ALtymuQ=</latexit>
a0(1 bY )
<latexit sha1_base64="Qh92ZIfH2oI7jamDTNoKJxAOFjQ=">AAACBnicbVDJSgNBEO1xjXEb9aYeGoMYD4YZEVxOAS9ehAhmkSSEmk4nadI9M3T3KGEIgiD4KZ4EBfEm/oMnf8SzneWgiQ8KHu9VUVXPCzlT2nG+rInJqemZ2cRccn5hcWnZXlktqCCShOZJwANZ8kBRznya10xzWgolBeFxWvTapz2/eE2lYoF/qTshrQpo+qzBCGgj1ezNShOEgFoMO920i/dw5YbVaQt0fNXdrdkpJ+P0gceJOySp7Pp96vv2/D1Xsz8r9YBEgvqacFCq7DqhrsYgNSOcdpOVSNEQSBuatGyoD4Kqatz/oou3jVLHjUCa8jXuq78nYhBKdYRnOgXolhr1euJ/XjnSjaNqzPww0tQng0WNiGMd4F4kuM4kJZp3DAEimbkVkxZIINoEl0yaFNzRn8dJYT/jHmSOL0wcJ2iABNpAWyiNXHSIsugM5VAeEXSHHtEzerEerCfr1XobtE5Yw5k19AfWxw8iVJsV</latexit>
(c) Feasible areas for , and eYin
<latexit sha1_base64="WgNrvz3DlliQRdhE1EH3cGlEpN0=">AAACA3icbVC7SgNBFJ2Nr7i+Vq3EZjEIVmFXBBWbgI2VRDA+SEKcnb1Jhsw+mLmrhmWx8gv8BitBQWz9CitrK//CyaPQxAMDh3Pu5c45Xiy4Qsf5NHITk1PTM/lZc25+YXHJWl45U1EiGVRYJCJ54VEFgodQQY4CLmIJNPAEnHudw55/fg1S8Sg8xW4M9YC2Qt7kjKKWGtZa7Yb7gFz4kF5mjbSGcIspD7OsYRWcotOHPU7cISmUrPer7+Ovh3LD+qj5EUsCCJEJqlTVdWKsp1QiZwIys5YoiCnr0BZUNQ1pAKqe9iNk9qZWfLsZSf1CtPvq742UBkp1A09PBhTbatTrif951QSbe3UdKE4QQjY41EyEjZHd68P2uQSGoqsJZZLrv9qsTSVlqFszTd2CO5p5nJxtF92d4v6JruOADJAn62SDbBGX7JISOSJlUiGM3JFH8kxejHvjyXg13gajOWO4s0r+wHj/AeSfnH8=</latexit>
eYpost
<latexit sha1_base64="oUG/CX0cOSSIWN7pPbNOJdFDIYA=">AAACBXicbVDJSgNBEO1JXGLcoh5zcDAInsKMCCqCBrx4jGAWSULo6akkTXoWu2vUMMzBkxf/w5OgIF79CE/+jZ3loIkPCh7vVVFVzwkFV2hZ30YqPTe/sJhZyi6vrK6t5zY2qyqIJIMKC0Qg6w5VILgPFeQooB5KoJ4joOb0z4d+7Rak4oF/hYMQWh7t+rzDGUUttXP55h13AblwIb5O2nET4R7jMFCYJO1cwSpaI5izxJ6QQmk7fDo7Td+U27mvphuwyAMfmaBKNWwrxFZMJXImIMk2IwUhZX3ahYamPvVAteLRE4m5qxXX7ARSl4/mSP09EVNPqYHn6E6PYk9Ne0PxP68RYeeoFXM/jBB8Nl7UiYSJgTlMxHS5BIZioAllkutbTdajkjLUuWWzOgV7+udZUt0v2gfF40sdxwkZI0PyZIfsEZsckhK5IGVSIYw8kGfySt6MR+PFeDc+xq0pYzKzRf7A+PwBQ12btA==</latexit>
bYopt
<latexit sha1_base64="5L0DDDKMIR3vYh2pRr4P0T2/Ols=">AAACAnicbVDJSgNBEO1JXGLcRr0IHhwMgqcwI4KKoAEvHiOYRZIQejqVpEnPYneNGobx5NHP8CQoiFf/wpN/Y2c5aOKDgsd7VVTVc0PBFdr2t5FKz8zOzWcWsotLyyur5tp6WQWRZFBigQhk1aUKBPehhBwFVEMJ1HMFVNze+cCv3IJUPPCvsB9Cw6Mdn7c5o6ilprlZv+Mt6FKMr5NmXEe4xzgIMUmaZs7O20NY08QZk1xhO3w6O03fFJvmV70VsMgDH5mgStUcO8RGTCVyJiDJ1iMFIWU92oGapj71QDXi4QeJtauVltUOpC4fraH6eyKmnlJ9z9WdHsWumvQG4n9eLcL2USPmfhgh+Gy0qB0JCwNrEIfV4hIYir4mlEmub7VYl0rKUIeWzeoUnMmfp0l5P+8c5I8vdRwnZIQM2SI7ZI845JAUyAUpkhJh5IE8k1fyZjwaL8a78TFqTRnjmQ3yB8bnD8Glmk4=</latexit>
(d) with “pseudo” constraints⌦(eY ⇤in)
<latexit sha1_base64="oAqhiNPzI2+7mqo9To1qX8f0Bps=">AAACDXicbVC7SgNBFJ2NrxhfUcs0i0GIFmFXBCM2ARs7IxiNZGOYnb1JBmcfzNyNhmU/QBs/xUpQEFtrsfJvnDwKXwcGDuecy5173EhwhZb1aWSmpmdm57LzuYXFpeWV/OramQpjyaDOQhHKhksVCB5AHTkKaEQSqO8KOHevDof+eR+k4mFwioMIWj7tBrzDGUUttfNF59iHLi0519wD5MKD5CJtJw7CDSY8SNPL7S2dssrWCOZfYk9IsVq4q+z08b3Wzn84XshiHwJkgirVtK0IWwmVyJmANOfECiLKrmgXmpoG1AfVSkbHpOamVjyzE0r9AjRH6veJhPpKDXxXJ32KPfXbG4r/ec0YO5WWvimKEQI2XtSJhYmhOWzG9LgEhmKgCWWS67+arEclZaj7y+V0C/bvm/+Ss52yvVveP9F1HJAxsqRANkiJ2GSPVMkRqZE6YeSWPJAn8mzcG4/Gi/E6jmaMycw6+QHj7QsTlJ7x</latexit>
0.00 0.25 0.50 0.75 1.00 P (eY = 1 | A, Y = 0) 0.0
0.2
0.4
0.6
0.8
1.0
P (e Y
= 1
|A ,Y
= 1)≠(eYpost) A = 0 : bYopt A = 1 : bYopt eYin eYpost ≠(eYin)
Figure 1: ROC feasible area illustrations. Panels (a)-(b): Attainability of Equalized Odds for binary classifiers with discrete or continuous protected feature. Panels (c)-(d): ROC feasible areas comparison between Ω(Ỹin), Ω(Ỹpost), Ω(Ŷopt), and Ω(Ỹ ∗in ).
necessarily a fair one) with certain value of protected feature A = a corresponds to a point γa(Ŷ ) = (FPR, TPR) on the plane. Denote each coordinate according to the value of Y as γay(Ŷ ):
γa(Ŷ ) = ( γa0(Ŷ ), γa1(Ŷ ) ) := ( PŶ |AY (1|a, 0), PŶ |AY (1|a, 1) ) . (6)
Further denote the corresponding convex hull of Ŷ on the ROC plane as Ca(Ŷ ) using vertices:
Ca(Ŷ ) := convhull { (0, 0), γa(Ŷ ), γa(1− Ŷ ), (1, 1) } , (7)
and then, as already stated in Hardt et al. (2016), the (FPR, TPR) pair corresponding to a postprocessing predictor falls within (including the boundary of) Ca(Ŷ ). Definition 4.1. (ROC feasible area) The feasible area of a predictor Ω(Ŷ ), specified by the hypothesis space of available predictors Ŷ , is the set containing all attainable (FPR, TPR) pairs by the predictor on the ROC plane satisfying Equalized Odds.
In Hardt et al. (2016) it is proposed that the post-processing fair predictor can be derived by solving a linear programming problem on the ROC plane. However, it is not clearly stated whether or not such problem always has a non-trivial solution. Following Hardt et al. (2016), we analyze the relation between the (FPR, TPR) pair of predictors on the ROC plane and formally establish the existence of the non-trivial Equalized-Odds predictor. Actually as we shall see in Theorem 4.2, under mild assumptions, an Equalized-Odds predictor Ỹpost derived via post-processing Ŷ (a predictor optimized without fairness concern) always has non-empty ROC feasible area.
Theorem 4.2. (Attainability of Equalized Odds) Assume that the feature X is not independent from Y , and that Ŷ is a function of A and X . Then for binary classification, if Ŷ is a non-trivial predictor for Y , there is always at least one non-trivial (possibly randomized) predictor Ỹpost derived by post-processing Ŷ that can attain Equalized Odds:
Ω(Ỹpost) 6= ∅.
Here Ỹpost is a possibly randomized function of only A and Ŷ , trading off TPR with FPR across groups with different value of protected feature. From the panels (a) and (b) of Figure 1 we can also see that Ω(Ỹpost), the ROC feasible area of Ỹpost, is the intersection of Ωa(Ŷ ), indicating that although Equalized Odds is attained, the performance of Ỹpost is always worse than the weakest performance across different groups, which is obviously suboptimal.

heading: 4.2.3 OPTIMALITY OF PERFORMANCE AMONG FAIR CLASSIFIERS
text: In this subsection we discuss the optimality of performance of fair classifiers derived via different approaches. Considering the fact that recent efforts to impose Equalized Odds in the pre-processing manner (Madras et al., 2018; Zhao et al., 2020) approach the problem from a representation learning perspective, where the main focus is to learn fair representations that at the same time preserve sufficient information from the original data, we omit pre-processing approaches from the discussion and compare the performance of post-processing and in-processing fair classifiers.
Admittedly, when only the information about joint distribution of (A, Y, Ŷ ) is available, postprocessing is the best we can do. However, this is not the case when we have access to additional available features during training. For any predictor specified by parameters θ ∈ Θ, the derivation of the in-processing fair predictor Ỹin and the unconstrained statistical optimal predictor Ŷopt take following forms respectively:
min θ∈Θ E[l (f(A,X; θ), Y )] s.t. PỸin|AY (t | a, y) = PỸin|Y (t | y)
where Ỹin = f(A,X; θ),
(8)
min θ∈Θ
E[l (f(A,X; θ), Y )]
where Ŷopt = f(A,X; θ). (9)
It is natural to wonder, now that one can always directly solve for Ỹin from Equation 8, how is it related to Ỹpost, which is derived by post-processing the Ŷopt solved from Equation 9? Interestingly, although Ỹin and Ỹpost are solved separately using different constrained optimization schemes, one can draw a connection between them by utilizing Ŷopt as a bridge and reason about the relation between their ROC feasible areas Ω(Ỹin) and Ω(Ỹpost), as we summarize in the following theorem.
Theorem 4.3. (Equivalence between ROC feasible areas) Let Ω(Ỹpost) denote the ROC feasible area specified by the constraints enforced on Ỹpost. Then Ω(Ỹpost) is identical to the ROC feasible area Ω(Ỹ ∗in ) that is specified by the following set of constraints:
(i) constraints enforced on Ỹin ; (ii) additional “pseudo” constraints: ∀a ∈ A, β(0)a0 = β (0) a1 , β (1) a0 = β (1) a1 , where
β (u) ay = Σx∈XP (Ỹin = 1 | A = a,X = x)P (X = x | A = a, Y = y, Ŷopt = u).
As we can see from panels (c) and (d) of Figure 1, if the additional “pseudo” constraints are introduced when optimizing Ỹ ∗in , we have Ω(Ỹin) ⊇ Ω(Ỹpost) = Ω(Ỹ ∗in ). The ROC feasible area is fully specified by the hypothesis class and the fairness constraint. Therefore, with the same objective function and fairness constraint, the fair classifier derived from an in-processing approach always outperforms the one derived from a post-processing approach. We can see that when we have access to additional features and choose a post-processing approach, we lose performance (compared to Ỹin) by unintentionally introducing “pseudo” constraints during optimization. These “pseudo” constraints actually offset the benefit of utilizing additional features (in the hope to score a better performance while remaining fair).

heading: 5 EXPERIMENTS
text: In order to intuitively illustrate the claims, we provide numerical results for various settings. We first present the result for (linear non-Gaussian and nonlinear) regression tasks when Equalized Odds is not attained. We demonstrate the dependence between the prediction and the protected feature given true value of the target variable. Then for classification tasks we compare the performance of several
existing methods in the literature on the Adult, Bank, COMPAS, and German Credit data sets. The detailed description of the data sets is available in the appendix.

heading: 5.1 REGRESSION WITH LINEAR NON-GAUSSIAN AND NONLINEAR DATA
text: In Section 3.1 we showed the unattainability of Equalized Odds for regression with linear nonGaussian data. Although a proof for similar results in nonlinear cases does not seem straightforward, as strongly suggested by our numerical illustrations, the unattainability of Equalized Odds persists in nonlinear regression cases. In Figure 2 we present scatter plots of Ỹ versus A for Y in a small (compared to its support) interval, for linear non-Gaussian as well as nonlinear regression cases.
For linear cases, the data is generated as stated in Equation 4, with non-Gaussian distributed exogenous terms (EX , EH , and EY ). We use linear regression with the Equalized Correlations constraint (Woodworth et al., 2017), a weaker notion of Equalized Odds for linearly correlated data, as the predictor. For nonlinear cases, the data is generated using a similar scheme but with nonlinear transformations (e.g., combinations of sin(·), log(·), and polynomials) and Gaussian distributed exogenous terms. We use a neural net regressor with an Equalized Odds regularization term (Mary et al., 2019) to perform nonlinear fair regression. As we can see in Figure 2, for nonlinear regression tasks, Equalized Odds may not be attained even if every exogenous term is Gaussian distributed.

heading: 5.2 FAIR CLASSIFICATION
text: In Figure 3, we compare the performance under Equalized Odds of multiple methods proposed in the literature. Hardt et al. (2016) propose a post-processing approach where the prediction is randomized to minimize violation of fairness; Zafar et al. (2017a) use a covariance proxy measure as the regularization term when optimizing classification accuracy; Agarwal et al. (2018) take the reductions approach and reduce fair classification into solving a sequence of cost-sensitive classification problems; Rezaei et al. (2020) minimize the worst-case log loss using an approximated regularization term; Baharlouei et al. (2020) propose to use Rényi correlation as the regularization term to account for nonlinear dependence between variables. To measure the violation of the fairness criterion, we use Equalized Odds (EOdds) violation, defined as maxy∈Y a,a′∈A
∣∣PỸ |AY (1|a, y) − PỸ |AY (1|a′, y)
∣∣. Following Agarwal et al. (2018), we pick 0.01 as the default violation bound that the EOdds violation does not exceed (if practically achievable for the method) during training. For each method we plot the testing accuracy versus the violation of Equalized Odds. Although a probabilistic classification model is used across each method (here is logistic regression), if an algorithm output the class label where the prediction likelihood is maximized, the prediction is in essence performed by a deterministic function of input features (e.g., Rezaei et al. (2020); Baharlouei et al. (2020)). As we have shown in Section 4.1, for classification with a deterministic function, in general cases the conditions specified in Theorem 4.1 are easily violated, i.e., Equalized Odds may not be
attained even if there is an unlimited amount of data. Therefore, although here we are considering finite data cases, we can still anticipate a lower level of fairness violation with a randomized prediction. This is validated by the numerical experiment: while the approach by Hardt et al. (2016) does not score the lowest test error, the violation of Equalized Odds is the lowest compared to other approaches. The benefit of introducing randomization can also be witnessed by the Pareto frontier presented in Agarwal et al. (2018), where the approach can potentially achieve any desired fairnessaccuracy trade-off between that of the post-processing approach and that of the unconstrainedly optimized classifier2. In some scenarios people tend to only care about equal TPR (e.g., the rate of acceptance/admission) across groups, i.e., the Equal Opportunity (Hardt et al., 2016) notion of fairness. The related numerical result on real-world data sets is also presented.

heading: 6 CONCLUSION AND FUTURE WORK
text: In this paper, we focus on the Equalized-Odds criterion and consider the attainability of fairness, and furthermore, if attainable, the optimality of the prediction performance under various settings. We first show that, for fair regression, one can only achieve Equalized Odds when certain conditions on the joint distribution of the features and the target variable are met. Then for classification tasks with deterministic classifiers, we give the condition under which Equalized Odds can hold true; we also show that under mild assumptions, one can always find a non-trivial Equalized-Odds (randomized) predictor, even with a continuous protected feature; in terms of the optimality of performance, one can always (if conditions permit) benefit from exploiting all available features during training. Future work would naturally consider nonlinear regression algorithms with randomized output and fairness guarantees, and the attainability of more fine-grained (compared to group fairness) criteria of fairness (e.g., individual fairness) as well as the procedure fairness in the fairness hierarchy.

heading: A APPENDIX
text: A.1 PROOF FOR THEOREM 3.1
To prove the unattainability of Equalized Odds in regression, we will need the following lemma, which provides a way to characterize conditional independence/dependence with conditional or joint distributions. Lemma A.1. Variables V1 and V2 are conditionally independent given variable V3 if and only if there exist functions h(v1, v3) and g(v2, v3) such that
pV1,V2|V3(v1, v2 | v3) = h(v1, v3) · g(v2, v3). (10)
Proof. First, if V1 and V2 are conditionally independent given variable V3, then Equation 10 holds:
pV1,V2|V3(v1, v2 | v3) = pV1|V3(v1 | v3) · pV2|V3(v2 | v3). We then let h̃(v3) := ∫ h(v1, v3)dv1 and g̃(v3) := ∫ g(v2, v3)dv2. Take the integral of Equation 10 w.r.t. v1 and v2, we have:
pV2|V3(v2 | v3) = h̃(v3) · g(v2, v3), pV1|V3(v1 | v3) = g̃(v3) · h(v1, v3),
respectively. Bearing in mind Equation 10, one can see that the product of the two equations above is
pV2|V3(v2 | v3) · pV1|V3(v1 | v3) = h̃(v3) · g(v2, v3) · g̃(v3) · h(v2, v3) = h̃(v3) · g̃(v3) · pV1,V2|V3(v1, v2 | v3).
Take the integral of the equation above w.r.t. v1 and v2 gives h̃(v3) · g̃(v3) ≡ 1. The above equation then reduces to pV2|V3(v2 | v3) · pV1|V3(v1 | v3) = pV1,V2|V3(v1, v2 | v3). That is, V1 and V2 are conditionally independent given V3.
Now we are ready to prove the unattainability of Equalized Odds in linear non-Gaussian regression: Theorem. (Unattainability of Equalized Odds in the Linear Non-Gaussian Case) Assume that feature X has a causal influence on Y , i.e., c 6= 0 in Equation 4, and that the protected feature A and Y are not independent, i.e., qc + bd 6= 0. Assume pEX and pE are positive on R. Let f1 := log pA, f2 := log pEX , and f3 := log pE . Further assume that f2 and f3 are third-order differentiable. Then if at most one of EX and E is Gaussian, Z is always conditionally dependent on A given Y .
Proof. According to Equation 4, we have [ A Z Y ] = [ 1 0 0 α+ qβ β 0 qc+ bd c 1 ] · [ A EX E ] . (11)
The determinant of the above linear transformation is β, which relates the probability density function of the variables on the LHS and that of the variables on the RHS of the equation. Therefore, according to Equation 11, we can rewrite the joint probability density function by making use of the Jacobian determinant and factor the joint density into marginal density functions (A, EX , E are mutually independent according to the data generating process). Further let
α̃ := α+ qβ β , r̃ := bd− cα β , and c̃ := c β . (12)
Then we have EX = 1βZ − α̃A, E = Y − r̃A− c̃Z, and pA,Z,Y (a, z, y) = pA,EX ,E(a, ex, e)/|β|
= 1
|β|pA(a)pEX (ex)pE(e)
= 1 |β|pA(a)pEX ( 1 β z − α̃a)pE(y − r̃a− c̃z).
On its support, the log-density can be written as
J := log pA,Z,Y (a, z, y)
= log pA(a) + log pEX ( 1
β z − α̃a) + log pE(y − r̃a− c̃z)− log|β|
= f1(a) + f2( 1
β z − α̃a) + f3(y − r̃a− c̃z)− log |β|.
(13)
According to Lemma A.1, A ⊥ Z | Y if and only if pA,Z|Y (a, z | y) is a product of a function of a and y and a function of z and y. pA,Z,Y (a, z, y) is further a product of the above function and a function of only y. This property, under the conditions in Theorem 3.1, is equivalent to the constraint
∂2J
∂A∂Z ≡ 0. (14)
According to Equation 13, we have
∂J ∂z = 1 β · f ′2( 1 β z − α̃a)− c̃ · f ′3(y − r̃a− c̃z)
⇒ ∂ 2J ∂a∂z = − α̃ β · f ′′2 ( 1 β z − α̃a) + r̃c̃ · f ′′3 (y − r̃a− c̃z).
(15)
Combining Equations 14 and 15 gives
r̃c̃ · f ′′3 (y − r̃a− c̃z) = α̃ β · f ′′2 ( 1 β z − α̃a). (16)
Further taking the partial derivative of both sides of the above equation w.r.t. y yields
r̃c̃ · f ′′′3 (y − r̃a− c̃z) ≡ 0. (17)
There are three possible situations where the above equation holds: (i) c̃ = 0, which is equivalent to c = 0 and contradicts with the theorem assumption.
(ii) r̃ = 0. Then according to Equation 16, we have α̃β ·f ′′2 ( 1β z− α̃a) ≡ 0, implies either α̃ = 0 or f ′′2 ( 1 β z − α̃a) ≡ 0. If the latter is the case, then f2 is a linear function and, accordingly,
exp(f2) is not integrable and does not correspond to any valid density function. If the former is true, i.e., α̃ = 0, then according to Equation 12, we have α = −qβ, which further implies r̃ = bd − cαβ = bd + qc. Therefore, in this situation, bd + qc = 0, which again contradicts with the theorem assumption. (iii) f ′′′3 (y − r̃a − c̃z) ≡ 0. That is, f3 is a quadratic function with a nonzero coefficient for the quadratic term (otherwise f3 does not correspond to the logarithm of any valid density function). Thus E follows a Gaussian distribution.
Only situation (iii) is possible, i.e., r̃c̃ 6= 0 and E follows a Gaussian distribution. This further tells us that the RHS of Equation 16 is a nonzero constant. Hence f2 is a quadratic function and EX also follows a Gaussian distribution. Therefore if A ⊥ Z | Y were to be true, then EX and E are both Gaussian. Its contrapositive gives the conclusion of this theorem.
Corollary. Suppose that both EX and E are Gaussian, with variances σ2EX and σ 2 E , respectively. (The protected feature A is not necessarily Gaussian.) Then Z ⊥ A | Y if and only if α
β = bdc · σ2EX − q · σ2E c2 · σ2EX + σ2E . (18)
Proof. Under the condition that EX and E are Gaussian, their log-density functions are third-order differentiable. Then according to the proof of Theorem 3.1, the Equalized Odds conditionA⊥ Z | Y is equivalent to Equation 16, which, together with Equation 12 as well as the fact that f ′′2 =
1 σ2EX
and f ′′3 = 1 σ2E , yields Equation 18.
A.2 PROOF FOR THEOREM 4.1
Theorem. Assume that the protected feature A and Y are dependent and that their joint probability P (A, Y ) (for discreteA) or joint probability density p(A, Y ) (for continuousA) is positive for every combination of possible values ofA and Y . Further assume that Y is not fully determined byA, and that there are additional features X that are not independent of Y . Let the output of the classifier Ỹ be a deterministic function f : A × X → Y . Let S(t)A := {a | ∃x ∈ X s.t. f(a, x) = t}, and S
(t) X|a := {x | f(a, x) = t}. Equalized Odds holds true if and only if the following two conditions
are satisfied:
(i) ∀t ∈ Y : S(t)A = A, (ii) ∀t ∈ Y, ∀a, a′ ∈ A, a 6= a′ :
Σ x∈S(t)
X|a
P (X = x | A = a, Y = y) = Σ x∈S(t)
X|a′
P (X = x | A = a′, Y = y).
Proof. We begin by considering the case whenA andX are discrete (for the purpose of readability). The Equalized Odds criterion can be written in terms of the conditional probabilities:
∀a ∈ A, t, y ∈ Y : P (Ỹ = t | A = a, Y = y) = P (Ỹ = t | Y = y). (19) Expand the LHS of Equation 19:
P (Ỹ = t | A = a, Y = y) = Σ x∈X P (Ỹ = t | A = a,X = x, Y = y)P (X = x | A = a, Y = y),
and bear in mind that Ỹ := f(A,X) is a deterministic function of (A,X), we have:
P ( f(A,X) = t | A = a,X = x, Y = y) = P ( f(A,X) = t | A = a,X = x) ∈ {0, 1}. (20)
From Equation 20 we can see that the conditional probability P (X = x | A = a, Y = y) can contribute to the summation only when f(a, x) = t. We can rewrite the LHS of Equation 19:
P (Ỹ = t | A = a, Y = y) = Σ x∈S(t)
X|a
P (X = x | A = a, Y = y) := Q(t)(a, y).
Similarly, for the RHS of Equation 19, we have:
P (Ỹ = t | Y = y) = Σ a∈A Σ x∈X P (Ỹ = t | A = a,X = x, Y = y)P (X = x,A = a | Y = y)
= Σ a∈S(t)A Σ x∈S(t) X|a
P (X = x | A = a, Y = y)P (A = a | Y = y)
= Σ a∈S(t)A
Q(t)(a, y)P (A = a | Y = y).
Since Equalized Odds holds true if and only if Equation 19 holds true, then the LHS of the equation does not involve a (as is the case for the RHS), i.e.,Q(t)(a, y) does not change with a. Then Equation 19 becomes:
Q(t)(a, y) = Σ a∈S(t)A Q(t)(a, y)P (A = a | Y = y) = Q(t)(a, y) Σ a∈S(t)A P (A = a | Y = y),
which gives the condition (i) that S(t)A contains all possible values of A, i.e., A = S (t) A (otherwise Σ a∈S(t)A P (A = a | Y = y) < 1). Since Q(t)(a, y) does not change with a, we have:
∀a, a′ ∈ A, a 6= a′ : Σ x∈S(t)
X|a
P (X = x | A = a, Y = y) = Σ x∈S(t)
X|a′
P (X = x | A = a′, Y = y),
which gives the condition (ii). Therefore, Equalized Odds implies conditions (i) and (ii). On the other hand, it is easy to see that when conditions (i) and (ii) are satisfied, Equation 19 holds true, i.e., Equalized Odds holds true.
When A and X are continuous, one can replace the summation with integration accordingly.
A.3 PROOF FOR THEOREM 4.2
Theorem. (Attainability of Equalized Odds) Assume that the feature X is not independent from Y , and that Ŷ is a function of A and X . Then for binary classification, if Ŷ is a non-trivial predictor for Y , there is always at least one non-trivial predictor Ỹpost derived by post-processing Ŷ that can attain Equalized Odds, i.e.,
Ω(Ỹpost) 6= ∅.
Proof. Since Ŷ is a function of (A,X) and X ⊥6 Y , Ŷ is not conditionally independent from Y given protected feature A. Furthermore, since Ŷ is a non-trivial estimator of the binary target Y , there exists a positive constant > 0, such that:
∣∣P (Ŷ = 1 | A = a, Y = 1)− P (Ŷ = 1 | A = a, Y = 0) ∣∣ ≥ , ∀a ∈ A. (21)
Equation 21 implies that for each value of A, the corresponding true positive rate of the non-trivial predictor is always strictly larger than its false positive rate3. As illustrated in panels (a) and (b) of Figure 1, the (FPR, TPR) pair of the predictor Ŷ when A = a, i.e., the point γa(Ŷ ) on ROC plane, will never fall in the gray shaded area, and its coordinates are bounded away from the diagonal by at least . Therefore, the intersection of all Ca(Ŷ ) would always form a parallelogram with non-empty area, which corresponds to attainable non-trivial post-processing fair predictors Ỹpost.
A.4 PROOF FOR THEOREM 4.3
Theorem. (Equivalence between ROC feasible areas) Let Ω(Ỹpost) denote the ROC feasible area specified by the constraints enforced on Ỹpost. Then Ω(Ỹpost) is identical to the ROC feasible area Ω(Ỹ ∗in ) that is specified by the following set of constraints:
(i) constraints enforced on Ỹin ; (ii) additional “pseudo” constraints: ∀a ∈ A, β(0)a0 = β (0) a1 , β (1) a0 = β (1) a1 , where
β (u) ay = Σx∈XP (Ỹin = 1 | A = a,X = x)P (X = x | A = a, Y = y, Ŷopt = u).
Proof. Since the post-processing predictor Ỹpost is derived by optimizing over parameters or functions (of A) β(u)a . Therefore, considering the fact that PỸpost|AY (1|a, y) = γay(Ỹpost), PŶopt|AY (1|a, y) = γay(Ŷopt), we have the relation between γay(Ỹpost) and γay(Ŷopt):
γay(Ỹpost) = β (0) a γay(1− Ŷopt) + β(1)a γay(Ŷopt),
β(0)a = P (Ỹpost = 1 | A = a, Ŷopt = 0), β(1)a = P (Ỹpost = 1 | A = a, Ŷopt = 1).
(22)
Similarly, consider the relation between positive rates of Ỹin and those of Ŷopt, i.e., PỸin|AY (1|a, y) and PŶopt|AY (1|a, y), by factorizing PỸin|AY (1|a, y) over X and Ŷopt:
PỸin|AY (1|a, y) = ∑
u∈Y
[∑
x∈X PỸin|AX(1|a, x)PX|AY Ŷopt(x|a, y, u)
] PŶopt|AY (u|a, y). (23)
Therefore, we have the relation between γay(Ỹin) and γay(Ŷopt):
γay(Ỹin) = β (0) ay γay(1− Ŷopt) + β(1)ay γay(Ŷopt),
β(0)ay = Σx∈XP (Ỹin = 1 | A = a,X = x)P (X = x | A = a, Y = y, Ŷopt = 0), β(1)ay = Σx∈XP (Ỹin = 1 | A = a,X = x)P (X = x | A = a, Y = y, Ŷopt = 1).
(24)
3If the TPR of the predictor is always smaller than its FPR, one can simply flip the prediction (since the target is binary) and then Equation 21 holds true.
If there is more than one variable in X in Equation 24, one can expand the summation if needed; if some variables are continuous, one may also substitute the summation with integration accordingly.
From Equation 24, β(0)ay and β (1) ay depend on the value of Y :
β(0)ay = P (Ỹin = 1 | A = a, Y = y, Ŷopt = 1), β(0)ay = P (Ỹin = 1 | A = a, Y = y, Ŷopt = 0).
(25)
Apart from Equalized Odds constraints (which are shared by Ỹin and Ỹpost), when enforcing additional “pseudo” constraints β(0)a0 = β (0) a1 and β (1) a0 = β (1) a1 , conditional independence Ỹin⊥ Y | A, Ŷopt is enforced, making β(0)ay and β (0) ay no longer depend on Y . This is exactly the inherent constraint
Ỹpost satisfies. Therefore the stated equivalence between ROC feasible areas Ω(Ỹpost) (specified by the constraints enforced on Ỹpost) and Ω(Ỹ ∗in ) (specified by the constraints enforced on Ỹin together with the additional “pseudo” constraints) hold true.
A.5 DESCRIPTION OF THE DATA SETS
(1) Adult4: The UCI Adult data set contains 14 features for 45,222 individuals (32,561 samples for training and 12,661 samples for testing). The census information includes gender, marital status, education, capital gain, etc. The classification task is to predict whether a person’s annual income exceeds 50,000 USD. We use the provided testing set for evaluations and present the result with gender and race (consider white and black people only) set as the protected feature respectively.
(2) Bank5: The UCI Bank Marketing data set is related with marketing campaigns of a banking institution, containing 16 features of 45,211 individuals. The assigned classification task is to predict if a client will subscribe (yes/no) to a term deposit. The original data set is very unbalanced with only 4,667 positives out of 45,211 samples. Therefore, we combine “yes” points with randomly subsampled “no” points and perform experiments on the downsampled data set with 10,000 data points. The protected feature is the marital status of the client.
(3) COMPAS (Angwin et al., 2016): The COMPAS data set contains records of over 11,000 defendants from Broward County, Florida, whose risk (of recidivism) was assessed using the COMPAS tool. Each record contains multiple features of the defendant, including demographic information, prior convictions, degree of charge, and the ground truth for recidivism within two years. Following Zafar et al. (2017a); Nabi & Shpitser (2018), we limit our attention to the subset consisting of African-Americans and Caucasians defendants. The features we use include age, gender, race, number of priors, and degree of charges. The task is to predict the recidivism of the defendant and we choose race as the protected feature.
(4) German Credit6: The UCI German Credit data contains 20 features (7 numerical, 13 categorical) describing the social and economical status of 1,000 customers. The prediction task is to classify people as good or bad credit risks. We use the provided numerical version of the data and choose gender as the protected feature.
A.6 ADDITIONAL DISCUSSION
For classification, while randomization can ensure group level of fairness, there is still some inherent shortcoming of the criterion that we should pay attention to. For example, in the FICO case study in Hardt et al. (2016), for a specific client from certain demographic group, the decision of approve/deny the loan actually comes in two folds: if his/her credit score is above (below) the upper (lower) threshold, the bank approve (deny) the application for sure; if the score falls in the interval between two thresholds, the bank would flip a coin to make a decision. Then we can imagine the following situation when a client whose credit score falls within the interval between the upper and
4http://archive.ics.uci.edu/ml/datasets/Adult 5https://archive.ics.uci.edu/ml/datasets/bank+marketing 6https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data)
lower thresholds goes to a bank to apply a loan. He/she can ask (if conditions permit) the bank to run the model multiple times until the decision is approval. This would make the randomization that was built into the system for the sake of fairness no longer effective, and the system in essence only has one fixed threshold (i.e., the original lower threshold).

Review summaries:
This paper studies the attainability of Equalized Odds fairness criterion in both the classification and regression problems. When the prediction function is deterministic, it shows that Equalized Odds may not be attainable under certain conditions. In contrast, if the prediction function is randomized, then Equalized Odds classifiers can always be achieved under some conditions. Moreover, it shows that the performance attained using the in-processing approach after exploiting all available features is always better than attained using the post-processing approach. 

This paper studies under what conditions a classifier can satisfy the condition of equalized odds. The authors first prove an impossibility result which shows that (under linear non-gaussian case) any deterministic classifier	cannot achieve equalized odds across the protected groups. This leads to the question of randomized classifier. We can always satisfy equalized odds with randomized classifier  with a trivial classifier. However, the authors show two interesting results — (1) using the post-processing framework developed in Hard et. al. (2016) it is possible to obtain a non-trivial randomized classifier that satisfies EO, and (2) in-processing based classifiers are better than the post-processing based fair classifiers if we compare them in terms of accuracy.