# Fairness in Risk Assessment Instruments: Post-Processing to Achieve
Counterfactual Equalized Odds

Alan Mishler  Department of Statistics
Carnegie Mellon University 0000-0002-7654-208X ,  Edward H. Kennedy
Department of Statistics
Carnegie Mellon University and  Alexandra Chouldechova  Heinz College
Carnegie Mellon University

(2021)

###### Abstract.

In domains such as criminal justice, medicine, and social welfare, decision
makers increasingly have access to algorithmic Risk Assessment Instruments
(RAIs). RAIs estimate the risk of an adverse outcome such as recidivism or
child neglect, potentially informing high-stakes decisions such as whether to
release a defendant on bail or initiate a child welfare investigation. It is
important to ensure that RAIs are fair, so that the benefits and harms of such
decisions are equitably distributed.

The most widely used algorithmic fairness criteria are formulated with respect
to observable outcomes, such as whether a person actually recidivates, but
these criteria are misleading when applied to RAIs. Since RAIs are intended to
inform interventions that can reduce risk, the prediction itself affects the
downstream outcome. Recent work has argued that fairness criteria for RAIs
should instead utilize potential outcomes, i.e. the outcomes that _would_
occur in the absence of an appropriate intervention (Coston et al., 2020).
However, no methods currently exist to satisfy such fairness criteria.

In this paper, we target one such criterion, _counterfactual equalized odds_.
We develop a post-processed predictor that is estimated via doubly robust
estimators, extending and adapting previous post-processing approaches (Hardt
et al., 2016) to the counterfactual setting. We also provide doubly robust
estimators of the risk and fairness properties of arbitrary fixed post-
processed predictors. Our predictor converges to an optimal fair predictor at
fast rates. We illustrate properties of our method and show that it performs
well on both simulated and real data.

_Note: This is an extended version of the paper published in the FAccT ’21
proceedings, with some additional theorems, proofs, and simulation results._

fairness, risk assessment, post-processing, counterfactual

††journalyear: 2021††copyright: rightsretained††conference: Conference on
Fairness, Accountability, and Transparency; March 3–10, 2021; Virtual Event,
Canada††booktitle: Conference on Fairness, Accountability, and Transparency
(FAccT ’21), March 3–10, 2021, Virtual Event, Canada††doi:
10.1145/3442188.3445902††isbn: 978-1-4503-8309-7/21/03††ccs: Computing
methodologies Machine learning

##  1\. Introduction

Machine learning is increasingly involved in high stakes decisions in domains
such as healthcare, criminal justice, and consumer finance. In these settings,
ML models often take the form of Risk Assessment Instruments (RAIs): given
covariates such as demographic information and an individual’s
medical/criminal/financial history, the model predicts the likelihood of an
adverse outcome, such as a dangerous medical event, recidivism, or default on
a loan. Rather than rendering an automatic decision, the model produces a
“risk score,” which a decision maker may take into account when deciding
whether to prescribe a medical treatment, release a defendant on bail, or
issue a personal loan.

The proliferation of machine learning has raised concerns that learned models
may be discriminatory with respect to sensitive features like race, sex, age,
and socioeconomic status. For example, there has been vigorous debate about
whether a widely used recidivism prediction tool called COMPAS is biased
against black defendants (Angwin et al., 2016; Angwin and Larson, 2016;
Dieterich et al., 2016; Larson and Angwin, 2016; Lowenkamp et al., 2016).
Concerns have also been raised about risk assessments used to identify high
risk medical patients (Obermeyer et al., 2019) and about common credit scoring
algorithms such as FICO (Rice and Swesnik, 2012), among many others.
Collectively, these types of algorithms directly impact a large and growing
swath of the global population.

These concerns have led to an explosion of methods in recent years for
developing fair models and auditing the fairness of existing models. The most
widely discussed fairness criteria impose constraints on the joint
distribution of a sensitive feature, an outcome, and a predictor. These
“observational” fairness criteria are inappropriate for RAIs, however. RAIs
are not concerned with the _observable outcomes_ in the training data (“Did
patients of this type historically experience serious complications?”), which
are themselves a product of historical treatment decisions. Rather, they are
concerned with the _potential outcomes_ associated with available treatment
decisions (“ _Would_ patients of this type experience complications _if not
treated?_ ”). Because treatments are not assigned at random—doctors naturally
treat the patients they think are at high risk—these are distinct questions.

Coston et al. (2020) showed how RAIs that are optimized to predict observable
rather than potential outcomes systematically underestimate risk for units
that have historically been receptive to treatment, leading to suboptimal
treatment decisions. They further showed how evaluations of the performance
and fairness properties of RAIs with respect to observable outcomes are
misleading. They proposed that RAIs should instead target counterfactual
versions of standard performance and fairness metrics. However, they left open
the question of how to develop predictors that satisfy such fairness notions.

In this paper, we develop a method to generate predictors that satisfy the
fairness criterion _approximate counterfactual equalized odds_. While many
existing methods target observational fairness criteria (Kamiran and Calders,
2012; Hardt et al., 2016; Calmon et al., 2017; Zafar et al., 2017; Donini et
al., 2018; Narasimhan, 2018; Kim et al., 2019) and various types of causally
motivated fairness (Kilbertus et al., 2017; Kusner et al., 2017; Nabi and
Shpitser, 2018; Nabi et al., 2019), no methods currently exist that target
counterfactual versions of standard observable fairness criteria like
equalized odds. Our method post-processes an arbitrary existing predictor,
extending previous post-processing methods (Hardt et al., 2016) to the
counterfactual setting.

Our contributions are as follows. We first define approximate counterfactual
equalized odds (§2). After discussing related work (§3) and motivating the use
of equalized odds over other candidate criteria (§4), we present a linear
program that produces a loss-optimal post-processed predictor that satisfies
this criterion (§5). We provide theoretical results that our post-processed
predictor is consistent in a particular sense at rates that depend on certain
nuisance parameters. We show that our method performs well on both simulated
and real data (§6).

##  2\. Notation and fairness definitions

A table listing all notational choices can be found in Appendix F.

Let $A,D,Y$ denote a sensitive feature, decision, and outcome, respectively.
We consider the setting in which all three are binary, though most of the
definitions below extend readily to continuous settings. We define the
counterfactual quantities of interest via the potential outcomes framework of
(Neyman, 1923; Holland, 1986; Rubin, 2005). Denote by $Y^{0},Y^{1}$ the
potential (equivalently, “counterfactual”) outcomes $Y^{D=0},Y^{D=1}$.
$Y_{i}^{d}$ is the outcome that would be observed for unit $i$ if, possibly
contrary to fact, the decision were set to $D_{i}=d$. We refer to the two
levels of the sensitive feature $A$ as the two “groups,” and we use
“treatment” and “intervention” synonymously with “decision.” Let $S$ be any
random variable that takes values in $\\{0,1\\}$.

In most RAI settings, one of the decision options is a natural baseline
corresponding to “no intervention” $(D=0)$. Examples include the risk of
recidivism if a defendant is released pretrial, or the risk of neglect or
abuse if a child welfare call is not screened in for further investigation.
Many or most RAIs do not generate a separate risk score for the outcome
associated with intervention. In the case of child welfare, for example, call
screeners must screen in any case in which a child is in apparent danger of
neglect or abuse, regardless of the chances that a subsequent intervention
will successfully prevent that neglect or abuse.

Denote the observational and counterfactual false positive rates of $S$ for
group $a$ by $\operatorname{FPR}(S,a)=\mathbb{P}(S=1\mid Y=0,A=a)$ and
$\operatorname{cFPR}(S,a)=\mathbb{P}(S=1\mid Y^{0}=0,A=a)$. For example,
$\operatorname{cFPR}(S,0)$ could represent the chance of being falsely labeled
high-risk, among those black defendants who would not actually go on to
recidivate if released pretrial, while $\operatorname{cFPR}(S,1)$ could
represent the corresponding error rate for white defendants who would not
recidivate if released pretrial. Let $\operatorname{FNR}$,
$\operatorname{cFNR}$, $\operatorname{TPR}$, and $\operatorname{cTPR}$ denote
the corresponding observational and counterfactual false negative and true
positive rates.

###### Definition 2.0.

A predictor $S$ satisfies _observational equalized odds_ (oEO) with respect to
$A$ and $Y$ if $S\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y$. It satisfies _counterfactual
equalized odds_ (cEO) if $S\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y^{0}$.

When $A$, $Y$, and $S$ are all binary, equalized odds is equivalent to
requiring that the corresponding false positive and false negative rates be
equal for the two levels of $A$. Our post-processed predictor will target a
relaxation of this criterion, defined below.

###### Definition 2.0.

The _counterfactual error rate differences_ for a predictor $S$ are the
differences $\Delta^{\scriptscriptstyle+}$ and $\Delta^{\scriptscriptstyle-}$
in the $\operatorname{cFPR}$ and $\operatorname{cFNR}$ for the two groups
$A=0,A=1$, defined as follows:

$\displaystyle\Delta^{\scriptscriptstyle+}(S)$
$\displaystyle=\operatorname{cFPR}(S,0)-\operatorname{cFPR}(S,1)$
$\displaystyle\Delta^{\scriptscriptstyle-}(S)$
$\displaystyle=\operatorname{cFNR}(S,0)-\operatorname{cFNR}(S,1)$

###### Definition 2.0.

When $A,Y$, and $S$ are all binary, $S$ satisfies _approximate counterfactual
equalized odds_ with _fairness constraints_
$\epsilon^{\scriptscriptstyle+},\epsilon^{\scriptscriptstyle-}\in[0,1]$ if

$\displaystyle\left|\Delta^{\scriptscriptstyle+}(S)\right|$
$\displaystyle\leq\epsilon^{\scriptscriptstyle+}$
$\displaystyle\left|\Delta^{\scriptscriptstyle-}(S)\right|$
$\displaystyle\leq\epsilon^{\scriptscriptstyle-}$

In general, a fairness-constrained predictor would not outperform an optimal
unconstrained predictor, and in some cases, satisfying cEO exactly might
degrade performance to the point that the RAI is no longer useful. This
relaxation of cEO allows RAI designers to negotiate this tradeoff. This is
similar in spirit to notions of approximate fairness that appear throughout
the literature (Kearns et al., 2017; Donini et al., 2018; Menon and
Williamson, 2018).

##  3\. Related work

###  3.1. Observational and counterfactual fairness

Equalized odds is one of several popular fairness criteria that impose
constraints on the joint distribution of $(A,Y,S)$ (Barocas et al., 2018).
These criteria appear under a variety of names. Equalized odds is known more
generally as _separation_ , a term which covers settings in which these
variables are not necessarily binary. The other two popular criteria in this
class are _independence_ $(S\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A)$ and _sufficiency_
$(Y\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid S)$. Independence also manifests as
_demographic parity_ , _statistical parity_ , and _group fairness_.
Sufficiency is equivalent to _calibration_ or _predictive parity_ when all
three variables are binary. Variants of all three criteria may be defined for
example by conditioning on additional variables.

The counterfactual versions of these criteria simply replace $Y$ with the
potential outcome $Y^{0}$ that is of interest (Coston et al., 2020). Note that
these definitions cannot accommodate more than one potential outcome, such as
the vector $(Y^{0},Y^{1})$, because only one of these outcomes is observed for
each unit. This is the “fundamental problem of causal inference” (Holland,
1986).

Except in highly constrained, unrealistic conditions, these three criteria are
pairwise unsatisfiable, regardless of whether they are defined with respect to
$Y$ or $Y^{0}$ (Kleinberg et al., 2017; Chouldechova, 2017; Barocas et al.,
2018)111See (Imai and Jiang, 2020) for a set of sufficient conditions under
which these unsatisfiability results disappear.. We must therefore choose and
justify which criterion we wish to target.

###  3.2. Other causal fairness criteria

The counterfactual fairness criteria just described consider potential
outcomes with respect to a decision $D$. There is a distinct set of causally
motivated fairness criteria that consider counterfactuals of the sensitive
feature, or a proxy for the sensitive feature. They characterize a decision or
prediction as fair if the sensitive feature or proxy does not “cause” the
decision or prediction, either directly or along a prohibited pathway
(Kilbertus et al., 2017; Kusner et al., 2017; Nabi and Shpitser, 2018; Zhang
and Bareinboim, 2018; Nabi et al., 2019; Wang et al., 2019). There is some
controversy over whether it is meaningful to discuss a counterfactual of a
feature like race or gender (VanderWeele and Robinson, 2014; Glymour and
Glymour, 2014; Hu and Kohler-Hausmann, 2020). Additionally, satisfying these
metrics typically precludes use of most of the features that go into risk
assessment, like prior history, which is not tenable in practice (Coston et
al., 2020). Finally, it is not clear that counterfactuals of the sensitive
feature are useful or appropriate to consider in the context of risk
assessment. For example, in the child welfare setting, workers are compelled
to screen in calls whenever a child is in danger of neglect or abuse. While it
is important to ensure that risk is assessed accurately for different groups,
it would be inappropriate to make screen-in decisions based on what a child’s
risk of neglect or abuse would be _if they had been of a different race_ their
whole life, even if such an assessment were possible.

###  3.3. Ways of achieving fairness

There are three broad approaches to developing fair models: (1) preprocessing
the input data to remove bias (Kamiran and Calders, 2012; Calmon et al.,
2017), (2) constraining the learning process (aka “in-processing”) (Zafar et
al., 2017; Donini et al., 2018; Narasimhan, 2018), and (3) post-processing a
model to satisfy fairness constraints (Hardt et al., 2016; Kim et al., 2019).

Our approach belongs to class (3). We refer to the predictor that our method
returns equivalently as a “post-processed” or “derived” predictor. Each
approach has advantages and disadvantages. Many widely used RAIs are
proprietary tools developed by for-profit companies, so they are not amenable
to internal tinkering. Developing new, fair(er) RAIs would be costly and
perhaps infeasible from a policy perspective. The advantage of post-processing
in this setting is that it can be applied to models that are already in use.
The predictor that our method returns requires access at runtime only to the
sensitive feature and the output of the existing predictor, so in principle,
it could easily be incorporated into existing risk assessment pipelines.

In particular, our approach extends the work of Hardt et al. (2016), who
proposed a method to post-process binary predictors to satisfy observational
equalized odds (oEO) while minimizing loss with respect to observable $Y$.
Their post-processed predictor is the solution to a simple linear program. We
adapt their method to the counterfactual setting, in which the fairness
criterion is approximate cEO and the loss function is weighted classification
error with respect to $Y^{0}$. Because $Y^{0}$ is not observable when $D\neq
0$, we require tools from causal inference to solve this problem. Hardt et
al.’s analysis treats the joint distribution of $(A,S,Y)$ as known and frames
post-processing primarily as an optimization problem. We build on their
results by not making this assumption and treating post-processing as a
statistical estimation problem.

###  3.4. Why equalized odds?

When evaluating a predictive system, it seems natural to focus on its real-
world impact rather than its outputs per se. One desirable property of a
decision process is the avoidance of disparate impact. Disparate impact is a
legal doctrine enshrined in U.S. law that prohibits practices which have an
unjustifiable adverse impact on people who share a protected characteristic,
regardless of discriminatory intent. By way of shorthand, we will say that if
$D\not\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y^{0}$, then the system exhibits
discriminatory disparate impact222Some authors use “disparate impact” to refer
to the criterion $S\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A$, i.e. _independence_ (Zafar et al., 2017)..
In recidivism prediction, for example, this could mean that black defendants
$(A=0)$ who would not recidivate if released $(Y^{0}=0)$ are more likely to be
detained pretrial $(D=1)$ than white defendants who would not recidivate if
released $(A=1,Y^{0}=0)$.

In the context of RAIs, decision makers typically have wide latitude in how
they interpret and act on the risk scores, so constraining the RAI does not
enforce fairness with respect to their decisions. However, if decision makers,
after the introduction of the RAI, make their decisions only on the basis of
the RAI scores and other variables $U$ which are independent of the RAI and
$A$ given $Y^{0}$, then counterfactual equalized odds will imply
$D\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y^{0}$. That is, let $D=f(S,U)$
represent the function $f$ describing the decision process after the RAI $S$
is introduced. If cEO is satisfied and $U\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}(S,A)\mid Y^{0}$, then it follows that
$D\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y^{0}$. Even if
$U\not\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}(S,A)\mid Y^{0}$, it is easy to see that if
the conditional independence statement _nearly_ holds, or if $f$ depends
primarily on $S$ rather than $U$, then discriminatory disparate impact can be
small.

No such guarantees hold for predictors satisfying either independence or
sufficiency. Chouldechova (2017) in particular showed how predictors which
satisfy sufficiency (predictive parity) are likely to yield decisions such
that $D\not\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y$; these arguments are unchanged when
we substitute $Y^{0}$ for $Y$. Though there is no consensus about how to
quantify fairness, this is at least one consideration in favor of equalized
odds.

##  4\. Motivating Example

Having motivated equalized odds over predictive parity or independence, we now
motivate the use of counterfactual rather than observational equalized odds.

Consider a school district that assigns tutors to students who are believed to
be at risk of academic failure. The school district wishes to develop a RAI,
$S$, to better identify students who need tutors while ensuring that this
resource is allocated fairly across two levels of the sensitive feature $A$.
Let $D\in\\{0,1\\}$ represent the decision to assign (1) or not assign (0) a
tutor, and let $Y\in\\{0,1\\}$ represent academic success (0) or failure (1).

A cEO predictor $S$ satisfies $\mathbb{P}(S\mid Y^{0},A)=\mathbb{P}(S\mid
Y^{0})$, while an oEO predictor $S$ satisfies $\mathbb{P}(S\mid
Y,A)=\mathbb{P}(S\mid Y)$. Divergence in these predictors is driven by the
extent to which $Y\neq Y^{0}$ in the training data. In order to parameterize
this divergence, we introduce the following definitions.

###### Definition 4.0.

The _need rate_ for group $a$ is $\mathbb{P}(Y^{0}=1\mid A=a)$, the
probability that a student from group $a$ would fail without a tutor.

###### Definition 4.0.

The _opportunity rate_ for group $a$ is $\mathbb{P}(D=1\mid Y^{0}=1,A=a)$, the
probability that a student in group $a$ who needs a tutor receives one.

###### Definition 4.0.

The _intervention strength_ for group $a$ is $\mathbb{P}(Y^{1}=0\mid
Y^{0}=1,A=a)$, the probability that a student in group $a$ who would fail
without a tutor would succeed with a tutor.

We simulate a simple data generating process in which we allow the
intervention strength to vary, while constraining it to be equal for the two
groups. We fix all other parts of the distribution. In particular, we set
$\mathbb{P}(A=1)=0.7$, set the need rates to $0.4$ and $0.2$ for groups 0 and
1, and set the opportunity rates to $0.6$ and $0.4$. We set the probabilities
that a tutor is assigned when it is not needed to $\mathbb{P}(D=1\mid
Y^{0}=0,A=0)=0.3$ and $\mathbb{P}(D=1\mid Y^{0}=0,A=1)=0.2$. This represents a
scenario in which the minority group has greater need, perhaps due to
socioeconomic factors or prior educational opportunities, and also is likelier
than the majority group to receive resources at baseline (prior to the
development of the RAI). Finally, we set $\mathbb{P}(Y^{1}=0\mid Y^{0}=0)=1$,
meaning that tutoring never _increases_ the risk of failure.

We consider a hypothetical oEO predictor $S$ with fixed false positive rate
$\mathbb{P}(S=1\mid Y=0,A)=\mathbb{P}(S=1\mid Y=0)=0.1$ and false negative
rate $\mathbb{P}(S=0\mid Y=1,A)=\mathbb{P}(S=0\mid Y)=0.2$. We assume
$S\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y^{0}\mid A,Y$, as would be the case for
example when $S$ is a high quality predictor of $Y$. Figure 1 shows the cTPRs
(counterfactual true positive rates) for this predictor as a function of
intervention strength, relative to the baseline opportunity rates for the two
groups. When the intervention has no effect (strength 0), the cTPRs are equal
because $Y\equiv Y^{0}$, so the cTPR and TPR are identical. (Of course, a
strength of 0 means the tutoring is worthless.) For all strength values $>0$,
the cTPR of the minority group is lower than for the majority group. The
difference in error rates increases as intervention strength increases. A cEO
predictor avoids this problem by design: the cTPRs for the two groups are
constrained to be equal.

This example makes it clear that oEO predictors in general will not prevent
discriminatory disparate impact, whereas, as discussed in section 3.4,
counterfactual EO predictors have at least the potential to mitigate or avoid
it.

This example also illustrates how oEO predictors can reduce rates of
appropriate intervention. For example, suppose that decision makers, after the
introduction of the RAI, set $D\equiv S$, i.e. they assign tutors precisely to
students whom the RAI labels as high risk. Then, for any intervention strength
$>0.5$, the opportunity rate for the minority group decreases below baseline:
the RAI _harms the minority group_.

##  5\. An optimal fair derived predictor

Figure 1. Counterfactual true positive rates (cTPRs; solid lines) for a RAI
satisfying observational equalized odds (oEO), as a function of the
intervention strength $\mathbb{P}(Y^{1}=0\mid Y^{0}=1)$. Dashed lines indicate
opportunity rates $\mathbb{P}(D=1\mid Y^{0}=0)$ prior to the development of
the RAI. The more effective the tutoring (the higher the intervention
strength), the worse the RAI is at identifying students who need it, and the
greater the disparity in its performance between the minority and the majority
group. When tutoring is more effective, the RAI may reduce the appropriate
assignment of tutors below the baseline opportunity rates.

Having motivated counterfactual equalized odds, we now develop a method to
generate predictors which satisfy it.

###  5.1. Estimand

We expand our notation in order to fully describe our problem setting.
Consider a random vector $Z=(A,X,D,S,Y)\sim\mathbb{P}$, where in addition to
the binary sensitive feature $A$, decision $D$, and outcome $Y$, we have
covariates $X\in\mathbb{R}^{p}$ and a previously trained binary predictor
$S\in\\{0,1\\}$. We require only that $S$ is observable; we do not require
access to its inputs or internal structure. $S$ in practice could represent a
RAI that is already in use, such as a recidivism prediction tool. The
covariates $X$ may or may not overlap with the inputs to $S$. Their role in
the analysis is to render counterfactual quantities identifiable.

Our target is a derived predictor that satisfies approximate cEO. As in the
case of observable equalized odds considered by Hardt et al. (2016), we
achieve this by randomly flipping $S$ with probabilities that depend only on
$S$ and $A$. Consider a column vector
$\theta=(\theta_{0,0},\theta_{0,1},\theta_{1,0},\theta_{1,1})\in[0,1]^{4}$. We
define an associated derived predictor $S_{\theta}$:

$\displaystyle S_{\theta}\sim\operatorname{Bern}(\theta_{A,S})$
$\displaystyle\text{where
}\theta_{A,S}=\sum_{a,s\in\\{0,1\\}}\mathbbold{1}\\{A=a,S=s\\}\theta_{a,s}$

In other words, the $\theta_{a,0}$ parameters represent conditional
probabilities that $S$ flips, while the $\theta_{a,1}$ parameters represent
conditional probabilities that $S$ doesn’t flip. Notice that for
$\mathbf{\tilde{\theta}}=(0,1,0,1)$, we have $S_{\mathbf{\tilde{\theta}}}=S$:
the derived predictor is equal to the input predictor.

Our target is a loss-optimal fair predictor $S_{\theta^{*}}$, where the
fairness criterion is approximate cEO. The loss function we consider is
weighted classification error. For fixed $\theta$, denote the loss333We refer
to this quantity as “loss” instead of the conventional “risk” in order to
avoid confusion between risk assessment and the error rate of a predictor. by
$\mathcal{L}(S_{\theta};w^{+},w^{-})=w^{+}\mathbb{P}(Y^{0}=0,S_{\theta}=1)+w^{-}\mathbb{P}(Y^{0}=1,S_{\theta}=0)$,
where $w^{+},w^{-}$ are chosen by the user to capture the relative importance
of false positives and false negatives. (We will generally suppress the
dependence of $\mathcal{L}$ on $w^{+},w^{-}$.) The estimand is

$\displaystyle\theta^{*}\in\operatorname*{arg\,min}_{\theta}$
$\displaystyle\\-\ \mathcal{L}(S_{\theta})$ subject to $\displaystyle\\-\
\theta\in[0,1]^{4}$ $\displaystyle\\-\
\left|\Delta^{\scriptscriptstyle+}(S_{\theta})\right|\leq\epsilon^{\scriptscriptstyle+}$
$\displaystyle\\-\
\left|\Delta^{\scriptscriptstyle-}(S_{\theta})\right|\leq\epsilon^{\scriptscriptstyle-}$

where $\Delta^{\scriptscriptstyle+},\Delta^{\scriptscriptstyle-}$ are given
above in Definition 2, and the fairness constraints
$\epsilon^{\scriptscriptstyle+},\epsilon^{\scriptscriptstyle-}\in[0,1]$ are
chosen by the user. Setting both these constraint parameters to 0 requires cEO
to be satisfied exactly, while setting them to 1 allows $S_{\theta^{*}}$ to be
arbitrarily unfair. Setting $\epsilon^{\scriptscriptstyle-}$ to 0 regardless
of $\epsilon^{\scriptscriptstyle+}$ forces $S_{\theta^{*}}$ to satisfy
_counterfactual equal opportunity_ ; see Hardt et al. (2016) for the
observational definition of this criterion.

###### Remark 1.

The full vector $Z$ is required only to estimate the parameter
$\mathbf{\theta}^{*}$ that defines the optimal fair derived predictor. Once
$\mathbf{\theta}^{*}$ has been estimated, the resulting derived predictor
requires access at runtime only to the sensitive feature $A$ and the input
predictor $S$.

Since our estimands involve counterfactual quantities, distributional
assumptions are required in order to equate them to observable quantities.

###  5.2. Identification

In this subsection we show that the counterfactual error rates and loss can be
identified under standard causal inference assumptions. All the quantities to
be identified can be written in terms of the loss and the counterfactual error
rates of the input predictor $S$. For ease of notation, we first define two
nuisance parameters that appear in the estimand and associated estimators,
namely the outcome regression and propensity score function. We generally
suppress the arguments of these functions in subsequent usage for the sake of
conciseness.

$\displaystyle\mu_{0}(A,X,S)$ $\displaystyle=\mathbb{E}[Y\mid A,X,S,D=0]$
$\displaystyle\pi(A,X,S)$ $\displaystyle=\mathbb{P}(D=1\mid A,X,S)$

We make the following standard “no unmeasured confounding”-type causal
inference assumptions:

A1. (Consistency) $\displaystyle Y=DY^{1}+(1-D)Y^{0}$ A2. (Positivity)
$\displaystyle\exists\delta\in(0,1)\text{ s.t. }\mathbb{P}(\pi(A,X,S)\leq
1-\delta)=1$ A3. (Ignorability) $\displaystyle Y^{0}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}D\mid A,X,S$

The consistency assumption means that the outcome observed for each individual
is precisely the potential outcome corresponding to the treatment received.
This implies that one person’s treatment assignment does not affect another
person’s outcomes, meaning, for example, that an individual’s recidivism
behavior does not depend on whether other individuals are detained or
released. The positivity or _overlap_ assumption requires that within strata
of $(A,X,S)$ of measure $>0$, individuals have some chance of receiving no
intervention. Finally, the ignorability or _no unmeasured confounding_
assumption requires that within strata of $(A,X,S)$, the treatment $D$ is
essentially random with respect to $Y^{0}$. Satisfying ignorability
assumptions typically requires collecting a rich enough set of deconfounding
covariates. In the present case, even if $X$ is low dimensional, the
ignorability assumption is plausible if the input predictor $S$ substantially
drives decision making, or if it happens to be an accurate (if not necessarily
fair) predictor of $Y^{0}$.

Before giving the identifying expressions for $\mathcal{L}(S_{\theta})$ and
the error rate differences
$\Delta^{\scriptscriptstyle+},\Delta^{\scriptscriptstyle-}$, we give
identifying expressions for the error rates of the input predictor $S$, which
themselves appear in the expressions for
$\Delta^{\scriptscriptstyle+},\Delta^{\scriptscriptstyle-}$.

###### Proposition 0.

Under assumptions A1-A3, the counterfactual error rates of the input predictor
$S$ are identified as follows:

$\displaystyle\operatorname{cFPR}(S,a)$
$\displaystyle=\frac{\mathbb{E}[S(1-\mu_{0})\mathbbold{1}\\{A=a\\}]}{\mathbb{E}[(1-\mu_{0})\mathbbold{1}\\{A=a\\}]}$
$\displaystyle\operatorname{cFNR}(S,a)$
$\displaystyle=\frac{\mathbb{E}[(1-S)\mu_{0}\mathbbold{1}\\{A=a\\}]}{\mathbb{E}[\mu_{0}\mathbbold{1}\\{A=a\\}]}$

Proofs of propositions are given in Appendix A. We now define several
quantities that appear in the identifying expressions for
$\mathcal{L}(S_{\theta}),\Delta^{\scriptscriptstyle+}$, and
$\Delta^{\scriptscriptstyle-}$:

$\displaystyle\beta_{a,s}=\mathbb{E}\left[\mathbbold{1}\\{A=a,S=s\\}\left(w^{+}-(w^{+}+w^{-})\mu_{0}\right)\right],\text{
for }a,s\in\\{0,1\\}$
$\displaystyle\beta=(\beta_{0,0},\beta_{0,1},\beta_{1,0},\beta_{1,1})$
$\displaystyle\beta^{\scriptscriptstyle+}=\left(1-\operatorname{cFPR}(S,0),\\-\
\operatorname{cFPR}(S,0),\\-\ \operatorname{cFPR}(S,1)-1,\\-\
-\operatorname{cFPR}(S,1)\right)$
$\displaystyle\beta^{\scriptscriptstyle-}=\left(-\operatorname{cFNR}(S,0),\\-\
\operatorname{cFNR}(S,0)-1,\\-\ \operatorname{cFNR}(S,1),\\-\
1-\operatorname{cFNR}(S,1)\right)$

###### Proposition 0.

Under assumptions A1-A3, the loss and error rates of the derived predictor
$S_{\theta}$ are identified as:

$\displaystyle\mathcal{L}(S_{\theta})$
$\displaystyle=\theta^{T}\beta+w^{-}\mathbb{E}[\mu_{0}]$
$\displaystyle\Delta^{\scriptscriptstyle+}(S_{\theta})$
$\displaystyle=\theta^{T}\beta^{\scriptscriptstyle+}$
$\displaystyle\Delta^{\scriptscriptstyle-}(S_{\theta})$
$\displaystyle=\theta^{T}\beta^{\scriptscriptstyle-}$

Since the term $w^{-}\mathbb{E}[\mu_{0}]$ in the loss is fixed, we can drop it
without changing the minimizer of the loss. We can therefore rewrite the
estimand as

(1)
$\displaystyle\begin{split}\theta^{*}\in\operatorname*{arg\,min}_{\theta}&\quad\theta^{T}\beta\\\
\text{subject to }&\theta\in[0,1]^{4}\\\
&|\theta^{T}\beta^{\scriptscriptstyle+}|\leq\epsilon^{\scriptscriptstyle+}\\\
&|\theta^{T}\beta^{\scriptscriptstyle-}|\leq\epsilon^{\scriptscriptstyle-}\end{split}$

In other words, the optimal fair derived predictor is the solution to a linear
program (LP). We refer to this as the “true LP” since it defines the estimand.
We now define an estimator $\widehat{\theta}$ as the solution to an “estimated
LP.”

###  5.3. Estimation

An estimator for $\mathbf{\theta}^{*}$ is derived by computing estimates
$\widehat{\beta},\widehat{\beta}^{\scriptscriptstyle+},\widehat{\beta}^{\scriptscriptstyle-}$
of the true LP coefficients and then solving the resulting estimated LP:

$\displaystyle\begin{split}\widehat{\theta}\in\operatorname*{arg\,min}_{\theta}&\quad\theta^{T}\widehat{\beta}\\\
\text{ subject to }&\quad\theta\in[0,1]^{4}\\\
&\quad|\theta^{T}\widehat{\beta}^{\scriptscriptstyle+}|\leq\epsilon^{\scriptscriptstyle+}\\\
&\quad|\theta^{T}\widehat{\beta}^{\scriptscriptstyle-}|\leq\epsilon^{\scriptscriptstyle-}\end{split}$

Any solution $\widehat{\theta}$ suffices. How should
$\beta,\beta^{\scriptscriptstyle+},\beta^{\scriptscriptstyle-}$ be estimated?
Before proposing a specific set of estimators, we first show that
$S_{\widehat{\theta}}$ approaches optimal behavior at rates that depend on the
performance of these estimators444We ignore optimization error, since this is
a function of the number of optimization iterations and can be made
arbitrarily small (Boyd and Vandenberghe, 2004).. We define two quantities of
interest: the _loss gap_ and the _excess unfairness_ , and give accompanying
theorems. Proofs of all theorems are given in Appendix B.

Following standard usage, we say that an estimator $\widehat{\psi}$ of a
parameter $\psi$ is consistent at rate $f(n)$ for some real-valued function
$f(n)$ if $\|\widehat{\psi}-\psi\|=O_{\mathbb{P}}(1/f(n))$ for a suitable norm
$\|\cdot\|$. For example, if $f(n)=\sqrt{n}$, then we say $\widehat{\psi}$
converges at $\sqrt{n}$ rates. We say that an estimator converges _faster_
than $f(n)$ if $\|\widehat{\psi}-\psi\|=o_{\mathbb{P}}(1/f(n))$. When
$\psi\in\mathbb{R}^{k}$ for some $k$, the norm we are interested in is the
Euclidean norm defined by $\|\psi\|^{2}=\psi^{T}\psi$. When $\psi$ is a
function of the random variable $Z$, the relevant norm is the $L_{2}$ norm
with respect to $\mathbb{P}$, i.e.,
$\|\psi\|^{2}=\int\psi(z)^{2}d\mathbb{P}(z)$. For a random vector
$\psi=(\psi_{1},\ldots,\psi_{k})$ taking values in $\mathbb{R}^{k}$, the norm
is given by $\|\psi\|^{2}=\sum_{j=1}^{k}\int\psi_{j}(z)^{2}d\mathbb{P}(z)$.

###### Definition 5.0.

The _loss gap_ is
$\mathcal{L}(S_{\widehat{\theta}})-\mathcal{L}(S_{\theta^{*}})$, the
difference in loss between the derived predictor and the optimal derived
predictor.

We use the term _loss gap_ rather than _excess loss_ to acknowledge that the
loss of $S_{\widehat{\theta}}$ can be less than the loss of $S_{\theta^{*}}$,
if $\widehat{\theta}$ falls outside the true constraints. Of course, this can
only occur if $S_{\widehat{\theta}}$ violates the true fairness constraints,
which can happen because the constraints are estimated.

###### Theorem 4 (Loss gap).

Suppose that $\widehat{\beta},\widehat{\beta}^{\scriptscriptstyle+}$, and
$\widehat{\beta}^{\scriptscriptstyle-}$ are all consistent at rate $f(n)$.
Under Assumptions A1-A3:

$\displaystyle\mathcal{L}(S_{\widehat{\theta}})-\mathcal{L}(S_{\theta^{*}})=O_{\mathbb{P}}(1/f(n))$

###### Definition 5.0.

The _excess unfairness of $S_{\widehat{\theta}}$ in the $\operatorname{cFPR}$_
is

$\displaystyle\operatorname{UF}^{\scriptscriptstyle+}(S_{\theta}):=\max\\{|\operatorname{cFPR}(S_{\widehat{\theta}},0)-\operatorname{cFPR}(S_{\widehat{\theta}},1)|-\epsilon^{\scriptscriptstyle+},0\\},$

and the _excess unfairness of $S_{\widehat{\theta}}$ in the
$\operatorname{cFNR}$_ is

$\displaystyle\operatorname{UF}^{\scriptscriptstyle-}(S_{\theta}):=\max\\{|\operatorname{cFNR}(S_{\widehat{\theta}},0)-\operatorname{cFNR}(S_{\widehat{\theta}},1)|-\epsilon^{\scriptscriptstyle-},0\\}$

Since the estimated constraints should fluctuate around the true constraints,
it’s possible for $S_{\widehat{\theta}}$ to have error rate differences that
are smaller than
$\epsilon^{\scriptscriptstyle+},\epsilon^{\scriptscriptstyle-}$, which
motivates bounding these quantities below by 0.

###### Theorem 6 (Excess unfairness).

Suppose that $\widehat{\beta},\widehat{\beta}^{\scriptscriptstyle+}$, and
$\widehat{\beta}^{\scriptscriptstyle-}$ are all consistent at rate $f(n)$.
Under assumptions A1-A3:

$\displaystyle\max\left\\{\operatorname{UF}^{\scriptscriptstyle+}(S_{\widehat{\theta}}),\operatorname{UF}^{\scriptscriptstyle-}(S_{\widehat{\theta}})\right\\}=O_{\mathbb{P}}(1/f(n))$

###### Remark 2.

(The behavior of $\widehat{\theta}$ vs. $S_{\widehat{\theta}}$). Without
assumptions about how the loss and fairness of $S_{\widehat{\theta}}$ depend
on $\widehat{\theta}$, there is no guarantee about the rate at which
$\widehat{\theta}$ will approach $\mathbf{\theta}^{*}$. This is not a concern,
however, since the object of interest is not $\mathbf{\theta}^{*}$ per se but
a predictor that behaves like $S_{\theta^{*}}$.

Arguably the simplest estimators for
$\beta,\beta^{\scriptscriptstyle+},\beta^{\scriptscriptstyle-}$ involve
plugging an estimate of the regression function $\mu_{0}$ into the identifying
expressions in Proposition 1 and then computing empirical means in place of
expectations. We propose instead using doubly robust, influence function-based
estimators, which yield faster rates of convergence than plugin estimators in
general nonparametric settings (van der Vaart, 2002; Tsiatis, 2006).

For ease of notation, let

$\displaystyle\phi$ $\displaystyle=\frac{1-D}{1-\pi}(Y-\mu_{0})+\mu_{0}$

denote the uncentered efficient influence function for $\mathbb{E}(Y^{0})$,
and let $\widehat{\phi}$ denote an estimate constructed from estimates
$\widehat{\mu}_{0}$ and $\widehat{\pi}$ (Bickel et al., 1993; Hahn, 1998; van
der Laan and Robins, 2003; Kennedy, 2016). Both these nuisance functions can
be estimated with arbitrary nonparametric learners. To minimize the use of
indices, let $\mathbb{P}_{n}(f(Z))=n^{-1}\sum_{i=1}^{n}f(Z_{i})$ denote the
sample average of any fixed function $f:\mathcal{Z}\mapsto\mathbb{R}$, so that
for example $\mathbb{P}_{n}(\widehat{\phi})$ is the sample average of
$\widehat{\phi}(Z)$ after $\widehat{\phi}$ has been constructed. The doubly
robust estimators for individual coefficients are:

(2) $\displaystyle\widehat{\beta}_{a,s}$
$\displaystyle=\mathbb{P}_{n}[\mathbbold{1}\\{A=a,S=s\\}(w^{+}-(w^{+}+w^{-})\widehat{\phi})]$
(3) $\displaystyle\widehat{\operatorname{cFPR}}(S,a)$
$\displaystyle=\frac{\mathbb{P}_{n}[\mathbbold{1}\\{A=a\\}S(1-\widehat{\phi})]}{\mathbb{P}_{n}[\mathbbold{1}\\{A=a\\}(1-\widehat{\phi})]}$
(4) $\displaystyle\widehat{\operatorname{cFNR}}(S,a)$
$\displaystyle=\frac{\mathbb{P}_{n}[\mathbbold{1}\\{A=a\\}(1-S)\widehat{\phi}]}{\mathbb{P}_{n}[\mathbbold{1}\\{A=a\\}\widehat{\phi}]}$

These estimates are assembled into the corresponding vectors
$\widehat{\beta},\widehat{\beta}^{\scriptscriptstyle+},\widehat{\beta}^{\scriptscriptstyle-}$.

In order to obtain optimal convergence rates, it is generally necessary to
estimate the nuisance functions $\widehat{\mu}_{0}$ and $\widehat{\pi}$ on one
sample and then compute the sample mean $\mathbb{P}_{n}$ on an independent
sample conditional on those estimates. To obtain full sample size efficiency,
one can swap the folds, repeat the procedure, and average the results, an
approach that is popularly called cross-fitting (Bickel and Ritov, 1988;
Robins et al., 2008; Zheng and van der Laan, Mark, 2010; Chernozhukov et al.,
2018). A $k$-fold version of cross-fitting with $k>2$ is also possible. If
$\widehat{\mu}_{0}$ and $\widehat{\pi}$ are assumed to be sufficiently “well-
behaved,” i.e. if they belong to Donsker classes, then no such sample
splitting is necessary. We prefer to avoid this assumption and utilize sample
splitting. See Appendix C for a schematic of the sample splitting procedure.

The next theorem captures the double robustness property: under this sample
splitting procedure, the coefficient estimators converge at a rate determined
by the product of rates for the nuisance parameter estimators. Two additional
mild assumptions are required.

A4. (Bounded propensity estimator)
$\displaystyle\quad\quad\exists\gamma\in(0,1)\text{ s.t.
}\mathbb{P}(\widehat{\pi}(A,X,S)\leq 1-\gamma)=1$ A5. (Nuisance estimator
consistency)
$\displaystyle\quad\quad\|\widehat{\mu}_{0}-\mu_{0}\|=o_{\mathbb{P}}(1),\\-\
\|\widehat{\pi}-\pi\|=o_{\mathbb{P}}(1)$

Assumption A4 is the empirical analogue of the positivity assumption (A2). It
can be trivially satisfied by truncating $\widehat{\pi}$ at $1-\delta$, the
positivity threshold in assumption A2. Assumption A5 requires the nuisance
parameter estimators to be consistent at any rate, which is reasonable if the
nuisance parameters are estimated nonparametrically.

###### Theorem 7 (Double robustness).

Suppose that
$\|\widehat{\mu}_{0}-\mu_{0}\|\|\widehat{\pi}-\pi\|=O_{\mathbb{P}}(g(n))$ for
some function $g(n)$. Under assumptions A1-A5:

$\displaystyle\|\widehat{\beta}-\beta\|=O_{\mathbb{P}}\left(\max\left\\{g(n),n^{-1/2}\right\\}\right)$

and the same result holds for
$\|\widehat{\beta}^{\scriptscriptstyle+}-\beta^{\scriptscriptstyle+}\|$ and
$\|\widehat{\beta}^{\scriptscriptstyle-}-\beta^{\scriptscriptstyle-}\|$.

###### Corollary 8.0.

If
$\|\widehat{\mu}_{0}-\mu_{0}\|\|\widehat{\pi}-\pi\|=O_{\mathbb{P}}(n^{-1/2})$,
then $\|\widehat{\beta}-\beta\|=O_{\mathbb{P}}(n^{-1/2})$, and likewise for
$\|\widehat{\beta}^{\scriptscriptstyle+}-\beta^{\scriptscriptstyle+}\|$ and
$\|\widehat{\beta}^{\scriptscriptstyle-}-\beta^{\scriptscriptstyle-}\|$.

The corollary shows that it is possible to obtain $\sqrt{n}$ convergence, the
fastest rate attainable in general nonparametric settings, even when the
nuisance parameters are estimated at slower than $\sqrt{n}$ rates. The
condition of Corollary 8 can be satisfied under relatively weak and
nonparametric smoothness or sparsity assumptions (Györfi et al., 2002;
Raskutti et al., 2011). For example, let $d=p+2$ be the dimension of
$(A,X,S)$. If $\mu_{0}$ and $\pi$ are in Hölder classes with smoothness index
$s>d/2$, then there exist nonparametric estimators $\widehat{\mu}_{0}$ and
$\widehat{\pi}$ such that $\|\widehat{\mu}_{0}-\mu\|=o_{\mathbb{P}}(n^{-1/4})$
and $\|\widehat{\pi}-\pi\|=o_{\mathbb{P}}(n^{-1/4})$, in which case the
product of the rates would be $o_{\mathbb{P}}(n^{-1/2})$, which is faster than
$O_{\mathbb{P}}(n^{-1/2})$.

By contrast, a plugin version of $\widehat{\beta}$ would converge at a rate of
$\sqrt{n}$ or the rate for $\|\widehat{\mu}_{0}-\mu_{0}\|$, whichever is
slower, and likewise for plugin versions of
$\widehat{\beta}^{\scriptscriptstyle+}$ and
$\widehat{\beta}^{\scriptscriptstyle-}$. Since $\sqrt{n}$ rates are generally
unattainable in nonparametric regression, this means that plugin estimators
would converge at slower than $\sqrt{n}$ rates, which, per Theorems 4 and 6,
would result in slower convergence in the loss gap and excess unfairness.

Corollary 8 combined with Theorems 4 and 6 shows that if
$\|\widehat{\mu}_{0}-\mu_{0}\|\|\widehat{\pi}-\pi\|=O_{\mathbb{P}}(n^{-1/2})$,
then the excess risk and excess unfairness of $S_{\widehat{\theta}}$ decay at
$\sqrt{n}$ rates.

###  5.4. Estimating performance of the derived predictor

Once $\widehat{\theta}$ has been computed, it is of interest to check both
$\mathcal{L}(S_{\widehat{\theta}})$ and the error rate differences
$\Delta^{\scriptscriptstyle+}(S_{\widehat{\theta}}),\\-\
\Delta^{\scriptscriptstyle-}(S_{\widehat{\theta}})$ of the resulting derived
predictor $S_{\widehat{\theta}}$, for example to understand the performance
“cost” of fairness and to check whether the procedure successfully controlled
the error rate differences.

These estimates should be computed on a test set that is independent of the
sample used to estimate $\widehat{\theta}$. Within the test set, the same
sample splitting considerations apply: unless they are assumed to belong to
Donsker classes, the nuisance parameters $\widehat{\mu}_{0}$ and
$\widehat{\pi}$ should be estimated on separate folds from the folds used to
compute the relevant sample means $\mathbb{P}_{n}$.

Since the estimators below are conditional on a fixed $\widehat{\theta}$, they
can in fact be applied to any fixed parameter value $\theta\in[0,1]^{4}$. We
define two additional quantities of interest.

###### Definition 5.0.

The _loss change_ for a derived predictor $S_{\theta}$ relative to an input
predictor $S$ is $\Gamma(S_{\theta})=\mathcal{L}(S_{\theta})-\mathcal{L}(S)$.

We refer to a _loss change_ rather than an _increase in loss_ because it is
possible for $S_{\theta}$ to have smaller loss that $S$. This is not a typical
expectation: in fair prediction problems, the set of fair classifiers is
necessarily smaller than the set of fair and unfair classifiers, so there is a
fairness-accuracy tradeoff. In the RAI setting, however, since predictors are
typically trained to predict observable outcomes, their performance may be
arbitrarily bad with respect to the potential outcome $Y^{0}$. It is therefore
not implausible than a derived fair predictor could have higher accuracy than
the input predictor.

###### Definition 5.0.

The _predictive change_ for a derived predictor $S_{\theta}$ relative to an
input predictor $S$ is $\mathbb{P}(S_{\widehat{\theta}}\neq S)$.

The predictive change is the proportion of input predictions that the post-
processed predictor flips, which gives a measure of the effect of post-
processing.

Once again, we propose using doubly robust estimators. These estimators are
essentially identical to the estimators of the LP coefficients used in the
previous section. Here, however, we are interested in properties of these
estimators, rather than properties of our derived predictor
$S_{\widehat{\theta}}$. In particular, we are interested in deriving
confidence intervals, in addition to guaranteeing rates of convergence. The
estimators are

(loss)
$\displaystyle\widehat{\mathcal{L}}(S_{\theta})=\theta^{T}\widehat{\beta}+w^{-}\mathbb{P}_{n}(\widehat{\phi})$
(loss change)
$\displaystyle\widehat{\Gamma}(S_{\theta})=(\theta-\mathbf{\tilde{\theta}})^{T}\widehat{\beta}$
(cFPR)
$\displaystyle\widehat{\operatorname{cFPR}}(S_{\theta},a)=\theta_{a,0}\left(1-\widehat{\operatorname{cFPR}}(S,a)\right)+\theta_{a,1}\widehat{\operatorname{cFPR}}(S,a)\quad$
(cFNR)
$\displaystyle\widehat{\operatorname{cFNR}}(S_{\theta},a)=(1-\theta_{a,0})\left(\widehat{\operatorname{cFNR}}(S,a)\right)+\theta_{a,1}\left(1-\widehat{\operatorname{cFNR}}(S,a)\right)$
(error rate difference in cFPR)
$\displaystyle\widehat{\Delta}^{\scriptscriptstyle+}(S_{\theta})=\theta^{T}\widehat{\beta}^{+}$
(error rates difference in cFNR)
$\displaystyle\widehat{\Delta}^{\scriptscriptstyle-}(S_{\theta})=\theta^{T}\widehat{\beta}^{-}$

where recall $\mathbf{\tilde{\theta}}=(0,1,0,1)$, so that
$S_{\mathbf{\tilde{\theta}}}=S$ (i.e., the derived predictor is simply the
input predictor). Note that the loss estimator adds back in the portion of the
loss that doesn’t depend on $\theta$ and that we consequently removed from the
LP in (1).

The predictive change does not involve counterfactual quantities, so it can be
straightforwardly estimated with a plugin estimator:
$\widehat{\mathbb{P}}(S_{\widehat{\theta}}\neq
S)=\mathbb{P}_{n}\left\\{\mathbb{P}\left(S_{\widehat{\theta}}\neq
S|A,S\right)\right\\}=$

$\displaystyle\mathbb{P}_{n}\left\\{\sum_{a\in\\{0,1\\}}\left[\theta_{a,0}\mathbbold{1}\\{A=a,S=0\\}+(1-\theta_{a,1})\mathbbold{1}\\{A=a,S=1\\}\right]\right\\}$

Since this is a sample average, it is asymptotically normal, and confidence
intervals can be derived via the central limit theorem. In order to obtain
asymptotic normality for the remaining estimators, we require the produce of
nuisance parameter errors to decay faster than $\sqrt{n}$:

A6. (Nuisance estimator rates).
$\displaystyle\quad\quad\|\widehat{\mu}_{0}-\mu_{0}\|\|\widehat{\pi}-\pi\|=o_{\mathbb{P}}(1/\sqrt{n})$

As described above, assumption A6 can be satisfied under sparsity or
smoothness conditions on $\mu_{0}$ and $\pi$.

###### Theorem 11 (Asymptotic normality).

Fix $\theta\in[0,1]^{4}$. Under assumptions A1-A6:

$\displaystyle\sqrt{n}\left(\widehat{\mathcal{L}}(S_{\theta})-\mathcal{L}(S_{\theta})\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(f_{\theta}\right)\right)$
$\displaystyle\sqrt{n}\left(\widehat{\Gamma}-\Gamma\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(f_{\theta}-f_{\mathbf{\tilde{\theta}}}\right)\right)$
$\displaystyle\sqrt{n}\left(\widehat{\operatorname{cFPR}}(S_{\theta},a)-\operatorname{cFPR}(S_{\theta},a)\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(g_{a}\right)\right)$
$\displaystyle\sqrt{n}\left(\widehat{\operatorname{cFNR}}(S_{\theta},a)-\operatorname{cFNR}(S_{\theta},a)\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(h_{a}\right)\right)$
$\displaystyle\sqrt{n}\left(\widehat{\Delta}^{\scriptscriptstyle+}-\Delta^{\scriptscriptstyle+}\right)\rightsquigarrow
N\left(0,\operatorname{var}(g_{0}-g_{1})\right)$
$\displaystyle\sqrt{n}\left(\widehat{\Delta}^{\scriptscriptstyle-}-\Delta^{\scriptscriptstyle-}\right)\rightsquigarrow
N\left(0,\operatorname{var}(h_{0}-h_{1})\right)$

where

$\displaystyle f_{\theta}$
$\displaystyle=\theta_{A,S}(w^{+}-(w^{+}+w^{-})\phi)+w^{-}\phi$ $\displaystyle
g_{a}$
$\displaystyle=(\theta_{a,1}-\theta_{a,0})\frac{\mathbbold{1}\\{A=a\\}(1-\phi)(S-\operatorname{cFPR}(S,a))}{\mathbb{E}[\mathbbold{1}\\{A=a\\}(1-\phi)]}$
$\displaystyle h_{a}$
$\displaystyle=(\theta_{a,1}-\theta_{a,0})\frac{\mathbbold{1}\\{A=a\\}\phi(S-\operatorname{cFNR}(S,0))}{\mathbb{E}[\mathbbold{1}\\{A=a\\}\phi]}$

and recall

$\displaystyle\theta_{A,S}$
$\displaystyle=\sum_{a,s\in{0,1}}\theta_{a,s}\mathbbold{1}\\{A=a,S=s\\}$

and the estimators $\widehat{\mathcal{L}},\\-\
\widehat{\Gamma},\widehat{\operatorname{cFPR}},\\-\
\widehat{\operatorname{cFNR}},\\-\ \widehat{\Delta}^{\scriptscriptstyle+},\\-\
\widehat{\Delta}^{\scriptscriptstyle-}$ attain the nonparametric efficiency
bound, meaning that no other estimator has smaller asymptotic variance.

###### Corollary 12.0.

Given a consistent estimator for $\operatorname{var}(f_{\theta})$, an
asymptotically valid 95% confidence interval for $\mathcal{L}(S_{\theta})$ is
given by $\widehat{\mathcal{L}}(S_{\theta})\pm
1.96\cdot\widehat{\operatorname{var}}(f_{\theta})/\sqrt{n}$. An asymptotically
valid test of the hypothesis $\mathcal{L}(S_{\theta})=C$ for any $C$ consists
of evaluating whether $C$ is in the confidence interval. Analogous results
hold for $\Gamma,\\-\
\operatorname{cFPR},\operatorname{cFNR},\Delta^{\scriptscriptstyle+},\Delta^{\scriptscriptstyle+}$.

Perhaps the most natural estimators for these variances are the sample
variances of $\widehat{f}_{\theta},\\-\ \widehat{g}_{a},\\-\
\widehat{h}_{a},\\-\ \widehat{g}_{0}-\widehat{g}_{1}$, and
$\widehat{h}_{0}-\widehat{h}_{1}$, where these quantities are defined by the
following:

$\displaystyle\widehat{f}_{\theta}$
$\displaystyle=(w^{+}-(w^{+}+w^{-})\widehat{\phi})\theta_{A,S}+w^{-}\widehat{\phi}$
$\displaystyle\widehat{g}_{a}$
$\displaystyle=(\theta_{a,1}-\theta_{a,0})\frac{\mathbbold{1}\\{A=a\\}(1-\widehat{\phi})(S-\widehat{\operatorname{cFPR}}(S_{\theta},a))}{\mathbb{P}_{n}[\mathbbold{1}\\{A=a\\}(1-\widehat{\phi})]^{-1}}$
$\displaystyle\widehat{h}_{a}$
$\displaystyle=(\theta_{a,1}-\theta_{a,0})\frac{\mathbbold{1}\\{A=a\\}\widehat{\phi}(S-\widehat{\operatorname{cFNR}}(S_{\theta},0))}{\mathbb{P}_{n}[\mathbbold{1}\\{A=a\\}\widehat{\phi}]^{-1}}$

The quantities $f_{\theta},g_{a}$, and $h_{a}$ are the efficient influence
functions for the loss and error rates.

##  6\. Results

There is no previous method designed to achieve counterfactual equalized odds
or related fairness criteria that we can compare our method to. We instead
compare our method to an approach that uses plugin estimators for the LP
coefficients, in order to illustrate the advantages of the doubly robust
estimators.

###  6.1. Simulations

We use one set of simulations to illustrate Theorems 4-7 and another set to
explore fairness-performance tradeoffs. We use equal misclassification weights
$w^{+}=w^{-}=1$, so that false positives and false negatives contribute
equally to the loss. Simulations illustrating Theorem 11 can be found in
Appendix E.

Each estimation procedure was run 500 times for each sample size
$n\in\\{100,200,500,1000,5000,20000\\}$. Since $\mu_{0}$ is known here, the
“true” loss and fairness values were computed on a separate validation set of
size 500,000, using plugin estimators with the true $\mu_{0}$. These values
showed negligible variation over many repetitions.

####  6.1.1. Setup

First, we define a _pre-RAI_ data generating process. Using this data, we
train a predictor $S$ to predict observable outcomes $Y$, mirroring how RAIs
are typically constructed in practice. We then define a _post-RAI_ data
generating process, which only differs in that the predictor $S$ now affects
the decisions $D$. This emulates the way RAIs are intended to work in
practice; for example, a criminal defendant labeled high-risk $(S=1)$ be a RAI
might be less likely to be released pre-trial $(D=0)$ than they would have
been prior to the introduction of the RAI. The data generating process is
designed to meet assumptions A1-A3, with $\pi(D\mid A,X,S)$ upper bounded at
$0.975$. It is described fully in Appendix D. We apply our method to the post-
RAI data generating process, simulating the application of post-processing to
a predictor that is already embedded in a decision making context.

####  6.1.2. Theorems 4-7

To simulate the estimation of the LP coefficient vectors at a particular rate,
we add random noise $\epsilon$ of magnitude $o_{\mathbb{P}}(1/n^{1/4})$ to the
nuisance parameters $\mu_{0}$ and $\pi$555The noise is added on the logit
scale to ensure that $\widehat{\mu}_{0},\widehat{\pi}$ remain in $[0,1]$, and
$\widehat{\pi}$ is again truncated to 0.975.. As described above, in general
nonparametric settings, regression functions cannot be estimated at $\sqrt{n}$
rates, but they can be estimated at $n^{-1/4}$ rates under relatively weak
assumptions (van der Vaart, 2002).

Figure 2 shows $\mathcal{L}(S_{\widehat{\theta}})$ and the excess unfairness
values $\operatorname{UF}^{\scriptscriptstyle+}(S_{\widehat{\theta}})$,
$\operatorname{UF}^{\scriptscriptstyle-}(S_{\widehat{\theta}})$ for the post-
processed predictor $S_{\widehat{\theta}}$ with fairness constraints
$\epsilon^{\scriptscriptstyle+}=0.10,\\-\
\epsilon^{\scriptscriptstyle-}=0.20$. As expected, when doubly robust
estimators are used, the loss and excess unfairness values converge at
$\sqrt{n}$ rates to $\mathcal{L}(S_{\theta^{*}})$, the loss of the optimal
derived predictor and 0, respectively. When plugin estimators are used, the
rates are slower than $\sqrt{n}$.

Figure 2. (Illustration of Theorems 4-7). Loss
$\text{L}(S_{\widehat{\theta}})$ and excess unfairness values
$\operatorname{UF}^{\scriptscriptstyle+}(S_{\widehat{\theta}}),\operatorname{UF}^{\scriptscriptstyle-}(S_{\widehat{\theta}})$
for the derived predictor $S_{\widehat{\theta}}$ for samples of size 100 to
20,000. Each vertical line represents a mean $\pm 1$ sd over 500 simulations.
Orange horizontal lines represent the loss of the optimal derived predictor
$S_{\theta^{*}}$ (top left panel) or 0. The top row represents our doubly
robust (DR) procedure and shows that the loss and excess unfairness converge
to their target values. The bottom two rows represent values from the DR
procedure or a plugin (PI) procedure, transformed by
$\psi(S_{\widehat{\theta}})\mapsto\sqrt{n}(\psi(S_{\widehat{\theta}})-\psi(S_{\theta^{*}}))$,
where $\psi$ is $\mathcal{L}$ or $\operatorname{UF}^{\scriptscriptstyle+}$ or
$\operatorname{UF}^{\scriptscriptstyle-}$, as appropriate. These rows
illustrate that $\sqrt{n}$-convergence is only guaranteed for
$\widehat{\theta}_{\text{DR}}$: the scaled values for
$\widehat{\theta}_{\text{DR}}$ do not grow in $n$, while the scaled values for
$\widehat{\theta}_{\text{PI}}$ begin to diverge.

####  6.1.3. Fairness-performance tradeoffs

Figure 3 shows the loss change
$\Gamma(S_{\theta^{*}})=\mathcal{L}(S_{\theta^{*}})-\mathcal{L}(S)$ for each
point in a grid of fairness constraints $\epsilon^{\scriptscriptstyle+},\\-\
\epsilon^{\scriptscriptstyle-}$. Here, $S$ is the Bayes-optimal predictor of
$Y^{0}$ in our data generating scenario, meaning $S(A,X)=\mathbb{E}[Y^{0}\mid
A,X]$. Since any derived predictor necessarily has greater loss than the
Bayes-optimal predictor, we refer to the loss change here equivalently as the
_performance cost_.

Figure 3. (Fairness-performance tradeoffs). Loss change
$\Gamma(\mathbf{\theta}^{*})=\mathcal{L}(S_{\theta^{*}})-\mathcal{L}(S)$ for
the Bayes-optimal input predictor $S(A,X)=\mathbb{E}[Y^{0}\mid A,X]$ and
$\mathbf{\theta}^{*}$ corresponding to different fairness constraints
$\epsilon^{\scriptscriptstyle+},\\-\ \epsilon^{\scriptscriptstyle-}$. The
black area represents fairness constraints that are looser than the error rate
differences of the input predictor
$(\Delta^{\scriptscriptstyle+}(S)=0.24,\\-\,\Delta^{\scriptscriptstyle-}(S)=0.40)$,
which incur no performance cost. The highest performance cost $(0.10)$ occurs
when the error rates differences are both constrained to be 0, meaning the
derived predictor $S_{\theta^{*}}$ satisfies cEO exactly.

In the data generating process used in the previous section, the Bayes-optimal
predictor has absolute error rate differences of only $0.05$
($\Delta^{\scriptscriptstyle+}$) and $0.04$ ($\Delta^{\scriptscriptstyle-}$),
which leaves little room to illustrate the potential cost of fairness. For
these simulations, therefore, we alter the data generating process slightly.
(See Appendix D). This results in a Bayes-optimal predictor with absolute
error rate differences of $0.23$ ($\Delta^{\scriptscriptstyle+}$) and $0.40$
($\Delta^{\scriptscriptstyle-}$) and a loss of $0.24$, which are plausible
values for a real predictor.

As expected, when
$\epsilon^{\scriptscriptstyle+}\geq\Delta^{\scriptscriptstyle+}(S)$ or
$\epsilon^{\scriptscriptstyle-}\geq\Delta^{\scriptscriptstyle-}(S)$, the
performance cost is 0: the input predictor already falls satisfies the
fairness constraints, so our method simply returns the input predictor. As the
tolerances tighten towards 0, the performance declines, though never
substantially. For
$\epsilon^{\scriptscriptstyle+}=\epsilon^{\scriptscriptstyle-}=0$, when the
derived predictor is constrained to satisfy exact cEO, the loss increases by
0.10, to 0.34. The different values for $\Delta^{\scriptscriptstyle+}(S)$ and
$\Delta^{\scriptscriptstyle-}(S)$ in the input predictor are reflected in the
differing costs of satisfying fairness along the two axes: the cost of
controlling $\Delta^{\scriptscriptstyle+}(S_{\theta})$ are lower than the
costs of controlling $\Delta^{\scriptscriptstyle-}(S_{\theta})$.

Woodworth et al. (2017) showed that post-processing can result in predictors
with poor performance, but it is unclear how likely this is to be a problem in
practice. While the fairness-accuracy tradeoff naturally depends on the data
generating process, our example illustrates that fairness can in some cases be
achieved without substantial performance costs.

###  6.2. COMPAS data

We illustrate our method on the COMPAS recidivism dataset gathered by
ProPublica (Angwin et al., 2016; Larson et al., 2016). COMPAS refers to a
collection of tools designed to assess the risk of recidivism. The dataset
comprises public arrest records, criminal records, and COMPAS RAI scores from
Broward County, Florida, spanning 2013–2016. After filtering the data in the
same manner as Larson et al. (2016) and restricting to defendants who are
labeled African-American ($A=0$) or Caucasian ($A=1$), we are left with data
for 5278 individuals (3175 African-American, 2103 Caucasian).

We utilize the COMPAS scores for general, as opposed to violent, recidivism.
The scores are given in risk deciles. Since our method operates on a binary
input predictor $S$, we follow ProPublica and set scores of 1-4 to $S=0$ (“low
risk”) and scores of 5-10 to $S=1$ (“high risk”). The outcome $Y$ is
recidivism within a two-year time period. (See Larson et al. (2016) for how
recidivism is operationalized.) ProPublica’s analysis focuses on the use of
COMPAS to inform pretrial release decisions. The dataset includes dates in and
out of jail but does not indicate whether defendants were released pretrial,
so we set the treatment $D$ to 0 if defendants left jail within three days of
being arrested, and 1 otherwise. This yields 3645 released individuals (2158
African-American, 1487 Caucasian) and 1633 incarcerated individuals (1017
African-American, 616 Caucasian). Note that this threshold is somewhat
arbitrary. Florida state law generally requires individuals to be brought
before a judge for a bail hearing within 48 hours of arrest, but it may take
time for individuals to post bail if they are required and able to do so.

The covariates $X$ consist of gender (coded male or female), age (coded
categorically for $<25$, between 25 and 45, and $>45$), the number of prior
crimes, and charge degree (misdemeanor or felony). Without consulting with
domain experts, it is difficult to assess the plausibility of the positivity
and ignorability assumptions given these covariates. Hence we intend our
analysis primarily to be illustrative of our method, and we resist drawing
strong substantive conclusions about COMPAS.

We weight false positives and false negatives equally, i.e. we set
$w^{+}=w^{-}=1$. We randomly split the data into training and test sets of
equal size. For $\epsilon\in\\{0,0.01,0.05,0.10,0.20,\ldots,0.90,1\\}$, we set
the fairness constraints to
$\epsilon^{\scriptscriptstyle+}=\epsilon^{\scriptscriptstyle-}=\epsilon$,
compute the corresponding estimate $\widehat{\theta}$ on the training set, and
estimate properties of the post-processed predictor $S_{\widehat{\theta}}$ on
the test set. We also estimate properties of the binarized COMPAS score $S$ on
the test set. We use random forests to estimate both the propensity scores
$\widehat{\pi}$ and the outcome regression $\widehat{\mu}_{0}$. To reduce the
variance of the estimates, we employ 5-fold cross-fitting: within the train
set, we compute five estimates $\widehat{\theta}_{j},j=1,\ldots 5$, using four
folds at a time to estimate the nuisance parameters and the held-out fold to
compute $\widehat{\theta}_{j}$. Then
$\widehat{\theta}:=\frac{1}{5}\sum_{j}\widehat{\theta}_{j}$. We utilize the
test set in an analogous fashion for the remaining estimators.

Table 1 contains estimates and confidence intervals for COMPAS and for the
post-processed predictor corresponding to fairness constraints of
$\epsilon^{\scriptscriptstyle+}=\epsilon^{\scriptscriptstyle-}=0.05$. The loss
for COMPAS is 0.36, and the differences in the $\operatorname{cFPR}$ and
$\operatorname{cFNR}$ are -0.24 and 0.16, respectively. The signs of these
differences are consistent with what ProPublica found in their analysis with
respect to observable $Y$: the false positive rates are higher for African-
American defendants, while the false negative rates are higher for Caucasian
defendants. The post-processing procedure successfully shrinks these
differences to -0.05 and -0.03, which fall within the target range of
$[-0.05,0.05]$. This reduction corresponds to flipping $9\%$ of the COMPAS
scores, and it incurs an increase in risk of only 0.03.

The value of $\widehat{\theta}$ corresponding to $S_{\widehat{\theta}}$ here
is $(0,0.91,0.23,1)$. The 0 and the 1 indicate that $S_{\widehat{\theta}}$
does not change the COMPAS scores for African-American defendants who receive
a “low-risk” score or Caucasian defendants who receive a “high-risk” score.
The scores for high-risk African-American defendants are flipped to low-risk
$1-0.91=9\%$ of the time, while the scores for low-risk Caucasian defendants
are flipped to high-risk $23\%$ of the time. This has the effect of increasing
the false positive rate and decreasing the false negative rate for Caucasians,
while moving the rates in the opposite directions for African-Americans.

Figure 4 shows the loss, error rate differences, and predictive change for
fairness constraints ranging from 0 (requiring no gap in error rates) to 1
(imposing no fairness constraints). Each constraint induces an estimate
$\widehat{\theta}$ and a corresponding post-processed predictor
$S_{\widehat{\theta}}$. The estimated fairness gaps fall along or within the
lines $y=\pm x$, indicating that each $S_{\widehat{\theta}}$ satisfies its
target constraints. At the most stringent setting of 0, the loss for
$S_{\widehat{\theta}}$ is approximately 0.40, which compares favorably with
the estimated baseline loss of 0.36 for COMPAS. This $S_{\widehat{\theta}}$
flips slightly less than $20\%$ of the scores.

Figure 4. Convergence of the estimated loss
$\widehat{\mathcal{L}}(S_{\widehat{\theta}})$, predictive change
$\widehat{\mathbb{P}}(S_{\widehat{\theta}}\neq S)$, and error rate differences
$\widehat{\Delta}^{\scriptscriptstyle+}(S_{\widehat{\theta}}),\widehat{\Delta}^{\scriptscriptstyle-}(S_{\widehat{\theta}})$,
for post-processed versions of the binarized COMPAS predictor. Fairness
constraints are set to
$\epsilon^{\scriptscriptstyle+}=\epsilon^{\scriptscriptstyle-}=\epsilon$ over
a range of values $\epsilon$. Vertical lines are 95% CIs. Horizontal orange
lines indicate the reference values for COMPAS, or 0 in the case of predictive
change. The dashed blue lines $y=x$ and $y=-x$, mark the target fairness
constraints.

For $\epsilon>0.24$, the fairness constraints are essentially no longer
active, since COMPAS itself satisfies these constraints. Indeed, as expected,
the $\widehat{\theta}$ values for $\epsilon>0.24$ are all essentially
$[0,1,0,1]$, meaning that $S_{\widehat{\theta}}=S$, and the estimated risk and
fairness values all fall close to the estimated values for COMPAS. (There is
still some variation in the estimated values due to randomness in the k-fold
cross-fitting procedure.)

These results illustrate that our approach performs as intended on a real
dataset: if these data were indeed generated from a distribution satisfying
the identifying assumptions, then our post-processed predictor would satisfy
approximate counterfactual equalized odds while incurring little cost in
performance.

Table 1. Estimates and 95% confidence intervals for the loss $\mathcal{L}$, loss change $\Gamma$, error rates $\operatorname{cFPR}$ and $\operatorname{cFNR}$ for groups 0 and 1, error rate differences $\Delta^{\scriptscriptstyle+},\Delta^{\scriptscriptstyle-}$, and predictive change $\mathbb{P}(S_{\widehat{\theta}}\neq S)$ for the binarized COMPAS predictor $S$ and the post-processed predictor $S_{\widehat{\theta}}$, with $\epsilon^{\scriptscriptstyle+}$ and $\epsilon^{\scriptscriptstyle-}$ set to $0.05$. | $S$ | $S_{\widehat{\theta}}$
---|---|---
$\widehat{\mathcal{L}}(\cdot)$ | 0.36 (0.32, 0.41) | 0.39 (0.35, 0.42)
$\widehat{\Gamma}(\cdot)$ | – | 0.03 (0.01, 0.04)
$\widehat{\operatorname{cFPR}}(\cdot,0)$ | 0.43 (0.36, 0.49) | 0.39 (0.33, 0.45)
$\widehat{\operatorname{cFPR}}(\cdot,1)$ | 0.24 (0.18, 0.31) | 0.42 (0.37, 0.47)
$\widehat{\operatorname{cFNR}}(\cdot,0)$ | 0.30 (0.25, 0.35) | 0.36 (0.31, 0.40)
$\widehat{\operatorname{cFNR}}(\cdot,1)$ | 0.53 (0.46, 0.60) | 0.41 (0.35, 0.46)
$\widehat{\Delta}^{\scriptscriptstyle+}(\cdot)$ | -0.24 (-0.32, -0.15) | -0.05 (-0.12, 0.02)
$\widehat{\Delta}^{\scriptscriptstyle-}(\cdot)$ | 0.18 (0.09, 0.28) | -0.03 (-0.10, 0.05)
$\widehat{\mathbb{P}}(\cdot\neq S)$ | – | 0.09 (0.09, 0.09)

###  6.3. Child welfare data

Cost-sensitive loss functions can drive $\widehat{\theta}$ to a trivial
classifier that always predicts one class. We illustrate this phenomenon on a
dataset representing calls to a child-welfare hotline in Allegheny County,
Pennsylvania. The data comprises over 30,000 calls and contains over 1,000
features. The features describe allegations made in the call, assessments of
risk made by hotline workers, and features pertaining to individuals
associated with the call. Workers must decide whether to _screen in_ a call,
which means opening an investigation into the allegations. The baseline
decision $D=0$ is to screen out, meaning no investigation takes place. The
outcome $Y$ is re-referral to the hotline within a six month period. For
further details about the child welfare setting and this dataset in
particular, see Chouldechova et al. (2018) and Coston et al. (2020).

Unlike the COMPAS dataset, this dataset does not include a previously trained
predictor. We therefore first build a predictor $S$ that predicts $Y^{0}$, and
then we post-process $S$. In this setting, we have reason to believe that the
identification assumptions in section 5.2 are plausible, once cases with the
highest propensity for screen-in are removed; see Coston et al. (2020). (RAIs
are not necessary or useful for cases that are already guaranteed to be
screened in.) In order to accomplish this filtering, we first build a
propensity score model using random forests on roughly one third of the data.
The model appears well-calibrated, so we filter out the approximately 20% of
the cases with estimated propensity scores greater than 0.99. Note that
downstream results did not change substantially when these cases were left in.

We then train a classification random forest $S$ to predict $Y$ conditional on
$A,X,D=0$, using the same third of the data. Under the identifying
assumptions, $Y|X,A,D=0$ is equal in distribution to $Y^{0}|A,X$, so $S$ is
indeed an estimate of the target $Y^{0}$. Following recommended usage in this
setting, we set the classification threshold to capture the top 25% riskiest
cases (Chouldechova et al., 2018).

The predictor $S$ has estimated error rate differences and 95% confidence
intervals of $\widehat{\Delta}^{\scriptscriptstyle+}=-0.02\pm 0.01$ and
$\widehat{\Delta}^{\scriptscriptstyle-}=0.09\pm 0.08$. It is unsurprising that
these differences are small, given that rereferral rates are similar for Black
(0.24) and White (0.27) cases. See Chouldechova (2017) for an examination of
the relationship between base rates and error rates.

In order to have nontrivial (active) fairness constraints, we set
$\epsilon^{\scriptscriptstyle+}=\epsilon^{\scriptscriptstyle-}=0.01$. Figure 5
shows the value of $\widehat{\theta}$ over a range of cost ratios
$w^{+}/w^{-}$ and $w^{-}/w^{+}$. When false positives are weighted more than
1.5 times as heavily as false negatives, post-processing returns classifiers
that are very close to the simple majority classifier $S_{(0,0,0,0)}\equiv 0$.
When false negatives are weighted more than 2 times as heavily as false
positives, post-processing returns the simple minority classifier
$S_{(1,1,1,1)}\equiv 1$. Since the input classifier is approximately fair,
between those ranges, post-processing returns classifiers that are very close
to the input classifier $S=S_{(0,1,0,1)}$, with only the fourth component
$\widehat{\theta}_{1,1}$ deviating slightly from 1.

Figure 5. Cost-sensitive post-processing for the child welfare predictor over
a range of cost ratios, with fairness constraints
$\epsilon^{\scriptscriptstyle+}=\epsilon^{\scriptscriptstyle-}=0.01$. Each
column represents a single $\widehat{\theta}$, with the four components
$\theta_{a,s}$ for $a,s\in\\{0,1\\},$ in rows. False positives are weighted
between 1.25 and 3 times as heavily as false negatives to the left of the
dashed line, and vice versa to the right. Extreme cost ratios push the post-
processed classifier to a trivial classifier that always predicts 0 (to the
left of the orange lines) or 1 (to the right). Between these, post-processing
essentially returns the input predictor.

This behavior is expected. Note that a simple majority or minority classifier
always satisfies counterfactual equalized odds, since the error rate
differences are 0. Since the post-processed predictor only has access at
runtime to two binary features, as either false positives or false negatives
become sufficiently important, one of these simple classifiers will at some
point become the lowest risk option. This is possible in principle when
$w^{+}$ and $w^{-}$ are equal, but it is guaranteed as their ratio grows.
Since this dataset did not include a pretrained predictor of $Y^{0}$, it would
be preferable to adopt an in-processing approach, i.e. to train a predictor
that satisfies the desired fairness constraints in a single stage, rather than
training an unconstrained predictor and then post-processing it. We pursue
this task in ongoing work.

##  7\. Discussion and conclusion

In this paper we considered fairness in risk assessment instruments (RAIs),
which are naturally concerned with potential outcomes rather than strictly
observable outcomes. We defined the fairness criterion _approximate
counterfactual equalized odds_ (approximate cEO), which allows users to
negotiate the tradeoff between fairness and performance. We argued that this
fairness criterion is likelier than other candidate criteria to reduce
discriminatory disparate impact, which we defined as
$D\not\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}A\mid Y^{0}$.

We presented a method to post-process an existing binary predictor to satisfy
approximate cEO using doubly robust estimators, and we showed that our method
has favorable convergence properties. Our rate results translate readily to
the post-processing setting of (Hardt et al., 2016), in which the outcome of
interest is the observable $Y$ and the fairness criterion is (approximate)
observational equalized odds.

Once it is constructed, the post-processed predictor requires access at
runtime only to the sensitive feature and the input predictor, making it
relatively feasible to implement on top of existing RAIs. A predictor trained
from scratch would be constrained by the set of covariates available in
deployment, whereas the post-processing approach allows researchers to devise
a set of suitable deconfounding covariates and then collect an appropriate
dataset on a one-time basis.

In closing, we note that from our perspective, notions of fairness in
predictive systems ought to be subordinate to notions of fairness grounded in
the actual decisions or events that those systems inform, and the impact that
those decisions have on people’s lives. Though little is currently known about
how decision makers respond to RAIs, there is some evidence that judges do not
have much faith in recidivism predictions and that RAIs can have little impact
on decisions (Jonnson, 2018; Stevenson, 2018). As RAIs and the general
public’s understanding of how they function co-evolve, it is likely that the
ways in which decision makers respond to them will evolve as well.

Nevertheless, it seems plausible that some fairness criteria for RAIs are
likelier than others to lead to increased (un)fairness with respect to
decisions and outcomes. While this is ultimately an empirical question, we
believe that this kind of consideration ought to ground discussions of
fairness in RAIs and predictive systems generally. As long as there are
domains involving high stakes decisions that we do not wish to fully automate,
RAIs will remain relevant, and so will the task of ensuring that they lead to
a society that is more fair, not less.

###### Acknowledgements.

Edward Kennedy gratefully acknowledges support from NSF DMS Grant 1810979.
Additionally, we are grateful to the Block Center for Technology and Society
at Carnegie Mellon University for funding this work, and to the Allegheny
County Department of Human Services for furnishing the child welfare data.

## References

  * (1)
  * Angwin and Larson (2016) Julia Angwin and Jeff Larson. 2016.  Bias in Criminal Risk Scores Is Mathematically Inevitable, Researchers Say.  _ProPublica_ (Dec 2016).  https://www.propublica.org/article/bias-in-criminal-risk-scores-is-mathematically-inevitable-researchers-say
  * Angwin et al. (2016) Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016.  Machine Bias.  _ProPublica_ (May 2016).  https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing
  * Barocas et al. (2018) Solon Barocas, Moritz Hardt, and Arvind Narayanan. 2018\.  Fairness and Machine Learning.  (2018).  http://www.fairmlbook.org
  * Bickel et al. (1993) Peter J. Bickel, Chris A.J. Klaassen Ya’acov Ritov, and Jon A. Wellner. 1993\.  _Efficient and adaptive estimation for semiparametric models_.  Johns Hopkins University Press, Baltimore.
  * Bickel and Ritov (1988) Peter J. Bickel and Ya’acov Ritov. 1988.  Estimating Integrated Squared Density Derivatives : Sharp Best Order of Convergence Estimates.  _Sankhyā: The Indian Journal of Statistics, Series A_ 50, 3 (1988), 381–393.  https://www.jstor.org/stable/25050710
  * Boyd and Vandenberghe (2004) Stephen P. Boyd and Lieven Vandenberghe. 2004.  _Convex optimization_.  Cambridge University Press.
  * Calmon et al. (2017) Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. 2017\.  Optimized Pre-Processing for Discrimination Prevention. In _Advances in Neural Information Processing Systems_ (Long Beach, CA) _(NIPS 2017)_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 3992–4001.  http://papers.nips.cc/paper/6988-optimized-pre-processing-for-discrimination-prevention.pdf
  * Chernozhukov et al. (2018) Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. 2018.  Double/debiased machine learning for treatment and structural parameters.  _The Econometrics Journal_ 21, 1 (Feb. 2018), C1–C68.  https://doi.org/10.1111/ectj.12097
  * Chouldechova (2017) Alexandra Chouldechova. 2017\.  Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.  _Big data_ 5, 2 (2017), 153–163.
  * Chouldechova et al. (2018) Alexandra Chouldechova, Diana Benavides-Prado, Oleksandr Fialko, and Rhema Vaithianathan. 2018\.  A case study of algorithm-assisted decision making in child maltreatment hotline screening decisions. 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, New York, NY, USA, 134–148.  http://proceedings.mlr.press/v81/chouldechova18a.html
  * Coston et al. (2020) Amanda Coston, Alan Mishler, Edward H. Kennedy, and Alexandra Chouldechova. 2020.  Counterfactual Risk Assessments, Evaluation, and Fairness _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 582–593.  https://doi.org/10.1145/3351095.3372851
  * Dieterich et al. (2016) William Dieterich, Christina Mendoza, and Tim Brennan. 2016\.  _COMPAS Risk Scales: Demonstrating Accuracy Equity and Predictive Parity_.  Technical Report.
  * Donini et al. (2018) Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. 2018\.  Empirical Risk Minimization Under Fairness Constraints. In _Advances in Neural Information Processing Systems 31_ (Montréal, Canada) _(NeurIPS 2018)_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc., 2791–2801.  http://papers.nips.cc/paper/7544-empirical-risk-minimization-under-fairness-constraints.pdf
  * Glymour and Glymour (2014) Clark Glymour and Madelyn R. Glymour. 2014.  Commentary: Race and sex are causes.  _Epidemiology_ 25, 4 (2014), 488–490.  https://doi.org/10.1097/EDE.0000000000000122
  * Györfi et al. (2002) Laszlo Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. 2002\.  _A Distribution-Free Theory of Nonparametric Regression_.  Springer.
  * Hahn (1998) Jinyong Hahn. 1998\.  On the Role of the Propensity Score in Efficient Semiparametric Estimation of Average Treatment Effects.  _Econometrica_ 66, 2 (1998), 315–331.  https://www.jstor.org/stable/2998560
  * Hardt et al. (2016) Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. 2016\.  Equality of Opportunity in Supervised Learning. In _Advances in Neural Information Processing Systems 29_ _(NIPS 2016)_ , D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (Eds.). Curran Associates, Inc., 3315–3323.  http://papers.nips.cc/paper/6374-equality-of-opportunity-in-supervised-learning.pdf
  * Holland (1986) Paul W. Holland. 1986\.  Statistics and Causal Inference.  _J. Amer. Statist. Assoc._ 81, 396 (1986), 968\.  http://www.jstor.org/stable/2289069
  * Hu and Kohler-Hausmann (2020) Lily Hu and Issa Kohler-Hausmann. 2020.  What’s Sex Got to Do with Machine Learning?. In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ (Barcelona, Spain) _(FAT* ’20)_. Association for Computing Machinery, New York, NY, USA, 513\.  https://doi.org/10.1145/3351095.3375674
  * Imai and Jiang (2020) Kosuke Imai and Zhichao Jiang. 2020.  Principal Fairness for Human and Algorithmic Decision-Making.  (2020).  arXiv:2006.01770 [cs.CY] https://arxiv.org/abs/2005.10400
  * Jonnson (2018) Melissa Jonnson. 2018\.  _The Influence of Risk Assessment Evidence on Judicial Sentencing Decisions_.  Master’s thesis.  http://summit.sfu.ca/item/18704
  * 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.  http://doi.org/10.1007/s10115-011-0463-8
  * Kearns et al. (2017) Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. 2017\.  Meritocratic Fairness for Cross-Population Selection. In _Proceedings of the 34th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, International Convention Centre, Sydney, Australia, 1828–1836.  http://proceedings.mlr.press/v70/kearns17a.html
  * Kennedy (2016) Edward H. Kennedy. 2016\.  Semiparametric Theory and Empirical Processes in Causal Inference. In _Statistical Causal Inferences and Their Applications in Public Health Research_ , Hua He, Pan Wu, and Ding-Geng (Din) Chen (Eds.). Springer, 141–167.  https://doi.org/10.1007/978-3-319-41259-7_8
  * Kennedy et al. (2020) Edward H. Kennedy, Sivaraman Balakrishnan, and Max G’Sell. 2020.  Sharp instruments for classifying compliers and generalizing causal effects.  _Annals of Statistics_ 48, 4 (08 2020), 2008–2030.  https://doi.org/10.1214/19-AOS1874
  * Kilbertus et al. (2017) Niki Kilbertus, Mateo Rojas Carulla, Giambattista Parascandolo, Moritz Hardt, Dominik Janzing, and Bernhard Schölkopf. 2017.  Avoiding Discrimination through Causal Reasoning. In _Advances in Neural Information Processing Systems 30_ (Long Beach, CA) _(NIPS 2017)_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 656–666.  http://papers.nips.cc/paper/6668-avoiding-discrimination-through-causal-reasoning.pdf
  * 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_ (Honolulu, HI, USA) _(AIES ’19)_. Association for Computing Machinery, New York, NY, USA, 247–254.  https://doi.org/10.1145/3306618.3314287
  * Kleinberg et al. (2017) Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2017\.  Inherent Trade-Offs in the Fair Determination of Risk Scores. In _8th Innovations in Theoretical Computer Science Conference (ITCS 2017)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 67)_ , Christos H. Papadimitriou (Ed.). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 43:1–43:23.  http://doi.org/10.4230/LIPIcs.ITCS.2017.0
  * Kusner et al. (2017) Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual Fairness. In _Advances in Neural Information Processing Systems 30_ _(NIPS 2017)_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 4066–4076.  http://papers.nips.cc/paper/6995-counterfactual-fairness.pdf
  * Larson and Angwin (2016) Jeff Larson and Julia Angwin. 2016.  Technical Response to Northpointe.  _ProPublica_ (July 2016).  https://www.propublica.org/article/technical-response-to-northpointe
  * Larson et al. (2016) Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. 2016\.  How We Analayzed the COMPAS Recidivism Algorithm.  _ProPublica_ (May 2016).  https://www.propublica.org/article/how-we-analyzed-the-compas-recidivism-algorithm.
  * Lowenkamp et al. (2016) Anthony W. Lowenkamp, Flores Kristin, and Bechtel Christopher T. 2016.  False Positives, False Negatives, and False Analyses: A Rejoinder to Machine Bias: There’s Software Used across the Country to Predict Future Criminals. And It’s Biased against Blacks.  _Federal Probation_ 80, 2 (2016), 38–46.  https://www.uscourts.gov/federal-probation-journal/2016/09/false-positives-false-negatives-and-false-analyses-rejoinder
  * Menon and Williamson (2018) Aditya Krishna Menon and Robert C Williamson. 2018.  The cost of fairness in binary 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, New York, NY, USA, 107–118.  http://proceedings.mlr.press/v81/menon18a.html
  * Nabi et al. (2019) Razieh Nabi, Daniel Malinsky, and Ilya Shpitser. 2019\.  Learning Optimal Fair Policies. In _Proceedings of the 36th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 97)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 4674–4682.  http://proceedings.mlr.press/v97/nabi19a.html
  * Nabi and Shpitser (2018) Razieh Nabi and Ilya Shpitser. 2018.  Fair Inference on Outcomes. In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence_ (New Orleans, LA). Association for the Advancement of Artificial Intelligence, 1931–1940.  https://aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16683
  * Narasimhan (2018) Harikrishna Narasimhan. 2018\.  Learning with Complex Loss Functions and Constraints. In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 84)_ , Amos Storkey and Fernando Perez-Cruz (Eds.). PMLR, 1646–1654.  http://proceedings.mlr.press/v84/narasimhan18a.html
  * Neyman (1923) Jerzy Neyman. 1923\.  Justification of applications of the calculus of probabilities to the solutions of certain questions in agricultural experimentation. Excerpts English translation (Reprinted).  _Statist. Sci._ 5 (1923), 463–472.
  * Obermeyer et al. (2019) Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. 2019.  Dissecting racial bias in an algorithm used to manage the health of populations.  _Science_ 366, 6464 (Oct. 2019), 447–453.  https://doi.org/10.1126/science.aax2342
  * Raskutti et al. (2011) Garvesh Raskutti, Martin J Wainwright, and Bin Yu. 2011\.  Minimax rates of estimation for high-dimensional linear regression over $\ell_{q}$-balls.  _IEEE transactions on information theory_ 57, 10 (2011), 6976–6994.  https://doi.org/10.1109/TIT.2011.2165799
  * Rice and Swesnik (2012) Lisa Rice and Deidre Swesnik. 2012.  Discriminatory Effects of Credit Scoring on Communities of Color.  _Suffolk University Law Review_ 46 (2012), 935.
  * Robins et al. (2008) James Robins, Lingling Li, Eric Tchetgen, and Aad van der Vaart. 2008.  Higher order influence functions and minimax estimation of nonlinear functionals.  In _Probability and Statistics: Essays in Honor of David A. Freedman_ , Deborah Nolan and Terry Speed (Eds.). Institute of Mathematical Statistics, Beachwood, Ohio, USA, 335–421.  https://doi.org/10.1214/193940307000000527
  * Rubin (2005) Donald B Rubin. 2005\.  Causal Inference Using Potential Outcomes: Design, Modeling, Decisions.  _J. Amer. Statist. Assoc._ 100, 469 (March 2005), 322–331.  https://doi.org/10.1198/016214504000001880
  * Stevenson (2018) Megan Stevenson. 2018\.  Assessing Risk Assessment in Action.  _Minnesota Law Review_ 103, 1 (2018), 83.  https://dx.doi.org/10.2139/ssrn.3016088
  * Tsiatis (2006) Anastasios A. Tsiatis. 2006\.  _Semiparametric Theory and Missing Data_.  Springer, New York, NY.  https://doi.org/10.1007/978-0-387-98135-2
  * van der Laan and Robins (2003) Mark J. van der Laan and James M. Robins. 2003.  _Unified Methods for Censored Longitudinal Data and Causality_.  Springer, New York, NY.  https://doi.org/10.1007/978-0-387-21700-0
  * van der Vaart (2002) Aad van der Vaart. 2002\.  Semiparametric Statistics. In _Lectures on probability theory and statistics_ _(Lecture notes in mathematics, 1781)_ , Pierre Bernard (Ed.). Springer, Berlin.  https://doi.org/10.1007/b93152
  * VanderWeele and Robinson (2014) Tyler J. VanderWeele and Whitney R. Robinson. 2014.  On the causal interpretation of race in regressions adjusting for confounding and mediating variables.  _Epidemiology_ 25, 4 (2014), 473–484.  https://doi.org/10.1097/EDE.0000000000000105
  * Wang et al. (2019) Yixin Wang, Dhanya Sridhar, and David M. Blei. 2019\.  Equal Opportunity and Affirmative Action via Counterfactual Predictions.  (2019).  arXiv:1905.10870 http://arxiv.org/abs/1905.10870
  * Woodworth et al. (2017) Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. 2017.  Learning Non-Discriminatory Predictors. In _Proceedings of the 2017 Conference on Learning Theory_ _(Proceedings of Machine Learning Research, Vol. 65)_ , Satyen Kale and Ohad Shamir (Eds.). PMLR, Amsterdam, Netherlands, 1920–1953.  http://proceedings.mlr.press/v65/woodworth17a.html
  * Zafar et al. (2017) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. 2017.  Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment. In _Proceedings of the 26th International Conference on World Wide Web_ (Perth, Australia) _(WWW ’17)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1171–1180.  https://doi.org/10.1145/3038912.3052660
  * Zhang and Bareinboim (2018) Junzhe Zhang and Elias Bareinboim. 2018.  Fairness in Decision-Making – The Causal Explanation Formula. In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence_ (New Orleans, LA, 2018). Association for the Advancement of Artificial Intelligence, 2037–2045.  https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16949/15911
  * Zheng and van der Laan, Mark (2010) Wenjing Zheng and van der Laan, Mark. 2010.  Asymptotic Theory for Cross-validated Targeted Maximum Likelihood Estimation.  _U.C. Berkeley Division of Biostatistics Working Paper Series_ Working Paper 273 (2010).  https://biostats.bepress.com/ucbbiostat/paper273/

##  Appendix A Proofs of propositions

For convenience, we restate all our assumptions.

$\displaystyle\text{A1. (Consistency) }\quad Y=DY^{1}+(1-D)Y^{0}$
$\displaystyle\text{A2. (Positivity)
}\qquad\exists\delta\in(0,1):\mathbb{P}(\pi(A,X,S)\leq 1-\delta)=1$
$\displaystyle\text{A3. (Ignorability) }\,\quad
Y^{0}\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}D\mid A,X,S$ A4. (Bounded propensity
estimator) $\displaystyle\quad\quad\exists\gamma\in(0,1)\text{ s.t.
}\mathbb{P}(\widehat{\pi}(A,X,S)\leq 1-\gamma)=1$ A5. (Nuisance estimator
consistency)
$\displaystyle\quad\quad\|\widehat{\mu}_{0}-\mu_{0}\|=o_{\mathbb{P}}(1),\\-\
\|\widehat{\pi}-\pi\|=o_{\mathbb{P}}(1)$ A6. (Nuisance estimator rates).
$\displaystyle\quad\quad\|\widehat{\mu}_{0}-\mu_{0}\|\|\widehat{\pi}-\pi\|=o_{\mathbb{P}}(1/\sqrt{n})$

### Proof of Proposition 1 (Identification of error rates for input predictor
$S$)

###### Proof.

$\displaystyle\operatorname{cFPR}(S,a)$ $\displaystyle=\mathbb{P}(S=1\mid
Y^{0}=0,A=a)$
$\displaystyle=\frac{\mathbb{P}(S=1,Y^{0}=0,A=a)}{\mathbb{P}(Y^{0}=0,A=a)}$
$\displaystyle=\frac{\mathbb{E}[S(1-Y^{0})\mathbbold{1}\\{A=a\\}]}{\mathbb{E}[(1-Y^{0})\mathbbold{1}\\{A=a\\}]}$
$\displaystyle=\frac{\mathbb{E}[S(1-\mathbb{E}[Y^{0}\mid
A,X,S,D=0)]\mathbbold{1}\\{A=a\\}}{\mathbb{E}[(1-\mathbb{E}[Y^{0}\mid
A,X,S,D=0])\mathbbold{1}\\{A=a\\}]}$
$\displaystyle=\frac{\mathbb{E}[S(1-\mu_{0})\mathbbold{1}\\{A=a\\}]}{\mathbb{E}[(1-\mu_{0})\mathbbold{1}\\{A=a\\}]}$
$\displaystyle\operatorname{cFNR}(S,a)$ $\displaystyle=\mathbb{P}(S=0\mid
Y^{0}=1,A=a)$
$\displaystyle=\frac{\mathbb{P}(S=0,Y^{0}=1,A=a)}{\mathbb{P}(Y^{0}=1,A=a)}$
$\displaystyle=\frac{\mathbb{E}[(1-S)Y^{0}\mathbbold{1}\\{A=a\\}]}{\mathbb{E}[Y^{0}\mathbbold{1}\\{A=a\\}]}$
$\displaystyle=\frac{\mathbb{E}[(1-S)\mathbb{E}[Y^{0}\mid
A,X,S,D=0]\mathbbold{1}\\{A=a\\}}{\mathbb{E}[\mathbb{E}[Y^{0}\mid
A,X,S,D=0]\mathbbold{1}\\{A=a\\}]}$
$\displaystyle=\frac{\mathbb{E}[(1-S)\mu_{0}\mathbbold{1}\\{A=a\\}]}{\mathbb{E}[\mu_{0}\mathbbold{1}\\{A=a\\}]}$

The fourth equality in both derivations uses iterated expectation as well as
positivity and ignorability, and the fifth equality uses consistency. ∎

### Proof of Proposition 2 (Identification of the loss and fairness
constraints)

###### Proof.

Considering just the first component of the loss, we have:

$\displaystyle(w^{+})\mathbb{P}(S_{\theta}=1,Y^{0}=0)$
$\displaystyle=(w^{+})\mathbb{E}[S_{\theta}(1-Y^{0})]$
$\displaystyle=(w^{+})\mathbb{E}[\mathbb{E}[S_{\theta}(1-Y^{0})|A,S,X]]$
$\displaystyle=(w^{+})\mathbb{E}\left\\{\mathbb{E}[S_{\theta}|A,S](1-\mathbb{E}[Y^{0}|A,X,S])\right\\}$
$\displaystyle=(w^{+})\mathbb{E}\left\\{\theta_{A,S}(1-\mathbb{E}[Y^{0}|A,X,S,D=0])\right\\}$
$\displaystyle=(w^{+})\mathbb{E}\left\\{\theta_{A,S}(1-\mu_{0})\right\\}$

where the third equality uses that $S_{\theta}$ only depends on $(A,S)$, the
fourth uses the definition of $\theta_{A,S}$ and ignorability, and the fifth
uses consistency. Similar reasoning shows that
$(w^{-})\mathbb{P}(S=0,Y^{0}=1)=(w^{-})\mathbb{E}\left\\{(1-\theta_{A,S})\mu_{0}\right\\}$.
Combining these, we have

$\displaystyle\mathcal{L}(S_{\theta}):$
$\displaystyle=w^{+}\mathbb{P}(S=1,Y^{0}=0)+w^{-}\mathbb{P}(S=0,Y^{0}=1)$
$\displaystyle=\mathbb{E}[\theta_{A,S}(w^{+}-(w^{+}+w^{-})\mu_{0})]+(w^{-})\mathbb{E}[\mu_{0}]$
$\displaystyle=\theta^{T}\beta+(w^{-})\mathbb{E}[\mu_{0}]$

We turn now to the fairness constraints. The error rates of the derived
predictor $S_{\theta}$ depend on the error rates on the input predictor $S$ as
follows. Beginning with $\operatorname{cFPR}(S_{\theta},a)$, we have:

$\displaystyle\mathbb{P}(S_{\theta}=1\mid Y^{0}=0,A=a)=$
$\displaystyle\quad\sum_{s\in\\{0,1\\}}\mathbb{P}(S_{\theta}=1\mid
Y^{0}=0,A=a,S=s)\mathbb{P}(S=s\mid Y^{0}=0,A=a)$ $\displaystyle\\-\ =$
$\displaystyle\quad\sum_{s\in\\{0,1\\}}\mathbb{P}(S_{\theta}=1\mid
A=a,S=s)\mathbb{P}(S=s\mid Y^{0}=0,A=a)$ $\displaystyle\\-\ =$
$\displaystyle\quad\theta_{a,0}(1-\operatorname{cFPR}(S,a))+\theta_{a,1}\operatorname{cFPR}(S,a)$

where the first equality simply involves conditioning on $S$, and the second
equality uses that $S_{\theta}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y^{0}\mid A,S$. In other words, the false
positive rate of $S_{\theta}$ depends only on $\theta$ and the false positive
rate of the input predictor $S$. For the cFNR, by similar reasoning, we have:

$\displaystyle\mathbb{P}(S_{\theta}=0\mid Y^{0}=1,A=a)=$ $\displaystyle\quad
1-\theta_{a,0}(\operatorname{cFNR}(S,a))+\theta_{a,1}(\operatorname{cFNR}(S,a)-1)$

The identification statements in the proposition follow by simply substituting
in the expressions for $\operatorname{cFPR}(S,a),\operatorname{cFNR}(S,a)$
from Proposition 1 and rearranging. ∎

For any function $f(A,X,S)$, it straightforward to show that

$\displaystyle\mathbb{E}[f(A,X,S)\phi]$
$\displaystyle=\mathbb{E}[f(A,X,S)\mu_{0}]$

It follows that the identification results in Propositions 1 and 2 hold when
$\mu_{0}$ is replaced by $\phi$. We utilize this equivalence in the proofs of
Theorems 7 and 11.

##  Appendix B Proofs of Theorems

###  B.1. Theorem 1 (Loss gap)

We first introduce a lemma used in the proof of the theorem. The lemma gives
sufficient conditions under which the optimal value of an estimated convex
program converges at a particular rate $f(n)$ to the optimal value of the
target convex program. It is a adaptation of Theorem 3.5 in Shapiro (1991)
that follows immediately from Theorems 2.1 and 3.4 in that same paper.

###### Lemma 0 (Shapiro, 1991).

Let $\Theta$ be a compact subset of $\mathbb{R}^{k}$. Let $C(\Theta)$ denote
the set of continuous real-valued functions on $\Theta$, with
$\mathscr{L}=C(\Theta)\times\ldots\times C(\Theta)$ the $r$-dimensional
Cartesian product. Let
$\psi(\theta)=\left(\psi_{0},\ldots,\psi_{r}\right)\in\mathscr{L}$ be a vector
of convex functions. Consider the quantity $\alpha^{*}$ defined as the
solution to the following convex optimization program:

$\displaystyle\alpha^{*}=\min_{\theta\in\Theta}\quad$
$\displaystyle\psi_{0}(\theta)$ subject to $\displaystyle\psi_{j}(\theta)\leq
0,\\-\ j=1,\ldots,r$

Assume that Slater’s condition holds, so that there is some $\theta\in\Theta$
for which the inequalities are satisfied and non-affine inequalities are
strictly satisfied, i.e. $\psi_{j}(\theta)<0$ if $\psi_{j}$ is non-affine. Now
consider a sequence of approximating programs, for $n=1,2,\ldots$:

$\displaystyle\widehat{\alpha}_{n}=\min_{\theta\in\Theta}\quad$
$\displaystyle\widehat{\psi}_{0n}(\theta)$ subject to
$\displaystyle\widehat{\psi}_{jn}(\theta)\leq 0,\\-\ j=1,\ldots,r$

with
$\widehat{\psi}_{n}(\theta):=\left(\widehat{\psi}_{0n},\ldots,\widehat{\psi}_{rn}\right)\in\mathscr{L}$.
Assume that $f(n)(\widehat{\psi}_{n}-\psi)$ converges in distribution to a
random element $W\in\mathscr{L}$ for some real-valued function $f(n)$. Then:

$\displaystyle f(n)(\widehat{\alpha}_{n}-\alpha_{0})\rightsquigarrow L$

for a particular random variable $L$. It follows that
$\widehat{\alpha}_{n}-\alpha_{0}=O_{\mathbb{P}}(1/f(n))$.

####  B.1.1. Proof of theorem

We expand the loss by introducing the term
$\widehat{\beta}^{T}\widehat{\theta}$, which is the quantity that is minimized
in the course of computing $\widehat{\theta}$. We proceed by splitting the
loss into two terms and showing that each of those terms is
$O_{\mathbb{P}}(1/f(n))$.

###### Proof.

The loss gap can be expanded as follows:

$\displaystyle\mathcal{L}(S_{\widehat{\theta}})-\mathcal{L}(S_{\theta^{*}})$
$\displaystyle=\beta^{T}\widehat{\theta}-\beta^{T}\mathbf{\theta}^{*}$
$\displaystyle=\underbrace{\left(\beta^{T}\widehat{\theta}-\widehat{\beta}^{T}\widehat{\theta}\right)}_{(1)}+\underbrace{\left(\widehat{\beta}^{T}\widehat{\theta}-\beta^{T}\mathbf{\theta}^{*}\right)}_{(2)}$

For term (1), we have

$\displaystyle\widehat{\theta}^{T}\left(\beta-\widehat{\beta}\right)$
$\displaystyle\leq\|\widehat{\theta}\|\|\beta-\widehat{\beta}\|$
$\displaystyle\leq 2\|\beta-\widehat{\beta}\|$
$\displaystyle=O_{\mathbb{P}}(1/f(n))$

where the first line uses Cauchy-Schwarz, the second line follows from the
fact that $\widehat{\theta}\in[0,1]^{4}$, and the third line follows by
assumption. For term (2), we rely on Lemma 1. Note that we can write

$\displaystyle\mathcal{L}(S_{\theta^{*}})=\min_{\theta\in\Theta}\quad$
$\displaystyle\psi_{0}(\theta)$ subject to $\displaystyle\psi_{j}(\theta)\leq
0,\\-\ j=1,\ldots,4$
$\displaystyle\widehat{\mathcal{L}}(S_{\widehat{\theta}})=\min_{\theta\in\Theta}\quad$
$\displaystyle\widehat{\psi}_{0}(\theta)$ subject to
$\displaystyle\widehat{\psi}_{j}(\theta)\leq 0,\\-\ j=1,\ldots,4$

with $\Theta=[0,1]^{4}$, and
$\psi(\theta)=(\psi_{0}(\theta),\ldots,\psi_{4}(\theta))$ defined by

$\displaystyle\psi(\theta)$ $\displaystyle=(\mathcal{L},\\-\
\Delta^{\scriptscriptstyle+}-\epsilon^{\scriptscriptstyle+},\\-\
-\Delta^{\scriptscriptstyle+}-\epsilon^{\scriptscriptstyle+},\\-\
\Delta^{\scriptscriptstyle-}-\epsilon^{\scriptscriptstyle-},\\-\
-\Delta^{\scriptscriptstyle-}-\epsilon^{\scriptscriptstyle-})$
$\displaystyle\widehat{\psi}(\theta)$
$\displaystyle=(\widehat{\mathcal{L}},\\-\
\widehat{\Delta}^{\scriptscriptstyle+}-\epsilon^{\scriptscriptstyle+},\\-\
-\widehat{\Delta}^{\scriptscriptstyle+}-\epsilon^{\scriptscriptstyle+},\\-\
\widehat{\Delta}^{\scriptscriptstyle-}-\epsilon^{\scriptscriptstyle-},\\-\
-\widehat{\Delta}^{\scriptscriptstyle-}-\epsilon^{\scriptscriptstyle-})$

where for brevity we omit the argument $S_{\theta}$ to $\mathcal{L}$ and the
error rate differences
$\Delta^{\scriptscriptstyle+},\Delta^{\scriptscriptstyle-}$. Since these are
linear programs, Slater’s condition is satisfied. (The LPs are always
feasible, since $(0,0,0,0)$ and $(1,1,1,1)$ are always solutions.) By
assumption, each of the estimators in $\widehat{\psi}(\theta)$ converges at
rate $f(n)$, so $f(n)\left(\widehat{\psi}(\theta)-\psi(\theta)\right)$
converges to some (unknown) random variable. (We rule out pathological cases
in which this does not happen.) Per Lemma 1, it follows that
$\widehat{\beta}^{T}\widehat{\theta}-\beta^{T}\mathbf{\theta}^{*}=\widehat{\mathcal{L}}(S_{\widehat{\theta}})-\mathcal{L}(S_{\theta^{*}})=O_{\mathbb{P}}(1/f(n))$.

The sum of the two terms in the loss gap is therefore also
$O_{\mathbb{P}}(1/f(n))$. ∎

###  B.2. Theorem 2 (Excess unfairness)

The proof relies on the following lemma, as well as the convergence of the
estimated LP coefficient vectors
$\widehat{\beta}^{\scriptscriptstyle+},\widehat{\beta}^{\scriptscriptstyle-}$.
When
$\widehat{\beta}^{\scriptscriptstyle+},\widehat{\beta}^{\scriptscriptstyle-}$
are close to $\beta^{\scriptscriptstyle+},\beta^{\scriptscriptstyle-}$, the
excess unfairness must be small for any $\theta\in\Theta=[0,1]^{4}$, including
of course $\widehat{\theta}$.

###### Lemma 0.

Let $\xi,W$ be constant vectors and $\widehat{\xi}_{n},\widehat{W}_{n}$ be
random vectors, with $\|\xi-\widehat{\xi}_{n}\|=O_{\mathbb{P}}(1/f(n))$ for
some real-valued $f(n)$. If, for all $M>0$,
$\mathbb{P}(\|W-\widehat{W}_{n}\|>M)\leq\mathbb{P}(\|\xi-\widehat{\xi}_{n}\|>CM)$
for some constant $C$, then $\|W-\widehat{W}_{n}\|=O_{\mathbb{P}}(1/f(n))$.

###### Proof.

For any $\epsilon>0$, there exists some $M_{\epsilon}>0$ such that
$\mathbb{P}(f(n)\|\xi-\widehat{\xi}_{n}\|>M_{\epsilon})<\epsilon$ for all $n$
large enough. Set $M=M_{\epsilon}/C$. Then
$\mathbb{P}(f(n)\|W-\widehat{W}_{n}\|>M)<\epsilon$ for all $n$ large enough. ∎

####  B.2.1. Proof of theorem

###### Proof.

Fix $\delta\in(0,1)$. We have

$\displaystyle\mathbb{P}\left(\operatorname{UF}^{\scriptscriptstyle+}(S_{\widehat{\theta}})>\delta\text{
or
}\operatorname{UF}^{\scriptscriptstyle-}(S_{\widehat{\theta}})>\delta\right)$
$\displaystyle\leq\mathbb{P}\Big{(}|\theta^{T}\beta^{\scriptscriptstyle+}|-|\theta^{T}\widehat{\beta}^{\scriptscriptstyle+}|>\delta\text{
or
}|\theta^{T}\beta^{\scriptscriptstyle-}|-|\theta^{T}\widehat{\beta}^{\scriptscriptstyle-}|>\delta$
$\displaystyle\hskip 170.00026pt\text{ for some }\theta\in[0,1]^{4}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}|\theta^{T}\beta^{\scriptscriptstyle+}-\theta^{T}\widehat{\beta}^{\scriptscriptstyle+}|>\delta\text{
or
}|\theta^{T}\beta^{\scriptscriptstyle-}-\theta^{T}\widehat{\beta}^{\scriptscriptstyle-}|>\delta$
$\displaystyle\hskip 170.00026pt\text{ for some }\theta\in[0,1]^{4}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\|\theta\|\cdot\|\widehat{\beta^{\scriptscriptstyle+}}-\beta^{\scriptscriptstyle+}\|>\delta\text{
or
}\|\theta\|\cdot\|\widehat{\beta^{\scriptscriptstyle-}}-\beta^{\scriptscriptstyle-}\|>\delta$
$\displaystyle\hskip 170.00026pt\text{ for some }\theta\in[0,1]^{4}\Big{)}$
$\displaystyle\leq\mathbb{P}\left(2\|\widehat{\beta}^{+}-\beta^{\scriptscriptstyle+}\|>\delta\text{
or }2\|\widehat{\beta}^{-}-\beta^{\scriptscriptstyle-}\|>\delta\right)$
$\displaystyle\leq\mathbb{P}\left(2\|\widehat{\beta}^{+}-\beta^{\scriptscriptstyle+}\|>\delta\right)+\mathbb{P}\left(2\|\widehat{\beta}^{-}-\beta^{\scriptscriptstyle-}\|>\delta\right)$
$\displaystyle=\mathbb{P}\left(\|\widehat{\beta}^{+}-\beta^{\scriptscriptstyle+}\|>\delta/2\right)+\mathbb{P}\left(\|\widehat{\beta}^{-}-\beta^{\scriptscriptstyle-}\|>\delta/2\right)$

where the third inequality uses Cauchy-Schwartz, the fourth uses that
$\theta\in[0,1]^{4}\implies\|\theta\|\leq 2$, and the fifth uses the union
bound. The reasoning in the first inequality is as follows: if
$\operatorname{UF}^{\scriptscriptstyle+}(S_{\widehat{\theta}})>\delta$, then
$|\widehat{\theta}^{T}\beta^{\scriptscriptstyle+}|-|\widehat{\theta}^{T}\widehat{\beta}^{\scriptscriptstyle+}|>\delta$,
since
$\widehat{\theta}^{T}\widehat{\beta}^{\scriptscriptstyle+}\leq\epsilon^{\scriptscriptstyle+}$
by construction. A necessary condition, then, is that
$|\theta^{T}\beta^{\scriptscriptstyle+}|-|\theta^{T}\widehat{\beta}^{\scriptscriptstyle+}|>\delta$
for some $\theta\in[0,1]^{4}$.

Since $\widehat{\beta}^{\scriptscriptstyle+}$ and
$\widehat{\beta}^{\scriptscriptstyle-}$ are consistent at rate $f(n)$ by
assumption, it follows from Lemma 2 that

$\displaystyle\max\left\\{\operatorname{UF}^{\scriptscriptstyle+}(S_{\widehat{\theta}}),\operatorname{UF}^{\scriptscriptstyle-}(S_{\widehat{\theta}})\right\\}=O_{\mathbb{P}}(1/f(n))$

∎

###  B.3. Theorem 7 (Double robustness.)

Recall that $\mathbb{P}_{n}(f(Z))=n^{-1}\sum_{i=1}^{n}f(Z_{i})$ denotes the
sample average of any fixed function $f:\mathcal{Z}\mapsto\mathbb{R}$. In this
proof and the proof of Theorem 11, we let $\mathbb{P}(f)=\int
f(z)d\mathbb{P}(z)$ denote the expected value of a fixed function $f(Z)$ with
respect to $Z$. For example,
$\mathbb{P}(\widehat{\phi})=\int\widehat{\phi}(z)d\mathbb{P}(z)$ is the
expected value of $\widehat{\phi}(Z)$ conditional on the sample used to
construct $\widehat{\phi}$.

The proofs of each of these theorems utilize the following two lemmas.

###### Lemma 0.

Let $W$ be a function of (at most) $A,X,S$ such that $\|W\|\leq M<\infty$ for
some $M$. Suppose that
$\|\widehat{\mu}_{0}-\mu_{0}\|\|\widehat{\pi}-\pi\|=O_{\mathbb{P}}(g(n))$ for
some function $g(n)$. Then, under assumption A4 (bounded propensity
estimator),

$\displaystyle\mathbb{P}\left(W(\widehat{\phi}-\phi)\right)=O_{\mathbb{P}}(g(n))$

###### Proof.

$\displaystyle\mathbb{P}\left(W(\widehat{\phi}-\phi)\right)$
$\displaystyle=\mathbb{P}\left(W\left(\frac{1-D}{1-\widehat{\pi}}(Y-\widehat{\mu}_{0})+\widehat{\mu}_{0}-\frac{1-D}{1-\pi}(Y-\mu_{0})-\mu_{0}\right)\right)$
$\displaystyle=\mathbb{P}\left(W\left(\frac{1-D}{1-\widehat{\pi}}(\mu_{0}-\widehat{\mu}_{0})+\widehat{\mu}_{0}-\frac{1-D}{1-\pi}(\mu_{0}-\mu_{0})-\mu_{0}\right)\right)$
$\displaystyle=\mathbb{P}\left(W\left(\frac{1-\pi}{1-\widehat{\pi}}(\mu_{0}-\widehat{\mu}_{0})+\widehat{\mu}_{0}-\mu_{0}\right)\right)$
$\displaystyle=\mathbb{P}\left(W\left(\frac{(\mu_{0}-\widehat{\mu}_{0})(\widehat{\pi}-\pi)}{1-\widehat{\pi}}\right)\right)$
$\displaystyle\leq\frac{1}{\gamma}\mathbb{P}(W(\mu_{0}-\widehat{\mu}_{0})(\widehat{\pi}-\pi))$
$\displaystyle\leq\frac{1}{\gamma}\|W\|\|\mu_{0}-\widehat{\mu}_{0}\|\|\widehat{\pi}-\pi\|$
$\displaystyle=O_{\mathbb{P}}(g(n))$

where $\gamma$ is the bound on the propensity estimator in assumption A4. The
second and third lines use iterated expectation and consistency; the third
line uses iterated expectation, conditioning on $(A,S)$; the fifth line uses
assumption A4; and the sixth line uses the Cauchy-Schwarz inequality. ∎

The next lemma is a restatement of Lemma 2 in Kennedy et al. (2020).

###### Lemma 0 (Kennedy, 2020).

$\displaystyle(\mathbb{P}_{n}-\mathbb{P})(\widehat{\phi}-\phi)$
$\displaystyle=O_{\mathbb{P}}\left(\frac{\|\widehat{\phi}-\phi\|}{\sqrt{n}}\right)$

####  B.3.1. Proof of the theorem

Recall that in the statement of the theorem, $g(n)$ is the convergence rate of
$\|\mu_{0}-\widehat{\mu}_{0}\|\|\widehat{\pi}-\pi\|$, i.e.
$\|\mu_{0}-\widehat{\mu}_{0}\|\|\widehat{\pi}-\pi\|=O_{\mathbb{P}}(g(n))$.

###### Proof.

Note that for a fixed length vector $v\in\mathbb{R}^{k}$:

$\displaystyle\|\widehat{v}-v\|=O_{\mathbb{P}}(f(n))\iff\widehat{v}_{j}-v_{j}=O_{\mathbb{P}}(f(n)),\\-\
j=1,\ldots k$

It therefore suffices to show that the rate result in the theorem holds for
each component of
$\widehat{\beta},\widehat{\beta}^{\scriptscriptstyle+},\widehat{\beta}^{\scriptscriptstyle-}$.

Starting with $\widehat{\beta}_{a,s}$, a component of $\widehat{\beta}$, we
have the following, by simple addition and subtraction of measures:

$\displaystyle\widehat{\beta}_{a,s}-\beta_{a,s}=$ $\displaystyle\\-\
(\mathbb{P}_{n}-\mathbb{P})\left\\{\mathbbold{1}\\{A=a,S=s\\}(w^{+}-(w^{+}+w^{-})\phi)\right\\}\\-\
+$ $\displaystyle\\-\
(\mathbb{P}_{n}-\mathbb{P})\left\\{\mathbbold{1}\\{A=a,S=s\\}(w^{-}-w^{+})(\widehat{\phi}-\phi)\right\\}\\-\
+$ $\displaystyle\\-\
\mathbb{P}\left\\{\mathbbold{1}\\{A=a,S=s\\}(w^{-}-w^{+})(\widehat{\phi}-\phi)\right\\}$

The first term is $O_{\mathbb{P}}(1/\sqrt{n})$ by the central limit theorem.
The second term is $O_{\mathbb{P}}(g(n)/\sqrt{n})$ by Lemmas 3 and 4. The
third term is $O_{\mathbb{P}}(g(n))$ by Lemma 3. Thus

$\displaystyle\widehat{\beta}_{a,s}-\beta_{a,s}$
$\displaystyle=O_{\mathbb{P}}\left(\max\\{n^{-1/2},g(n)\\}\right)$

and the result therefore holds for $\|\widehat{\beta}-\beta\|$.

We now turn to $\widehat{\beta}^{\scriptscriptstyle+}$ and
$\widehat{\beta}^{\scriptscriptstyle-}$. It suffices to show that the rate
result holds for $\widehat{\operatorname{cFPR}}(S,a)$ and
$\widehat{\operatorname{cFNR}}(S,a)$, for $a\in\\{0,1\\}$. For notational
convenience, let $\gamma_{a}=(1-\phi)\mathbbold{1}\\{A=a\\}$ and
$\widehat{\gamma}_{a}=(1-\widehat{\phi})\mathbbold{1}\\{A=a\\}$. We have

$\displaystyle\widehat{\operatorname{cFPR}}(S,a)-\operatorname{cFPR}(S,a)=\frac{\mathbb{P}_{n}[S\widehat{\gamma}_{a}]}{\mathbb{P}_{n}[\widehat{\gamma}_{a}]}-\frac{\mathbb{P}[S\gamma_{a}]}{\mathbb{P}[\gamma_{a}]}$
$\displaystyle=\frac{\mathbb{P}_{n}[S\widehat{\gamma}_{a}]\mathbb{P}[\gamma_{a}]-\mathbb{P}[S\gamma_{a}]\mathbb{P}_{n}[\widehat{\gamma}_{a}]}{\mathbb{P}_{n}[\widehat{\gamma}_{a}]\mathbb{P}[\gamma_{a}]}$
$\displaystyle=\frac{\mathbb{P}[\gamma_{a}]\Big{(}\mathbb{P}_{n}[S\widehat{\gamma}_{a}]-\mathbb{P}[S\gamma_{a}]\Big{)}-\mathbb{P}[S\gamma_{a}]\Big{(}\mathbb{P}_{n}[\widehat{\gamma}_{a}]-\mathbb{P}[\gamma_{a}]\Big{)}}{\mathbb{P}_{n}[\widehat{\gamma}_{a}]\mathbb{P}[\gamma_{a}]}$
(5)
$\displaystyle=\mathbb{P}_{n}[\widehat{\gamma}_{a}]^{-1}\Big{\\{}\underbrace{\left(\mathbb{P}_{n}[S\widehat{\gamma}_{a}]-\mathbb{P}[S\gamma_{a}]\right)}_{(1)}-\operatorname{cFPR}(S,a)\underbrace{(\mathbb{P}_{n}[\widehat{\gamma}_{a}]-\mathbb{P}[\gamma_{a}])}_{(2)}\Big{\\}}$

The two terms can be expanded as follows:

$\displaystyle(1)$
$\displaystyle=(\mathbb{P}_{n}-\mathbb{P})S\gamma_{a}+(\mathbb{P}_{n}-\mathbb{P})(S(\widehat{\gamma}_{a}-\gamma_{a}))+\mathbb{P}(S(\widehat{\gamma}_{a}-\gamma_{a}))$
$\displaystyle(2)$
$\displaystyle=(\mathbb{P}_{n}-\mathbb{P})\gamma_{a}+(\mathbb{P}_{n}-\mathbb{P})(\widehat{\gamma}_{a}-\gamma_{a})+\mathbb{P}(\widehat{\gamma}_{a}-\gamma_{a})$

Once again, in both these expressions the first term is
$O_{\mathbb{P}}(1/\sqrt{n})$ by the central limit theorem, the second term is
$O_{\mathbb{P}}(g(n)/\sqrt{n})$ by Lemma 4, and the third term is
$O_{\mathbb{P}}(g(n))$. Under assumption A4 (bounded propensity estimator),
$\mathbb{P}_{n}[\widehat{\gamma}_{a}]^{-1}$ is bounded a.s., and
$\operatorname{cFPR}(S,a)$ is always bounded in $[0,1]$. Therefore, we can
rewrite (5) as

(6)
$\displaystyle\mathbb{P}_{n}[\widehat{\gamma}_{a}]^{-1}(\mathbb{P}_{n}-\mathbb{P})\Big{\\{}\big{(}S-\operatorname{cFPR}(S,a)\big{)}\gamma_{a}\Big{\\}}+O_{\mathbb{P}}(g(n))$

This expression is $O_{\mathbb{P}}(\max\\{n^{-1/2},g(n)\\}$ and therefore so
is $\|\widehat{\beta}^{\scriptscriptstyle+}-\beta^{\scriptscriptstyle+}\|$.
The result for $\widehat{\operatorname{cFNR}}(S,a)$, and consequently for
$\|\widehat{\beta}^{\scriptscriptstyle-}-\beta^{\scriptscriptstyle-}\|$,
follows by identical reasoning, with $\gamma_{a}$ redefined as
$\phi\mathbbold{1}\\{A=a\\}$ so that
$\operatorname{cFNR}(S,a)=\mathbb{E}[(1-S)\gamma_{a}]/\mathbb{E}[\gamma_{a}]$.
∎

###  B.4. Theorem 11 (asymptotic normality)

For ease of reference, we reiterate the following quantities defined in the
theorem.

$\displaystyle f_{\theta}$
$\displaystyle=\theta_{A,S}(w^{+}-(w^{+}+w^{-})\phi)+w^{-}\phi$ $\displaystyle
g_{a}$
$\displaystyle=(\theta_{a,1}-\theta_{a,0})\frac{\mathbbold{1}\\{A=a\\}(1-\phi)(S-\operatorname{cFPR}(S,a))}{\mathbb{E}[\mathbbold{1}\\{A=a\\}(1-\phi)]}$
$\displaystyle h_{a}$
$\displaystyle=(\theta_{a,1}-\theta_{a,0})\frac{\mathbbold{1}\\{A=a\\}\phi(S-\operatorname{cFNR}(S,0))}{\mathbb{E}[\mathbbold{1}\\{A=a\\}\phi]}$

Define $\widehat{f}_{\theta},\\-\ \widehat{g}_{a},\\-\ \widehat{h}_{a}$
analogously, substituting $\widehat{\phi},\\-\
\widehat{\operatorname{cFPR}},\\-\ \widehat{\operatorname{cFNR}}$ for $\phi$,
$\operatorname{cFPR},\\-\ \operatorname{cFNR}$.

We first prove the statements for the loss $\mathcal{L}$ and loss change
$\Gamma$. Note that $\mathcal{L}(S_{\theta})=\mathbb{P}[f_{\theta}]$ and
$\widehat{\mathcal{L}}(S_{\theta})=\mathbb{P}_{n}[\widehat{f}_{\theta}]$. By
simple addition and subtraction of measures, we have

$\displaystyle\widehat{\mathcal{L}}(S_{\theta})-\mathcal{L}(S_{\theta})$
$\displaystyle=(\mathbb{P}_{n}-\mathbb{P})f_{\theta}+(\mathbb{P}_{n}-\mathbb{P})(\widehat{f}_{\theta}-f_{\theta})+\mathbb{P}(\widehat{f}_{\theta}-f_{\theta})$

Under assumption A6 (nuisance estimator rates), the third term in this sum is
$o_{\mathbb{P}}(1/\sqrt{n})$ by Lemma 3, and the second term is
$o_{\mathbb{P}}(1/\sqrt{n})$ by Lemmas 3 and 4. We can therefore write

$\displaystyle\widehat{\mathcal{L}}(S_{\theta})-\mathcal{L}(S_{\theta})$
$\displaystyle=(\mathbb{P}_{n}-\mathbb{P})f_{\theta}+o_{\mathbb{P}}(1/\sqrt{n})$

By equivalent reasoning,

$\displaystyle\widehat{\Gamma}(\theta,S)-\Gamma(\theta,S)$
$\displaystyle=(\mathbb{P}_{n}-\mathbb{P})(f_{\theta}-f_{\mathbf{\tilde{\theta}}})+o_{\mathbb{P}}(1/\sqrt{n})$

Therefore, by the central limit theorem,

$\displaystyle\sqrt{n}\left(\widehat{\mathcal{L}}(S_{\theta})-\mathcal{L}(S_{\theta})\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(f_{\theta}\right)\right)$
$\displaystyle\sqrt{n}\left(\widehat{\Gamma}-\Gamma\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(f_{\theta}-f_{\mathbf{\tilde{\theta}}}\right)\right)$

as claimed.

The reasoning for the fairness estimators is virtually identical. Let
$\gamma_{a}=(1-\phi)\mathbbold{1}\\{A=a\\}$ and
$\widehat{\gamma}_{a}=(1-\widehat{\phi})\mathbbold{1}\\{A=a\\}$ as in the
proof of Theorem 7. From equation (6), Proposition 2, and assumption A6
(nuisance estimator rates), we have

$\displaystyle\widehat{\operatorname{cFPR}}(S_{\theta},a)-\operatorname{cFPR}(S_{\theta},a)=$
$\displaystyle\\-\
\mathbb{P}_{n}[\widehat{\gamma}_{a}]^{-1}(\mathbb{P}_{n}-\mathbb{P})\Big{\\{}(\theta_{a,1}-\theta_{a,0})\big{(}S-\operatorname{cFPR}(S,a)\big{)}\gamma_{a}\Big{\\}}+o_{\mathbb{P}}(1/\sqrt{n})$

By the central limit theorem and Slutsky’s theorem,

$\displaystyle\sqrt{n}\left(\widehat{\operatorname{cFPR}}(S_{\theta},a)-\operatorname{cFPR}(S_{\theta},a)\right)\rightsquigarrow
N\left(0,\operatorname{var}\left(g_{a}\right)\right)$

as claimed. The remaining statements follow by equivalent reasoning.

##  Appendix C Sample splitting

A training sample, $\mathcal{D}_{\text{train}}$, is used to estimate
$\widehat{\theta}$, while a separate sample $\mathcal{D}_{\text{test}}$ is
used to estimate the risk and fairness properties of the derived predictor
$S_{\widehat{\theta}}$ conditional on $\widehat{\theta}$. Within each sample,
separate folds are used to estimate the nuisance parameters $\mu_{0}$ and
$\widehat{\pi}$ versus the target parameters.

The following schematic illustrates this procedure. $k$-fold cross fitting can
be used within each sample to recover full sample size efficiency. For
convenience, we suppose that each of the four samples is of size $n$, though
our results require only that each sample is $O(n)$.

$\mathcal{D}_{\text{train}}$
---
$\mathcal{D}_{\text{train}}^{\text{nuis}}$ |  $\mathcal{D}_{\text{train}}^{\text{target}}$
$\underbrace{\hskip 6.79999pt\hphantom{xxxxxxxxxx}}_{\begin{subarray}{c}\\\ \text{\large$\widehat{\mu}_{0},\\-\ \widehat{\pi}$}\end{subarray}}$ | $\underbrace{\hskip 6.79999pt\hphantom{xxxxxxxxxx}}_{\begin{subarray}{c}\\\ \text{\large$\widehat{\theta}$}\end{subarray}}$

$\mathcal{D}_{\text{test}}$
---
$\mathcal{D}_{\text{test}}^{\text{nuis}}$ |  $\mathcal{D}_{\text{test}}^{\text{target}}$
$\underbrace{\hskip 6.79999pt\hphantom{xxxxxxxxxx}}_{\begin{subarray}{c}\\\ \text{\large$\widehat{\mu}_{0},\\-\ \widehat{\pi}$}\end{subarray}}$ | $\underbrace{\hskip 6.79999pt\hphantom{xxxxxxxxxx}}_{\begin{subarray}{c}\\\ \text{\normalsize{Properties of } \large{$S_{\widehat{\theta}}$}}\end{subarray}}$

##  Appendix D Simulations: data generating process

The data generating process used in section 6.1.2 to illustrate Theorems 1 and
2 is as follows, for data $Z=(A,X,S,D,Y^{0},Y^{1},Y)$.

$\displaystyle\mathbb{P}(A=1)$ $\displaystyle=0.3$ $\displaystyle X\mid A$
$\displaystyle\sim\text{N}(A*(1,-0.8,4,2)^{T},I_{4})$
$\displaystyle\mathbb{P}_{\text{pre}}(D=1\mid A,X)$
$\displaystyle=\min\\{0.975,\operatorname{expit}((A,X)^{T}(0.2,-1,1,-1,1))\\}$
$\displaystyle\mathbb{P}_{\text{post}}(D=1\mid A,X,S)$
$\displaystyle=\min\\{0.975,\operatorname{expit}((A,X,S)^{T}(0.2,-1,1,-1,1,1))\\}$
$\displaystyle\mathbb{P}(Y^{0}=1\mid A,X)$
$\displaystyle=\operatorname{expit}((A,X)^{T}(-5,2,-3,4,-5))$
$\displaystyle\mathbb{P}(Y^{1}=1\mid A,X)$
$\displaystyle=\operatorname{expit}((A,X)^{T}(1,-2,3,-4,5))$ $\displaystyle Y$
$\displaystyle=(1-D)Y^{0}+DY^{1}$

where $I_{4}$ denotes the $4\times 4$ identity matrix and N denotes a Gaussian
distribution. The predictor $S(A,X)$ is trained using random forests. The pre-
RAI decision making process doesn’t depend on $S$; the post-RAI process does.

For the simulations used in section 6.1.3 to illustrate fairness-performance
tradeoffs, the distribution is identical except that $\mathbb{P}(Y^{0}=1\mid
A,X)=\operatorname{expit}((A,X)^{T}(-4,0.4,0.6,0.8,-1))$.

##  Appendix E Asymptotic normality of doubly robust estimators

To illustrate Theorem 11, an additional set of simulations was run using the
post-RAI data generating process described above. First, $\theta$ was randomly
set to $(0.74,1.0,0,0.8)$. (Note that solutions to a linear program with a
compact feasible set must occur at an extreme point of the set, so the
presence of 0 and/or 1 in $\widehat{\theta}$ and $\mathbf{\theta}^{*}$ is
virtually guaranteed.) The “true” risk $\mathcal{L}(S_{\theta})$, risk change
$\Gamma(S_{\theta})$, and error rate differences
$\Delta^{\scriptscriptstyle+}(S_{\theta}),\Delta^{\scriptscriptstyle-}(S_{\theta})$
were again computed on a separate validation set of size 500,000, using plugin
estimators with the true $\mu_{0}$. For conciseness, we omit results for
$\widehat{\operatorname{cFPR}}$ and $\widehat{\operatorname{cFNR}}$.

Figures 6 and 7 illustrate results for doubly robust (DR) vs. plugin (PI)
estimators of these quantities, for samples of size 100 to 20,000. Each
vertical line represents a mean $\pm 1$ sd over 500 simulations. Orange
horizontal lines represent the true parameter values (top rows in each figure)
or 0. The top row shows that the doubly robust estimators converge to their
target values. The bottom two rows represent values from the doubly robust and
plugin estimators, transformed by
$\psi(S_{\widehat{\theta}})\mapsto\sqrt{n}(\widehat{\psi}-\psi)$, where
$\widehat{\psi},\psi$ are the relevant estimator and parameter for that
column. These rows illustrate that $\sqrt{n}$-convergence is only guaranteed
for the doubly robust estimators: the scaled values for the doubly robust
estimators do not grow in $n$, while the scaled values for the plugin
estimators begin to diverge (at least for $\widehat{\Gamma}$ and
$\widehat{\Delta}^{\scriptscriptstyle-}$).

Table 2 contains coverage results of 95% confidence intervals for the error
rates, error rate differences, loss, and loss change for the same arbitrary
$S_{\theta}$. The CIs were constructed using sample variances. To ensure that
they did not exceed the bounds of the possible parameter values (i.e. $[0,1]$
for the loss and error rates, $[-1,1]$ for the error rate differences and loss
change), the CIs were constructed using the delta method, via the
transformations $\widehat{\psi}\mapsto\operatorname{logit}(\widehat{\psi})$,
for
$\widehat{\psi}\in\\{\widehat{\operatorname{cFPR}},\widehat{\operatorname{cFNR}},\widehat{\mathcal{L}}\\}$,
or $\widehat{\psi}\mapsto\operatorname{logit}((\widehat{\psi}+1)/2)$, for
$\widehat{\psi}\in\\{\widehat{\Delta}^{\scriptscriptstyle+},\widehat{\Delta}^{\scriptscriptstyle-},\widehat{\Gamma}\\}$.
Nominal coverage is achieved for various quantities at various sample sizes,
but since the coverage guarantees are asymptotic, it is not surprising that it
is not achieved everywhere. Interestingly, the median coverage rate in the
table is 0.95.

A separate set of CIs was computed without using the delta method; those
results did not differ substantially and are therefore omitted here.

Figure 6. Doubly robust (DR) vs. plugin (PI) estimates of the loss and loss change for an arbitrary derived predictor $S_{\theta}$, with $\theta=(0.74,1.0,0,0.8)$, for samples of size 100 to 20,000. Figure 7. Doubly robust (DR) vs. plugin (PI) estimates of the error rate differences for an arbitrary derived predictor $S_{\theta}$, with $\theta=(0.74,1.0,0,0.8)$, for samples of size 100 to 20,000. | 100 | 200 | 500 | 1000 | 5000 | 20000
---|---|---|---|---|---|---
$\widehat{\mathcal{L}}(S_{\theta})$ | 0.98 | 0.92 | 0.87 | 0.84 | 0.84 | 0.85
$\widehat{\Gamma}(S_{\theta})$ | 1.00 | 0.99 | 0.93 | 0.94 | 0.71 | 0.78
$\widehat{\operatorname{cFPR}}(S_{\theta},0)$ | 0.99 | 0.98 | 0.98 | 0.96 | 0.94 | 0.95
$\widehat{\operatorname{cFPR}}(S_{\theta},1)$ | 0.90 | 0.89 | 0.93 | 0.95 | 0.96 | 0.57
$\widehat{\operatorname{cFNR}}(S_{\theta},0)$ | 0.99 | 0.99 | 0.98 | 0.99 | 0.92 | 0.93
$\widehat{\operatorname{cFNR}}(S_{\theta},1)$ | 0.99 | 0.99 | 0.99 | 1.00 | 0.98 | 0.71
$\widehat{\Delta}^{\scriptscriptstyle+}(S_{\theta})$ | 0.98 | 0.98 | 0.97 | 0.99 | 0.97 | 0.92
$\widehat{\Delta}^{\scriptscriptstyle-}(S_{\theta})$ | 0.99 | 1.00 | 0.99 | 0.99 | 0.94 | 0.94