Demographic parity in regression and classification within the unawareness framework
Vincent Divol Solenne Gaucher




1]Vincent Divol vincent.divol@ensae.fr
1]Solenne Gaucher solenne.gaucher@ensae.fr
[1]CREST, ENSAE, IP Paris
Demographic parity in regression and
classification within the unawareness framework
    [
     
====================================================================================



§ ABSTRACT 
This paper explores the theoretical foundations of fair regression under the constraint of demographic parity within the unawareness framework, where disparate treatment is prohibited, extending existing results where such treatment is permitted. Specifically, we aim to characterize the optimal fair regression function when minimizing the quadratic loss. Our results reveal that this function is given by the solution to a barycenter problem with optimal transport costs. Additionally, we study the connection between optimal fair cost-sensitive classification, and optimal fair regression. We demonstrate that nestedness of the decision sets of the classifiers is both necessary and sufficient to establish a form of equivalence between classification and regression. Under this nestedness assumption, the optimal classifiers can be derived by applying thresholds to the optimal fair regression function; conversely, the optimal fair regression function is characterized by the family of cost-sensitive classifiers.






§ INTRODUCTION



 §.§ Motivation









Recent breakthroughs in artificial intelligence have led to the widespread adoption of machine learning algorithms, exerting an increasingly influential and insidious impact on our lives. Essentially, these algorithms learn to detect and reproduce patterns using massive datasets. It is now widely recognized that these predictions carry the risk of perpetuating, or even exacerbating, the social discriminations and biases often present in these datasets <cit.>. Algorithmic fairness seeks to measure and mitigate the unfair impact of algorithms; we refer the reader to the reviews by <cit.> for an introduction.

Different approaches have been developed to mitigate algorithmic unfairness. One approach focuses on individual fairness, ensuring that similar individuals are treated similarly, regardless of potentially discriminatory factors. Another approach targets group fairness, aiming to prevent algorithmic  predictions
from discriminating against groups of individuals.
Statistical fairness falls under the latter approach and relies on the formalism of supervised learning to impose fairness criteria while minimizing a risk measure. In this work, we study risk minimization under the demographic parity criterion, which requires that predictions be statistically independent of sensitive attributes. Although this criterion, introduced by <cit.>, has some known limitations <cit.>, it finds application in a wide range of scenarios <cit.>. Its simplicity arguably makes it the most extensively studied criterion.





The statistical fairness literature can be broadly divided into two currents, depending on whether the direct use of the protected attribute in predictions is permitted or not. A first line of works, studying the awareness framework, considers regression functions that make explicit use of discriminating attributes, thus treating individuals differently based on discriminating factors. For this reason, this approach is also often referred to as disparate treatment. In this work, we adopt the unawareness framework, in which disparate treatment is prohibited and the regression function cannot directly use the sensitive attribute. Empirical evidence from simulations <cit.> indicates that within the unawareness framework, predictions often result in suboptimal trade-offs between fairness and accuracy and may induce within-group discrimination. Moreover, the authors conjecture that while the unawareness framework aims to prevent discrimination based on sensitive attributes, predictions in this setting implicitly rely on estimates of these attributes—a phenomenon later proven in <cit.> for classification problems. Nevertheless, this framework remains crucial in practice, as the direct use of sensitive attributes may be legally prohibited or simply unavailable at prediction time.

In this paper, we investigate the problem of fair regression under demographic parity constraints within the unawareness framework. A key difficulty in overcoming algorithmic unfairness is the limited understanding of how fair algorithms make predictions. Therefore, we focus on providing a simple mathematical characterization of the optimal regression function in the presence of fairness constraints. 




 §.§ Problem statement
  
Let (X,S,Y) be a tuple in ×× with distribution , where X corresponds to a non-sensitive feature in a feature space , S is a sensitive attribute in a finite set , and Y is a response variable that we want to predict, which has a finite second moment. To illustrate this problem with an example, assume, as in <cit.>, that X represents a candidate's skill, S is an attribute indicating groups of populations, and Y is the current market salary of the candidate. Due to historical biases, the distribution of the salary may be unbalanced between the groups. Our aim is to make predictions that are fair, and as close as possible to the current market value Y. In the unawareness framework, we cannot make explicit use of the sensitive attribute to make our predictions. Therefore, we consider regression functions of the form f :  → in the set of score functions . We want to ensure that our regression function satisfies the following demographic parity criterion.

The function f :  → verifies the Demographic Parity criterion if 

    f(X) ⊥ S.


In essence, the demographic parity criterion requires that the distribution of predictions (in our example, the salary) be identical across all groups. We assess the quality of a regression function f through its quadratic risk 

    _sq(f) = 𝔼[(Y - f(X))^2].


An optimal fair regression function f^* satisfies

    f^* ∈_f ∈{_sq(f) :  f(X) ⊥ S },

where  is the set of regression functions from  to . 

Classical results show that when no fairness constraints are imposed, the Bayes regression function  minimizing the squared risk _sq is a.s. equal to the conditional expectation η, where 

    η(x) = 𝔼[Y | X = x].

In this paper, we also investigate the relationship between classification and regression problem. When Y ∈{0,1} a.s., the quality of a classification function g : →{0,1} can be assessed through its expected weighted 0-1 loss _y(g), where for y ∈ [0,1], _y(g) is defined as

    _y(g) = y·ℙ[Y = 0,  g(X) = 1] + (1-y)·ℙ[Y = 1,  g(X) = 0].

For the choice y = 1/2, minimizing this risk measure corresponds to maximizing the classical accuracy measure. 

For a given value y∈ [0,1], an optimal fair classification function g^*_y verifies

    g^*_y ∈_g ∈{_y(g) :  g(X) ⊥ S },

where  is the set of classification
 functions from  to {0,1}. 

Let us again illustrate this problem with an example from recruitment. Assume that X represents a candidate's skill, S is an attribute indicating different population groups, and Y denotes whether a human recruiter would consider the candidate qualified for a given position. Due to historical biases, the distribution of the binary response Y may be unbalanced across the groups. We aim to make a prediction, or equivalently take the decision to accept or reject a candidate. Our goal is to make predictions for the value of Y, or equivalently, to decide whether to accept or reject a candidate, in a way that is both accurate and fair. Specifically, under demographic parity, we aim to ensure that the probability of acceptance is the same across all groups.

Classical results show that when no fairness constraints are imposed, the classifier _y(x) = 1{(x)  ≥ y } is a Bayes classifier that minimizes _y(g). This relationship is at the heart of the design and study of plug-in classifiers <cit.>. Interestingly, it was recently shown that a similar relationship holds under demographic parity constraints in the awareness framework <cit.>. Extending this result to the unawareness framework has remained an open problem, which we address in this paper.





  
Notation We first set some notation.  Recall that we are given a tuple (X,S,Y) in ×× with distribution , where  is any measurable space (the space of features) and  is a finite set (the set of labels). For s∈, we denote by p_s the probability (S=s) and by μ_s the conditional law of X|S=s. We let μ =  ∑_s∈ p_sμ_s be the marginal distribution of X. We let () be the set of probability measures on the measurable space . Moreover, we let L^1(ν)  be the space of functions integrable with respect to the probability measure ν. Finally, C denotes the interior of the set C.



 §.§ Related work



  
Fair classification Research on optimal prediction under demographic parity constraints has primarily focused on classification, where the goal is to predict a binary response in {0,1}, as this problem is intrinsically linked to the issue of fair candidate selection, central in algorithmic fairness. This problem is well understood in the awareness setting from an algorithmic point of view <cit.>. On the theoretical side, <cit.>  recently proved  that the optimal classifier for the risk _y can be obtained as the indicator that the optimal fair prediction function for the squared loss  f^* is above the threshold y, a result that was later extended in <cit.> to multi-class classification. 

Less is known about fair classification in the unawareness framework. On the algorithmic side, several works have proposed various relaxations of the demographic parity constraint, leading to tractable algorithms for computing  classifiers <cit.>. On the theoretical side, <cit.> provided empirical evidence suggesting that fair classifiers may base their decisions on non-relevant features correlated with the sensitive attribute, potentially disrupting within-group ordering. This hypothesis was further confirmed by <cit.>, who characterized the optimal fair classifier in the unawareness framework. They showed that it is given by the indicator that the conditional expectation η(X) is above a threshold, which depends on the probabilities that the individual described by X belongs to the different groups. Notably, the question of whether this classifier can be obtained by thresholding the optimal fair prediction function for the squared loss remains an open problem.



  
Fair regression In the awareness framework, fair regression is well understood  from both the algorithmic and theoretical points of view <cit.>. On the theoretical front, it has been shown that the problem of fair regression under demographic parity can be rephrased as the problem of finding the weighted barycenter of the distributions of η(X,S)=[Y|X,S] across different groups, with costs given by optimal transport problems.

    Assume that for all s ∈, the distribution ν_s of η(X,S) for S=s has no atoms, and let p_s = ℙ(S = s). Then,
    
    f is fairmin_sq(f) = min_ν∈()∑_s∈p_s_2^2(ν_s, ν)

    where _2^2(ν_s, ν) is the squared Wasserstein distance between ν_s and ν. Moreover, if f^* and ν solve the left-hand side and the right-hand side problems respectively, then ν is equal to the distribution of f^*(X,S), and 
    
    f^*(x,s) = (∑_s' ∈ p_s'_s')∘ F_s(η(x,s)),

    where _s and F_s are respectively the  quantile function and the c.d.f. of ν_s.

This result relates the problem of fair regression in the awareness framework to  a more general optimal transport problem. Interestingly, this problem has an explicit solution, given by the quantiles and c.d.fs of the conditional expectation η(X,S) across the different groups. This explicit formulation yields, as an immediate consequence, that the optimal fair regression function preserves order, a property introduced in <cit.> within the awareness framework. Recall that the Bayes regression function in the awareness framework is η. A prediction function f is said to preserve order if for any two candidates (x,x') ∈^2 in the same group s ∈, η(x,s) ≤η(x',s) implies f(x, s) ≤ f(x',s). Thus, this property implies that the fairness correction does not alter the ordering of the predictions within a group.

In contrast, the problem of fair regression within the unawareness framework has been seldom studied, particularly from a theoretical perspective. One reason for this is that the demographic parity constraint is more challenging to implement without disparate treatment. While algorithms complying with these constraints have been proposed by <cit.> and <cit.>,  the authors do not claim that the estimators obtained are optimal in terms of risk. <cit.> propose an algorithm based on a discretization of the problem, followed by a reduction to cost-sensitive classification. However, their algorithm requires calling an oracle cost-sensitive classifier, which may not be available in practice. Additionally, their results are limited to a class of regression functions with bounded Rademacher complexity.



 §.§ Outline and contribution


In this paper, we focus on the theoretical aspects of the problem of fair regression in the unawareness framework, specifically on characterizing and studying the optimal regression function. We extend  results presented earlier in the awareness framework to this setting, albeit under the assumption that the sensitive attribute takes only two values; henceforth, we assume that = {1,2}. Although restrictive, this assumption is not uncommon in the literature <cit.> and covers the important case where one of the two groups includes protected individuals. Our results shed light on important phenomena, and we leave the extension to scenarios with more than two groups to future work.

Similarly to the awareness case characterized in Theorem <ref>, we show that the solution to the fair regression problem in the unawareness framework is given by the solution to a barycenter problem with optimal transport costs. We begin  in Section <ref> with a brief introduction to optimal transport theory and to the main tools used in the proofs of our results. In Section <ref>, we characterize the optimal fair regression function. First, we prove in Proposition <ref> that in general, the optimal fair regression function f^* does not preserve order. Next, we demonstrate the following result, which relates fair regression in the unawareness framework to an optimal transport problem.


This result is formalized in Theorem <ref>.
    Under mild assumptions, the optimal fair regression function f^* is given by the solution to a barycenter problem with optimal transport costs. In particular, there exists a function f^* such that 
    
    f^*(x) = f^*(η(x), Δ(x)),

    where Δ(x) ∝ℙ(S= 1| X=x)/p_1 - ℙ(S= 2| X=x)/p_2.

Comparing this result to the one provided in Theorem <ref> within the awareness framework, we note that there is no explicit formula for the optimal fair regression function within the unawareness framework. Moreover, Theorem <ref> underscores that the optimal fair regression function effectively relies on an estimate Δ(X) of the unobserved sensitive attribute S to make predictions, thereby indirectly implementing disparate treatment. This result provides a theoretical explanation for the empirical phenomenon observed by <cit.>. As noted in their work,  this behavior is problematic as it can lead to basing predictions on factors that are not relevant to predicting the outcome Y, simply because they are informative for predicting the sensitive attribute S. 

In Section <ref>, we investigate the relationship between fair regression and fair classification when Y ∈{0,1}. We demonstrate the existence of a dichotomy based on a nestedness criterion.  Recall that as the threshold y increases, the Bayes classifier _y predicts 1 for a decreasing proportion of candidates; we show that this also holds for the optimal fair classifier g_y^*. We say that the fair classification problem is nested if, almost surely with respect to the measure μ of X, the prediction g^*_y(X) for the candidate X decreases as y increases. In other words, candidates rejected (i.e., with prediction 0) at low values of y cannot be accepted at higher values of y, when the proportion of accepted candidates is lower. For example, the Bayes classifier defined by _y(x) = 1{(x)  ≥ y } satisfies this condition. When the nestedness criterion holds, the decision boundaries for the optimal fair classifier for different risk _y form nested sets. 
The following informal result summarizes our findings.

    Under mild assumptions, if the fair classification problem is nested, then the regression function
    
    f^*(x) = sup{y ∈ : g^*_y(x) = 1}

    is optimal for the fair regression problem (<ref>); equivalently, the classifier
    
    g_y(x) = 1{f^*(x) ≥ y}

    is optimal for the fair classification problem (<ref>) for the risk _y. Conversely, if the classification problem is not nested and if f^* is the optimal fair regression function, then there exists y ∈ (0,1) such that 
    
    g_y(x) = 1{f^*(x) ≥ y}

    is sub-optimal for the fair classification problem with risk _y.

This result is formalized in Proposition <ref> and in Corollary <ref>
While nestedness may initially appear to be a natural assumption, it does not always hold. In Section <ref>, we show how to design examples of problems where this assumption is either met or violated.



§ A SHORT INTRODUCTION TO OPTIMAL TRANSPORT

In this section, we provide a brief introduction to optimal transport. We present the main tools that will be used in the proofs of the theorems in Sections <ref> and <ref>. We begin by providing an overview of  optimal transport in Section <ref>, before discussing the multi-to-one dimensional transport problem in Section <ref>.



 §.§ The optimal transport problem

Optimal transport provides a mathematical framework  to compare probability distributions. Consider a Borel probability measure μ on a Polish space  and a Borel probability measure ν on some other Polish space . We are given a  continuous cost function c:×→ [0,+∞], where c(x,y) represents the cost of moving a unit of mass from x∈ to y∈. The optimal transport problem consists in finding the optimal way of moving the distribution of mass μ to ν by minimizing the total displacement cost. Formally, a transport map is a measurable map T:→ such that the pushforward measure T♯μ of μ by T is equal to ν, where the pushforward measure is defined for all measurable sets B⊂ by

    T♯μ(B)=μ(T^-1(B)).

The optimal transport problem  is then the following

    minimize  ∫ c(x,T(x))μ(x)
       under the constraint T♯μ = ν.

The existence of minimizers of the optimization problem (<ref>) is a delicate problem that depends on both  the regularity of the cost function c and the properties of μ and ν. For instance, when ==^d  and c(x,y)=x-y^2, a solution exists whenever μ gives zero mass to sets of dimensions smaller than d-1; otherwise, a solution may not exist, see <cit.>.  When ==^d  and c(x,y)=x-y^2, the corresponding minimum is known  as the (squared) Wasserstein distance between μ and ν, denoted by _2^2(μ,ν).
More generally, an optimal transport map exists whenever μ gives zero mass to sets of dimensions smaller than d-1 and the cost function c(x,y)=x-y^2 is replaced by any smooth cost function c satisfying the so-called twist condition, which states that the determinant (∂^2 c/∂ y_j∂ x_i) never vanishes.

The optimal transport problem also admits a relaxed version in terms of transport plans, which is often more convenient to work with. A transport plan is a probability measure π on the product space × which has first marginal equal to μ and second marginal equal to ν: for all measurable sets A⊂ and B⊂,

    π(A×)=μ(A),  π(× B)=ν(B),

or, in probabilistic terms, if (X,Y)∼π, then X∼μ and Y∼ν. Informally, for x∈, the conditional law of Y|X=x describes the different locations where the mass initially at x will be sent. 
The cost of a transport plan π is given by

    ∬ c(x,y) π(x,y).

Note that a transport map T induces a transport plan by considering the law π of (X,T(X)) (formally, π=(𝕀, T)♯μ). The optimal transport cost is defined by the following minimization problem:

    _c(μ,ν)=min_π∈Π(μ,ν)∫ c(x,y)π(x,y),

where Π(μ,ν) is the set of transport plans between μ and ν. Optimal transport plans always exist, whereas optimal transport maps may fail to do so. When optimal transport maps exist and the source measure μ has no atoms, the minimization problem (<ref>) gives the same value as the optimal transport cost defined in (<ref>), see <cit.>.


Our proofs will rely heavily on the dual formulation of the optimal transport problem, which we now introduce. The c-transform of a function ϕ:→∪{+∞} is defined as

    ∀ x∈, ϕ^c(x)=sup_y∈(ϕ(y)-c(x,y)).


The subdifferential of ϕ is defined as

    ∂_cϕ={(x,y)∈×: ϕ(y)-ϕ^c(x)=c(x,y)}.

For the quadratic cost, these notions are closely related to the usual notions of convexity, with c-transforms being analogous to the concept of convex conjugates.


Kantorovich duality  <cit.> states that 

    _c(μ,ν)       =sup_ϕ∈ L^1(ν)∫ϕ(y)ν(y)-∫ϕ^c(x)μ(x).

Moreover, under the mild assumption that there exist two  functions a∈ L^1(μ) and b∈ L^1(ν) such that c(x,y)≤ a(x)+b(y) for all x∈, y∈, the previous supremum is attained by a function ϕ, which we call a Kantorovich potential. In that case, any optimal transport π is supported on the subdifferential of the c-convex function ϕ, meaning that

    π(∂_cϕ)=1.

This last condition imposes significant constraints on the structure of optimal transport plans. For the quadratic cost, this fact is the key ingredient in proving that optimal transport plans are induced by optimal transport maps.






















 §.§ Multi-to-one dimensional optimal transport

In the next section, we demonstrate that the fair regression problem within the unawareness framework can be reduced to a barycenter problem of the form:

    min_ν∈() p_1_c(μ_1,ν)+p_2_c(μ_2,ν),

where μ_1, μ_2 are two-dimensional probability measures and c:^2×→ [0,+∞) is a cost function. This reduction raises the question of whether the solutions to the barycenter problem (<ref>) can be characterized by transport maps.


Proving that the optimal transport problem _c(μ_s,ν) is solved by a transport map is nontrivial. Complications arise because the measures μ_s and ν are defined on spaces of different dimensions. Optimal transport problems involving spaces of different dimensions have not been as extensively studied and exhibit distinct properties compared to the standard case where both measures are defined on the same space, see  <cit.>. For instance, the classical twist condition (∂^2 c/∂ y_j∂ x_i)≠ 0 does not make sense in this setting: the Hessian matrix of c is not squared, so that the determinant is not even well-defined. 

 <cit.> focus on the optimal transport problem between a measure μ supported on a domain ⊂^m (with m>1) and a measure ν on an interval ⊂ for some cost function c:×→ [0,+∞). They demonstrate that an optimal transport map T:→ between μ and ν exists under a natural condition on (c,μ,ν) known as nestedness. For y∈, k∈, let

    _≤(y,k)={x∈: ∂_y c(x,y)≤ k}.

Kantorovich duality implies that an optimal transport plan between μ and ν will match an interval (-∞,y] to a set _≤(y,k), where k=k(y) is a solution of the equation ν((-∞,y])=μ(_≤(y,k)). 
The triplet (c,μ,ν) is called nested if the collection of sets (_≤(y,k(y)))_y  increases with y. <cit.> prove that an optimal transport map T between μ and ν exists when the problem is nested: informally, the monotonicity of (_≤(y,k(y)))_y ensures that a given x_0∈ belongs to the boundary of a single set _≤(y_0,k(y_0)), with y_0 being equal to T(x_0).

This nestedness condition will be crucial in <Ref>, where it will be  used to establish the equivalence between regression and classification problems. However, in <Ref>, we will be able to show the existence of optimal transport maps for the barycenter problem (<ref>) (and consequently of optimal fair regression functions) without any nestedness condition. 



§ FAIR REGRESSION AND THE BARYCENTER PROBLEM
 
In this section, we characterize the solution to the fair regression problem. We begin by showing in Section <ref> that, under mild assumptions, the fair regression function does not preserve order. Then, in Section <ref>, we show that the fair regression problem can be reduced to a barycenter problem with optimal transport costs. Using the tools introduced in Section <ref>, we prove the existence of a fair optimal prediction function and study some of its properties.



 §.§ Fair regression functions do not preserve order

Before analyzing in detail the fair regression problem in the unawareness framework, we establish a simple yet important property of fair regression functions. We begin by extending the definition of order preservation <cit.> to the unawareness framework. Recall that in this case, the Bayes prediction for a candidate x is given by η(x)=[Y|X=x]. A prediction function f is said to preserve order if, for any two candidates (x,x') ∈^2 in the same group s ∈, η(x) ≤η(x') implies f(x) ≤ f(x'). This definition is formalized below.



A prediction function f preserves order if ⊗-almost surely,

    {η(X)<η(X')  and  S = S' } f(X)< f(X').
  

This property implies that the fairness correction does not alter the ordering of the predictions of the Bayes prediction function within a group. It is related to the concept of “rational ordering” introduced by <cit.> in the context of classification, where the authors require that within a group, the most able candidates are the ones accepted. 


    Let f:→ be a  regression function with [f(X)^2]< ∞ satisfying the demographic parity constraint. Assume that the Bayes regression function η does not satisfy the demographic parity constraint and that 
    (S=s|X=x)∈ (0,1) for all s∈, x∈. Then, f does not preserve order.





We prove the contrapositive: if f is a regression function satisfying the demographic parity constraint and preserving order, then the Bayes regression function also satisfies the demographic parity constraint. For a fixed group s∈, consider the joint law π_s of (η(X),f(X)), where X∼μ_s. As f is envy-free, the support of the measure π_s is monotone, in the sense that

    ∀ (y_1,z_1), (y_2,z_2)∈(π_s), y_1< y_2 z_1<  z_2.

According to <cit.>, this implies that π_s is actually the optimal transport plan for the quadratic cost between the first marginal of π_s, equal to η♯μ_sν_s and the second marginal of π_s, equal to f♯μ_sν (the second measure does not depend on s because of demographic parity). We claim that  strict monotonicity implies that the  transport plan π_s takes the form of a transport map T_s transporting ν towards ν_s, that is π_s = (T_s,𝕀)♯ν (see a proof below). So, if X∼μ_s, we have (η(X),f(X))=(T_s(f(X)),f(X)) almost surely. To put it another way, we have for every s,

    η(x) = T_s∘ f(x)  μ_s-almost everywhere.

As (S=s|X=x)>0 for all x∈, this equality is also satisfied μ-almost everywhere. Hence, for μ-almost all x, the quantity T_s∘ f(x) does not depend on s (it is equal to η(x)). This defines a function T with  η♯μ_s = T♯ f♯μ_s= T♯ν. As this measure does not depend on s, this proves that η satisfies the demographic parity constraint. 

To conclude our proof, it remains to prove our claim. Decompose ν as ν_1+ν_2 where ν_2 is atomless and ν_1 = ∑_j p_j δ_z_j. If f(X)=z_j, then we have η(X)=y_j for some value y_j: this value y_j has to be unique, for otherwise it would contradict the monotonicity assumption. Therefore, ν_s can be written as ν_s = ν_1s+ν_2s, where ν_1s = ∑_j p_jδ_y_j. Consider the plan π_1 = ∑_j p_j δ_(y_j,z_j). Then π-π_1 is a plan between ν_2s and ν_2. By <cit.>, as ν_2 is atomless, the monotonicity condition implies that it is induced by a transport map T̃_s. In total, we can define T_s by T_s(z_j)=y_j and by T_s=T̃_s on the complementary set of the atoms. 

Proposition <ref> implies, in particular, that in many instances, the optimal fair regression function does not preserve order. Consequently, highly qualified individuals who belong to  protected groups could potentially suffer from  fairness corrections due to the demographic parity constraint.

The condition that  (S=s|X=x)∈ (0,1) for all s∈, x∈ ensures that the sensitive attribute S cannot be determined from the observation of X. When this condition is not satisfied, the distinction between the unawareness and awareness frameworks becomes blurred: if S can be inferred from  X alone, it becomes meaningless to differentiate  between a regression function that depends on both X and S, and one that depends solely  on X. Furthermore, it is important to note that in the awareness framework, there do exist regression functions that satisfy the demographic parity constraint and preserve order, with the optimal fair regression function described in  <Ref> being one such example.



 §.§ Reduction to an optimal transport problem

In the following, we let ={1,2}. 
We assume that μ_1≠μ_2 (otherwise the Bayes regression function η already solves the fair regression problem). We now show how to transform the fair regression problem into a barycenter problem using optimal transport costs. To do so, we first leverage a reformulation of the demographic parity constraint due to <cit.>, which is based on  the Jordan decomposition of the signed measure μ_1 - μ_2. Then, we show how to rephrase the regression problem as a barycenter problem, using this new constraint. Finally, we show that, under mild assumptions, the barycenter problem admits a unique solution, which is given by a transport map.



  §.§.§ Reformulation of the demographic parity constraint
 Let |μ_1-μ_2| be the  variation of μ_1-μ_2 and define

    (μ_1 - μ_2)_+ = 1/2(|μ_1-μ_2|+μ_1-μ_2), 
    
     (μ_1 - μ_2)_- = 1/2(|μ_1-μ_2|-μ_1+μ_2)

the Jordan decomposition of μ_1-μ_2. The two measures (μ_1 - μ_2)_+ and (μ_1 - μ_2)_- have the same mass, which we denote by m. We define the scaled Jordan decomposition of μ_1-μ_2 as the pair of probability measures

    μ_+ = (μ_1 - μ_2)_+/m   and  μ_- = (μ_1 - μ_2)_-/m.

Let μ_+/μ (resp. μ_-/μ) be the density of μ_+ (resp. μ_-) with respect to μ (that are defined uniquely μ-almost everywhere). As μ_+ and μ_- are mutually singular measures, we can always find versions of μ_+/μ and μ_-/μ such that the sets

    _+={x∈ : μ_+/μ(x)>0},
    _-={x∈ : μ_-/μ(x)>0},
    _==\ ( _+⊔_-).

form a partition of , with μ_+ giving mass 1 to _+ and μ_- giving mass 1 to _-. Then, for for any three functions f_+, f_-, and f_= from  to ℝ, we can define the associated function (f_+, f_-, f_=) equal to f_+ on _+, f_- on _-, and f_= on _=:

    (f_+, f_-, f_=)(x) = 
            f_+(x)    if  x ∈_+
    
            f_-(x)    if   x ∈_-
    
            f_=(x)    if   x ∈_=.

Conversely, for any function f:→ℝ, there exist functions f_+, f_-, and f_= corresponding respectively to the restriction of f on _+, _-, and _=, i.e., such that f = (f_+, f_-, f_=).
The following lemma, due to <cit.>, rephrases the demographic parity constraint in terms of μ_+ and μ_-.

    A regression function f : →ℝ verifies the demographic parity constraint if and only if 
    
    f♯μ_+ = f♯μ_-.






Lemma <ref> reveals that for any 
functions f, and f_+, f_-,  f_= such that f = (f_+, f_-, f_=), the regression function f
satisfies the demography parity constraint if and only if f_+♯μ_+ =f_-♯μ_-. The two functions f_+ and f_- can be chosen with disjoint support (in _+ and _-, respectively). Thus, the demographic parity constraint essentially reduces to the equality of the pushforward measures of two distinct probabilities (μ_+ and μ_-) by two distinct functions (f_+ and f_-). 



  §.§.§ A barycenter problem

In order to rephrase the regression problem as a barycenter problem, we introduce further notation. We define 

    Δ(x)= μ_+/μ(x)     if  x∈_+,
    Δ(x)= -μ_-/μ(x)     if  x∈_-,
    Δ(x)= 0     if  x∈_=.

Equivalently, Δ(x) is proportional to μ_1/μ(x)-μ_2/μ(x).




We also define the cost c : ×→ [0,+∞] given by c(x,y) = (η(x) - y)^2/|Δ(x)| for all x∈ and all y∈ℝ. When X∼μ_±, the variables (η(X), Δ(X)) belong to Ω{(h,d)∈^2: d≠ 0}. 
In the following, we use bold notation to denote functions related to these two-dimensional variables. For example, we denote by  (resp. ) the distributions of (η(X), Δ(X)) when X follows the distribution μ_+ (resp. μ_-). Note that the support of  is included in the upper half-plane {d>0} while  is included in the lower half-plane {d<0}. 

We define the two-to-one dimensional cost , given by (, y) = (h - y)^2/|d| for all = (h,d)∈Ω and y∈. 

Consider the barycenter problem

    minimize  _(, ν) + _(,ν)  over ν∈()

where we recall that _(, ν) is the optimal transport cost for sending  to ν with cost function , defined in Equation (<ref>). We say that a solution ν^bar of the barycenter problem is solved by optimal transport maps if 

    _(, ν^bar) = ∫(, ())()

for some transport maps  :Ω→ from  to ν^bar.


There is a one-to-one correspondence between the set of solutions to the barycenter problem (<ref>) solved by optimal transport maps and the set of optimal fair regression functions solving (<ref>). This correspondence associates  a barycenter ν^bar with optimal transport maps  to the optimal fair regression function f=(f_+,f_-,η), where f_±(x)= (η(x),Δ(x)) for x∈.


Classical computations show that _sq(f) = 𝔼[(η(X) - f(X))^2] + 𝔼[(η(X) - Y)^2]. Thus, minimizing the risk is equivalent to minimizing 𝔼[(η(X) - f(X))^2]. Now,

    𝔼[(η(X) - f(X))^2] = ∫ (η(x)-f(x))^2 μ(x)
          =∫_𝒳_+  (η(x)-f(x))^2 μ/μ_+(x) μ_+(x) + ∫_𝒳_- (η(x)-f(x))^2 μ/μ_-(x) μ_-(x)
             +  ∫_𝒳_=  (η(x)-f(x))^2 μ(x).

Using the definition of Δ along with Lemma <ref>, we see that any solution to the fair regression problem can be written as f = (f_+, f_-, η), where (f_+, f_-) is solution to the problem

    minimize  ∫_𝒳_+(η(x) - f_+(x))^2/|Δ(x)|μ_+(x) + ∫_𝒳_-(η(x) - f_-(x))^2/|Δ(x)|μ_-(x) 
       such that    f_+♯μ_+ = f_-♯μ_-.

The triplet (η(X), Δ(X), f(X)) defines a  coupling π_f+ between  and ν_f+ = f_+ ♯μ_+. Likewise, we define a coupling π_f- between   and ν_f-. We can rewrite (<ref>) as

    𝔼[(η(X) - (f_+, f_-, η)(X))^2]    = ∫(,y)π_+f(,y) + ∫ c(,y)π_-f(,y) 
       ≥_ (,ν_f+)+_(,ν_f-).

The constraint  f_+♯μ_+ = f_-♯μ_- implies that ν_f+ = ν_f-. Hence,

    inf_f fair𝔼[(η(X) - f(X))^2] ≥inf_ν∈()_ (,ν)+_(,ν).



Reciprocally, assume that there exists ν^bar solving the above barycenter problem, and that an optimal transport map between  and ν^bar is given by an application : Ω→, with () ♯=ν^bar. Likewise, we assume that there exists an optimal transport map  between  and ν^bar. Then, ♯ = ♯ = ν^bar. Defining f_±(x) =(η(x),Δ(x)), we have f_-♯μ_- =  f_+♯μ_+ = ν^bar, and so (f_+, f_-, η) is a fair regression function. Also, we have by optimality that

    _(,ν^bar)+_(,ν^bar)    = ∫ c(x,f_+(x))μ_+(x) + ∫ c(x,f_-(x)) μ_-(x) 
       = [(η(X)-(f_+, f_-, η)(X))^2].

Hence, by (<ref>), the regression function (f_+, f_-, η) is optimal. This concludes the proof of Lemma <ref>.




  §.§.§ Transport maps for the barycenter problem


The rest of this section is devoted to proving that the barycenter problem indeed admits a solution given by transport maps, which will imply that there exists a solution to the fair regression problem. We show that this holds under the following mild regularity assumption.

 
The measures  and  give zero mass to graphs of functions in the sense that for  any measurable function F:\{0}→, ({(F(d),d): d≠ 0})=0.

By Fubini's theorem, this assumption is trivially satisfied if  and  have a density with respect to the Lebesgue measure. Another interesting example is given by the awareness framework, seen as a particular instance of the unawareness framework. 

 
Consider a triplet of random variable (X,S,Y)∼, where X∈ is a feature, S∈{1,2} is a sensitive attribute and Y∈ is a response variable of interest. Let Z = (X,S) and let  be the law of the triplet (Z,S,Y). Then, there is an  equivalence between considering an aware regression function f(X,S) under law  and an unaware regression function f(Z) under law . Note that Z is a random variable on =×{1,2}. The laws μ_1 of Z|S=1 and μ_2 of Z|S=2 have disjoint support. It follows that _+=×{1} with μ_+=μ_1 and _-=×{2} with μ_-=μ_2. Then, Δ(x)=1/p_1 if x∈_+ and Δ(x) = -1/p_2 if x∈_-. In particular, both measures  and  are supported on horizontal lines in Ω. 

In that case, Assumption <ref> is equivalent to the fact that  and  have no atoms, which is exactly equivalent to the fact that the law of η(X) (for X∼μ) has no atoms. This assumption is often considered to be a minimal assumption to ensure the existence of optimal fair regression functions in the awareness framework. Hence, Assumption <ref> constitutes a  generalization of this assumption to the unawareness framework.



Assume that (X,Y,S)∼ is such that [Y^2]<∞. 
Under Assumption <ref>, there is a unique  minimizer ν^bar of the barycenter problem 

    inf_ν_ (,ν)+_(,ν).

Moreover, this problem is solved by optimal transport maps . In particular, there exists a unique solution f^* of the regression problem under the demographic parity constraint (<ref>), which is given by

    ∀ x∈,    f^*(x) = ((η(x), Δ(x) ), (η(x), Δ(x)), η(x)).





  
Using Lemma <ref>, it is enough to show that the barycenter problem admits a unique solution ν^bar such that the corresponding transport problems _(, ν^bar) and _(, ν^bar) are solved by transport maps. 


Step 1: reduction to a standard transport problem. We begin by reducing the barycenter problem (<ref>) to a single two-to-two dimensional optimal transport problem _(, ). The multimarginal version of the barycenter problem reads

    inf_ν∈()_ (,ν)+_(,ν)= inf_ρ∈Π(·, ,)∫ ( (_1,y)+(_2,y)) ρ(y,_1,_2),

where Π(·, ,) stands for the set of measures on ×Ω×Ω with second marginal  and third marginal . Indeed, if ρ∈Π(·, ,), then its two first marginals provide a transport plan between its first marginal ν and , while the first and last marginals provide a transport plan between ν and . This proves that the left-hand side of Equation (<ref>) is smaller than the right-hand side. For the other inequality, consider ν∈(), with associated optimal transport plans π_+∈Π(,ν) and π_-∈Π(,ν). By the gluing lemma (see, e.g., Lemma 5.5 in <cit.>), there exists ρ∈Π(·, ,) such that the joint law of the first two marginals is equal to π_+, and the joint law of the first and last marginal is equal to π_-. Then, _ (,ν)+_(,ν)=∫ ( (_1,y)+(_2,y)) ρ(y,_1,_2), proving that the right-hand side is smaller than the left-hand side in (<ref>). This shows the validity of (<ref>).



Furthermore, if ρ solves the right-hand side of (<ref>), then its first marginal ν is a barycenter. Actually, by optimality, for any (y,_1,_2) in the support of the optimal ρ, the point y necessarily minimizes the function z↦(_1,z)+(_2,z). Let us compute this minimizer. For  _1 = (h_1, d_1) and _2 = (h_2, d_2), we have

    (_1,y) + (_2,y) = (h_1-y)^2/|d_1| + (h_2-y)^2 /|d_2|.

This function is convex in y. The first order condition for optimality reads

    (y-h_1)/|d_1| + (y-h_2)/|d_2| = 0  ⟺ y = m(_1,_2)h_1 /|d_1| + h_2 /|d_2|/1/|d_1|+1/|d_2|.

Moreover, the cost (_1,_2) inf_y (_1, y) +  (_2, y) corresponding to this minimum is equal to 

    (_1,_2) =  (h_2-h_1)^2 /|d_1|+|d_2|.

These considerations show that

    inf_ν∈()_ (,ν)+_(,ν)=_(,),

and that optimal transport plans π^*∈Π(,) are in correspondence with barycenters ν through the formula ν=m ♯π^*. In particular, as there exists at least one optimal transport plan, the infimum in the barycenter problem is actually a minimum. 







Step 2: existence of a transport map.
Note that 

    (_1,_2)=(h_1-h_2)^2/|d_1|+|d_2|≤ 2h_1^2/|d_1| + 2h_2^2/|d_2|.

This quantity is integrable against ⊗. Indeed, 

    ∫h_1^2/|d_1|(h_1,d_1)=∫η(x)^2/Δ(x)μ_+(x) = ∫__+η(x)^2 μ(x) ≤[[Y|X]^2]≤[Y^2]<∞.

In particular, the optimal cost _(, ) is finite. Hence, by Kantorovich duality (see <Ref>), there is a -convex function (called a Kantorovich potential) ϕ: Ω→∪{+∞} such that if we let 

    Γ = {(_1,_2): ϕ(_1)-ϕ^(_2)=(_1,_2)}

be the subdifferential of ϕ, 
then any optimal transport plan π satisfies π(Γ)=1, see <Ref>. 
 We show in Appendix <ref> the following lemma.
 
 
    Let  ϕ:Ω→∪{+∞} be a -convex function with dom(ϕ):={: ϕ()<+∞}. Then, the set  of points ∈dom(ϕ) such that the partial derivative ∂_h ϕ() does not exist is included in a countable union of graphs of measurable functions F:d∈\{0}↦ F(d)∈.


Let Σ be the countable union of graphs given by Lemma <ref> for the Kantorovich potential ϕ. According to Assumption <ref>, if we let Ω_0=Ω\Σ, then (Ω_0)=1. 

Let _1∈Ω_0 and let (_1,_2)∈Γ. Consider the function g__2:∈Ω↦ϕ()-(,_2). As ϕ^(_2) =ϕ(_1)- (_1,_2), by definition of the -transform, the function g__2 attains its maximum at _1.  In particular, as ∂_h_1ϕ(_1) exists by assumption, we have

    ∂_h ϕ(_1)= ∂_h_1(_1,_2) = 2(h_1-h_2)/|d_1|+|d_2|.












This implies that

    h_2 = h_1 - |d_1|+|d_2|/2∂_h_1ϕ(_1).

Using this expression, we find that

    m(_1,_2) =  h_1 - |d_1|∂_h_1ϕ(_1)/2.

In particular, m(_1,_2) is uniquely determined by _1. This defines a  measurable map _1∈Ω_0 ↦(_1). We extend  on Ω by setting (_1)=0 if _1∈Ω\Ω_0. As explained in Step 1, for (_1,_2)∼π^*, the law ν of m(_1,_2) solves the barycenter problem _(, ).  Hence,  ν = m♯π^*=(𝕀 ,)♯ is a barycenter.

Step 3: uniqueness of a transport map. 

Likewise, we show the existence of a function  such that  ν' =(𝕀 , )♯ is a barycenter. If we show that there is a unique barycenter, then ν=ν'=ν^bar, and the theorem is proven.


We now show uniqueness of the barycenter. Let ν be any measure that solves the barycenter problem. Let π_+ (resp. π_-) be an optimal transport plan for _(,ν) (resp. _(,ν)). By the gluing lemma, there exists ρ∈Π(·, , ) whose joint law of the two first marginals is equal to π_+, and whose joint law of the first and last marginal is equal to π_-. The joint distribution π between the second and last marginal is a transport plan between  and . Furthermore, as ν is a barycenter and by definition of , we have 

    _(,)   =_(,ν)+_(,ν)= ∫ ((_1,y)+c(_2,y))ρ(y,_1,_2)
       ≥∫(_1,_2)π(_1,_2),
 
so that π is an optimal transport plan between  and , with  ν=m♯π. But then, recall that (<ref>) holds for any optimal transport plan π (for the same potential ϕ). Hence, by the same arguments as before, we have ν=()♯ for the map :_1↦  h_1 - d_1∂_h_1ϕ(_1)/2 (defined -almost everywhere). In particular, ν is uniquely determined  by  and  through the potential ϕ.



Theorem <ref> is the counterpart of Theorem <ref>, established by <cit.> and <cit.> within the awareness framework. Both theorems demonstrate that the optimal fair regression function solves a barycenter problem with optimal transport costs. Remark <ref> further indicates that Theorem <ref>  generalizes Theorem 2.3 in <cit.>, as the awareness framework can be considered as a special case of the unawareness framework. However, unlike in the awareness framework, there is no explicit formulation of the optimal fair prediction function in the unawareness framework, as the corresponding barycenter problem involves multi-to-one dimensional transport costs with no explicit solutions.

Theorem <ref> reveals that the fair prediction f^*(x) only depends on the bi-dimensional feature (η(x), Δ(x)) of the candidate x. By definition, Δ(x)∝μ_1/μ(x) - μ_2/μ(x). Moreover, we have ℙ(S= 1| X=x) = p_1μ_1/μ(x) and ℙ(S= 2| X=x) = p_2μ_2/μ(x). Thus,  Δ(x) ∝ℙ(S= 1| X=x)/p_1 - ℙ(S= 2| X=x)/p_2. In other words, Δ(x) reflects the probability that x belongs to the different groups. Hence, in the unawareness framework, the optimal fair regression function effectively relies on estimates of S to make its prediction. This result provides a theoretical justification for the empirical observations of <cit.>. As noted by these authors, this phenomenon may be undesirable, as it means that the predictions can rely on features not relevant to predict the response Y, simply because they are predictive of the group S.



§ LINKS BETWEEN CLASSIFICATION AND REGRESSION PROBLEMS


We now turn to the study of the relationship between fair regression and fair classification problems within the unawareness framework.  When Y∈{0,1}, classical results show that the Bayes classifier _y minimizing the risk

    _y(g) = y·ℙ[Y = 0,  g(X) = 1] + (1-y)·ℙ[Y = 1,  g(X) = 0].

is given by _y(x) = 1{(x)  ≥ y }, where  is the Bayes regression function minimizing _sq. Similarly, recent results by <cit.> demonstrate that in the awareness framework, the optimal fair classifier g_y^* minimizing the risk _y is given by g^*_y(x,s) = 1{f^*(x,s)  ≥ y }, where f^* is the optimal fair regression function minimizing _sq. These results can be leveraged to obtain plug-in classifiers ĝ using estimates f̂ of the regression function. 

Somewhat less explored is the converse relationship: given a family of optimal classifiers (g_y)_y∈ [0,1] for the risks (_y)_y∈ [0,1], one could define a regression function f of the form f(x) = sup{y : g_y(x) = 1}. For example, this formulation yields the Bayes regression function when using Bayes classifiers and the optimal fair regression function when using optimal fair classifiers in the awareness framework. In both examples, this relationship may not be particularly useful since there already exists an explicit characterization of the optimal regression function. However, if this relationship were to hold in the unawareness framework, it would be significantly more valuable. Indeed, Theorem <ref>  rephrases the fair regression problem as a barycenter problem with optimal transport costs but does not provide an explicit solution.

<cit.> proposed leveraging this relationship to address the problem of fair regression using cost-sensitive classifiers. The authors demonstrate an equivalence between minimizing a discretized version of the risk _sq and minimizing the average of the cost-sensitive risks (_y(g_f,y))_y ∈ for a finite set , where g_f,y is defined as g_f,y(x) = 1{f(x) ≥ y}. To obtain the optimal fair regression function for this discretized risk, the authors assume access to an oracle that returns the regression function f such that g_f,y minimizes the average of the risks (_y(g_f,y))_y ∈. We emphasize that minimizing the average of the risks (_y(g_f,y))_y ∈ remains an open and challenging problem. 

In contrast, to define a regression function of the form  f(x) = sup{y : g_y(x) = 1}, one only needs to solve independent cost-sensitive classification problems. Recent results by <cit.> offer an explicit characterization of these classifiers. This raises the intriguing possibility of constructing the optimal fair regression function in the unawareness framework using these fair classifiers. In this section, we demonstrate that such a construction is not always possible. To do so, we begin by providing some reminders on fair classification in the unawareness framework.



 §.§ Fair classification

In this section, we assume that Y∈{0,1} almost surely. We consider the problem of minimizing a family of risk measures _y under the demographic parity constraint. We show that the optimal fair classifier for the risk _y is of the form g_y^κ 
for some κ∈ℝ, where g_y^κ
is given by 

    ∀ x∈,      g_y^κ(x)= {η(x) ≥ y + κΔ(x)}.

The following proposition extends Proposition 5.3 in <cit.>, and characterizes the optimal fair classifier.

Let y∈, and let κ^*∈ verify

    μ_+η(X) ≥ y + κ^*Δ(X) = μ_-η(X) ≥ y + κ^*Δ(X).

Under Assumption <ref>, g_y^κ^* solves the fair classification problem

    C_yminimize     ℛ_y(g)
    such that     𝔼[g(X) | S = 1] = 𝔼[g(X) | S = 2].

Moreover, all solutions to (C_y) are a.s. equal to g_y^κ^* on ∖{x∈: η(x) = y  and Δ(x) = 0}.

The optimal classifier is uniquely defined outside of  {η(x) = y}. While the set {η(x) = y  and Δ(x) ≠ 0} has null measure under Assumption <ref>, the set {η(x) = y  and Δ(x) = 0} may have positive measure. On this set, the classifiers {η(x) ≥ y} and {η(x) > y} differ, yet they are both optimal for the risk _y(g).

The proof of this proposition is postponed to Appendix <ref>. As discussed in the previous section, Assumption <ref> encompasses as a special case the awareness framework. In this case, the optimal classifier presented in Proposition <ref> reduces to the optimal fair classifier in the awareness framework given by

    ∀ (x,s)∈×{1,2},   g_y^aware(x,s)= {η(x) ≥ y + κ^*/p_1}    if  s=1
    {η(x) ≥ y - κ^*/p_2}    if  s=2,

as described in <cit.>.



In the unawareness framework, the optimal classifier relies on the probability that the observation X belongs to the different groups Δ(X). This behavior is similar to that of the optimal fair regression function, as established in Theorem <ref>. Next, we investigate whether the optimal classifier is envy-free.


    We say that a classifier g : →{0,1} is envy-free within group if ⊗-a.s., for (X,S) and (X',S') such that S = S' and (X) > (X'), we have g(X) ≥ g(X').

In essence, this property ensures that no candidate who would have been accepted by the Bayes classifier but is rejected after fairness correction envies another candidate from the same group who would have been rejected by the Bayes classifier but is accepted after fairness correction. Note that this property is weaker than order preservation, as a classifier that preserves order is envy-free within groups. 

Proposition <ref> reveals that in the unawareness framework, the optimal fair classifier is generally not envy free. This behavior contrasts with that of optimal fair classifiers in the awareness framework: indeed, since these classifiers preserve order, they are also envy-free.


Let y∈. Under Assumption <ref>, if ℙ(S = s| X = x)∈ (0,1) for all s∈, x∈, then one of the following cases hold:

    
  *  _y(x) = 1  g^κ^*_y(x) = 1 μ-a.s.
    
  *  g^κ^*_y(x) = 1 _y(x) = 1 μ-a.s.
    
  * the classifier g^κ^*_y is not envy-free within group.




Assume that <ref>. and <ref>. do not hold. Then, we have κ^* ≠ 0, and we can assume without loss of generality that κ^* > 0. Since <ref>. does not hold, we have that μ(_y(X) = 1  and  g^κ^*_y(X) = 0)>0.  This implies in turn that μ_+((X) = 1  and  g^κ^*_y(X) = 0)>0, since _y and g^κ^*_y coincide on _=, and since by definition when κ^* >0, we have μ_-(_y(X) = 1  and  g^κ^*_y(X) = 0) = 0. Similarly, we can show that since <ref>. does not hold, μ_-(_y(X) = 0  and  g^κ^*_y(X) = 1) >0. Now, ℙ(S = s| X = x)∈ (0,1) for all s∈, so μ_1 ≫μ_+ and μ_1 ≫μ_-. Therefore, μ_1(_y(X) = 1  and  g^κ^*_y(X) = 0) > 0, and μ_1(_y(X) = 0  and  g^κ^*_y(X) = 1)> 0. This implies 
    ℙ(_y(X) > _y(X')  and  g^κ^*_y(X) <  g^κ^*_y(X')| S = S' = 1)>0

which concludes the proof.




  
Extending cost-sensitive classification to = ℝ In the following, we consider the more general case where = ℝ. Although the interpretation in terms of optimal classification is no longer applicable, we can still analyze the family of functions g_y^κ defined in Equation (<ref>). The following proposition characterizes the values of the parameter κ^* such that g_y^κ^* satisfies demographic parity. These values partition the feature space equally, see <Ref>.




Let y∈. Under Assumption <ref>, the set of numbers κ∈ such that

    μ_+η(X)≥ y + κΔ(X) = μ_-η(X)≥ y + κΔ(X)

is a nonempty closed interval I(y) = [κ^-(y),κ^+(y)]. The function y↦κ^+(y) is upper semicontinuous and the function y↦κ^-(y) is lower semicontinuous.  
Moreover, it holds that for μ-almost all x, for all y ∈ℝ and all κ, κ' ∈ I(y), g_y^κ(x) = g_y^κ'(x).


Introduce the function 

    G:(κ,y)↦μ_+η(X)≥ y + κΔ(X) -μ_-η(X)≥ y + κΔ(X).
 Under Assumption <ref>, the measures  and  give zero mass to non-horizontal lines, implying that the function G is continuous. Furthermore, for y∈, the function G(·,y) is nonincreasing (recall that Δ(X)<0 for X∼μ_-). Hence, its zeroes form a closed interval I(y). For κ∈, the set {y∈: κ^-(y)>κ} is equal to the set {y∈: G(κ,y)>0}, which is an open set by continuity of G. This proves that κ^- is lower semicontinuous. We prove similarly that κ^+ is upper semicontinuous.

It remains to prove the last statement. Fix y∈. First, we may assume without loss of generality that κ=κ^-(y) and that κ'=κ^+(y). 
 We have μ_+η(X)≥ y + κ^+(y)Δ(X) = μ_+η(X)≥ y + κ^-(y)Δ(X) (and likewise for μ_-). Thus, we have 

    μ_+(g^κ_y(X)≠ g^κ'_y(X))    = μ_+(g^κ_y(X)=1,  g^κ'_y(X)=0)  
       = μ_+η(X)-y/Δ(X)∈ [κ,κ']=0.

The same equality holds for μ_-. Also,  the equality g^κ^+(y)_y(x)=g^κ^-(y)_y(x) holds on _= (as Δ(x)=0 on _=). Hence, for a fixed y, the equality g^κ^+(y)_y(x)=g^κ^-(y)_y(x) holds for μ-almost all x.

However, the set of points x (of full measure) where this equality is satisfied depends on y, so that it is not trivial to show that this equality holds simultaneously for all y∈, almost surely.

To do so, we show that the set {(h,d)∈Ω: ∃ y∈ℝ,  y+κ^-(y)d≤  h ≤ y+κ^+(y)d} has mass 0 under  and . For y∈, let C_y={(h,d)∈Ω: y+κ^-(y)d≤  h ≤ y+κ^+(y)d}. We have previously shown that for any given y∈ℝ, g_y^κ^-(y)(x)=g_y^κ^+(y)(x) for μ-almost all x, implying  that (C_y)=0. Let C=⋃_y∈ C_y. Let us show that (C)=0. Let C_1 =⋃_y∈ C_y. First, it holds that (C_1)=0. 
If it were not the case, as the measure  is inner regular, there would exist a compact set K⊂ C_1 with (K)>0. But then, the compact set K is covered by the family of open sets ( C_y)_y∈. By compactness, there exists a finite cover C_y_1,…, C_y_N covering K. As each C_y_i has zero mass, we obtain a contradiction with the positivity of (K). Furthermore, if (h,d)∈ C\ C_1, then there exists y_0 with either h=y_0+κ^-(y_0)d or h= y_0+κ^+(y_0)d, with also y+κ^-(y)d≤  h ≤ y+κ^+(y)d for all y∈. This implies that C\ C_1 is included in the union of the graphs of the two functions d↦sup_y (y+κ^-(y)d) and d↦inf_y(y+κ^+(y) d). These two functions can easily be seen to be measurable because of the semicontinuity of κ^- and κ^+. Thus, by Assumption <ref>, (C\ C_1)=0. In conclusion, we have proven that (C)=0. We show likewise that (C)=0.




 §.§ The nestedness assumption
 Recall that our goal is to determine whether the optimal fair regression function can be expressed as f^*(x) = sup{ y : g_y^κ(y)(x) = 1} for a certain  choice κ(y)∈ I(y).  In this section, we introduce an assumption regarding the family of classifiers g_y^κ(y) and demonstrate that this assumption is necessary for the relationship to hold. Specifically, we wish to use the decision boundaries of optimal classifiers at different risk levels to define the regression function. For this to be possible, the function y ↦ g_y^κ(y)(x) must be nonincreasing for any choice of x: in other words, the rejection regions {x : g^κ(y)_y(x) < y} must be nested. We formalize this assumption in the following definition.


We say that the problem corresponding to (X,Y,S)∼ is nested if there  exists a 
choice of κ(y)∈ I(y) for all y∈ such that 

    Nestedfor μ-almost all  x∈, the map  y∈↦ g^κ(y)_y(x)  is nonincreasing.


A straightforward (but key) property implied by nestedness is the fact that the sets 

    ∀ y∈, A(y) = {x∈: η(x)< y + κ(y)·Δ(x)}

are “almost” nested, in the sense that there exists a set  of full μ-measure such that for all y'≤ y, it holds that A(y')∩⊆ A(y)∩. 






Assume that Assumption <ref> holds. Then, 
the problem is nested with choice κ(y)∈ I(y) for all y∈ if and only if for all y<y', 
 
    μ(g_y^κ(y)(X)=0  and  g_y'^κ(y')(X)=1)=0.
 
 Furthermore, if the problem is nested, one can always choose κ(y)=κ^+(y) for all y∈ in the definition of g_y^κ(y).


The direct implication is clear. For the converse one, 
    assume that the nestedness assumption does not hold. By definition, there exists a measurable set _0 of positive μ-mass such that y↦ g_y^κ(y)(x) is not nonincreasing for all x∈_0. It holds that either μ_+(_0)>0 or that μ_-(_0)>0. Assume without loss of generality that the first condition is satisfied, and let  be the set of points x in _0∩_+ that satisfy 

    ∀ y∈, η(x)-y/Δ(x)∉[κ^-(y),κ^+(y)]

According to Proposition <ref>, μ_+()=μ_+(_0∩_+)>0. 
    
    
    For x ∈, there exists y<y' with g_y^κ(y)(x) = 0 and g_y'^κ(y')(x) = 1. As x satisfies (<ref>), we have that 
    
    η(x)< y+ κ^-(y)Δ(x)
    η(x)> y'+κ^+(y')Δ(x).

    
    
Because the function κ^- is lower semicontinuous, for ỹ close enough to y, we also have η(x)<ỹ+κ^-(ỹ)Δ(x). Likewise, there exists ỹ' close enough to y' with η(x)>ỹ'+κ^+(ỹ')Δ(x). In conclusion, we have shown that

    ⊂⋃_y,y'∈
     y<y'{x: η(x)< y+ κ^-(y)Δ(x)  and η(x)> y'+κ^+(y')Δ(x)}

In particular, as μ_+()>0, there exists y<y'∈ with 

    μ_+(η(X)< y+ κ^-(y)Δ(X)  and η(X)> y'+κ^+(y')Δ(X))>0.
  According to Proposition <ref> and Assumption <ref>, as the equality η(X)= y'+κ^+(y')Δ(X) happens with zero μ_+-probability, we have 
    
    μ_+(g_y^κ(y)(X)=0  and  g_y'^κ(y')(X)=1)>0,

proving the first claim.

The second claim follows from the characterization of nestedness that we have just established. Indeed, let y<y'. By Proposition <ref>, for μ-almost all x, g_y^κ(y)(x)=g_y^κ^+(y)(x) and g_y'^κ(y')(x)=g_y'^κ^+(y')(x). Thus, if (<ref>) holds for κ(y) and κ(y'), it also holds for κ^+(y) and κ^+(y').




As a warm-up, we begin by showing that the nestedness assumption is always verified in the awareness setting.


    Assume that S is X-measurable. Then, under Assumption <ref>, the classification problem is nested.



We prove Proposition <ref> by contradiction. Assume that the problem is not nested. Using Lemma <ref>, there exist y < y' and a set _0 of positive μ probability such that for all x∈_0, g_y^κ(y)(x) = 0 and g_y'^κ(y')(x) = 1. Using Proposition <ref>, we can also assume without loss of generality that η(x) < y + κ^-(y)Δ(x) and η(x) > y' + κ^+(y')Δ(x) for x∈_0.

Letting x∈_0, that we assume without loss of generality is in _+, the previous inequalities become

    y' + κ^+(y')/p_1 < η(x) < y + κ^-(y)/p_1.

In words, the threshold for admission is lower at level y' that at level y. This implies in particular that μ_+(g_y'^κ^+(y')(X) = 1) ≥μ_+(g_y^κ^-(y)(X) = 1). On the other hand, since y<y', it also implies that κ^+(y')<κ^-(y). Therefore,  y - κ^-(y)/p_2 < y' - κ^+(y')/p_2, so μ_-(g_y'^κ^+(y')(X) = 1) ≤μ_-(g_y^κ^-(y)(X) = 1). Using μ_+(g_y'^κ^+(y')(X) = 1) = μ_-(g_y'^κ^+(y')(X) = 1) and μ_+(g_y^κ^-(y)(X) = 1) = μ_-(g_y^κ^-(y)(X) = 1), we find that μ_+(g_y'^κ^+(y')(X) = 1) = μ_+(g_y^κ^-(y)(X) = 1). It implies that

    μ_+(η(X) ∈[y' + κ^+(y')/p_1, y + κ^-(y)/p_1]) = 0.

Likewise, 

    μ_-(η(X) ∈[y - κ^-(y)/p_2, y' - κ^+(y')/p_2]) = 0.

In particular, for κ = κ^+(y') + p_1(y' - y), we see that y + κ/p_1 = y' + κ^+(y')/p_1< y + κ^-(y)/p_1. Thus, κ < κ^-(y), and y - κ/p_2≥ y - κ^-(y)/p_2. Moreover, κ > κ^+(y'), and y < y', so y - κ/p_2 < y' - κ^+(y')/p_2. This implies that 

    y' - κ^+(y')/p_2 - (y - κ/p_2) = y' - y + 1/p_2(κ^+(y') + p_1(y' - y) - κ^+(y') ) > 0.

so y - κ/p_2∈[y - κ^-(y)/p_2, y' - κ^+(y')/p_2]. Thus, 

    μ_+(η(X) ≥ y + κ/p_1) = μ_-(η(X) ≥ y - κ/p_2)

and κ∈ I(y). Since κ < κ^-(y), this yields a contradiction.

Somewhat surprisingly, although the nestedness assumption may  appear  intuitive, it is not always verified. In Section <ref>, we present examples where this assumption holds and others where it does not. 

Before proving  in the next section that under the nestedness assumption, the optimal fair classification functions g_y^κ(y) can be recovered by thresholding the optimal fair regression function f^*, we prove the converse: if the problem is not nested, there exists a value of y∈ where the classifier {f^*(x)≥ y} is suboptimal for the fair classification problem (C_y).




Assume that = {0,1}, that 
Assumption <ref> holds and that the classification problem is not nested. Let f^* be the optimal fair regression function in the unawareness framework. Then, there exists y∈ such that the classifier x↦{f^*(x)≥ y} is not the optimal fair classifier for the risk _y.



According to Lemma <ref>, there exists y<y' with 

    μ(g_y^κ(y)(X)=0  and  g_y'^κ(y')(X)=1)>0.

    Let _0 be the set corresponding to this event. 
Let us consider a classifier of the form g_y(x) = {f(x) ≥ y}. On the one hand, if μ(X∈_0  and  f(X) < y ) >0, then the probability μ(X∈_0  and  f(X) < y' ) is also positive, so g_y'(x) and g_y'^κ(y')(x) disagree on a set of positive probability. Now, Proposition <ref> implies that all optimal classifiers are a.s. equal, so g_y' is sub-optimal. On the other hand, if μ(X∈_0  and  f(X) < y ) = 0, then g_y(x)=1 for almost all x∈_0. This implies that g_y(x) and g_y^κ(y)(x) disagree on a set of positive probability, so g_y is sub-optimal.





































 §.§ Constructing a regression function using nested classifiers


In the previous section, we proved that under mild assumptions, nestedness is a necessary condition for the relationship g^*_y(x) = {f^*(x) ≥ y} between the optimal fair classification and regression functions to hold. We now conclude by showing that nestedness is also a sufficient condition for this relationship to hold.

We begin by defining the function f^* : → as

    ∀ x ∈, f^*(x) = sup{y : g_y^κ(y)(x) = 1}

where g_y^κ(y) is given by Equation (<ref>). We assume without loss of generality (using Lemma <ref>) that κ(y)=κ^+(y) for all y∈. Remark that f^* is then almost measurable because of the upper semicontinuity of κ^+, in the sense that its restriction to some set of full measure is measurable (here given by the set of full measure where y↦ g_y^κ(y)(x) is nonincreasing).


Assume that the classification problem is nested and that Assumption <ref> is satisfied. Then, the regression function f^* is optimal for the fair regression problem (<ref>).

Before proving Theorem <ref>, we state the following corollary.

Assume that the classification problem is nested, that Assumption <ref> is satisfied, and that = {0,1}. Then, the classification function g_y : y ↦{f^*(x) ≥ y} is optimal for the fair classification problem problem with cost _y, where f^* is the solution to the fair regression problem (<ref>).

The proof of Corollary <ref> follows immediately by noticing that by Theorem <ref>, f^* is uniquely defined, and that the nestedness assumption and Theorem <ref> imply that g_y(x) = g_y^κ(y)(x) a.s.



The rest of the section is devoted to proving Theorem <ref>. To do so, we begin by proving that f^* is a fair regression function, and by defining F, the c.d.f. of the predictions under μ_+ and μ_-.


Assume that the problem is nested  and that Assumption <ref> is satisfied.  Let F:→ be defined by 

    ∀ y∈, F(y) =  μ_+η(X)≤ y+κ(y)Δ(X)= μ_-η(X)≤ y+κ(y)Δ(X).


Then, there exists a probability measure ν^* with continuous c.d.f. F and finite second moment such that f^*♯μ_+ = f^*♯μ_-= ν^*. In particular, f^* is a fair regression function.


The “almost” nestedness of the sets (A(y))_y implies that F is nondecreasing. Let us show that the function F is the c.d.f. of some continuous random variable, i.e., that it goes to 0 in -∞, that it goes to 1 in +∞, and that it is continuous.

First, recall that Δ(X)>0 for X∼μ_+ and that Δ(X)<0 for X∼μ_-. Thus, if κ(y)≤ 0, then F(y)≤μ_+η(X)-y ≤ 0 and if κ(y)≥ 0, then F(y)≤μ_-η(X)-y ≤ 0. Hence, 

    F(y)≤max{μ_+η(X)-y ≤ 0,  μ_-η(X)-y≤ 0},

and F converges to 0 in -∞. Similarly, F(y)→ 1 when y converges to +∞.

Next, let us show that F is continuous. Let y_0, y_1∈ be such that y_0 < y_1. Now, if κ(y_0)≥κ(y_1), then 

    F(y_1) - F(y_0)    = μ_+η(X)≤ y_1+κ(y_1)Δ(X) - μ_+η(X)≤ y_0+κ(y_0)Δ(X)
       ≤μ_+η(X)≤ y_1+κ(y_0)Δ(X) - μ_+η(X)≤ y_0+κ(y_0)Δ(X)

Similarly, if κ(y_0)≤κ(y_1), then, (recalling that Δ(X)<0 for X∼μ_-)

    F(y_1) - F(y_0)    =μ_-η(X)≤ y_1+κ(y_1) Δ(X)  -  μ_-η(X)≤ y_0+κ(y_0) Δ(X) 
       ≤μ_-η(X)≤ y_1+κ(y_0) Δ(X)  -  μ_-η(X)≤ y_0+κ(y_0) Δ(X) .

Thus, 

    F(y_1) - F(y_0) ≤μ_+η(X) - κ(y_0)Δ(X) ∈[y_0, y_1] + μ_-η(X) - κ(y_0)Δ(X)  ∈[y_0, y_1]

We have shown that F is non-decreasing, so F(y_1) - F(y_0) ≥ 0. Under Assumption <ref>, μ_+ and μ_- give zero mass to the sets {η(X) = y_0 + κ(y_0)Δ(X)}, so F(y_1) - F(y_0) → 0 as y_1 → y_0^+. This proves that F is right-continuous. To show that F is left-continuous, we note that if κ(y_0)≥κ(y_1), then 

    F(y_1) - F(y_0)    ≤μ_+η(X)≤ y_1+κ(y_1)Δ(X) - μ_+η(X)≤ y_0+κ(y_1)Δ(X).

Similarly, if κ(y_0)≤κ(y_1), then, 

    F(y_1) - F(y_0)    ≤μ_-η(X)≤ y_1+κ(y_1) Δ(X)  -  μ_-η(X)≤ y_0+κ(y_1) Δ(X) .

Thus, 

    F(y_1) - F(y_0) ≤μ_+η(X) - κ(y_1)Δ(X) ∈[y_0, y_1] + μ_-η(X) - κ(y_1)Δ(X)  ∈[y_0, y_1]

and F is also left-continuous.

Then, let us show that ν^* has finite second moment. Let Z∼ν^*. We have

    [Y^2] = ∫_0^+∞(Z^2>t)  t= ∫_0^+∞ (F(√(t))+(1-F(-√(t)))) t

We use (<ref>) to obtain that for y∈, F(y)≤max(μ_+(η(X)≤ y), μ_-(η(X)≤ y)). But, as [Y^2]<+∞, the random variable η(X) has a finite second moment under the law of either μ_+ or μ_-. In particular, ∫_0^+∞ F(√(t))  t is finite. Similarly, ∫_0^+∞ (1-F(-√(t))) t is finite.
    
Finally, we prove the statement f^*♯μ_+ = ν^*. Indeed, for all y_0 ∈, we have using that upper semicontinuity of κ(y)=κ^+(y) that

    f^*♯μ_+((-∞,y_0])   = μ_+ sup{y : g_y^κ(y)(X) = 1}≤  y_0 
       = μ_+  g_y_0^κ(y_0)(X) = 0=μ_+(η(X)<y_0+κ(y_0)Δ(X))=F(y_0).

where the second line follows from the nestedness assumption and the fact that the line {η(X)=y_0+κ(y_0)Δ(X)} has zero mass. We show similarly that f^*♯μ_- = ν^*, thus concluding the proof of Lemma <ref>. 


The function f^* depends only on x through the pair (η(x),Δ(x)). Let ^*:Ω→ be defined by the relation f^*(x) = ^*(η(x),Δ(x)) for x∈_±. 
We show that ^* defines an optimal transport map between  and ν^* with respect to the cost .


Assume that the problem is nested. Then, ^* is an optimal transport map between  and ν^* for the cost , with Kantorovich potential between ν^* and  given by v:y↦ -2∫_0^y κ(t) t. The same holds for , with Kantorovich potential given by -v.


The proof of Lemma <ref> relies on the following technical lemma, whose proof is postponned to Appendix <ref>.

    The function y↦κ(y) satisfies |κ(y)|≤ C(1+|y|) for some C>0.


To prove Lemma <ref>, we begin by remarking that the potential v is in L^1(ν^*) because of Lemma <ref> and Lemma <ref>. 
Let us now show that for almost all x∈_+,

    v^c(x) sup_y∈ (v(y)-c(x,y)) = v(f^*(x))- c(x,f^*(x)).

Let x∈_+ be a point such that y↦ g_y^κ(y)(x) is nonincreasing (almost all points satisfy this condition by nestedness). 
 We remark that ∂_y c(x,y) = 2(y-η(x))/Δ(x). Hence,

    c(x,y)-c(x,f^*(x))    = ∫_f^*(x)^y 2(t-η(x))/Δ(x) t 
       = -2∫_f^*(x)^y η(x)-t/Δ(x)-κ(t) t  -2∫_f^*(x)^y κ(t)  t 
       = -2∫_f^*(x)^y η(x)-t/Δ(x)-κ(t) t  + v(y)-v(f^*(x)).



Assume that y≥ f^*(x). For t∈ (f^*(x),y], by definition of f^* and by nestedness, g_t^κ(t)(x)=0. Thus, 

    η(x)-t/Δ(x)-κ(t)< 0.

This implies that

    - 2∫_f(x)^y η(x)-t/Δ(x)-κ(t) t ≥ 0.

We obtain that

    c(x,y)-c(x,f^*(x)) ≥ v(y)-v(f^*(x)).

The same result holds when y<f^*(x). Indeed, in that case, for all t∈ [y,f^*(x)), 

    η(x)-t/Δ(x)-κ(t)≥ 0.

Hence, 

    - 2∫_f^*(x)^y η(x)-t/Δ(x)-κ(t) t = 2∫_y^f^*(x)η(x)-t/Δ(x)-κ(t) t ≥ 0.

This proves (<ref>). This relation implies that the -transform of the function v∈ L^1(ν^*) is a function w:Ω→ satisfying for μ_+-almost all x∈_+ (with =(η(x),Δ(x)))

    w() = v(f^*(x))- c(x,f^*(x)) = v(^*())-(,^*()).


As v∈ L^1(ν^*), Kantorovich duality  implies

    _(,ν^*)    ≥∫ v(y)ν^*(y) -∫ w() ()= ∫ v(^*())()-∫ w() () 
       = ∫(,^*()) (),
 
see  <Ref>. 
This shows that ^* is the optimal transport map between  and ν^*. The same holds for , where we use the potential -v instead of v: precisely, we can show that we have for almost all x∈_-

    (-v)^c(x) sup_y∈ (-v(y)-c(x,y)) = -v(f^*(x))- c(x,f^*(x)).

This concludes the proof of Lemma <ref>.


Lemma <ref> shows that ^* defines an optimal transport map from  to ν^*, and from  to ν^*. To conclude the proof of Theorem <ref>, it remains to show that ν^* is solution to the barycenter problem described in Lemma <ref>.


The distribution ν^* is solution to the barycenter problem described in Lemma <ref>.



Let ϕ:_1∈Ω↦(_1,^*(_1))-v(^*(_1)) and let ψ:_2∈Ω↦(_2,^*(_2)) + v(^*(_2)). Using (<ref>) and (<ref>), we see that for all y∈, for  -almost all _1 and -almost all _2, it holds that

    ϕ(_1)+ψ(_2)    = (_1,^*(_1))-v(^*(_1))+ (_2,^*(_2)) + v(^*(_2))
       ≤(_1,y)-v(y) + (_2,y)+v(y) 
       = (_1,y)+(_2,y).

By taking the value y that minimizes this last term, we obtain that

    ϕ(_1)+ψ(_2)≤(_1,_2),

where  is the cost function defined in (<ref>). In particular, -ϕ(_1)≥ψ^(_1).
Furthermore, remark that

    -v(^*(_1))≤ϕ(_1)≤ c(_1,0).

Thus, as v∈ L^1(ν^*) and ∫h^2/d(h,d)<+∞, it holds that ϕ∈ L^1(). Likewise, ψ∈ L^1().  
By Kantorovich duality, it holds that

    _(,)    ≥∫ψ(_2)(_2)-∫ψ^(_1) (_1)
       ≥∫ψ(_2)(_2)+∫ϕ(_1) (_1)
       = ∫(_1,^*(_1))(_1)+ ∫(_2,^*(_2))(_2) 
          - ∫ v(^*(_1))(_1) + ∫ v(^*(_2))(_2)  
       = _(,ν^*) + _(,ν^*) + ∫ v(y)ν^*(y)-∫ v(y)ν^*(y) 
       = _(,ν^*) + _(,ν^*) ≥_(,).

This proves that ν^* is the solution to the barycenter problem, and that f^* is an optimal regression function.




§ BUILDING EXAMPLES AND COUNTEREXAMPLES

In the previous section, we  proved that under mild assumptions, the relationship g^*_y(x) = {f^*(x) ≥ y} only holds under the nestedness assumption. In this section, we now explain how to build large classes of triplets (X,Y,S)∈××{1,2} whose distributions  either satisfy or do not satisfy this criterion. The starting point of our approach consisted in associating to each distribution  a pair of distributions (,)=((),()) on Ω, where we recall that () is the distribution of (η(X),  Δ(X) ) when X ∼μ_±. Then, both the optimal fair regression function and the nestedness criterion are best understood in terms of the pair  ((),()).

However, given a pair of measure (,) on Ω, it is not a priori clear whether there exists a triplet (X,Y,S)∼ with (,)=((),()). We give a definitive answer to this problem by providing a list of necessary and sufficient conditions for the existence of such a probability distribution . We then use this theoretical result to build probability distributions  for which the associated fair classification problem is either nested or not nested.

Let  be the distribution of a triplet (X,Y,S)∈××{1,2}, with [Y^2]<+∞. Let (,)=((),()) be the associated pair of measures on Ω.  Then, it always holds that

    ∫_Ω |d|^-1(h,d) = ∫_1/Δ(x)μ_+(x) = ∫_μ/μ_+(x) μ_+(x) =μ(_+),

while ∫_Ω| d|^-1(h,d)=μ(_-). In particular, 

    0< ∫_Ω |d|^-1(h,d)+∫_Ω |d|^-1(h,d) ≤ 1.

Also, note that μ=p_1μ_1+p_2μ_2, so that Δ(x) = μ_+/μ(x)≤1/p_1m when x ∈_+, whereas Δ(x)≥- 1/p_2m when x∈_- (recall that m is the mass of the measure (μ_1-μ_2)_+). In particular, the supports of  and  are located in an horizontal strip of the form {(h,d): -M≤ d≤ M} for some M>0. The next proposition states that these two conditions are actually sufficient for the existence of a probability measure  with (,)=((),()).


Assume that  is an uncountable standard Borel space (e.g., =[0,1]). Then, the set of pairs of measures ((),()) that can be obtained from a distribution  of a triplet  (X,Y,S)∈××{1,2} with [Y^2]<∞ is exactly equal to the set of  pairs (,) supported on bounded horizontal strips, satisfying <Ref>, with  supported on {d>0} and  supported on {d<0}.

This proposition allows us to easily build examples where either nestedness or nonnestedness is satisfied: one does not need to build from scratch a joint distribution on ××{1,2}, but can simply define a pair of measures (,) on Ω. As long as this pair satisfies the conditions given in Proposition <ref>, the existence of a probability distribution  such that (,)=((),()) is ensured. 



We have already established that the  pairs of measures ((),()) satisfy the conditions stated in Proposition <ref>. Reciprocally, consider a pair (,) satisfying <Ref>, supported on bounded horizontal strips, with  supported on {d>0} and  supported on {d<0}. 
Let a_± = ∫_Ω |d|^-1(h,d). 

Due to the Borel isomorphism theorem,  is Borel isomorphic to ^2, so we may assume without loss of generality that =^2.  Let _+ = {(h,d)∈^2: d>0}, _-={(h,d)∈^2: d<0} and _= = {(h,0): h∈}. Let μ_==δ_0. We let μ_+ = and μ_-=.


Let

    μ(h,d) = 1/|d|μ_+(h,d) + 1/|d|μ_-(h,d) + (1-a_+-a_-)μ_=(h,d).

Remark that μ is a probability measure:

    ∫μ    = ∫1/|d|μ_+(h,d) + ∫1/|d|μ_-(h,d) + (1-a_+-a_-)∫μ_= =1.
 
Consider m small enough so that the inequality m|d|/2≤ 1  holds on the support of μ (this is possible because the d coordinate is bounded in the support of  and ). We define

    μ_1(h,d)  = (1+m/2d) μ(h,d)   and  μ_2(h,d)  = (1-m/2d) μ(h,d)

















Note that μ = 1/2μ_1+1/2μ_2. Also, μ_1 and μ_2 are probability measures, as

    ∫ d μ = ∫d/|d|μ_+(h,d) + ∫d/|d|μ_-(h,d) = 1-1=0.






Let η(h,d)=h.  
We define the triplet (X,Y,S) by letting S be uniform on {1,2}. If S=1, we draw X∼μ_1 and let Y=η(X). If S=2, we draw X∼μ_2 and let Y=η(X). Let  be the distribution of (X,Y,S). One can easily check that ((),())=(,), as desired.









To build examples of nested and non-nested problems, we consider probability measures  and  supported on small horizontal segments:

    = 1/K∑_i=1^K ν_±^(i)

where ν_±^(i) is the uniform measure on [a^(i)_±,a^(i)_±+1]×{d_±^(i)}. 







[A nested classification problem]
    Take K=1, d_+^(1)=d_-^(1)=1 and a^(1)_+=0, a^(1)_-=-1. Let  be the probability associated with the pair (,) defined for this choice of parameters. Then, it holds that 1/2 ∈ I(y) for all y∈. By choosing κ(y)=1/2 for all y∈, we see that the classification problem associated with  is nested. See also Figure <ref>.


[A non-nested classification problem]
    Take K=2. Let d_+^(1)=d_-^(1)=1 and a_+^(1)=a_-^(1)=0. Let d_+^(2)=d_-^(2)=1/2, and a_+^(2)=-1, a_-^(2)=-6. Then, for y=0, I(y)={0}, so the support of ν_+^(2) is to the left of the classification threshold for y=0. But for y=-3, we have I(y)={4 } and the support of ν_+^(2)  is to the right of the classification threshold. Hence, the classification problem is non-nested. See also Figure <ref>.

















§ CONCLUSION AND FUTURE WORK

This work presents the first theoretical characterization of the optimal fair regression function as the solution to a barycenter problem with an optimal transport cost. Our results also demonstrate that, under the nestedness assumption, the optimal fair regression function can be represented by the family of classifiers g_y^κ(y). Although both approaches—whether based on optimal transport or cost-sensitive classifiers—depend on the underlying distribution 
ℙ which is generally unknown, they pave the way for developing new algorithms that estimate these unknown quantities from observed data. Designing such estimators, along with bounding their excess risk and potential unfairness, represents a critical step toward the development of fair algorithms.

While this work provides an initial characterization of the optimal fair regression function in the unawareness framework, it also has notable limitations. For instance, our results are currently limited to cases where the sensitive attribute is binary and apply only to univariate regression. Addressing these limitations and extending our findings to more general cases would be a valuable direction for future research.





§ ACKNOWLEDGEMENTS

The authors gratefully acknowledge valuable and insightful discussions with Evgenii Chzhen and Nicolas Schreuder. S. G. gratefully acknowledges funding from the Fondation Mathématique Jacques Hadamard and from the ANR TopAI chair (ANR–19–CHIA–0001).

alpha







§ ADDITIONAL PROOFS



 §.§ Proof of Lemma <ref>




Let f:→∪{+∞} be a lower semicontinuous convex function. The domain of such a function is an interval (f). Its right derivative f'_+ is defined and finite everywhere on (f), except on the right endpoint of the interval (should the right endpoint be included in (f)) where it is equal to +∞. 
Such a function is  upper semicontinuous, with the representation:

    ∀ h∈(f), f'_+(h) = inf_u>hf(u)-f(h)/u-h,

where the infimum can be restricted to a countable dense collection of values u if needed.
Likewise, the right derivative f'_- can be defined on (f), and is lower semicontinuous. Note also that the oscillation function (f)=f'_+-f'_-∈ [0,+∞] can be defined on (f), and is upper semicontinuous. Indeed, only one of f'_+ and f'_- can be infinite on (f) (and only at one of the endpoints of the domain), so that the difference is well defined. 

Recall that a function ϕ is -convex if

    ∀ (h,d)∈Ω, ϕ(h,d) = sup_(h',d')∈Ωϕ^(h',d') - (h-h')^2/|d|+|d'|.

The function ϕ is lower semicontinuous as a supremum of continuous functions. Furthermore,  for any d≠ 0, the function

    ϕ_d: h↦ϕ(h,d)+ h^2/|d| =sup_(h',d')∈Ωϕ^(h',d') + h^2/|d|- (h-h')^2/|d|+|d'|

is convex as a supremum of lower semicontinuous convex functions. 

Let G:(ϕ)→ [0,+∞] be defined as G(h,d)=(ϕ_d)(h) for (h,d)∈(ϕ).  
Let L>0, and consider the  set  Σ_d,L defined as  the set of points h∈(ϕ_d) such that  G(h,d)≥ L^-1, (ϕ_d)'_+(h)≥ -L and (ϕ_d)'_-(h)≤ L. As the left and right derivatives of ϕ_d are nondecreasing, the set Σ_d,L is finite and its cardinality is bounded by a constant depending only on L. 
Let Σ_L = ⋃_d≠ 0Σ_d,L and Σ=⋃_L∈Σ_L. 
The set of points ∈(ϕ) such that ∂_hϕ() does not exist is equal to Σ. 
 Let us show that for any integer L, the set Σ_L is included in a countable union of graphs of measurable functions. 

 


 To do so, we use the following general result, see <cit.>. A correspondence Φ from a measurable set S to a topological space X assigns to each s∈ S a subset Φ(s) of X. We say that the correspondence is (weakly) measurable if for each open subset U⊂ X, the set Φ^ℓ(U)={s∈ S: Φ(s)∩ U≠∅} is measurable.
 

    If X is a Polish space and Φ is a measurable correspondence with non-empty closed values  between S and X, then there exists a sequence (f_n)_n of measurable functions S→ X such that for every s∈ S, Φ(s)={f_1(s),f_2(s),⋯}. 


Let Φ be the correspondence that assigns to each d≠ 0 the subset Σ_d,L∪{0} of . As each set Σ_d,L is finite, this correspondence takes non-empty closed values. If we show that this correspondence is measurable, then Castaing theorem asserts the existence of a sequence of measurable functions (f_n)_n such that for every d≠ 0, Σ_d,L∪{0} = {f_1(d),f_2(d),⋯}. For each d, the set Σ_d,L is finite, so that Σ_d,L∪{0} =  {f_1(d),f_2(d),⋯}, implying that Σ_L is included in a countable union of graphs of measurable functions. It remains to show the measurability of Φ.





 The function G is measurable.
  


The representation (<ref>) implies that (h,d)↦ (ϕ_d)'_+(h) is given by a countable infimum of measurable functions, and is therefore measurable. Likewise, (h,d)↦ (ϕ_d)'_-(h) is measurable, so that G is also measurable.
 


Let U⊂ be an open set.  If 0∈ U, then Φ^ℓ(U)=\{0} is measurable. If 0∉U, we have

    Φ^ℓ(U) ={d≠ 0: ∃ h∈ [-L,L]∩ U, G(h,d)≥ L^-1, (ϕ_d)'_+(h)≥ -L,  (ϕ_d)'_-(h)≤ L }.

This set is the projection on the d-axis of the measurable set 

    B={(h,d)∈Ω: h∈ [-L,L]∩ U, G(h,d)≥ L^-1, (ϕ_d)'_+(h)≥ -L,  (ϕ_d)'_-(h)≤ L }

Furthermore, for each d, the section {h∈: (h,d)∈ B}=Σ_d,L is compact. By <cit.>, this implies that Φ^ℓ(U) is measurable, concluding the proof of Lemma <ref>.
























 §.§ Proof of Proposition <ref>


Classical manipulations show that the risk _y(g) of a classifier g can be expressed as

    ℛ_y(g)    = y𝔼[(1-Y)g(X)] + (1-y) 𝔼[Y(1-g(X))]
        = (1-y)𝔼[Y] + 𝔼[g(X)(y-η(X))].

Using the definition of μ_+, μ_- and Δ given in Section <ref>, we find that 

    𝔼[g(X)(y-η(X))]
           = ∫_𝒳_+ g(x)(y-η(x))μ/μ_+(x) μ_+(x) + ∫_𝒳_- g(x)(y-η(x))μ/μ_-(x) μ_-(x) 
               + ∫_𝒳_= g(x)(y-η(x)) μ(x)
           = ∫_𝒳_+ g(x)y-η(x)/|Δ(x)|μ_+(x) + ∫_𝒳_- g(x)y-η(x)/|Δ(x)|μ_-(x) + ∫_𝒳_= g(x)(y-η(x)) μ(x).

Moreover, Lemma <ref> implies that the demographic parity constraint is equivalent to the constraint 𝔼_X∼μ_+[g(X)] = 𝔼_X∼μ_-[g(X)]. Using the decomposition g = (g_+, g_-, g_=), we see that the fair classification problem can be rephrased as follows

    C_y'minimize   𝔼_μ_+[g_+(X)y-η(X)/Δ(X)] -𝔼_μ_-[g_-(X)y-η(X)/Δ(X)]  
          + 𝔼_μ[1__=
                 (X)g_+(X)(y-η(X))] 
    such that   𝔼_μ_+[g_+(X)] = 𝔼_μ_-[g_-(X)].

The following lemma characterizes the solutions to the problem (C_y').


Under Assumption <ref>, for any optimal classifier g, there exist κ^+, κ^- such that g= (g^κ^+, g^κ^-, g_=), with 

    g_=(x) = 1{η(x) > y}   or    g_=(x) = 1{η(x) ≥ y},
    and     g^κ(x) = 1{η(x) ≥ y+ κΔ(x)}.


To conclude the proof of Proposition <ref>, it remains to prove that all optimal classifier are a.s. equal when Δ(X)≠ 0, and that the optimal classifier can be chosen as g^* = (g^κ^*, g^κ^*, g_=) for some κ^*.

Denote by F_+ the c.d.f. of the random variable Z_+ = η(X)-y/Δ(X) when X∼μ_+ and by F_- the c.d.f. of Z_-= y-η(X)/Δ(X) when X∼μ_-. Let _+ (resp. _-) be the associated quantile function. To verify the demographic parity constraint, the classifier (g^κ^+, g^κ^-, g_=) must be such that

    F_+(κ^+) = F_-(-κ^-)

(recall that Δ(X)<0 when X∼μ_-, so that g^κ^-(X)=1 if and only if Z_- ≥ -κ^-).
Denoting β = F_+(κ^+)= F_-(-κ^-) and using the definition of the quantile function, we see that the law of g^κ^±(X), where X ∼μ_± is equal to the law of 

    {U≥β} = {_±(U)≥±κ^±},

where U is a uniform random variable on [0,1].
 



 

Then, minimizing the risk of the classifier is equivalent to maximizing

    𝔼[(_+(U) + _-(U))1{U≥β}]
 




Since F_+ and F_- are continuous, u →_+(u)+_-(u) is strictly increasing and left-continuous. Straightforward computations show that the expression in (<ref>) has a unique maximum, which is attained for 

    β^* = max{β : _+(β)+_-(β) ≤ 0 }.

Hence, it holds that F_+(κ^+)=F_-(-κ^-)=β^*. Let g^*_1 = (g^κ^+_1, g^κ^-_1, g_=) and g^*_2 = (g^κ^+_2, g^κ^-_2, g_=) be two optimal classifiers. For Δ(X)> 0, they take different values only if Z_+ ∈ [κ^+_1, κ^+_2]. As F_+(κ^+_1)=F_+(κ^+_2)=β^*, this happens with zero probability. Likewise, the two classifiers are a.s. equal when Δ(X)<0.

It remains to show that we can pick κ^+=κ^-. If _++_- is continuous at β^*, the proof is complete: in this case, _+(β^*)+_-(β^*)=0, and the choice κ^* = _+(β^*) = - _-(β^*) satisfies F_+(κ^*)=F_-(-κ^*)=β^*.

Otherwise, _+(β^*)+_-(β^*)<0. Defining 

    q_+ = lim inf_β→β^*_+_+(β)  and  q_- = lim inf_β→β^*_+_-(β),

we have q_+ +  q_->0. Because q_+>-q_- and _+(β^*)<-_-(β^*), there exists κ^*∈ [_+(β^*), q_+] ∩ [-q_-, - _-(β^*)]. By construction, F_+(κ^*)=F_-(-κ^*)=β^*, concluding the proof.











 §.§ Proof of Lemma <ref>


Let g^* be a solution to the problem (C_y'), and let g_+^*, g_-^* and g_=^* be the restrictions of g^* to _+, _= and _=, so that g^* = (g_+^*, g_-^*, g_=^*). Straightforward computations show that  we necessarily have g_=^*(X) = 1{η(X) ≥ y}1__=(X) or g_=^*(X) = 1{η(X) > y}1__=(X).

Now, let us assume (without loss of generality) that g_+^* is not of the form g^κ^+. More precisely, assume that for κ^+ such that 𝔼_μ_+[g^κ^+(X)] = 𝔼_μ_+[g^*_+(X)], we have g^κ^+(X)≠ g^*_+(X) with positive μ_+-probability. Then, the classifier (g^κ^+, g^*_-, g^*_=) verifies the demographic parity constraint. Moreover, we have

    𝔼_μ_+[g^κ^+(X)y-η(X)/Δ(X)] - 𝔼_μ_+[g_+^*(X)y-η(X)/Δ(X)] 
       = 𝔼_μ_+[y-η(X)/Δ(X) g^κ^+(X)(1-g^*_+(X)) - y-η(X)/Δ(X) (1-g^κ^+(X))g^*_+(X)]
       = 𝔼_μ_+[(κ^+- η(X)-y/Δ(X)) g^κ^+(X)(1-g^*_+(X))] - κ^+𝔼_μ_+[g^κ^+(X)(1-g^*_+(X))] 
          - 𝔼_μ_+[(κ^+- η(X)-y/Δ(X)) (1-g^κ^+(X))g^*_+(X)] + κ^+𝔼_μ_+[(1-g^κ^+(X))g^*_+(X)].

Since 𝔼_μ_+[g^κ^+(X)] = 𝔼_μ_+[g^*_+(X)], we obtain that 
    𝔼_μ_+[g^κ^+(X)(1-g^*_+(X))] = 𝔼_μ_+[(1-g^κ^+(X))g^*_+(X)].
 Then, the definition of g^κ^+ implies 


    𝔼_μ_+[g^κ^+(X)y-η(X)/Δ(X)] - 𝔼_μ_+[g_+^*(X)y-η(X)/Δ(X)] 
       =- 𝔼_μ_+[(κ^+- η(X)-y/Δ(X))_-(1-g^*_+(X))] - 𝔼_μ_+[(κ^+- η(X)-y/Δ(X))_+g^*_+(X)] < 0.

This implies that _y((g^κ^+, g_-^*, g_=^*)) <  _y((g_+^*, g_-^*, g_=^*)), which is absurd. Using a similar argument for g_-^*, we arrive to the conclusion that  any optimal classifier is of the form (g^κ^+, g^κ^-, g_=^*) with g_=^*(X) = 1{η(X) ≥ y}1__=(X) or g_=^*(X) = 1{η(X) > y}1__=(X).



 §.§ Proof of Lemma <ref>


Let us first show that κ is locally bounded. Let [y_0,y_1] be a bounded interval. Then, if κ(y)≥ M for some y∈ [y_0,y_1],

    F(y)   = μ_+η(X)≤ y+κ(y)Δ(X)≥μ_+η(X)≤ y_0+MΔ(X)

and

    F(y)   = μ_-η(X)≤ y+κ(y)Δ(X)≤μ_-η(X)≤ y_1+MΔ(X).

However, for M large enough,

    μ_-η(X)≤ y_1+MΔ(X) < μ_+η(X)≤ y_0+MΔ(X),

and therefore it holds that κ(y)≤ M for all y∈ [y_0,y_1]. Likewise, we show that for M large enough, κ(y)≥ -M for all y∈ [y_0,y_1]. Hence, κ is locally bounded.

We refine this argument to obtain a control on κ for large values of y. Let L>1 and let y>1 be such that κ(y)≥ L y. Then, because of the definition of κ(y) and as Δ(X)<0 for X∼μ_-,
    
    μ_+(η(X)≥ y)   ≥μ_+(η(X)≥ y+ κ(y)Δ(X)) 
       = μ_-(η(X)≥ y+ κ(y)Δ(X)) ≥μ_-(η(X)≥ y+ LyΔ(X)).

    The complementary of the region {(h,d)∈Ω: d<0, h≥ y+Lyd} in the lower half-plane {(h,d)∈Ω: d<0} is contained in the set A_L given by the union of the horizontal strip {d≥ -1/L} with the region {(h,d)∈Ω: d<0, h≤ 1+Ld}. For L large enough, (A_L)<1/2. Then it holds that μ_+(η(X)≥ y)≥ 1/2. For y large enough, this is not possible. Thus, we have shown that there exist L>0 and C>0 such that for y>C, we have κ(y)≤ Ly. Likewise, we show that there exist constants L,C>0 such that for |y|>C, |κ(y)|≤ L|y|. As κ is also locally bounded, the conclusion follows.


