# Achieving Downstream Fairness with Geometric Repair

Kweku Kwegyir-Aggrey<EMAIL_ADDRESS>,  Jessica Dai<EMAIL_ADDRESS>,
John P. Dickerson<EMAIL_ADDRESS>0000-0003-2231-680X and  Keegan Hines
<EMAIL_ADDRESS>Arthur AIUSA

(2022)

###### Abstract.

Consider a scenario where some “upstream” model developer must train a fair
model, but is unaware of the fairness requirements of a “downstream” model
user/stakeholder. In the context of fair classification, we present a
technique that specifically addresses this setting, by post-processing a
regressor’s scores such they yield fair classifications for any downstream
choice in decision threshold. To begin, we leverage ideas from optimal
transport to show how this can be achieved for binary protected groups across
a broad class of fairness metrics. Then, we extend our approach to address the
setting where a protected attribute takes on multiple values, by re-recasting
our technique as a convex optimization problem that leverages lexicographic
fairness.

fairness in machine learning, optimal transport, fair classification

††copyright: acmcopyright††journalyear: 2022††doi: XX.XXXX/XXXXXXX.XXXXXXX

##  1\. Introduction

A common critique of fair algorithmic interventions is that they do not center
real-world usage (Hoffmann, 2019; Selbst et al., 2019). In this work, we study
a problem that exists in the gap between the design of “fair” machine learning
interventions and their deployment in “in the wild”—a gap that exists due to
the fact that the users of (fair) machine learning models are not always the
people who created the tool. To illustrate this gap, we begin with a sketch of
how machine learning tools are often used in the context of some
sociotechnical pipeline where fairness is a concern. First, a model developer
trains a machine learning model to make predictions about individuals based on
past data. Typically, these decisions are made by taking the continuous
outputs (or scores) from a model, such as predicted probabilities, and then
using a cutoff (or threshold), a final classification decision (e.g. yes/no)
is made based on whether the individual’s score was above or below the
threshold. Once trained, the model is evaluated for bias and correctness. If
the model exhibits bias, then some appropriate fairness intervention may be
applied, and the model is modified or retrained to mitigate the observed bias.
At the last stage, when the model is deployed for usage, the prior steps are
repeated as necessary if new biases emerge.

In many cases, a machine learning pipeline similar to the one described above
involves two parties: an “upstream” model developer who is responsible for
creating and/or engineering the model, and a “downstream” user, stakeholder,
or practitioner, who uses the model for decision-making (Bower et al., 2017;
Dwork et al., 2020). The upstream developer and downstream user are often
different parties; the steps detailed above might be done only by the upstream
model developer, while the downstream end-user must rely solely on the model
provided by the developer. Furthermore, either party may be constrained by
resources, logistical barriers, or context-specific barriers, leading the
downstream model user to employ a different threshold for making final
classification decisions than the upstream model developer had anticipated and
optimized for(Forde et al., 2021; Cooper et al., 2022).

Consider the following example. Suppose a model developer validates the
performance and fairness of their model by computing the Area Under the Curve
(AUC) for each protected group. AUC scores, which fall between 0 and 1, are
computed by aggregating false positive and true positive rates across all
possible thresholds used to make classification decisions. In many domains, a
model is said to be “good,” i.e. usable, if its AUC is above 0.8 (jus,
[n.d.]). In this case, if all groups have an AUC above 0.8, the model is
deemed to be “fair” and perform well. However, AUC measures performance across
all thresholds. This means that for a single choice in threshold, a model
could perform poorly for only one group despite a relatively high overall or
group-wise AUC. In the context of the pipeline described above, the model user
ultimately determines which threshold(s) they will use with the model,
regardless of the developer’s upstream validation.

In this way, a model user can create unfair outcomes through their choice of
thresholds, even if the original model was relatively well calibrated and
ostensibly fair. Even if the model user notices biased outcomes, the
application of fairness interventions can be prohibitively data hungry or
computationally expensive, and, in many cases, the model user may not have the
expertise to retrain the model for their specific use case. All this to say,
fair models are brittle: if they are used beyond the particular assumptions
made at development time, their fair properties are weakened (Selbst et al.,
2019).

The core question which motivates our work, therefore, is as follows: how can
we create a model that is fair irrespective of how it is used downstream?
Specifically, we focus on settings where a model user has a correctly
validated model from an upstream developer, but has a choice in threshold(s)
for their specific domain. From this, we can formally restate our problem: In
the context of binary classification, how might we arrive at a model which
produces fair decisions irrespective of the threshold used? Our contributions
are as follows.

  1. (1)

We introduce a post-processing framework for achieving various
(classification-based) definitions of fairness over all possible choices in
threshold; provide theoretical justifications for our approach, and
demonstrate how to use our method in the case where the sensitive attribute is
binary.

  2. (2)

We extend our framework to a setting where the protected attribute takes on
more than two values and motivate the use of lexicographic fairness for our
problem; show how to compute a lexicographically fair solution; and illustrate
the connection to the simpler approach introduced for binary sensitive
attributes.

In Section 1.1, we overview the problem setting in more detail. In Section 2,
we provide technical background for our method and begin to show the
connections between fairness and ideas from optimal transport. Section 3
details the key ideas of our proposed method, its theoretical justifications,
and some experimental evidence validating our approach. In Section 4, we
discuss the limitations of other methods for achieving fairness based on
optimal transport. Then, in Section 5, we extend our approach to address
settings where the protected attribute takes on more than two values and
examine the effectiveness of our approach with a case study based on FICO
credit scores. Finally, Section 6 discusses the implications and limitations
of our approach as well as intended future work and open questions.

###  1.1. Notation & Setting

We begin by introducing the notation and framework we use for fair regression
and binary classification. A notation glossary can be found in Appendix A.1.
Allow $\mathcal{G}$ to be the set of protected attributes. First, we consider
the binary protected group setting $\mathcal{G}=\\{0,1\\}$. Let
$D=\\{(x_{i},g_{i},y_{i})\\}_{i=1}^{N}$ be a dataset consisting of features
$x_{i}\in\mathbb{R}^{d}$, a protected attribute $g_{i}\in\mathcal{G}$, and a
classification label $y_{i}\in\\{0,1\\}$. Allow
$f:X\times\mathcal{G}\rightarrow\Omega$ with $\Omega=[0,1]$ to be a regressor
that estimates the likelihood $(x,g)$ attains the outcome denoted by the
positive classification label

(1) $\displaystyle f(x,g)=\Pr(\bm{Y}=1|\bm{X}=x,\bm{G}=g)$

where $\bm{X},\bm{G},\bm{Y}$ are the associated random variables. We will
often refer to the probabilities output by $f(x,g)$ as scores given that they
“rank” the $(x,g)$ based on their estimated likelihood of attaining the
outcome associated with $\bm{Y}=1$. The scores output from $f(x,g)$ are used
to determine discrete decisions denoted $\hat{y}\in\\{0,1\\}$. For binary
predictions, these are obtained using a threshold $\tau\in[0,1]$ where
$\hat{y}_{i}=\mathds{1}_{f(x_{i},g_{i})\geq\tau}$.

If a regressor performs poorly for one group, or if the base risk of two
groups differs, classifications instantiated from thresholding can lead to
unbalanced allocation of interventions across groups, and ultimately lead to
disparate impact (Feldman et al., 2015; Chouldechova, 2016; Zafar et al.,
2017a; Kleinberg, 2018).111Here, disparate impact does not refer to the 80/20
legal doctrine, nor the frequently referenced fairness criteria (Feldman et
al., 2015), but rather refers to each group observing different impacts from
some machine learning tool. See (Barocas et al., 2019) for a complete
treatment of this discussion. If the thresholds used to produce
classifications are known or assumed at model development time, there is a
myriad of fair interventions which can be deployed to (at least partially)
mitigate disparities (Feldman et al., 2015; Zemel et al., 2013; Calmon et al.,
2017; Kamiran and Calders, 2012; Agarwal et al., 2018) at deployment. There
are many situations however, where classification thresholds are not known in
advance, or may change over time. Consider a case where the model user lacks
the expertise or resources to train a model. This frequently occurs in
healthcare and criminal justice contexts, where predictive scores are used in
tandem with human experts to allocate treatments or determine legal decisions
(Chouldechova, 2016; Obermeyer and Mullainathan, 2019). In these contexts,
model users will operationalize the model at whichever threshold best suits
their domain-specific requirements. We make this clear in the following
example:

###### Example 1.1.

Suppose a healthcare organization has a model to predict the likelihood of
being diagnosed with severe illness. An outreach team may want to notify all
the patients that are more likely than not to be diagnosed, therefore using a
threshold of $0.5$ to determine which patients to contact. The clinical team,
on the other hand, only has the resources to treat the riskiest patients, and
therefore uses a much higher threshold, such as $0.8$, to determine which
patients to treat.

Ideally, a regressor performs well under some fairness metric regardless of
the decision threshold that is selected. In practice, however, this is often
not the case. In fact, it is well studied that different choices in threshold
can lead to wildly different social outcomes (Hu and Chen, 2020; Zafar et al.,
2017b; Hardt et al., 2016). From this observation, we see that fair solutions
are often not portable (Abebe et al., 2020); achieving fairness with respect
to one specific application or threshold does not imply fair performance at
other thresholds (Corbett-Davies and Goel, 2018) for a similar task or even
for the same model. Moreover, if the use case or underlying population of a
model change downstream, but retraining or modifying a model is not viable
(e.g. is prohibitively expensive), additional engineering is required in order
to ensure model performance. Our solution is to develop a model which is fair
with respect to many thresholds at the same time. If a model can achieve
fairness across all possible choices in threshold simultaneously, it can be
deployed by any downstream user who flexibly utilizes such a model at
different thresholds, and subsequently for different applications.

##  2\. Fair Regressors & Optimal Transport

In this section, we will overview important preliminaries in algorithmic
fairness and optimal transport, and discuss the connection between the two.
Then, we will introduce total and geometric repair, two techniques that lie at
the intersection of fairness and optimal transport, and begin to motivate
their use in our post-processing method.

###  2.1. Fairness Metrics and the Confusion Matrix

In the context of classification, the performance of a classifier222Herein,
“classifier” will refer to thresholded output of a regressor. is often
evaluated by performance metrics in the confusion matrix. For a regressor $f$,
each of these confusion-matrix based metrics is a function
$\gamma_{g}^{y,c}:\Omega\rightarrow[0,1]$ such that

(2)
$\displaystyle\gamma_{g}^{y,c}(\tau)=\Pr[\bm{\hat{Y}}(\tau)=c|\bm{Y}=y,\bm{G}=g)]$

where $y,c\in\\{0,1\\}$ denote dataset label and predicted class respectively,
and $g$ denotes protected attribute such that
$\Pr[\bm{\hat{Y}}(\tau)=c|\bm{G}=g]=\mathop{\mathbb{E}_{x\sim\bm{X}}}[\mathds{1}_{\hat{y}=c}|\bm{G}=g]$
with $\hat{y}=\mathds{1}_{f(x,g)}\geq\tau$ indicating that
$\hat{y}\sim\bm{\hat{Y}}$. For a regressor $f$, we refer to the set of all
such confusion-matrix based metrics $\gamma_{g}^{y,c}(\tau)$ as $\Gamma_{f}$.
For example, under this notation, the True Negative Rate (TNR) of a classifier
for some group $g$ is $\gamma_{g}^{0,0}(\cdot)$ (see Table 2 in the appendix
for additional examples). In cases where we consider both values of a
sub/superscript, we omit it from our $\gamma$ notation. For example, the
Positive Rate (PR) of the classifier is written $\gamma^{c=1}(\cdot)$ since we
consider all groups $\bm{G}=0,1$ and all labelings $\bm{Y}=0,1$. Occasionally
we may also index our metrics $\gamma_{k}$.333Note although we do not address
this case specifically, our framework can be easily extended to the
$m$-multiclass setting by considering $c_{1}....c_{m}$ and using rates of the
form $\gamma^{c=c_{i}}$ for positive classification of class $c_{i}$ or
$\gamma^{c\neq c_{i}}$ in the negative case.

Returning to our original goal, we’d like to express the fairness of some
classifications across all thresholds, for $\Gamma_{f}$. To express exact
equality in these metrics across all threshold we introduce the notion of
distributional parity.

###### Definition 2.1 (Distributional Parity).

A regressor $f$ satisfies distributional parity with respect to
$\gamma\in\Gamma_{f}$ if

(3)
$\displaystyle|\gamma_{g=1}^{y,c}(\tau)-\gamma_{g=0}^{y,c}(\tau)|=0\quad\forall\tau\in\Omega,y\in
Y,c\in C.$

with $\mathop{\mathbb{E}_{\tau\sim
U(\Omega)}}|\gamma_{g=1}^{y,c}(\tau)-\gamma_{g=0}^{y,c}(\tau)|$ acting as a
measure of distributional (dis)parity. 444We refer to “distributional parity”
both as a fairness notion and as a fairness metric.

Definition 2.1 generalizes existing definitions of strong fairness. For
example, if we were to consider only the Positive Rate of each group, we
recover the definition of Strong Demographic Parity from Jiang et al. (2020).

###### Definition 2.2 (Strong Demographic Parity (SDP)).

A regressor $f$ satisfies strong demographic parity if

(4)
$\displaystyle\max_{\tau\in[0,1]}|\gamma_{g=1}^{c=1}(\tau)-\gamma_{g=0}^{c=1}(\tau)|=0$

It has been shown that Strong Demographic Parity is closely related to notions
of statistical distance, specifically the Wasserstein Distance (Chzhen et al.,
2020b; Gordaliza et al., 2019; Gouic et al., 2020; Jiang et al., 2020). In the
next section, we will briefly introduce the Wasserstein Distance and
demonstrate its connection to SDP and other measures of distributional parity.

(a) Difference in shaded area between curves shows disparity in some $\gamma$
at a single threshold. This difference suggests a high level of distributional
disparity.

(b) These curves nearly overlap, with both curves having similar area to the
left of every threshold depicted. This illustration of distributions of scores
being geometrically “similar” forms intuition at the core of distributional
parity.

(c) To achieve distributional parity, we interpolate distributions in
Wasserstein space. The dotted figures are the various barycenters of the
distributions, which represent the least expensive set of transformations
which would equalize their shaded areas.

Figure 1. An illustration of distributional parity and its relationship to the
Wasserstein geometry of distributions. Each plot shows groupwise distributions
of scores.

###  2.2. Wasserstein Preliminaries

Let $p\geq 1$, and $\mathcal{P}_{p}(\Omega)$ be the space of Borel probability
measures 555We review the atomicity of these distributions in the Appendix A.3
on $\Omega$ with finite $p\textsuperscript{th}$ moments. We denote the
distribution of scores for group $g\in\mathcal{G}$ as
$\mu_{g}\in\mathcal{P}_{p}(\Omega)$. The cumulative distribution function
(CDF) of any $\mu$ is denoted $F_{\mu}(\tau)=\mu((-\infty,\tau])$. We also
make heavy use of the generalized inverse of the CDF of some $\mu$, called the
quantile function, denoted $F^{-1}_{\mu}$. In cases where $supp\mu\neq\Omega$,
the CDF of $\mu$ is not strictly increasing, and therefore does not have a
well defined inverse. In this case, we define the quantile function as a
pseudo-inverse.

###### Definition 2.3 (Pseudo-inverse of a CDF).

Given some cumulative distribution function $F_{\mu}:\Omega\rightarrow[0,1]$
its pseudo-inverse is the function $F^{-1}_{\mu}:[0,1]\rightarrow\Omega$ where
$F^{-1}_{\mu}(a)=\inf\\{\tau\in\Omega:F_{\mu}(\tau)\geq a)$

####  2.2.1. Wasserstein Distance

The Wasserstein distance is a method of comparing two probability
distributions by measuring the “cost” of transporting one distribution to
another. If this transportation is costly, then the Wasserstein distance
between the two distributions will be large. Formally, suppose
$\Omega_{x},\Omega_{y}\subseteq\Omega$ are endowed with cost function
$c:\Omega_{x}\times\Omega_{y}\rightarrow\mathbb{R}$. Let
$\mu\in\mathcal{P}_{p}(\Omega_{x})$ and $\nu\in\mathcal{P}_{p}(\Omega_{y})$.
The notion of transport is formally defined by a transport plan. A transport
plan is a function $T:\Omega_{x}\rightarrow\Omega_{y}$ subject to the
following constraint: if the elements in the pre-image of $T$ have measure
$\mu$, and the output of $T$ is distributed according to $\nu$, i.e. if $T$ is
the transport plan from $\mu\rightarrow\nu$ then $v(A)=\mu(T^{-1}(A))$ for all
measurable $A\subseteq\Omega_{y}$. The measure resulting from a transportation
$T$ plan from $\mu\rightarrow\nu$ under this constraint is called the push
forward of $\mu$ and is denoted $T_{\\#}\mu=\nu$. Let $\mathcal{T}$ be the set
of transportation plans. The optimal transport plan is the plan that obeys
push-forward constraints while minimizing transportation costs

(5) $\displaystyle
T^{*}:=\operatorname*{arg\,inf}_{T\in\mathcal{T}}\int_{\Omega}c(\omega,T(\omega))d\mu(\omega)\quad\text{where}\quad
T_{\\#}\mu=\nu.$

For univariate measures, the optimal transport plan and Wasserstein distance
both admit a closed form. The transport plan $T$ from $\mu\rightarrow\nu$ is
computed $T(\omega)=F^{-1}_{\nu}(F_{\mu}(\omega))$, and the Wasserstein
distance is computed as follows:

###### Definition 2.4 (Wasserstein distance666Wasserstein distances on
$\mathbb{R}$ are sometimes refereed to as Earth Mover distances. on univariate
measures).

(6)
$\displaystyle\mathcal{W}(\mu,\nu)_{p}^{p}:=\left(\int_{\Omega}|F^{-1}_{\mu}(x)-F^{-1}_{\nu}(x)|^{p}dx\right)=\|F^{-1}_{\mu}-F^{-1}_{\nu}\|_{L_{p}(\Omega)}^{p}.$

From the second equality, we can also see that the geometry of univariate
probability measures in Wasserstein space is linear-like,777The map
$\mu\rightarrow F^{-1}_{\mu}$ is an isometric embedding which can map the
Wasserstein space defined
$(\mathcal{P}_{p}(\Omega),\mathcal{W}_{p}(\cdot,\cdot))$ to the space
$L_{p}(\Omega)$. allowing us to evoke familiar geometric concepts like
midpoints, or averages, but over probability measures and using the
Wasserstein distance as a distance kernel.

####  2.2.2. Wasserstein Barycenters

The midpoint or geometric average of a set of measures in Wasserstein space is
called the Wasserstein Barycenter (Agueh and Carlier, 2011). Intuitively, the
barycenter is a weighted composition of several probability measures,
geometrically averaging their densities into a single new probability measure.

###### Definition 2.5 (Wasserstein Barycenter).

Allow $\mu_{1}...\mu_{m}\in\mathcal{P}_{p}(\Omega)$ and
$\vec{w}\in\mathbb{R}^{m}$ to be a weight vector with $\sum_{i=1}^{m}w_{i}=1$.
The Wasserstein Barycenter of these measures, denoted by $\beta$ is

(7)
$\displaystyle\beta:=\operatorname*{arg\,min}_{\nu\in\mathcal{P}_{p}(\Omega)}\sum_{i=1}^{m}w_{i}\mathcal{W}_{p}(\nu,\mu_{i}).$

###  2.3. On the Connection between Wasserstein Distance and Fairness Metrics

There is an intimate connection between fairness metrics in $\Gamma_{f}$ and
the Wasserstein distance. Specifically, the average difference (taken over
thresholds) in some performance metric across groups is measured by the
Wasserstein distance between the score distributions of each group. We express
this formally with Proposition 2.6.

###### Proposition 2.6.

Let $f:X\times\mathcal{G}\rightarrow\Omega$ and assume without loss of
generality that $c=1$. Then, let $\mu^{y}_{g=0},\mu^{y}_{g=1}$ be the
groupwise distributions of scores $f$ produces. We have

(8) $\displaystyle\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}|\gamma_{g=1}^{y}(\tau)-\gamma_{g=0}^{y}(\tau)|^{p}=\mathcal{W}_{p}^{p}(\mu^{y}_{g=0},\mu^{y}_{g=1}).$

Proofs of mathematical results can be found in Appendix E.

If we consider $\gamma^{c=1}_{g}$, then the first term in Proposition 2.6
measures distributional disparity with respect to positive rates, functioning
like a disparity metric for strong demographic parity. Results from (Gordaliza
et al., 2019; Gouic et al., 2020; Jiang et al., 2020; Chzhen et al., 2020b)
have already shown that achieving strong demographic parity is equivalent to
vanishing the Wasserstein distance between group-conditioned score
distributions. With the above proposition, we extend this result to all rates
in the confusion matrix.

Although this is a handy result, what remains to show is a good way of
removing the Wasserstein distance between some group-conditional
distributions: how do we modify a regressor such that the Wasserstein distance
between its group conditioned score distributions is minimized? So far, this
has been achieved using total and geometric repair. Next, we will introduce
these repair methods and demonstrate their use.

###  2.4. Geometric Repair and Fair Regressors

One way to eliminate the Wasserstein distance between some distributions is to
map them onto some common distribution such that for each group, all scores
are distributed identically under the image of this mapping. The Wasserstein
barycenter is a candidate distribution in this regard due to several optimal
properties. Notably, Jiang et al. (2020) show that transport onto the
1-Wasserstein barycenter minimizes changes to the predicted class888In fact,
the expected changes in predicted class through total repair is exactly the
quantity $\mathcal{W}_{1}(\mu,\beta)$. By Jensen’s inequality we see
$\mathcal{W}_{p}(\mu,\beta)\leq\mathcal{W}_{r}(\mu,\beta)$ for all $r\geq
p\geq 1$ and so we assert this result holds for all orders of Wasserstein
Distance. in pursuit of SDP. Similarly, Chiappa et al. (2020) show that
transport onto a Wasserstein barycenter is Pareto-optimal with respect to a
tradeoff between fairness and accuracy. We will informally revisit this result
in Section 3.1. In fact, the barycenter of univariate distributions can be
computed as a closed-form solution to the optimization in Definition 2.5.
Given two distributions $\mu,\nu\in\mathcal{P}_{p}(\Omega)$ and some
$w\in[0,1]$, the quantile function of their weighted barycenter is

(9) $\displaystyle
F^{-1}_{\beta}(q)=(1-w)F^{-1}_{\mu}(q)+wF^{-1}_{\nu}(q),\quad q\in[0,1]$

where $\beta$ is the barycenter solution given in Definition 2.5.

By applying Remark 8 for transport on univariate measures, we can compute a
closed-form solution for the distribution-specific transportation functions
that map from $\mu$ or $\nu$ onto their barycenter.

###### Corollary 2.7.

Recall that given two distributions $\mu,\nu\in\mathcal{P}_{p}(\Omega)$ and
their barycenter $\beta$, the optimal transport plan from
$\mu\rightarrow\beta$ is $T_{\mu}(x)=F^{-1}_{\beta}(F_{\mu}(x))$ and from
$\nu\rightarrow\beta$ is $T_{\nu}(x)=F^{-1}_{\beta}(F_{\nu}(x))$. Suppose we
allow the input to the quantile function of a barycenter be $q=F_{\mu}(x)$,
then we can view the barycenter computation as the weighted sum of
transportation plans

$\displaystyle
F^{-1}_{\beta}(F_{\mu}(x))=(1-w)F^{-1}_{\mu}(F_{\mu}(x))+wF^{-1}_{\nu}(F_{\mu}(x))$

.

If $f(\bm{X},g)\sim\beta$ for both groups, then surely the Wasserstein
distance between these group conditional score distributions
$\mathcal{W}{}(\mu_{g},\mu_{g^{\prime}})=0$. With Proposition 2.6, we conclude
that transporting scores onto their barycenter achieves distributional parity
in a regressor. Like (Chzhen et al., 2020a; Gouic et al., 2020), we can
present a closed-form solution to this regressor.

###### Proposition 2.8.

Let $f:X\times\mathcal{G}\rightarrow\Omega$ be a regressor and define
$\alpha(x,g)=\inf\\{a\in\Omega:F_{\mu_{g}}(a)\geq
F_{\mu_{g^{\prime}}}(f(a,g))\\}$ for $g,g^{\prime}\in\mathcal{G}$. With
respect to some fair metric $\gamma_{g}^{y}(\tau)$ their fair regressor
$f_{\beta}:X\times\mathcal{G}\rightarrow\Omega$ is

(10) $\displaystyle f_{\beta}(x,g)=p_{g}f(x,g)+(1-p_{g})\alpha(x,g),\quad x\in
X_{y}$

where $p_{g}$ is the likelihood of belonging to group $g$ and $X_{y}$ is the
set of all elements with labeling $y$.

This type of mapping to the barycenter for some fixed $p$ is called total
repair (Gordaliza et al., 2019; Feldman et al., 2015). These works also show
that partially repairing some distributions by parametrizing the weights of
the barycenter computation can be useful in computing a repair distribution.
This type of repair is typically referred to as geometric repair, and is the
basis for our main contributions.

##  3\. Distributional Fairness via Geometric Repair

Our key methodological contribution makes use of geometric repair to achieve
distributional parity. Geometric repair is a type of partial repair which does
not fully map distributions onto the barycenter, but rather linearly
interpolates between the source distributions and their barycenter in
Wasserstein space. Let’s define the shift function
$t:X\times\mathcal{G}\rightarrow\Omega$, which gives the difference between an
unrepaired score and its fully repaired version:
$t(x,g)=f_{\beta}(x,g)-f(x,g)$.

###### Definition 3.1 (Geometric Repair).

Let $\lambda\in[0,1]$ be the repair parameter. We define geometric repair as

(11) $\displaystyle f_{\beta}^{\lambda}(x,g)=f(x,g)+\lambda t(x,g)$

Figure 2. Experiments using the (old) Adult dataset. X-axis: all possible
choices of threshold $\tau\in[0,1]$. Y-axis: group-conditional selection rate,
TPR, and FPR for the classifications resulting from each possible $\tau$. Top
row: classifications based on original, uncorrected classifier probabilities.
Bottom left: full correction ($\lambda=1$). Bottom middle & right:
$\lambda\approx 0.32$, $\lambda\approx 0.68$. $\lambda$ values are calculated
based on the labelled training data, and shown here applied to the unlabelled
testing data.

Figure 2 illustrates our method on an example dataset (see Appendix 2 for
experimental details). The plots visualize various confusion matrix rates over
all possible classifier thresholds, for each of two groups. When the group-
conditional metric curves do not overlap, the resulting classifications will
exhibit disparity; distributional parity is achieved only when the group-
conditional metric curves overlap across all possible thresholds. In this
example,while there is disparity over all thresholds in all three metrics
displayed for the uncorrected score distribution ($\lambda=0$), various values
of $\lambda$ make it possible to achieve distributional parity in positive
rates, true positive rates, and false positive rates. This is an empirical
illustration of the following observation: with a single barycenter, for any
distributional parity metric in $\Gamma_{f}$, there is always a value for the
repair parameter $\lambda$ which minimizes that metric – through mapping onto
the $\lambda-$repaired distribution. We explain this result by examining some
key properties of geometric repair and Wasserstein space.

###  3.1. Wasserstein Geodesics

Geometric repair is a method for optimally interpolating between distributions
in Wasserstein space. Here, optimal refers to the length of the “path” that
emerges between two measures and their barycenters for various values of the
weight parameter $\lambda$. This path is called a geodesic, and it defines a
length-minimizing path between distributions in Wasserstein space.

###### Definition 3.2 (Wasserstein geodesic).

A curve $\eta:[0,1]\rightarrow\mathcal{P}_{p}(\Omega)$ is a Wasserstein
geodesic999This is also known as a constant speed geodesic. if for any
$\mu_{0},\mu_{1}\in\mathcal{P}_{p}(\Omega)$, it locally minimizes the distance
between any points along a curve between $\mu_{0},\mu_{1}$ with
$\eta(0)=\mu_{0}$ and $\eta(1)=\mu_{1}$ such that
$\mathcal{W}_{p}(\eta(\lambda_{1}),\eta(\lambda_{2}))=|\lambda_{2}-\lambda_{1}|\mathcal{W}_{p}(\mu_{0},\mu_{1})$
for all $\lambda_{1},\lambda_{2}\in[0,1]$.

Let $\beta_{\lambda}$ be a set of measures between $\mu_{g},\mu_{g^{\prime}}$
in Wasserstein space defined
$\beta_{\lambda}=\\{\nu^{*}\in\mathcal{P}_{p}(\Omega):\nu^{*}=\operatorname*{arg\,min}_{\nu\in\mathcal{P}_{p}(\Omega)}(1-\lambda)\mathcal{W}_{p}(\mu_{g},\nu)+\lambda\mathcal{W}_{p}(\nu,\mu_{g^{\prime}})\;\forall\lambda\in[0,1]\\}$.
Then, $\beta_{\lambda}$ is the set of all barycenters between $\mu_{g}$ and
$\mu_{g}^{\prime}$ and contains all distributions along the geodesic (Agueh
and Carlier, 2011).

This result indicates that geometric repair enumerates a geodesic of
barycenters between distributions, and is therefore the optimal way to
transport two distributions in Wasserstein space. In other words, given some
desired amount of repair towards a fairness objective, geometric repair
induces minimal changes to the original distributions, and therefore incurs
minimal loss of their desirable properties. This suggests that geometric
repair is optimal with respect to the infamous “fairness-utility trade-off,”
as discussed in Section 2.1 101010Despite these properties, there is extensive
work criticizing and contesting the merit of the fairness-accuracy trade-off
(Cooper and Abrams, 2021; Dutta et al., 2020)..

With the following corollary, we show that geometric repair, as parametrized
by $\lambda$, is able to recover every barycenter between two distributions:
in other words, it can fully express the entire geodesic between curves
through interpolation.

###### Corollary 3.3.

A geometrically repaired regressor $f_{\beta}^{\lambda}$ can be computed as
the barycenter of $\mu_{g},\mu_{g^{\prime}}$ with weights $(1-\lambda+\lambda
p_{g})$ and $\lambda(1-p_{g})$.

###  3.2. Optimization with the Barycenter: finding $\bm{\lambda}$

Figure 3. Each plot shows the absolute (total) area between the pairs of
curves belonging to $\gamma_{g},\gamma_{g^{\prime}}$ after partial repair over
possible values of $\lambda\in[0,1].$ The diamond marker and dashed line
indicate the average and 95% confidence interval for the value of $\lambda$
which minimizes the area between the group-conditional curves for each metric.

We first show that for any metric $\gamma\in\Gamma_{f}$, there exists a value
of $\lambda\in[0,1]$ that minimizes distributional disparity in the partially-
repaired scores. Using Proposition 3.5, we will prove that metrics in
$\Gamma_{f}$ are convex on Wasserstein geodesics. This allows us to use
standard optimization tools to find the value of the repair parameter
$\lambda$ that minimizes an objective function—specifically, distributional
parity between two groupwise score distributions.

First, we present Lemma 3.4, which motivates the convexity of distributional
parity metrics. We begin by demonstrating that with respect to some metric
$\gamma$, fair performance changes monotonically with the repair parameter.
The direction of this change depends on which distribution has better average
performance with respect to the desired metric—said differently, changes in
the repair parameter will either strictly increase or decrease the value of a
performance metric (e.g. true positive rate) at a given threshold. Allow
$\mu^{\lambda}_{g}$ to be the groupwise distribution of scores corresponding
to the the $\lambda-$repaired regressor, i.e.
$f_{\beta}^{\lambda}(x,g)\sim\mu^{\lambda}_{g}$.

###### Lemma 3.4.

Fix some threshold $\tau\in\Omega$. Assume
$F_{\mu^{\lambda}_{g}},F_{\mu^{\lambda}_{g^{\prime}}}$ have continuous first
derivatives for all $\lambda\in[0,1]$. If $F_{\mu^{\lambda}_{g}}(\tau)\geq
F_{\mu^{\lambda}_{g^{\prime}}}(\tau)$ then $\gamma_{g}(\tau)$ decreases
monotonically at that threshold with increase in $\lambda$, and increases
monotonically if $F_{\mu^{\lambda}_{g}}(\tau)\leq
F_{\mu^{\lambda}_{g^{\prime}}}(\tau)$.

If at every threshold, one group’s distribution is monotonically “increasing”
with respect to some metric during repair while the other’s is monotonically
“decreasing,” it follows that the difference between the metrics should
resemble a convex function, as both distributions move towards their
barycenter with increases in $\lambda$. We formalize this intuition in the
following theorem:

###### Theorem 3.5.

Define
$\delta_{\gamma_{g}}(\lambda):=\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda},\mu_{g^{\prime}}^{\lambda})$
or equivalently $\delta_{\gamma_{g}}(\lambda):=\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}|\gamma_{g}(\tau)-\gamma_{g^{\prime}}(\tau)|^{p}$ for all
$\lambda\in[0,1]$ and $\gamma_{g}\in\Gamma_{f_{\beta}^{\lambda}}$. Then
$\delta_{\gamma_{g}}(\lambda)$ is convex.

###### Corollary 3.6.

Let $v\in\mathbb{R}^{k}_{\geq 0}$ and
$\gamma_{k=1}...\gamma_{k=k}\in\Gamma_{f}$. The linear combination
$v_{1}\delta_{\gamma_{1}}(\lambda)+...+v_{k}\delta_{\gamma_{k}}(\lambda)$ is
also convex.

The convexity of $\delta_{\gamma}$ implies that there exists a value of the
repair parameter $\lambda$ along the Wasserstein geodesic which can minimize
groupwise differences in distributional parity. Additionally, Corollary 3.6,
guarantees that a minima exists for any linear combination of metrics, thereby
allowing us to compute a repair parameter that minimizes distributional
disparity for multiple rates at once—for example, equalized odds, which
measures both TPR and FPR differences.

Due to the convexity of distributional parity metrics, this repair parameter
is guaranteed to achieve a minima111111This minima is only guaranteed to be
locally optimal; we aim to characterize the global optimality of this approach
in future work., and is computed by solving the following
optimization121212The optimal repair parameter for any distributional parity
metric can be calculated exactly using standard convex optimization tools.

Let $f_{\beta}^{\lambda}(x,g)$ be a repaired regressor,
$\gamma_{k=1}...\gamma_{k=k}$ be performance metrics in
$\Gamma_{f_{\beta}^{\lambda}}$ and $\vec{w}\in\mathbb{R}^{k}_{\geq 0}$ be a
weight vector, the distributional parity minimizing $\lambda^{*}$ along the
geodesic 131313We refer the reader to Algorithm 2 in the appendix to compute
this exactly. is given by

(12)
$\displaystyle\lambda^{*}\leftarrow\arg\min_{\lambda\in[0,1]}\sum_{j=1}^{k}w_{j}\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}[\gamma_{k=j,g}(\tau)-\gamma_{k=j,g^{\prime}}(\tau)]$

Figure 4. A comparison of three methods of finding $\lambda$s: empirical
estimation, which was done by testing all values of $\lambda$, probabilistic
estimation, which was calculated according to Proposition 3.8, and exact
calculation, as in Remark 3.2, over the same ten trials.

###  3.3. Estimating $\bm{\lambda}$ with Probabilistic Distributional Parity.

As datasets become large, computing the distributional (dis)parity minimizing
$\lambda$ in Remark 3.2 can become computationally expensive, as the objective
function must evaluate some $\gamma$ across the entire dataset, and at every
threshold. Although this computation is not always prohibitively expensive, in
more complex optimization routines like that of Section 5, it can become
extremely slow in practice. To remedy this issue, we present a high-quality
approximation for such an optimal $\lambda$. The exact value of $\lambda$ that
minimizes a distributional parity metric can be approximated instantaneously
with Probabilistic Distributional Parity, an extension of probabilistic equal
opportunity as introduced in Taskesen et al. (2021).

###### Definition 3.7 (Probabilistic Distributional Parity).

A regressor $f$ satisfies Probabilistic Distributional Parity if

(13)
$\displaystyle\mathbb{E}_{x\sim\mathcal{X}_{g}}[f(x,g)|\bm{Y}=y,\bm{G}=g]=\mathbb{E}_{x\sim\mathcal{X}_{g^{\prime}}}[f(x,g)|\bm{Y}=y,\bm{G}=g^{\prime}].$

Like its non-probabilistic counterpart, Probabilistic Distributional Parity
encompasses all metrics contained in $\Gamma_{f}$. For example, to consider a
probabilistic variant of equal opportunity, we compute the above expectation
with $Y=1$; conversely, for false positive rates, we condition on $Y=0$.
Computing a repair parameter with respect to probabilistic distributional
parity also admits a closed form solution.

###### Proposition 3.8.

The $\lambda$ which approximates the optimal repair parameter with respect to
some fairness definition is

(14)
$\displaystyle\lambda=\frac{\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}}}[f(x,g^{\prime})|\bm{Y},\bm{G}=g^{\prime}]-\mathop{\mathbb{E}_{\mathcal{X}_{g}}}[f(x,g)|\bm{Y},\bm{G}=g]}{\mathop{\mathbb{E}_{\mathcal{X}_{g}}}[t(x,g)|\bm{Y},\bm{G}=g]-\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}}}[t(x,g^{\prime})|\bm{Y},\bm{G}=g^{\prime}]}$

In Figure 4, we illustrate the quality of $\lambda$ approximations using
Proposition 3.8. In addition to $\lambda$’s computed with exact and
probabilistic methods, we also show the empirical $\lambda$ found in each
trial141414See Appendix 2 for experimental details. . Note the range of
estimated optimal $\lambda$s is remarkably similar for both methods across all
ten random splits of the dataset.

Finally, we are ready to summarize our general approach, illustrated in Figure
5. Appendix D provides additional comments on using our method in practice.

Figure 5. A summary of how each step of our post-processing method proceeds.
As noted in (Chzhen et al., 2020b), calculating the adjustment of score
distributions to the barycenter does not require ground-truth labels. Labels
are only required to determine the best $\lambda$ for the dataset given a
desired metric; $\lambda$s are therefore calculated with the labeled training
data and are used to control the barycenter adjustment for unlabeled data.
Finally, note that we do not require any of the features used for the machine
learning model, only group membership and the model’s predicted scores. This
general framework also describes our method workflow for the setting discussed
in Section 5.

##  4\. Limitations of existing methods

Our approach is most closely related to other works using optimal transport to
satisfy notions of fairness. In (Jiang et al., 2020; Chzhen et al., 2020b;
Gouic et al., 2020), optimal transport is used to achieve strong demographic
parity; however, these works do not extend their approach to other metrics in
the confusion matrix. In (Feldman et al., 2015; Gordaliza et al., 2019)
optimal transport is applied to the input features, whereas our work focuses
on applying optimal transport to classifier output. In addition, the quality
of Wasserstein distance estimation in optimal transport decreases in higher
dimensions (i.e. on input features), whereas using only output scores, we do
not suffer the same curse-of-dimensionality issues(Chizat et al., 2020). A
growing body of work utilizes the Wasserstein distance as a measure for
fairness, achieving fair classification through distributionally robust
optimization (Yurochkin et al., 2019; Taskesen et al., 2021); however, these
works are a train-time intervention, rather than post-processing.

Our problem setting is conceptually similar to the problem of fair regression
(Berk et al., 2017; Chzhen et al., 2020a, b), where the goal is to achieve
some definition of fairness by adjusting the group-conditional distribution of
predictions in a continuous output space. However, we do not seek to make
groupwise distributions identical; this also distinguishes our work from the
fair top-$k$ ranking problem (Zehlike et al., 2017). Vogel et al. (2021) also
explore the problem of adjusting rankings in order to satisfy classification
fairness for many thresholds; however, they propose an in-processing method
for learning the scores during train time.

As a fairness intervention, our work is most closely related to other post-
processing methods such as those implemented in popular libraries like IBM’s
AI Fairness 360 (Bellamy et al., 2018), Microsoft’s Fairlearn (Bird et al.,
2020), or those introduced in (Hardt et al., 2016; Kamiran et al., 2012;
Pleiss et al., 2017). In these works, fair classifications are produced over
some discrete decision space, thereby implying a specific decision threshold,
and limiting their applicability in the upstream/downstream case we study
here. The post-processing method introduced by Kim et al. (2019) seeks to
achieve multiaccuracy, i.e. equally-accurate predictions across all
identifiable subgroups of the data. Hébert-Johnson et al. (2018), which seeks
multicalibration, requires building a model from scratch.

Our method is an improvement on these approaches for several reasons: first,
it is a post-processing method and can therefore make use of information
learned by an existing classifier; second, our approach can achieve multiple
definitions of distributional parity; and third, as we will detail below, our
approach can naturally accommodate a sensitive attribute which takes on more
than two attributes. Though many of the works described above satisfy one or
multiple of these qualities, ours is the only to our knowledge that satisfies
all three.

##  5\. Beyond Binary Protected Attributes

In cases where a protected attribute takes on more than two values (i.e. where
$|\mathcal{G}|\geq 2$), the problem of locating an optimal repair parameter
becomes more complex. In the binary attribute setting, there was only one
possible comparison to optimize. In the non-binary attribute setting, however,
the number of possible pairwise comparisons between groups is exactly
$|\mathcal{G}|\choose 2$, which grows quadratically as the number of groups
increases. Now, suppose instead there are $n$ protected groups such that
$g=\\{g_{1},...g_{n}\\}$. As a necessary consequence of this extension, we
introduce repair parameters for each group $1\leq i\leq n$

(15) $\displaystyle\begin{aligned}
f_{\beta}^{\lambda_{i}}(x,g_{i})&=f(x,g_{i})+\lambda_{i}t(x,g_{i}).\end{aligned}$

Achieving distributional parity in positive rates in this context remains the
same: we solve this with total repair, by mapping each group’s score
distribution completely onto a barycenter, by setting $\lambda_{i}=1$ for all
$i\in[n]$. Achieving other notions of distributional parity, however, is
complicated by the fact we are searching for some optimal repair vector
$\vec{\lambda}=(\lambda_{1}...\lambda_{n})$ in an $n$-dimensional space. This
higher dimensional search problem introduces additional challenges. In
general, a fair intervention which minimizes disparities in a performance
metric across all groups simultaneously can artificially benefit or
disadvantage some groups with respect to that metric (Hu and Chen, 2020;
Corbett-Davies and Goel, 2018). In the binary sensitive attribute setting,
max-min fairness was introduced to alleviate this tension (Lahoti et al.,
2020): a max-min solution maximizes the performance of the group that is worst
off without minimizing the performance of the other, presumably advantaged,
group. One common criticism of current fair algorithmic scholarship, however,
is that binary protected attributes are not expressive enough to create a
meaningful model for the study or design of fair interventions that work in
practice (Kearns et al., 2018; Hanna et al., 2020; Hoffmann, 2019; Buolamwini
and Gebru, 2018).

As we look to extend geometric repair to the non-binary attribute setting,
max-min fairness is no longer sufficient, since the formulation of max-min
fairness relies on the assumption that protected attributes are binary.
Suppose we wish to achieve a max-min-like solution for an protected attribute
that takes on multiple (non-binary) values. Although a learning problem can be
constrained to replicate a max-min-like solution for all groups, this requires
the practitioner to develop a complete ordering of disparities—in other words,
to explicitly identify the group which should have the highest performance,
the group which should have the second highest performance, and so on. For a
large protected attribute space, this task requires a rather large normative
judgement on behalf of the practitioner. Even if this ordering were to exist,
it still has the potential to decrease overall groupwise performance, due to
performance tradeoffs that may be associated with the prescribed ordering of
disparities (Kearns et al., 2018). Lexicographic fairness was proposed to
remedy the above concerns. Here, we will describe lexicographic fairness as
introduced to the supervised learning literature, detail its relevance to
geometric repair, provide a constrained optimization algorithm that outputs a
lexicographically fair repair vector, and finally conclude with a case study
on FICO credit scores.

###  5.1. Lexicographic Fairness

Lexicographic fairness, introduced to the learning literature by Diana et al.
(2021) as an adaptation of previous work from social choice and fair division
(Brandt et al., 2016; Hooker, 2010), is an extension of max-min fairness
(Lahoti et al., 2020) that minimizes group-conditional error rates in a way
that prioritizes the groups that are the worst off. More specifically, a
lexicographically fair approach will first minimize the loss of the worst off
group, and then use the loss under of the worst off group as a constraint to
minimize the loss of the next worst off group, continuing until all groups
have had their losses minimized subject to the constraints established by
minimizing the losses for better-off groups.

Allow $\mathcal{H}$ to be the space of hypothesis for the classification task.
Let $L_{g}:\mathcal{H}\rightarrow\mathbb{R}$ be the loss for the group defined
$g$. We define the total loss of a hypothesis as the sum of group loss terms:

(16) $\displaystyle L(h)=\sum_{i=1}^{n}a_{g_{i}}L_{g_{i}}(h)$

where $a_{g_{i}}\in\mathbb{R}_{+}$ represents the weight given to the loss
term corresponding to group $g_{i}$. Allow
$\mathcal{O}:[n]\rightarrow\mathcal{G}$ to be a bijection ordering the group
error rates in decreasing order such that
$L_{\mathcal{O}(1)}(h)>L_{\mathcal{O}(2)}(h)...>L_{\mathcal{O}(n)}(h)$. The
total error rate for some hypothesis is computed recursively and in rounds. At
the $k^{th}$ round where $1\leq k\leq|\mathcal{G}|$, the error rate is defined
$\epsilon_{k}\coloneqq\min_{h\in\mathcal{H}_{k-1}}L_{\mathcal{O}(k)}(h)$ where
$\mathcal{H}_{k-1}$ is the hypothesis class at $kth$ round constrained to the
set of hypotheses which minimized at the previous rounds $H_{k}=\\{h\in
H_{k-1}:L_{\mathcal{O}(k)}(h)\leq\epsilon_{k}\\}$151515Note $k$ is slightly
overloaded—our use of $k$ here, to index rounds of lexicographic optimization,
is different from its usage in Section 3.. A lexicographically fair solution
is one which achieves the error rates defined recursively in this way.

###### Definition 5.1 (Lexicographic Fairness).

A model $h\in H$ satisfies lexicographic fairness if
$L_{\mathcal{O}(k)}(h)\leq\epsilon_{k}$ for all $k\leq n.$

Note that max-min fairness is actually a special case of lexicographic
fairness. That is, a max-min solution is identical to a single round of
lexicographic optimization; see Appendix C.1 for more detail.

Because lexicographic fairness is defined recursively, the set of hypotheses
that satisfy the above definition is not convex. To make lexicographic
fairness a convex set, we redefine the space of lexicographically fair
hypotheses by enumerating the recursive constraints into many linear
constraints:

###### Definition 5.2 (Convex Lexicographic Fairness).

A model $h$ satisfies convex lexicographic fairness if

(17) $\displaystyle\max_{R\in 2^{\mathcal{G}},|R|\leq j}\sum_{g\in
R}L_{\mathcal{O}(i)}(h)\leq\min_{h^{\prime}\in\mathcal{H}_{j-1}}\max_{R\in
2^{\mathcal{G}},|R|\leq j}\sum_{g\in R}L_{g}(h^{\prime})\quad\forall k\leq
n,j\leq k.$

Diana et al. (2021) show that a convex lexicographically fair classifier has
the same error profile as its non-convex counterpart, and that if the original
model class $\mathcal{H}$ is convex, then the lexicographically fair subset of
hypothesis that satisfy the above definition will also be convex.

###  5.2. Achieving Distributional Parity with Lexicographic Fairness

To apply the lexicographic fairness approach to our setting, we use
Probabilistic Distributional Parity, defined in Section 3.1, as the group loss
function:

(18) $\displaystyle L_{g_{i}}(\vec{\lambda})=\sum_{j\leq n,i\neq
j}\big{|}\mathop{\mathbb{E}_{X_{g_{i}}|Y}}[f(x,g_{i})]-\mathop{\mathbb{E}_{X_{g_{j}}|Y}}[f(x,g_{j})]\big{|}$

Due to the convexity of Probabilistic Distributional Parity, this loss is also
convex. Allow $\Lambda_{\ell}\subseteq\mathbb{R}^{n}$ to be the set of
lexicographically fair repair parameters. We compute the lexicographically
fair repair as the solution to the following optimization, subject to the
constraint set at round $k\leq n$:

(19)
$\displaystyle\min_{\vec{\lambda}\in\Lambda_{\ell}}\sum_{i=1}^{n}L_{g_{i}}(h,\vec{\lambda})\quad\text{s.t.}\quad
C_{k}(\epsilon_{1}...\epsilon_{k})=\\{\sum_{i_{j}}L_{i_{j}}\leq\epsilon_{j}:(i_{1},...i_{j})\subseteq[I]\quad\forall
j\leq k\\}.$

We present full pseudo-code for this procedure, formalized as Algorithm 3, in
Appendix C.1, and summarize the intuition here. At the first round ($k=1$),
the algorithm computes a max-min fairness solution by minimizing loss for the
group that is worst off. The worst loss in the max-min solution is
$\epsilon_{1}$. At the second round ($k=2$), the algorithm minimizes the loss
of the second worst-off group, subject to the condition that no single group’s
loss may exceed the loss of the max-min solution $\epsilon_{1}$. Then, the
loss of the two worst off groups under the max-min solution becomes
$\epsilon_{2}$. At the third round ($k=3$), the algorithm minimizes the loss
of the third worst-off group, subject to the constraint that no two groups
have a combined loss greater than $\epsilon_{2}$, and that no single group has
a loss which exceeds $\epsilon_{1}$. The algorithm continues in this fashion
until the last round, where the final lexicographic solution $\lambda_{k}$ is
computed.Next, we show in Theorem 5.3 that Algorithm 3 outputs a
lexicographically fair solution for some probabilistic distributional parity
loss.

###### Theorem 5.3.

For a convex and bounded choice in loss function
$L:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and convex hypothesis class
$\mathcal{H}$, Algorithm 3 will output a lexicographically fair solution.

###  5.3. Case Study: FICO

Figure 6. A replication of Figure 2, now with a sensitive attribute that takes
on four values using the FICO dataset. X-axis: all possible choices of
threshold $\tau\in[0,100]$. Y-axis: group-conditional positive rate, TPR, and
FPR for the classifications resulting from each $\tau$. Top row:
classifications based on uncorrected scores. Bottom row: classifications based
on $\lambda$s calculated with Algorithm 3.

To demonstrate the effect of our proposed post-processing, we study various
repair methods on FICO credit scores. The goal of a credit score is to
estimate an individual’s general credit risk, where low scores should
correspond to high-risk individuals and high scores to low-risk individuals.
In the United States, credit scores for various minority groups are often
lower than those of their white counterparts despite similar monetary
behaviors and financial histories (Nelson, 2010). The FICO credit scores we
examine are sourced from a 2003 government report that collected TransUnion
credit data on $\sim 300k$ individuals. The dataset consists of an
individual’s ethnic group (which we use as a protected group), their credit
score, and an outcome label $Y$ where $Y=0$ if an individual failed to pay a
debt within $18$–$24$ months of the data being collected.161616Our FICO
results also indicates our method’s flexibility—we do not require that the
quantity being thresholded represents a probability. We can consider the
credit scores to be the output of an unknown regressor $f$.

Since credit scores are not equally representative of true creditworthiness
for each group, any choice in threshold will induce some systematic disparity
in access to credit when credit scores are relied upon as an accurate proxy
for creditworthiness. Consider an algorithm developer who highly values
identifying eligible borrowers across groups, and suffers a high cost for
missed lending opportunities. In this framework, the goal of the designer is
TPR balance, otherwise known as equal opportunity. On the other hand, an
algorithm developer who cares more about the cost of unpaid loans may seek to
achieve FPR balance. Either way, we assume the developer is unsure which
decision threshold will be used downstream, and wishes to produce a regressor
which is fair regardless of choice in classification threshold. In this case
study, to achieve TPR balance, we use probabilistic distributional parity loss
with true positive rates, or probabilistic equal opportunity i.e.
$\mathop{\mathbb{E}_{x\sim X}}[f(x,g)|\bm{Y}=1,\bm{G}=g]$ where $X$ is the set
of credit features used by the regressor. To achieve FPR balance, the loss
function we use can be written as $\mathop{\mathbb{E}_{x\sim
X}}[f(x,g)|\bm{Y}=0,\bm{G}=g]$.

Figure 6 illustrates the efficacy of our method. While the uncorrected credit
scores lead to substantial disparity in positive rates, true positive rates,
and false positive rates across all thresholds, our method is able to find
sets of $\lambda$s for each metric such that disparity is minimized across all
thresholds. In each case, parity is achieved by improving performance on the
worst-off groups, rather than worsening overall performance; this is
especially clear in the TPR case (bottom middle). Additionally, note that
unlike Figure 2, which illustrated the binary case, there is a set of
$\lambda$s (one for each group) that achieves distributional parity in true
positive rates, and a separate set of $\lambda$s for false positive rates.

Table 1. Group-wise probabilistic equal opportunity losses (means across ten trials). See Appendix 3 for experimental details and how to interpret these numbers. | Asian | Black | Hispanic | White
---|---|---|---|---
Lexicographic | 7.25 | 7.56 | 7.92 | 6.25
Max-min | 7.25 | 9.09 | 8.08 | 7.80
Full repair (SDP) | 28.55 | 39.14 | 23.54 | 23.67
Unrepaired | 29.87 | 42.09 | 29.72 | 34.49

Table LABEL:tab:lex_loss shows the probabilistic equal opportunity loss on the
unrepaired scores, the fully-repaired scores, and the scores computed with the
lexicographic and maxmin solutions. In this case, the model developer seeks to
ensure equal true positive rates across groups for all thresholds. The
lexicographic solution achieves the smallest loss for every group compared to
other repair methods. The max-min solution is the second most effective, but
is dominated by the lexicographic solution. The full-repair solution, which
achieves distributional parity with respect to positive rates, highlights the
issues with strong demographic parity as a fair desideratum—the SDP solution
has groupwise losses on the order of the unrepaired scores, indicating that a
demographic parity based intervention may not be the most effective. The
unrepaired scores are several orders of magnitude worse than the repaired
scores.

##  6\. Discussion & Future Research

In this paper, we introduce a flexible post-processing method for minimizing
distributional disparities across various definitions of fairness, and over
all possible downstream choices of a classification threshold. On a technical
level (1) we demonstrate how to achieve measures of distributional fairness
other than (strong) demographic parity; (2) we show how to achieve fairness
over thresholds for the case when the sensitive attribute takes on more than
two attributes.

Here, we highlight a few potentially fruitful directions of future work. One
limitation of this work is that a single repair parameter controls entire
group-conditional score distributions. In future work, we look to utilize
partial optimal transport as a framework for repairing distributions, we may
seek to transport only a subset of the overall data. Additionally, we hope to
better understand how to locate global minimal repair, and quantify the gap
between local minima in distributional parity on the geodesic and the global
minima in Wasserstein space. Finally, given that the distributions of both
model predictions and ground truth may change over time, further exploration
of how sensitive our approach is to distribution shifts may be
worthwhile—especially since our method relies on model output, rather than
model input.

Broadly, we believe this work is a practical contribution to the set of tools
available to a fair machine learning practitioner. Ongoing commentary has
criticized the frequent conflation of making predictions and making decisions,
especially in the context of fairness (Corbett-Davies and Goel, 2018; Green
and Hu, 2018); this work is one step towards separating the two.

## References

  * (1)
  * jus ([n.d.]) [n.d.].  Why Inter-Rater Reliability Matters for Recidivism Risk Assessment.  https://bja.ojp.gov/sites/g/files/xyckuh186/files/media/document/pb-interrater-reliability.pdf
  * Abebe et al. (2020) Rediet Abebe, Solon Barocas, Jon Kleinberg, Karen Levy, Manish Raghavan, and David G. Robinson. 2020.  Roles for Computing in Social Change. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 252–260.  https://doi.org/10.1145/3351095.3372871
  * Agarwal et al. (2018) Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. 2018\.  A reductions approach to fair classification. In _International Conference on Machine Learning_. PMLR, 60–69.
  * Agueh and Carlier (2011) Martial Agueh and Guillaume Carlier. 2011.  Barycenters in the Wasserstein space.  _SIAM Journal on Mathematical Analysis_ 43, 2 (2011), 904–924.
  * Barocas et al. (2019) Solon Barocas, Moritz Hardt, and Arvind Narayanan. 2019\.  _Fairness and Machine Learning_.  fairmlbook.org.  http://www.fairmlbook.org.
  * Bellamy et al. (2018) Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al. 2018\.  AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias.  _arXiv preprint arXiv:1810.01943_ (2018).
  * Berk et al. (2017) Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. 2017\.  A convex framework for fair regression.  _arXiv preprint arXiv:1706.02409_ (2017).
  * Bird et al. (2020) Sarah Bird, Miro Dudík, Richard Edgar, Brandon Horn, Roman Lutz, Vanessa Milan, Mehrnoosh Sameki, Hanna Wallach, and Kathleen Walker. 2020.  Fairlearn: A toolkit for assessing and improving fairness in AI.  _Microsoft, Tech. Rep. MSR-TR-2020-32_ (2020).
  * Bower et al. (2017) Amanda Bower, Sarah N. Kitchen, Laura Niss, Martin J. Strauss, Alexander Vargas, and Suresh Venkatasubramanian. 2017.  Fair Pipelines.  arXiv:1707.00391 [cs.CY]
  * Brandt et al. (2016) Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. 2016\.  _Handbook of computational social choice_.  Cambridge University Press.
  * Buolamwini and Gebru (2018) Joy Buolamwini and Timnit Gebru. 2018.  Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification. In _Proceedings of the 1st Conference on Fairness, Accountability and Transparency_ _(Proceedings of Machine Learning Research, Vol. 81)_ , Sorelle A. Friedler and Christo Wilson (Eds.). PMLR, 77–91.  https://proceedings.mlr.press/v81/buolamwini18a.html
  * Calmon et al. (2017) Flavio P Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. 2017.  Optimized pre-processing for discrimination prevention. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_. 3995–4004.
  * Chiappa et al. (2020) Silvia Chiappa, Ray Jiang, Tom Stepleton, Aldo Pacchiano, Heinrich Jiang, and John Aslanides. 2020\.  A General Approach to Fairness with Optimal Transport.. In _AAAI_. 3633–3640.
  * Chizat et al. (2020) Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré. 2020.  Faster Wasserstein Distance Estimation with the Sinkhorn Divergence.  arXiv:2006.08172 [math.OC]
  * Chouldechova (2016) Alexandra Chouldechova. 2016\.  Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.  arXiv:1610.07524 [stat.AP]
  * Chzhen et al. (2020a) Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. 2020a.  Fair regression via plug-in estimator and recalibration with statistical guarantees.  (2020).
  * Chzhen et al. (2020b) Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. 2020b.  Fair regression with wasserstein barycenters.  _arXiv preprint arXiv:2006.07286_ (2020).
  * Cooper and Abrams (2021) A. Feder Cooper and Ellen Abrams. 2021.  Emergent Unfairness in Algorithmic Fairness-Accuracy Trade-Off Research. In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_. Association for Computing Machinery, New York, NY, USA, 46–54.
  * Cooper et al. (2022) A. Feder Cooper, Benjamin Laufer, Emanuel Moss, and Helen Nissenbaum. 2022.  Accountability in an Algorithmic Society: Relationality, Responsibility, and Robustness in Machine Learning.  arXiv:2202.05338 [cs.CY]
  * Corbett-Davies and Goel (2018) Sam Corbett-Davies and Sharad Goel. 2018.  The Measure and Mismeasure of Fairness: A Critical Review of Fair Machine Learning.  _CoRR_ abs/1808.00023 (2018).  arXiv:1808.00023 http://arxiv.org/abs/1808.00023
  * Diana et al. (2021) Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, and Saeed Sharifi-Malvajerdi. 2021.  Lexicographically Fair Learning: Algorithms and Generalization.  _CoRR_ abs/2102.08454 (2021).  arXiv:2102.08454 https://arxiv.org/abs/2102.08454
  * Ding et al. (2021) Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. 2021.  Retiring Adult: New Datasets for Fair Machine Learning.  _arXiv preprint arXiv:2108.04884_ (2021).
  * Dutta et al. (2020) Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin-Yu Chen, Sijia Liu, and Kush Varshney. 2020\.  Is There a Trade-Off Between Fairness and Accuracy? A Perspective Using Mismatched Hypothesis Testing. In _Proceedings of the 37th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 119)_ , Hal Daumé III and Aarti Singh (Eds.). PMLR, 2803–2813.  https://proceedings.mlr.press/v119/dutta20a.html
  * Dwork et al. (2020) Cynthia Dwork, Christina Ilvento, and Meena Jagadeesan. 2020\.  Individual Fairness in Pipelines.  _CoRR_ abs/2004.05167 (2020).  arXiv:2004.05167 https://arxiv.org/abs/2004.05167
  * Feldman et al. (2015) Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. 2015\.  Certifying and removing disparate impact. In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_. 259–268.
  * Forde et al. (2021) Jessica Zosa Forde, A Feder Cooper, Kweku Kwegyir-Aggrey, Chris De Sa, and Michael Littman. 2021\.  Model Selection’s Disparate Impact in Real-World Deep Learning Applications.  _arXiv preprint arXiv:2104.00606_ (2021).
  * Friedler et al. (2019) Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubramanian, Sonam Choudhary, Evan P Hamilton, and Derek Roth. 2019.  A comparative study of fairness-enhancing interventions in machine learning. In _Proceedings of the conference on fairness, accountability, and transparency_. 329–338.
  * Gordaliza et al. (2019) Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean-Michel Loubes. 2019.  Obtaining fairness using optimal transport theory. In _International Conference on Machine Learning_. PMLR, 2357–2365.
  * Gouic et al. (2020) Thibaut Le Gouic, Jean-Michel Loubes, and Philippe Rigollet. 2020.  Projection to fairness in statistical learning.  _arXiv preprint arXiv:2005.11720_ (2020).
  * Green and Hu (2018) Ben Green and Lily Hu. 2018\.  The myth in the methodology: Towards a recontextualization of fairness in machine learning. In _Proceedings of the machine learning: the debates workshop_.
  * Hanna et al. (2020) Alex Hanna, Emily Denton, Andrew Smart, and Jamila Smith-Loud. 2020\.  Towards a Critical Race Methodology in Algorithmic Fairness. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 501–512.  https://doi.org/10.1145/3351095.3372826
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nathan Srebro. 2016.  Equality of opportunity in supervised learning. In _Proceedings of the 30th International Conference on Neural Information Processing Systems_. 3323–3331.
  * Hébert-Johnson et al. (2018) Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. 2018.  Multicalibration: Calibration for the (computationally-identifiable) masses. In _International Conference on Machine Learning_. PMLR, 1939–1948.
  * Hod (18 ) Shlomi Hod. 2018–.  Responsibly: Toolkit for Auditing and Mitigating Bias and Fairness of Machine Learning Systems.  http://docs.responsibly.ai/
  * Hoffmann (2019) Anna Lauren Hoffmann. 2019\.  Where fairness fails: data, algorithms, and the limits of antidiscrimination discourse.  _Information, Communication & Society_ 22, 7 (2019), 900–915.
  * Hooker (2010) John N Hooker. 2010\.  Optimality conditions for distributive justice.  _International Transactions in Operational Research_ 17, 4 (2010), 485–505.
  * Hu and Chen (2020) Lily Hu and Yiling Chen. 2020.  Fair Classification and Social Welfare _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 535–545.  https://doi.org/10.1145/3351095.3372857
  * Jiang et al. (2020) Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. 2020\.  Wasserstein fair classification. In _Uncertainty in Artificial Intelligence_. PMLR, 862–872.
  * Kamiran and Calders (2012) Faisal Kamiran and Toon Calders. 2012.  Data preprocessing techniques for classification without discrimination.  _Knowledge and Information Systems_ 33, 1 (2012), 1–33.
  * Kamiran et al. (2012) Faisal Kamiran, Asim Karim, and Xiangliang Zhang. 2012\.  Decision theory for discrimination-aware classification. In _2012 IEEE 12th International Conference on Data Mining_. IEEE, 924–929.
  * Kearns et al. (2018) Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2018.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In _International Conference on Machine Learning_. PMLR, 2564–2572.
  * Kim et al. (2019) Michael P Kim, Amirata Ghorbani, and James Zou. 2019\.  Multiaccuracy: Black-box post-processing for fairness in classification. In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_. 247–254.
  * Kleinberg (2018) Jon Kleinberg. 2018\.  Inherent Trade-Offs in Algorithmic Fairness.  (2018), 40.  https://doi.org/10.1145/3219617.3219634
  * Lahoti et al. (2020) Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed H. Chi. 2020\.  Fairness without Demographics through Adversarially Reweighted Learning.  _CoRR_ abs/2006.13114 (2020).  arXiv:2006.13114 https://arxiv.org/abs/2006.13114
  * Mallasto and Feragen (2017) Anton Mallasto and Aasa Feragen. 2017.  Learning from uncertain curves: The 2-Wasserstein metric for Gaussian processes. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/7a006957be65e608e863301eb98e1808-Paper.pdf
  * Nelson (2010) Ashlyn Aiko Nelson. 2010\.  Credit scores, race, and residential sorting.  _Journal of Policy Analysis and Management_ 29, 1 (2010), 39–68.
  * Obermeyer and Mullainathan (2019) Ziad Obermeyer and Sendhil Mullainathan. 2019.  Dissecting Racial Bias in an Algorithm That Guides Health Decisions for 70 Million People. In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ (Atlanta, GA, USA) _(FAT* ’19)_. Association for Computing Machinery, New York, NY, USA, 89\.  https://doi.org/10.1145/3287560.3287593
  * Pleiss et al. (2017) Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. 2017.  On Fairness and Calibration.  _Advances in Neural Information Processing Systems_ 30 (2017), 5680–5689.
  * Selbst et al. (2019) Andrew D. Selbst, Danah Boyd, Sorelle A. Friedler, Suresh Venkatasubramanian, and Janet Vertesi. 2019\.  Fairness and Abstraction in Sociotechnical Systems. In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ (Atlanta, GA, USA) _(FAT* ’19)_. Association for Computing Machinery, New York, NY, USA, 59–68.  https://doi.org/10.1145/3287560.3287598
  * Taskesen et al. (2021) Bahar Taskesen, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. 2021.  A Statistical Test for Probabilistic Fairness. In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ (Virtual Event, Canada) _(FAccT ’21)_. Association for Computing Machinery, New York, NY, USA, 648–665.  https://doi.org/10.1145/3442188.3445927
  * Vogel et al. (2021) Robin Vogel, Aurélien Bellet, Stephan Clémen, et al. 2021\.  Learning Fair Scoring Functions: Bipartite Ranking under ROC-based Fairness Constraints. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 784–792.
  * Yurochkin et al. (2019) Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. 2019.  Training individually fair ML models with sensitive subspace robustness.  _arXiv preprint arXiv:1907.00020_ (2019).
  * Zafar et al. (2017a) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. 2017a.  Fairness Beyond Disparate Treatment & Disparate Impact.  _Proceedings of the 26th International Conference on World Wide Web_ (Apr 2017).  https://doi.org/10.1145/3038912.3052660
  * Zafar et al. (2017b) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi, and Adrian Weller. 2017b.  From Parity to Preference-based Notions of Fairness in Classification.  arXiv:1707.00010 [stat.ML]
  * Zehlike et al. (2017) Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yates. 2017.  Fa* ir: A fair top-k ranking algorithm. In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_. 1569–1578.
  * Zemel et al. (2013) Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. 2013.  Learning fair representations. In _International conference on machine learning_. PMLR, 325–333.

##  Appendix A Notation

###  A.1. Glossary of Symbols

Below is a glossary of the notation we use in this paper. Symbols generally
appear in this table in the order they appear above.

Symbol | Description |
---|---|---
$g\in\mathcal{G}$ | Set of protected groups |
$x\in\mathcal{X}$ | Feature space |
$y\in Y$ | Label space |
$D$ | A dataset consisting of features, protected attributes, and labels |
$\Omega$ | The output space of some regressor $f$ |
$f$ | An (unrepaired) regressor |
$\bm{X},\bm{G},\bm{Y}$ | Bold-faced notation expresses random variables |
$\tau$ | A classification threshold |
$\hat{y}$ | Classifications generated from thresholding regressor output |
$\Gamma_{f}$ | The set of metrics for a regressor f. See Table 2. |
$\gamma$ | A metric from the confusion matrix for f s.t. $\gamma\in\Gamma_{f}$. See Table 2. |
$\gamma^{y,c}_{g,k}$ | How we notate metrics: $y$ for label, $c$ for class, $g$ for group, and $k$ for index |
$\mathcal{P}_{p}(\Omega)$ | Space of Borel probability measures over $\Omega$ with finite $p^{th}$ moments |
$\mu,\nu$ | Some probability measures, usually in $\mathcal{P}_{p}(\Omega)$. Often $\mu_{g}$ denotes group-specific score distribution. |
$\pi_{\mu}$ | The probability density function (PDF) of a measure $\mu$ |
$\mathcal{W}_{p}(\mu,\nu)$ | p-Wasserstein Distance between $\mu,\nu$ |
$T\in\mathcal{T}$ | The set of transport plans |
$F_{\mu}$ | The Cumulative Distribution Function of $\mu$ |
$F^{-1}_{\mu}$ | The inverse of the CDF; occasionally this is a psuedo-inverse. |
$c(\cdot,\cdot)$ | A cost function |
$\beta$ | The Wasserstein barycenter of some measures |
$U(\Omega)$ | Uniform Distribution on $\Omega$ |
$\alpha(x,g)$ | Like a CDF inverse, but for a regressor |
$f_{\beta}$ | The regressor corresponding to total repair with a barycenter $\beta$ |
$t(x,g)$ | The “shift” function used in geometric repair |
$\lambda$ | Geometric repair parameter, sometimes used to parametrize a barycenter |
$f^{\lambda}_{\beta}$ | A geometrically repaired regressor |
$\eta$ | Wasserstein geodesic |
$\beta_{\lambda}$ | The set of barycenters between two measures, enumerated by geodesic as parametrized by $\lambda$ |
$\mu_{\lambda}$ | Geometrically repaired score distribution, usually used in tandem with $f^{\lambda}_{\beta}$ |
$\mathcal{H}$ | A hypothesis class |
$L_{g}$ | The loss for group $g$ |
$\mathcal{O}$ | A bijection ordered group error rates (error as measured by loss function) |
$\epsilon$ | The error rate at some round of lexicographic, sometimes indexed by k |
$\Lambda_{\ell}$ | The space of lexicographically fair repair parameters |

###  A.2. $\bm{\gamma}$-Notation for the Confusion Matrix

We also include a table to help better understand our $\gamma$ notation on
confusion matrix based metrics.

###  A.3. A Note On Borel Probability Measures

In general, when referring to borel measures analytically, we will assume they
are non-atomic, and therefore they are supported on the entire measurable
space over which they are defined. Specifically, we mean for a measure
$\mu\in\mathcal{P}_{p}(\Omega)$ that $\operatorname{supp}\mu=\Omega$ if $\mu$
is non-atomic. In cases where measures are assumed to be empirical, we do not
make this assumption. We do however, remind the reader that the set of non-
atomic Borel Probability measures is dense in the set of Borel probability
measures, and so often, these Boreal probability measures are indeed non-
atomic.

Performance Metric | Definition |  $\Gamma_{f}$-Notation
---|---|---
Positive \Selection Rate (PR) | $\Pr[\bm{\hat{Y}}(\tau)=1|\bm{G}=g)]$ | $\gamma_{g}^{c=1}(\tau)$
True Positive Rate (TPR) | $\Pr[\bm{\hat{Y}}(\tau)=1|\bm{Y}=1,\bm{G}=g)]$ | $\gamma_{g}^{1,1}(\tau)$
False Positive Rate (FPR) | $\Pr[\bm{\hat{Y}}(\tau)=1|\bm{Y}=0,\bm{G}=g)]$ | $\gamma_{g}^{0,1}(\tau)$
Negative Rate (NR) | $\Pr[\bm{\hat{Y}}(\tau)=0|\bm{G}=g)]$ | $\gamma_{g}^{c=0}(\tau)$
True Negative Rate (TNR) | $\Pr[\bm{\hat{Y}}(\tau)=0|\bm{Y}=0,\bm{G}=g)]$ | $\gamma_{g}^{0,0}(\tau)$
False Negative Rate (FNR) | $\Pr[\bm{\hat{Y}}(\tau)=0|\bm{Y}=1,\bm{G}=g)]$ | $\gamma_{g}^{1,0}(\tau)$
Table 2.  This chart illustrates how to express standard metrics in the the
confusion matrix, but with $\gamma$’s. Algorithm 1 Computing a
lexicographically fair partial Wasserstein repair

Input: Group conditional scores $f(x,g)$ and Barycenter function $\beta(x,g)$
and $\vec{\alpha}$, $\vec{\omega}$

$\epsilon_{1}\leftarrow\infty$

Compute $L_{g}(\vec{\lambda})$ for each group and order the loss terms
$L_{h(1)}<...<L_{h(n)}$ $\triangleright$ $\vec{\lambda}=0$

for all $1\leq k\leq n$ do

$\lambda_{k}\leftarrow\arg\min_{\lambda\in\mathbb{R}^{n}}L_{h(k)}(\vec{\lambda})$
subject to constraints $C(\epsilon_{1}...\epsilon_{k-1}$)

$\epsilon_{k}\leftarrow\max_{R\in 2^{\mathcal{G}},|R|=k}\sum_{g\in
R}L_{g}(\vec{\lambda})$

end for

Output: lexicographic solution $\lambda_{n}$ and error rate $\epsilon_{n}$

##  Appendix B Supplemental material: Section 3 (Binary Sensitive Attribute)

###  B.1. Computing an Optimal $\lambda$ for Geometric Repair

First we show the pseudo-code of the routine we use to compute an optimal
geometric repair $\lambda$. In practice, we cannot compute an expectation over
all thresholds, so empirically, we make use of a set of evenly spaced
candidate thresholds. In our experiments we used np.linspace(0,1,.01).

Algorithm 2 Computing repair parameter

Input: A dataset $D=\\{(x_{i},g_{i},y_{i})\\}_{i=1}^{N}$ regressor $f(x,g)$,
fair regressor $f_{\beta}(x,g)$, performance metrics(s)
$\gamma_{k=1}...\gamma_{k=k}\in\Gamma_{(\cdot)_{\beta}^{\lambda}}$, weight
vector $\vec{w}\in\mathbb{R}^{k}_{\geq 0}$, and candidate thresholds
$\\{\tau_{i}\\}_{i=1}^{m}\subseteq\Omega$.

Let $f_{\beta}^{\lambda}(x,g)=f(x,g)+\lambda t(x,g)$

$\lambda^{*}\leftarrow\arg\min_{\lambda\in[0,1]}\sum_{j=1}^{k}w_{j}\sum_{i=1}^{m}\gamma_{k=j,g}(\tau_{i})-\gamma_{k=j,g^{\prime}}(\tau_{i})$
subject to $\gamma_{k,g}\in\Gamma_{f^{\lambda}_{\beta}}$

Output: repair parameter $\lambda^{*}$

(a) German Credit

(b) Employment

Figure 7. Group-conditional selection rate, TPR, and FPR curves over
thresholds. In each plot, the first row illustrates the uncorrected scores,
and the second row illustrates the scores after full correction.

###  B.2. Experimental setup

For each dataset, we run ten trials of the experiment; all plots (except
Figure 4) show the 95% confidence interval given results from all ten trials.
In each trial, we set a new random seed (so that seed=1 iff trial=1). Each
trial proceeds as follows:

  1. (1)

Score generation. We training our underlying model, a scikit-learn
RandomForestClassifier with default parameters. Using the trained classifier,
we predict on a separate set of data to get the scores. For every instance in
this set, we now have information about its label, group membership, and its
score. Since this is a postprocessing method, we will assume that some of this
data is labeled (which we can access), and some of this data is unlabeled
(which we will use to validate our method).

  2. (2)

Baseline evaluation. To get a baseline for distributional (un)fairness, for
every $\tau\in\\{0,0.01,0.02,...,0.98,0.99,1.0\\}$, we calculate binary
decisions using $\tau$ as the decision threshold; then, we compute group-
conditional selection rates, TPR, and FPR using these decisions.

  3. (3)

Calculating the barycenter adjustment. Calculating the barycenter adjustment
does not require access to labels, so this step can use both the labeled and
unlabeled data from Step (1). We calculate the barycenter for the two groups.
For this computation, we use a vectorized Python implementation of Chzhen et
al. (2020b)’s code. Now, for every row of data from (1), both labeled and
unlabeled, we now additionally have its adjustment: a single (signed) number
indicating how it should be transformed in order to lie on the barycenter.

  4. (4)

Finding the best $\bm{\lambda}$. Finding $\lambda$ does require access to
labels, so we now work only with the labeled dataset from (1). Each $\lambda$
corresponds to a single distributional fairness definition, so these steps are
done once for TPR and once for FPR. For each row of this dataset, we have
access to its label, group membership, score, and adjustment to the
barycenter. In actual usage, we suggest either the probabilistic or exact
approaches; the empirical approach is extremely—and
unnecessarily—computationally intensive. We use the empirical approach in our
experiments simply to illustrate the validity of the probabilistic and exact
approaches.

    1. (a)

Finding $\lambda$ empirically. On this new test set, for each value of
$\lambda\in\\{0,0.01,0.02,...,0.98,0.99,1.0\\}$, we multiply $\lambda$ by the
adjustment returned in (3). For each $\lambda$, we then follow the evaluation
process from (2), and pick the $\lambda$ that yields the best results (least
distributional disparity).

    2. (b)

Estimating $\lambda$ probabilistically.  The probabilistic method for finding
$\lambda$ does not require calculating hypothetical decisions. Instead, we
apply Proposition 3.8 using the original scores for the numerator and the
adjustment found in step 2 for the denominator.

    3. (c)

Calculating $\lambda$ exactly.  The exact calculation also does not require
calculating hypothetical decisions. We use the standard convex optimization
approach implemented from scipy (optimize.minimize_scalar) to compute the
exact $\lambda$ following the equation in Remark 3.2.

  5. (5)

Evaluation on unlabeled data. Our results in Figure 2 illustrate the effect of
using the $\lambda$s found in (4c) on the unlabeled data. Our method makes the
assumption that the labeled and unlabeled data are drawn i.i.d. from the same
distribution, so it is expected (and unsurprising) that the $\lambda$s found
using the labeled data are highly effective when applied to the unlabeled
data.

###  B.3. Datasets

A summary of datasets used for distributional fairness experiments can be
found in the table below. For German Credit and Adult (Old), we used the
postprocessed versions from Friedler et al. (2019), while New Adult datasets
are from Ding et al. (2021). All sensitive attributes are binary, with Sex
binarized as male-female, Race binarized as white-nonwhite, the Education
feature binarized as low education-high education, and Age binarized as young-
old.

| Sens. Attr | Prediction Task | Source
---|---|---|---
Adult (Old) | Sex | High income | UCI
Income | Race | High income | New Adult
Public Coverage | Race | Medicare | New Adult
Employment | Sex | Employed | New Adult
Taiwan Credit | Education | Good Credit | UCI
German Credit | Age | Good Credit | UCI
Table 3. Summary of datasets used for distributional fairness experiments.

For all New Adult datasets, data is pulled from the 2018 California 1-Year
Person survey. We use the first 30000 examples. Our train-test splits are as
follows: 18000 for training the random forest, and the remaining 12000 for our
method, of which 6000 are part of the labeled set, and 6000 are part of the
unlabeled set.

The UCI Adult dataset has 30162 examples total. We use 15000 examples for
training the random forest, 7581 as the unlabeled set, and 6000 for the final
unlabeled set.

The UCI Taiwan dataset has 30000 examples, and we make train-test splits
identical to the New Adult datasets.

The UCI German dataset has 1000 examples. We use 500 for training the random
forest, 250 as the labeled dataset, and 250 as the unlabeled dataset.

##  Appendix C Supplemental Material: Section 5 (Lexicographic Repair)

###  C.1. Additional notes on lexicographic fairness.

Lexicographic Fairness has a very strong connection to max-min fairness.
Observe that at the first round of minimization, a lexicographically fair
solution will identify the group with the largest loss, and then limit the
hypothesis class to the set of hypotheses which minimize error on this group,
thereby computing a maxmin solution(Diana et al., 2021).

###### Definition C.1.

A hypothesis $h$ satisfies max-min fairness if $h\in\mathcal{H}_{mm}$ where
$H_{mm}=\\{h\in\mathcal{H}:L_{\mathcal{O}(1)}(h)=\min_{h^{\prime}\in\mathcal{H}}L_{\mathcal{O}(1)}(h^{\prime})\\}$.

###### Theorem C.2.

Allow $h_{mm}$ to be some hypothesis which satisfies max-min fairness and
$h_{\ell}$ to be a lexicographically fair hypothesis with error profiles
$\epsilon(h_{mm})$ and $\epsilon(h_{\ell})$ respectively. Then
$\epsilon(h_{mm})\prec\epsilon(h_{\ell})$.

###### Proof.

This theorem follows from the construction of lexicographic solution. By
algorithm (1), the loss profile of a lexicographic solution is upper bounded
by that of the maxmin solution, as the maxmin solution is produced at round
$j=1$ and at subsequent rounds, is used as an upper bound for remaining
optimization rounds. Therefore, if there is ever a round at which the
lexicographic solution is not upper bounded by the maxmin solution, the
lexicographic solution must no longer be considered lexicographic as it has
violated the constraints from round $j$. ∎

Below is the pseudo code of the algorithm we use to compute a
lexicographically fair repair. Here we directly enumerate the constraints for
the lexicographic objective rather than make use of no-regret max-min dynamics
like (Diana et al., 2021). Due to the number of constraints on our
optimization problem, we occasionally experience numerical instability issues
in our implementation. We look to improve these in future work.

Algorithm 3 Computing a lexicographically fair repair

Input: Group conditional scores $f(x,g)$ and Barycenter function $\beta(x,g)$
and $\vec{\alpha}$, $\vec{\omega}$

$\epsilon_{1}\leftarrow\infty$

Compute $L_{g}(\vec{\lambda})$ for each group and order the loss terms
$L_{h(1)}<...<L_{h(n)}$ $\triangleright$ $\vec{\lambda}=0$

for all $1\leq k\leq n$ do

$\lambda_{k}\leftarrow\arg\min_{\lambda\in\mathbb{R}^{n}}L_{h(k)}(\vec{\lambda})$
subject to constraints $C(\epsilon_{1}...\epsilon_{k-1}$)

$\epsilon_{k}\leftarrow\max_{R\in 2^{\mathcal{G}},|R|=k}\sum_{g\in
R}L_{g}(\vec{\lambda})$

end for

Output: lexicographic solution $\lambda_{n}$ and error rate $\epsilon_{n}$

###  C.2. Experimental Setup

  1. (1)

Data generation. We use the FICO dataset from from the responsibly python
package (Hod, 18), documentation for which can be found at
docs.responsibly.ai. The FICO dataset is not given in terms of individual data
entries. Rather, the dataset is defined in terms of the joint distribution of
features, attributes, and labels. The dataset consists of the proportion of
individuals with each race, the probability of having some specific credit
score given by race, and the likelihood of a missing payment (Y=0) for the
given race and credit score. The four races in the dataset are Black, White,
Hispanic, and Asian. Credit scores are typically between $300-850$, however in
the dataset they are normalized to the interval $[0,1]$. Using the joint
distribution over scores, races, and missed payment status, we can generate
our own dataset. For our experiments, we use $8k$ entries total, $4k$ as
“labeled” data (from which $\lambda$’s are calculated) and $4k$ as our
“unlabeled” data (which is illustrated in 6).

  2. (2)

Computing the barycenter. We compute the barycenter using the python optimal
transport library POT. To compute the barycenter we use the regularized
bregman optimal transport solver with a regularization parameter $10^{-3}$.
The weights used in the computation are the proportion of each race given in
the dataset.

  3. (3)

Lexicographic Solver. As reported in Diana et al. (2021), exact lexicographic
solvers suffer from numerical instability issues. To this extent, there are
two stabilizing parameters $(\alpha,\epsilon)$ that are proposed to help
compute a lexicographic optimizer. In our experiment we borrow their
stabilized computation and use $\alpha=10^{-4}$ and $\epsilon=10^{-6}$ as
hyper parameters in this routine. We encourage the reader to visit the
lexicographic paper for a complete treatment of this optimizer.

  4. (4)

Trials. We generate data and compute the following solutions 10 times:
Lexicographic (LEX), Max-Min (MM), Strong Demographic Parity (SDP), and
Unconstrained(Unconst). The unconstrained method is simply the original data
without repair. We compute the groupwise loss function for the probabilistic
true positive rate difference function, where
$L_{s}(\lambda)=\sum_{g^{\prime}\in\mathcal{G},g^{\prime}\neq
g}\big{|}\mathbb{E}_{x\sim\mathcal{X}_{g}}[f(x,g)|Y=1]-\mathbb{E}_{x\sim\mathcal{X}_{g^{\prime}}}[f(x,g)|Y=1]\big{|}$,
and the same for the probabilistic false positive rate.

###  C.3. Interpreting Results

As stated above, the loss function used in the optimizer is based on
probabilistic equality in true/false positive rates:
$\mathop{\mathbb{E}_{x\sim X}}[f(x,g)|\bm{Y}=1,\bm{G}=g]$ or
$\mathop{\mathbb{E}_{x\sim X}}[f(x,g)|\bm{Y}=0,\bm{G}=g]$. Practically, this
quantity (for a single group) is simply the average score of examples labeled
$y=1$. Then, the “loss” for a single group $g$ recorded in Table
LABEL:tab:lex_loss/ Table LABEL:tab:lex_loss_copy is the sum of every
difference between that group’s average score for examples labeled $y=1$ and
every other group’s average score for examples labeled $y=1$.

Table 4. Group-wise probabilistic equal opportunity losses (means across ten trials). (Replicated from Section 5.) | Asian | Black | Hispanic | White
---|---|---|---|---
Lexicographic | 7.25 | 7.56 | 7.92 | 6.25
Max-min | 7.25 | 9.09 | 8.08 | 7.80
Full repair (SDP) | 28.55 | 39.14 | 23.54 | 23.67
Unrepaired | 29.87 | 42.09 | 29.72 | 34.49
Table 5. Group-wise probabilistic equal opportunity losses (standard errors across ten trials) | Asian | Black | Hispanic | White
---|---|---|---|---
Lexicographic | 0.85 | 1.51 | 1.22 | 0.78
Max-min | 0.80 | 1.61 | 1.19 | 1.05
Full repair (SDP) | 1.79 | 1.27 | 0.86 | 0.77
Unrepaired | 1.31 | 2.15 | 1.21 | 1.08

##  Appendix D Usability

Appendix 2 roughly follows our anticipated workflow, illustrated in Figure 8.

Our method assumes that a reasonably-well-performing model already exists. We
do not need access to the model itself—only its predictions on some labeled
data. After calculating how each point’s score would need to change in order
to be mapped onto the barycenter, we use that labeled data to calculate the
best $\lambda$ (or $\vec{\lambda}$, in case of a non-binary sensitive
attribute) for a particular fairness goal (such as equal TPRs, equal FPRs, or
see below for more extensions).

Meanwhile, with the unlabeled data on which we want to make adjustments, we
use the model to predict scores for this data; then, we make the barycenter
calculation to compute the adjustment for each point. Then, we scale those
adjustments by the $\lambda$ or $\vec{\lambda}$ found from the labeled data.
At this point, the scores have been “corrected,” and can be used in downstream
applications.

By Corollary 3.6, linear combinations of the $\gamma\in\Gamma$ that we have
defined are also convex in $\lambda$. This means that more complex fairness
goals can be achieved: for example, equalized odds by considering
$\gamma_{g}^{1,1}(\tau)+\gamma_{g}^{0,1}(\tau)$, or even some less
conventional metrics like one which considers both TPR and FPR, but weights
TPR more heavily than FPR, or one which considers TPR, FPR, and PR.

Figure 8. Figure 5, copied here for convenience.

###  D.1. Suitability

Our experiments hint at a few possible scenarios where our method may be less
applicable: (1) when the dataset size is small; (2) when overall disparity is
low; and (3) when the relationship between scores and labels is noisier for
one group than another. These results suggest that in practice, it is critical
to first visualize the threshold curves for both the baseline and full
adjustment to determine whether our method is appropriate.

However, in industry production settings, datasets are unlikely to be small;
overall low disparity is a good thing, and may mean that no intervention is
strictly necessary at all; and finally, if the relationship between scores and
labels is noisier for one group than another, this is an indication that the
underlying regressor that produced the scores is a poor hypothesis for the
learning task, which means that the model itself should be improved and that
papering over its performance with a postprocessing method would be poor
practice.

Here, we show results on two datasets, German and Employment, where our method
does not perform as well. Figure 7 illustrates group-conditional metrics over
all thresholds both before and after the full adjustment to the barycenter is
applied, and Figure 9 illustrates the same information as Figure 3.

Figure 9. On the German Credit (left) and Employment (right) datasets:
absolute (total) area between the pairs of curves belonging to
$\gamma_{g},\gamma_{g^{\prime}}$ after partial repair over possible values of
$\lambda\in[0,1]$. Note that these curves do not have the same shape as those
in Figure 3: German does not show much variation in disparity across
$\lambda$, so the minimum is fairly shallow, while the minimums for Employment
fall at $\lambda=0$ or $\lambda=1$.

German Credit: small dataset size and low overall disparity. First, the top
row of Figure 7(a) shows that disparity over thresholds is quite low, even in
the uncorrected case. In fact, the TPR curves are approximately overlapping.
Applying the barycenter adjustment is successful—the bottom left of Figure
7(a) indicates that the selection rates have in fact overlapped over all
thresholds. Further, note that the TPR and FPR curves, even in the full
adjustment with $\lambda=1$, are still extremely close. Consequently, the
impact of varying $\lambda$, shown in Figure 9, is extremely minimal.
Furthermore, the small dataset size resulted in high variability across
different train-test splits and therefore extremely wide confirdence
intervals. In a single run, results (both across thresholds and across
$\lambda$s) were extremely noisy.

Employment: noisy labels. The Employment dataset, on the other hand, has
plenty of samples since it is from the new Adult dataset. However, taking a
closer look at the top row of Figure 7(b) shows that while the selection rate
and FPRs of Group A are higher than those of Group B over almost all
thresholds, the TPR of Group A is lower than that of Group B over almost all
thresholds. Contrast this with the behavior of the uncorrected scores in
Figure 2, where the rates for Group A were consistently higher than Group B
over all thresholds and for all three metrics. In practical terms, if Group A
has a lower TPR and a higher FPR than Group B at all thresholds, this implies
that the score-label relationship for Group A is much noisier than the score-
label relationship for Group B, which means that merely adjusting the score
distributions does not necessarily result in a strictly better or “fairer” set
of results. In fact, the full correction (as shown in the bottom left of
Figure 7(b)) is successful in that it results in identical selection rates
across all thresholds, as expected, yet looking at Figure 9, it is unclear
that a “true” minima for the distance between the TPR curves can be found over
$\lambda\in[0,1]$.

##  Appendix E Proofs and Proof Tools

Below are all of these proofs and helping proofs for major results in the
paper.

###  E.1. External Lemmas (Proofs Omitted)

###### Lemma E.1.

This is lemma 6 from (Jiang et al., 2020). Let
$\mu,\nu\in\mathcal{P}_{p}(\Omega)$ with differentiable and invertible
cumulative distribution function $F_{\mu},F_{\nu}$ then

$\displaystyle\int_{\Omega}F_{\mu}(x)-F_{\nu}(x)dx=\int_{\Omega}F^{-1}_{\mu}(y)-F^{-1}_{\nu}(y)dy.$

We remind the reader that $\Omega=[0,1]$

###### Lemma E.2.

This result is from section 6.1 in (Agueh and Carlier, 2011). Allow
$\mu_{1}...\mu_{k}\in\mathcal{P}_{p}(\Omega)$ and $\vec{p}\in\mathbb{R}^{k}$
to be a weight vector with $\sum_{i=1}^{k}p_{i}=1$. The barycenter of these
distributions can be defined with respect to one of the distribution $\mu_{j}$
with $1\leq j\leq k$. Let $T_{j}^{i}:=F^{-1}_{\mu_{i}}\circ F_{\mu_{j}}$ then

$\displaystyle\beta=\left(\sum_{i=1}p_{i}T^{j}_{i}\right)_{\\#\mu_{j}}.$

From this lemma we learn that (1) mapping onto the barycenter is the result of
a linear combination of transportation maps and (2) mass is transported
through the use of these transport and the push-forward measure. In other-
words, we encourage the reader to view the computation of a new the
transported score, and assignment of measure to this score under the
barycenter, as the result of separate operations: the transportation map, and
the push-forward operator, respectively.

###### Lemma E.3.

Fix some distribution $\nu\in\mathcal{P}_{p}(\Omega)$, then the map
$\mu\mapsto\mathcal{W}_{p}^{p}(\mu,\nu)$ is convex. This lemma is from
(Mallasto and Feragen, 2017) Proposition 5.

###  E.2. Proofs of Mathematical Results

Proposition 2.6. Let $f:X\times\mathcal{G}\rightarrow\Omega$ and assume
without loss of generality that $c=1$. Then, let $\mu^{y}_{g=0},\mu^{y}_{g=1}$
be the groupwise distributions of scores $f$ produces. We have

(20) $\displaystyle\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}|\gamma_{g=1}^{y}(\tau)-\gamma_{g=0}^{y}(\tau)|^{p}=\mathcal{W}_{p}^{p}(\mu^{y}_{g=0},\mu^{y}_{g=1}).$

The proof of this result makes use of the following lemma

###### Proof.

Recall by definition that

$\displaystyle\gamma_{g}^{y}(\tau)$
$\displaystyle=\Pr[\bm{\hat{Y}}(\tau)=1|\bm{Y}=y,\bm{G}=g)]$
$\displaystyle=\Pr[f(\bm{X},g)\geq\tau|\bm{Y}=y,\bm{G}=g)]$
$\displaystyle=1-\Pr[f(\bm{X},g)\leq\tau|\bm{Y}=y,\bm{G}=g)]$
$\displaystyle=1-\mu_{g}^{y}((-\infty,\tau])$
$\displaystyle=1-F_{\mu_{g}^{y}}(\tau)$

Substituting this into the original expectation yields

$\displaystyle\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}|\gamma_{g=1}^{y}(\tau)-\gamma_{g=0}^{y}(\tau)|^{p}$
$\displaystyle=\int_{\Omega}|\gamma_{g=1}^{y}(\tau)-\gamma_{g=0}^{y}(\tau)|^{p}d\tau$
$\displaystyle=\int_{\Omega}|(1-F_{\mu_{g=0}^{y}}(\tau))-(1-F_{\mu_{g=1}^{y}}(\tau))|^{p}d\tau$
$\displaystyle=\int_{\Omega}|F_{\mu_{g=1}^{y}}(\tau)-F_{\mu_{g=0}^{y}}(\tau)|^{p}d\tau$
$\displaystyle=\int_{\Omega}|F^{-1}_{\mu_{g=1}^{y}}(\tau)-F^{-1}_{\mu_{g=0}^{y}}(\tau)|^{p}d\tau=\mathcal{W}_{p}^{p}(\mu^{y}_{g=0},\mu^{y}_{g=1})$

where the second to last equality follows from lemma E.1. ∎

Proposition 2.8. Let $f:X\times\mathcal{G}\rightarrow\Omega$ be a regressor
define $\alpha(x,g)=\inf\\{a\in\Omega:F_{\mu_{g^{\prime}}}(a)\geq
F_{\mu_{g}}(f(a,g))\\}$ for $g,g^{\prime}\in\mathcal{G}$. With respect to some
fair metric $\gamma_{g=1}^{y}(\tau)$ their fair regressor
$f_{\beta}:X\times\mathcal{G}\rightarrow\Omega$ is

(21) $\displaystyle f_{\beta}(x,g)=p_{g}f(x,g)+(1-p_{g})\alpha(x,g),\quad x\in
X_{y}$

where $p_{g}$ is the likelihood of belong to group $g$ and $X_{y}$ is the set
of all elements with labeling $y$.

###### Proof.

Suppose $\beta$ is the barycenter of $\mu_{g=0},\mu_{g=1}$ with weights
$p_{g},(1-p_{g})$. Then, by Proposition 2.6, mapping onto the barycenter
achieves distributional parity for $\gamma_{g=1}^{y}(\cdot)$. Now we will show
how to compute the mapping from arbitrary $\mu_{g}$ to $\beta$ and show how
this is equivalent to computing $f_{\beta}(\cdot)$. First, we will recall two
facts we make use of in this proof:

  1. (1)

For non-atomic borel measures (see Appendix A.3), where
$\operatorname{supp}\mu_{g}=\Omega$, then the pseudo-inverse is well defined,
and is a true inverse. This allows us to write
$F^{-1}_{\mu_{g}}(F_{\mu_{g}}(f(x,g)))=f(x,g)$.

  2. (2)

The function $\alpha(x,g)$ defines a transportation plan, but in the notation
of a regressor as $\alpha(x,g)=F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(f(x,g)))$
by the definition of $\alpha(\cdot,\cdot)$ and the pseudo-inverse.

Allow $q=F_{\mu_{g}}(f(x,g))$, then barycentric quantile function is computed

$\displaystyle F^{-1}_{\beta}(q)$
$\displaystyle=p_{g}F^{-1}_{\mu_{g}}(q)+(1-p_{g})F^{-1}_{\mu_{g^{\prime}}}(q)$
$\displaystyle=p_{g}F^{-1}_{\mu_{g}}(F_{\mu_{g}}(f(x,g)))+(1-p_{g})F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(f(x,g))))$
$\displaystyle=p_{g}f(x,g)+(1-p_{g})\alpha(x,g)=f_{\beta}(x,g)$

In the second to last equality, we make use of the above two facts. ∎

Lemma 3.4. Fix some threshold $\tau\in\Omega$. Assume
$F_{\mu^{\lambda}_{g}},F_{\mu^{\lambda}_{g^{\prime}}}$ have continuous first
derivatives for all $\lambda\in[0,1]$. If $F_{\mu^{\lambda}_{g}}(\tau)\geq
F_{\mu^{\lambda}_{g^{\prime}}}(\tau)$ then $\gamma_{g}(\tau)$ decreases
monotonically at that threshold with increase in $\lambda$, and increases
monotonically if $F_{\mu^{\lambda}_{g}}(\tau)\leq
F_{\mu^{\lambda}_{g^{\prime}}}(\tau)$.

###### Proof.

Allow $f$ to be a regressor with metrics $\Gamma_{f}$. Fix $\tau\in[0,1]$. We
begin by noting that by definition, any $\gamma_{g}^{y,c}\in\Gamma_{f}$
(w.r.t. the threshold $\tau$) is some metric of the form

$\displaystyle\gamma_{g}^{y,c}(\tau)=\Pr[\bm{\hat{Y}}(\tau)=c|\bm{Y}=y,\bm{G}=g)]=\int_{\mathcal{X}}\mathbbm{1}_{f(x,g)\geq\tau}d\mu^{*}$

where $\mu^{*}$ is $\mu^{y,c}_{g}$. Define $\mathcal{X}_{\tau}=\\{x\in
X:f(x,g)\geq\tau\\}$ to be the set of all $x$ with a score that is above the
given threshold. By the definition of the indicator function, we can ignore
the measure of all $x\not\in\mathcal{X}_{t}$ function, and re-write

$\displaystyle\int_{\mathcal{X}}\mathbbm{1}_{f(x,g)\geq\tau}d\mu^{*}=\int_{\mathcal{X}_{\tau}}d\mu^{*}=\mu^{*}(X_{\tau})$

which is exactly $Pr_{x\sim\mathcal{X}}(f(x,g)\geq\tau)$ with respect to the
measure $\mu^{*}$. If we take the complement of this probability we can obtain

$\displaystyle
Pr_{x\sim\mathcal{X}}(f(x,g)\geq\tau)=1-Pr_{x\sim\mathcal{X}}(f(x,g)\leq\tau)$

Noting that $Pr_{x\sim X}(f(x,g)\leq\tau)=\mu^{*}([-\infty,\tau))$ is the CDF
of the regressor scores, we arrive at the equality that
$\gamma(\tau)=1-F_{\mu^{*}}(\tau)$. This demonstrates the connection between
metrics in $\Gamma_{f}$ and the confusion matrix.

To determine the monotonicity of $\gamma(\tau)$ where
$\gamma\in\Gamma_{f^{\lambda}_{\beta}}$, we take its partial derivative with
respect to $\lambda$. First we derive a relationship between scores input to
$\mu_{g}$ and $\mu_{g}^{\lambda}$, or equivalently between $\mu_{g}$ and
$f_{\beta}$. This equivalency follows from the fact that repaired score
distributions can be expressed as a barycenter. From Lemma E.2 we have that

(22)
$\displaystyle\beta(x)=\mu_{g}\left((1-\lambda)F^{-1}_{\mu_{g}}(F_{\mu_{g}}(x))+\lambda
F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(x))\right)=\mu_{g}\left((1-\lambda)x+\lambda
F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(x))\right)$

If we allow $\rho=(1-\lambda)x+\lambda
F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(x))$ then we can invert this mapping
operation and solve for $x$

(23) $\displaystyle M(\rho,\lambda)=\frac{\rho-\lambda
F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(x))}{(1-\lambda)}.$

with $x=M(\rho,\lambda)$. In the above, we view $\rho$ as where $x$ lives on
the barycenter after a transport mapping is applied, and $M(\rho,\lambda)$ to
be the function which undoes the transportation mapping—in other words, for
what value $x$ does $\mu_{g}$ assign same measure as $\beta$ assigns $\rho$?

Using this inverse mapping, we can take some score distributed according to
$\mu^{\lambda}_{g}$ (recalling that barycenters and repaired distributions can
be expressed to represent the same distribution) and determine its “source”
score under $\mu_{g}$ as a function of $\lambda$. Let
$\tau=(1-\lambda)x^{\prime}+\lambda
F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(x^{\prime}))$ for $x^{\prime}\in[0,1]$.
Then $M(\tau,\lambda)=\frac{\tau-\lambda
F^{-1}_{\mu_{g^{\prime}}}(F_{\mu_{g}}(x^{\prime}))}{(1-\lambda)}$ which yields

$\displaystyle\frac{d}{d\lambda}[-F_{\mu_{g}^{\lambda}}(\tau)]=-\frac{\partial}{\partial\lambda}F_{\mu_{g}}\left(M(\tau,\lambda)\right)$
$\displaystyle=$
$\displaystyle-\frac{\partial}{\partial\lambda}\int_{-\infty}^{M(\tau,\lambda)}f_{\mu_{g}}(t)dt=-f_{\mu_{g}}(M(\tau,\lambda))\frac{\partial}{\partial\lambda}M(\tau,\lambda)$
$\displaystyle=$ $\displaystyle
f_{\mu_{g}}\left(M(\tau,\lambda)\right)\left(\frac{F_{\mu_{g^{\prime}}}(F^{-1}_{\mu_{g}}(x^{\prime}))-x^{\prime}}{(1-\lambda)^{2}}\right)$

To determine if this derivative is positive or negative, we look at the two
quantities being multiplied on the last line of the above derivation. If we
assume that $\operatorname{supp}\mu_{g}=[0,1]$ then $f_{\mu_{g}}(\cdot)>0$
because it is a PDF. Additionally, since the denominator is squared, it is
also always positive. This means the sign of the derivative is controlled by
the term $F_{\mu_{g^{\prime}}}(F^{-1}_{g}(x^{\prime}))-x^{\prime}$ or
equivalently
$F_{\mu_{g^{\prime}}}(F^{-1}_{\mu_{g}}(x^{\prime}))-F^{-1}_{\mu_{g}}(F_{\mu_{g}}(x^{\prime}))$.
If
$F_{\mu_{g^{\prime}}}(F^{-1}_{\mu_{g}}(x^{\prime}))-F^{-1}_{\mu_{g}}(F_{\mu_{g}}(x^{\prime}))>0$
then $F_{\mu_{g^{\prime}}}(F^{-1}_{\mu_{g}}(x^{\prime}))>x$ and the derivative
is positive, indicating that $\gamma^{y,c}_{g}$ is increasing. If the
inequality switches direction, then $\gamma^{y,c}_{g}$ is decreasing.

∎

Theorem 3.5 Define
$\delta_{\gamma_{g}}(\lambda):=\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda},\mu_{g^{\prime}}^{\lambda})$
or equivalently $\delta_{\gamma_{g}}(\lambda):=\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}|\gamma_{g}(\tau)-\gamma_{g^{\prime}}(\tau)|^{p}$ for all
$\lambda\in[0,1]$ and $\gamma_{g}\in\Gamma_{f_{\beta}^{\lambda}}$. Then
$\delta_{\gamma_{g}}(\lambda)$ is convex.

###### Proof.

Let $\lambda_{1}\in[0,1]$ and $1-\lambda_{1}=\lambda_{2}$. By the triangle
inequality we have that

$\displaystyle\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})\leq\mathcal{W}_{p}^{p}(\mu,\mu_{g}^{\lambda_{1}})+\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda_{1}},\mu_{g}^{\lambda_{2}})+\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda_{2}},\mu_{g^{\prime}})$

Since, $\mu_{g}^{\lambda_{1}},\mu_{g}^{\lambda_{2}}$ are all contained on the
geodesic between $\mu_{g},\mu_{g^{\prime}}$ we can obtain equality in the
above expression by the following substitution

$\displaystyle\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})=$
$\displaystyle\lambda_{1}\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})+(\lambda_{2}-\lambda_{1})\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})+(1-\lambda_{2})\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})$
$\displaystyle=$
$\displaystyle\mathcal{W}_{p}^{p}(\mu,\mu_{g}^{\lambda_{1}})+\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda_{1}},\mu_{g}^{\lambda_{2}})+\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda_{2}},\mu_{g^{\prime}})$

since $\lambda_{1}+(\lambda_{2}-\lambda_{1})+(1-\lambda_{2})=1$. Additionally,
since $\mu_{g}^{\lambda_{2}}$ lies on the geodesic between $\mu_{g}$ and
$\mu_{g^{\prime}}$, the following two terms are equivalent
$\mu_{g^{\prime}}^{\lambda_{1}}=\mu_{g}^{\lambda_{2}}$. Using this relation
and re-arranging terms we arrive at

$\displaystyle\mathcal{W}_{p}^{p}(\mu^{\lambda_{1}}_{g},\mu^{\lambda_{1}}_{g^{\prime}})=\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})-\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g}^{\lambda_{1}})-\mathcal{W}_{p}^{p}(\mu_{g^{\prime}}^{\lambda_{1}},\mu_{g^{\prime}})$

Through observing the following facts, we can conclude the proof. By lemma E.3
we know that $\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g}^{\lambda_{1}})$ and
$\mathcal{W}_{p}^{p}(\mu_{g^{\prime}}^{\lambda_{1}},\mu_{g^{\prime}})$ are
convex. The term $\mathcal{W}_{p}^{p}(\mu_{g},\mu_{g^{\prime}})$ does not
depend on $\lambda$ so we view it as a constant. These facts imply that
$\mathcal{W}_{p}^{p}(\mu^{\lambda_{1}}_{g},\mu^{\lambda_{1}}_{g^{\prime}})$ is
a linear combination of convex functions, which therefore must be also convex.
Noting that
$\delta_{\gamma_{g}}(\lambda)=\mathcal{W}_{p}^{p}(\mu_{g}^{\lambda},\mu_{g^{\prime}}^{\lambda})=\mathop{\mathbb{E}_{\tau\in
U(\Omega)}}|\gamma_{g}(\tau)-\gamma_{g^{\prime}}(\tau)|^{p}$ concludes the
proof. ∎

Corollary 3.3 A geometrically repaired regressor $f_{\beta}^{\lambda}$ can be
computed as the barycenter of $\mu_{g},\mu_{g^{\prime}}$ with weights
$(1-\lambda+\lambda p_{g})$ and $\lambda(1-p_{g})$

###### Proof.

A geometrically repaired regressor is of the form $f(x,g)+\lambda t(x,g)$. If
we substitute $t=f_{\beta}(x,g)-f(x,g)$ into the above expression we obtain

$\displaystyle f(x,g)+\lambda t(x,g)$ $\displaystyle=$ $\displaystyle
f(x,g)+\lambda(f_{\beta}(x,g)-f(x,g))$ $\displaystyle=$
$\displaystyle(1-\lambda)f(x,g)+\lambda f_{\beta}(x,g)$ $\displaystyle=$
$\displaystyle(1-\lambda)f(x,g)+\lambda(p_{g}f(x,g)+(1-p_{g})\alpha(x,g))$
$\displaystyle=$ $\displaystyle(1-\lambda+\lambda
p_{g})f(x,g)+\lambda(1-p_{g})\alpha(x,g)$

Which is identical to the original barycenter computation, but with weight
coefficients $(1-\lambda+\lambda p_{g})$ and $\lambda(1-p_{g})$. ∎

Theorem 5.3 For a convex and bounded choice in loss function
$L:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and convex hypothesis class
$\mathcal{H}$, Algorithm 3 will output a lexicographically fair solution.

###### Proof Sketch.

We proceed by induction. In the base case, we assume that we can compute
$\lambda_{1}$, which is minima from the first round of lexicographic
optimization i.e. the maxmin solution. This follows by supposition since both
the hypothesis class the loss function are bounded and convex. Assume by
induction, we can compute the $kth$ round of optimization

$\displaystyle\lambda_{k}\leftarrow\arg\min_{\lambda\in\mathbb{R}^{n}}L_{h(k)}(\vec{\lambda})\text{
subject to constraints }C(\epsilon_{1}...\epsilon_{k-1})$

optimally subject to the lexicographic constraint set $C_{k}(\cdot)$, and so
the resulting $\lambda_{k},\epsilon_{k})$ satisfies lexicographic fairness.
Given that both $\lambda_{k},\epsilon_{k}$ are lexicographic, then by imposing
additional constraints $C(\epsilon_{1}...\epsilon_{k-1})$ we are guaranteed
that the loss at round $k+1$ the solution will be at most as small as the loss
at the previous round, thereby satisfying the definition of lexicographic
fairness. ∎

Proposition 3.8 The $\lambda$ which yields the minimum rate difference is
given by

$\displaystyle\lambda=\frac{\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}}}[f(x,g^{\prime})|\bm{Y},\mathcal{G}=g^{\prime}]-\mathop{\mathbb{E}_{\mathcal{X}_{g}}}[f(x,g)|\bm{Y},\mathcal{G}=g]}{\mathop{\mathbb{E}_{\mathcal{X}_{g}}}[t(x,g)|\bm{Y},\mathcal{G}=g]-\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}}}[t(x,g^{\prime})|\bm{Y},\mathcal{G}=g^{\prime}]}$

###### Proof.

Suppose there is some value $\lambda\in[0,1]$ such that the probabilistic
equal opportunity difference between groups is equal

$\displaystyle\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y=1}}[f^{\lambda}_{\beta}(x,g)]=\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}|Y=1}}[f^{\lambda}_{\beta}(x,g^{\prime})]$

We can use the formula for geometric repair to solve for this $\lambda$.
Recall $f^{\lambda}_{\beta}(x,g)=f(x,g)+\lambda t(x,g)$

$\displaystyle\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[f(x,g)+\lambda
t(x,g)]=\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}|Y}}[f(x,s^{\prime})+\lambda
t(x,s^{\prime})]$
$\displaystyle\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[f(x,g)]+\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[\lambda
t(x,g)]=\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}|Y}}[f(x,g^{\prime})]+\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[\lambda
t(x,g^{\prime})]$
$\displaystyle\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[f(x,g)]+\lambda\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[t(x,g)]=\mathop{\mathbb{E}_{\mathcal{X}_{g^{\prime}}|Y}}[f(x,g^{\prime})]+\lambda\mathop{\mathbb{E}_{\mathcal{X}_{g}|Y}}[t(x,g^{\prime})]$

where solving for $\lambda$ yields the proposition. ∎