# Fair Sequential Selection Using
Supervised Learning Models

Mohammad Mahdi Khalili
CIS Department
University of Delaware
Newark, DE, USA
<EMAIL_ADDRESS>&Xueru Zhang
CSE Department
Ohio State University
Columbus, OH, USA
<EMAIL_ADDRESS>&Mahed Abroshan
Alan Turing Institute
London, UK
<EMAIL_ADDRESS>
###### Abstract

We consider a selection problem where sequentially arrived applicants apply
for a limited number of positions/jobs. At each time step, a decision maker
accepts or rejects the given applicant using a pre-trained supervised learning
model until all the vacant positions are filled. In this paper, we discuss
whether the fairness notions (e.g., equal opportunity, statistical parity,
etc.) that are commonly used in classification problems are suitable for the
sequential selection problems. In particular, we show that even with a pre-
trained model that satisfies the common fairness notions, the selection
outcomes may still be biased against certain demographic groups. This
observation implies that the fairness notions used in classification problems
are not suitable for a selection problem where the applicants compete for a
limited number of positions. We introduce a new fairness notion, “Equal
Selection (ES),” suitable for sequential selection problems and propose a
post-processing approach to satisfy the ES fairness notion. We also consider a
setting where the applicants have privacy concerns, and the decision maker
only has access to the noisy version of sensitive attributes. In this setting,
we can show that the perfect ES fairness can still be attained under certain
conditions.

##  1 Introduction

Machine learning (ML) techniques have been increasingly used for automated
decision-making in high-stake applications such as criminal justice, loan
application, face recognition surveillance, etc. While the hope is to improve
societal outcomes with these ML models, they may inflict harm by being biased
against certain demographic groups. For example, companies such as IBM,
Amazon, and Microsoft had to stop sales of their face recognition surveillance
technology to the police in summer 2020 because of the significant racial bias
[1, 2]. COMPAS (Correctional Offender Management Profiling for Alternative
Sanctions), a decision support tool widely used by courts across the United
States to predict the recidivism risk of defendants, is biased against African
Americans [3]. In lending, the Apple card application system has shown gender
biases by assigning a lower credit limit to females than their male
counterparts [4].

To measure and remedy the unfairness issues in ML, various fairness notions
have been proposed. They can be roughly classified into two categories [5]: 1)
Individual fairness: it implies that similar individuals should be treated
similarly [6, 7, 8]. 2) Group fairness: it requires that certain statistical
measures to be equal across different groups [9, 10, 11, 12, 13, 14, 15]. In
this work, we mainly focus on the notions of group fairness. We consider a
sequential selection problem where a set of applicants compete for limited
positions and sequentially enter the decision-making system.111Rolling
admission, job application, and award nomination are examples of sequential
selection problems with limited approvals/positions. On the other hand, there
is no competition in the credit card application as the number of approvals is
unlimited.  At each time step, a decision maker accepts or rejects an
applicant until $m$ positions are filled. Each applicant can be either
qualified or unqualified and has some features related to its qualification
state. While applicants’ true qualification states are hidden to the decision
maker, their features are observable. We assume the decision maker has access
to a pre-trained supervised learning model, which maps each applicant’s
features to a predicted qualification state (qualified or unqualified) or a
qualification score indicating the applicant’s likelihood of being qualified.
Decisions are then made based on these qualification states/scores. Note that
this pre-trained model can possibly be biased or satisfy certain group
fairness notions (e.g., equal opportunity, statistical parity, etc.).

To make a fair selection with respect to multiple demographic groups, each
applicant’s group membership (sensitive attribute) is often required. However,
in many scenarios, such information can be applicants’ private information,
and applicants may be concerned about revealing them to the decision maker. As
such, we further consider a scenario where instead of the true sensitive
attribute, each applicant only reveals a noisy version of the sensitive
attribute to the decision maker. We adopt the notion of local differential
privacy [16] to measure the applicant’s privacy. This notion has been widely
used by researchers [17, 18, 19] and has been implemented by Apple, Google,
Uber, etc.

In this paper, we say the decision is fair if the probability that each
position is filled by a qualified applicant from one demographic group is the
same as the probability of filling the position by a qualified applicant from
the other demographic group. We call this notion equal selection (ES). We
first consider the case where the decision maker has access to the applicants’
true sensitive attributes. With no limit on the number of available positions
(i.e., no competition), our problem can be cast as classification, and
statistical parity and equal opportunity constraints are suitable for finding
qualified applicants. However, when the number of acceptances is limited
(e.g., job application, college admission, award nomination), we can show that
the decisions made based on a pre-trained model satisfying statistical parity
or equal opportunity fairness may still result in discrimination against a
demographic group. It implies that the fairness notions (i.e., statistical
parity and equal opportunity) defined for classification problems, are not
suitable for sequential selection problems with the limited number of
acceptances. We then propose a post-processing method by solving a linear
program, which can find a predictor satisfying the ES fairness notion. Our
contributions can be summarized as follows,

  1. 1.

We introduce Equal Selection (ES), a fairness notion suitable for the
sequential selection problems which ensures diversity among the selected
applicants.To the best of our knowledge, this is the first work that studies
the fairness issue in sequential selection problems.

  2. 2.

We show that decisions made based on a pre-trained model satisfying
statistical parity or equal opportunity fairness notion may still lead to an
unfair and undesirable selection outcome. To address this issue, we use the ES
fairness notion and introduce a post-processing approach which solves a linear
program and is applicable to any pre-trained model.

  3. 3.

We also consider a scenario where the applicants have privacy concerns and
only report the differentially private version of sensitive attributes. We
show that the perfect ES fairness is still attainable even when applicants’
sensitive attributes are differentially private.

  4. 4.

The experiments on real-world datasets validate the theoretical results.

Related work. Learning fair supervised machine learning models has been
studied extensively in the literature. In general, there are three main
approaches to finding a fair predictor,

  1. 1.

Pre-processing: remove pre-existing biases by modifying the training datasets
before the training process [20, 21];

  2. 2.

In-processing: impose certain fairness constraint during the training process,
e.g., solve a constrained optimization problem or add a regularizer to the
objective function [22, 23];

  3. 3.

Post-processing: mitigate biases by changing the output of an existing
algorithm [10, 24].

Among fairness constraints, statistical parity, equalized odds, and equal
opportunity have gained an increasing attention in supervised learning. Dwork
et al. [25] studies the relation between individual fairness and statistical
parity. They identify conditions under which individual fairness implies
statistical parity. Hardt et al. in [10] introduce a post-processing algorithm
to find an optimal binary classifier satisfying equal opportunity. Corbett-
Davies et al. [26] consider the classification in criminal justice with the
goal of maximizing public safety subject to a group fairness constraint (e.g.,
statistical parity, equalized odds, etc.). They show that the optimal policy
is in the form of a threshold policy. Cohen et al. [27] design a fair hiring
policy for a scenario where the employer can set various tests for each
candidate and observe a noisy outcome after each test.

There are also works studying both privacy and fairness issues in
classification problems. Cummings et al. in [28] examine the compatibility of
fairness and privacy. They show that it is impossible to train a
differentially private classifier that satisfies the perfect equal opportunity
and is more accurate than a constant classifier. This finding leads to several
works that design differentially private and approximately fair models [29,
30, 31]. For instance, [29] introduces an algorithm to train a differentially
private logistic regression model that is approximately fair. Jagielski et al.
[30] propose a differentially private fair learning method for training an
approximately fair classifier which protects privacy of sensitive attributes.
Mozannar et al. [31] adopt local differential privacy as the privacy notion
and examine the possibility of training a fair classifier given the noisy
sensitive attributes that satisfy local differential privacy. In a similar
line of research, [32, 33, 34] focus on developing fair models using noisy but
not differentially private sensitive attributes. Note that all of the above
works assume that the number of acceptances is unlimited (i.e., no
competition), and every applicant can be selected as long as it is predicted
as qualified.

Our work is closely connected to the literature on selection problems. Unlike
classification problems, the number of acceptances is limited in selection
problems, and an applicant may not be selected even if it is predicted as
qualified. Kleinberg and Raghavan [35] focus on the implicit bias in selection
problems and investigate the importance of the Rooney Rule in the selection
process. They show that this rule effectively improves both the disadvantaged
group’s representation and the decision maker’s utility. Dwork et al. [14]
also study the selection problem but consider individual fairness notion.
Khalili et al. [13] study the compatibility of fairness and privacy in
selection problems. They use the exponential mechanism and show that it is
possible to attain both differential privacy and perfect fairness. Note that
the selection in all of these works is one shot, i.e., the applicant pool is
static, and all the applicants come as a batch but not sequentially.

Fairness in reinforcement learning and online learning is also studied in the
literature. In [36], an algorithm is considered fair if it does not prefer an
action over another if the long-run reward of the latter is higher than the
former. The goal is to learn an optimal long-run policy satisfying such a
requirement. Note that this fairness constraint does not apply to
classification or selection problems. Joseph et al. [37] consider a multi-
armed bandit problem with the following fairness notion: Arm $i$ should be
selected with higher probability than arm $j$ in round $t$ only if arm $i$ has
higher mean reward than arm $j$ in round $t$. This notion is not applicable to
our selection problem with a group fairness notion. Metevier et al. [38] study
an offline multi-armed bandit problem under group fairness notions. However,
their method does not address the fairness issue in selection problems because
their model does not consider the competition among applicants.

The remainder of the paper is organized as follows. We present our model and
introduce the ES fairness in Section 2. We then propose a fair sequential
selection algorithm using pre-trained binary classifiers in Section 3.
Sequential selection problems using qualification scores are studied in
Section 4. We present our numerical experiments in Section 5.

##  2 Model

We consider a sequential selection problem where individuals indexed by
$\mathcal{N}=\\{1,2,3,\ldots\\}$ apply for jobs/tasks in a sequential manner.
At time step $i$, individual $i$ applies for the task/job and either gets
accepted or rejected. The goal of the decision maker is to select $m$
applicants, and s/he continues the process until $m$ applicants get accepted.
Each individual $i$ is characterized by tuple $(X_{i},A_{i},Y_{i})$, where
$Y_{i}\in\\{0,1\\}$ is the hidden state representing whether individual $i$ is
qualified $(Y_{i}=1)$ for the position or not $(Y_{i}=0)$,
$X_{i}\in\mathcal{X}$ is the observable feature vector, and
$A_{i}\in\\{0,1\\}$ is the sensitive attribute (e.g., gender) that
distinguishes an individual’s group identity. In this paper, we present our
results for a case where $m=1$. The result can be generalized to $m>1$ by
repeating the same process for $m$ times. We assume tuples
$(X_{i},A_{i},Y_{i}),i=1,2,\ldots$ are i.i.d. random variables following
distribution $f_{X,A,Y}(x,a,y)$. For the notational convenience, we sometimes
drop index $i$ and use tuple $(X,A,Y)$, which has the same distribution as
$(X_{i},A_{i},Y_{i}),i=1,2,\ldots$.

Pre-trained supervised learning model. We assume the decision maker has access
to a pre-trained supervised learning model
$r:\mathcal{X}\times\\{0,1\\}\to\mathcal{R}\subseteq[0,1]$ that maps
$(X_{i},A_{i})$ to $R_{i}=r(X_{i},A_{i})$, i.e., the predicted qualification
state or the qualification score indicating the likelihood of being qualified.
In particular, if $\mathcal{R}=\\{0,1\\}$, then $r(\cdot,\cdot)$ is a binary
classifier and $R_{i}=0$ (resp. $R_{i}=1$) implies that applicant $i$ is
predicted as unqualified (resp. qualified); if $\mathcal{R}\neq\\{0,1\\}$,
then $R_{i}=r(X_{i},A_{i})$ indicates the qualification score and a higher
$R_{i}$ implies that the individual is more likely to be qualified.

Selection Procedure. At time step $i$, an applicant with feature vector
$X_{i}$ and sensitive attribute $A_{i}$ arrives, and the decision maker uses
the output of supervised learning model $r(X_{i},A_{i})$ to select or reject
the individual. If $r(\cdot,\cdot)$ is a binary classifier (i.e.,
$\mathcal{R}=\\{0,1\\}$), then the decision maker selects applicant $i$ if
$r(X_{i},A_{i})=1$ and rejects otherwise. If $\mathcal{R}\neq\\{0,1\\}$, then
$r(X_{i},A_{i})$ indicates the likelihood of $i$ being qualified and the
decision maker uses threshold $\tau\in[0,1]$ to accept/reject the applicant,
i.e., accept applicant $i$ if $r(X_{i},A_{i})\geq\tau$.

Fairness Metric. Based on sensitive attribute $A$, the applicants can be
divided into two demographic groups. We shall focus on group fairness. Before
introducing our algorithm for fair sequential selection, we first define the
fairness notion in our setting.

In general, when there is no competition, the fairness notion used in
classification problems (e.g., Statistical Parity (SP) [25] and Equal
Opportunity (EO) [10]) can improve fairness. However, in our selection
problem, where the number of positions is limited, those fairness notions
should be adjusted. In particular, as we will see throughout this paper, the
decision maker may reject all the applicants from a demographic group while
satisfying SP or EO. This shows that EO and SP do not improve diversity among
the selected applicants. This motivates us to propose the following fairness
notion for (sequential) selection problems, which improves diversity among the
selected applicants.

######  Definition 1 (Equalized Selection (ES)).

Let $\mathscr{M}:\mathcal{X}\times\\{0,1\\}\to\\{0,1\\}$ be an algorithm used
by a decision maker at every time step to reject/select an applicant until one
applicant is selected. Let $E_{a}$ denote the event that an applicant with
sensitive attribute $A=a\leavevmode\nobreak\ (a\in\\{0,1\\})$ is selected, and
$\tilde{Y}=1$ (resp. $\tilde{Y}=0$) the event that a qualified (resp.
unqualified) applicant is selected under $\mathscr{M}(\cdot)$. Then the
selection algorithm $\mathscr{M}(\cdot)$ satisfies Equal Selection
(ES)222Similar to EO fairness in classifications, ES fairness only concerns
the equity among the qualified applicants. If the qualification of selected
applicants doesn’t matter, we can consider $\Pr\\{E_{0}\\}=\Pr\\{E_{1}\\}$ as
the fairness notion. While our paper focuses on the notion in Equation (1),
all the analysis and results can be extended for
$\Pr\\{E_{0}\\}=\Pr\\{E_{1}\\}$. See Appendix A.1 for more details. if

$\displaystyle\Pr\\{E_{0},\tilde{Y}=1\\}=\Pr\\{E_{1},\tilde{Y}=1\\}.$ (1)

To compare the ES notion with SP and EO and understand why SP and EO may lead
to undesirable outcomes in a selection problem, consider an example where 100
qualified applicants are competing for three positions. Among them, 90 are
from group 0, while ten are from group 1. Under ES, the probability that each
position is filled with an applicant from group 0 is the same as that from
group 1. Therefore, we expect that the selected applicants are diverse and
coming from both groups. However, neither statistical parity nor equal
opportunity cares about diversity, and they are likely to result in all the
positions being filled by the majority group.

The perfect fairness is satisfied when Equation (1) holds. The ES fairness
notion can also be relaxed to an approximate version as follows.

######  Definition 2 ($\gamma$-Equal Selection).

$\mathscr{M}(\cdot)$ satisfies $\gamma$-Equal Selection ($\gamma$-ES) if

$\displaystyle|\Pr\\{E_{0},\tilde{Y}=1\\}-\Pr\\{E_{1},\tilde{Y}=1\\}|\leq\gamma.$
(2)

Note that $\gamma\in[0,1]$ quantifies the fairness level, the smaller $\gamma$
implies the fairer selection outcome.

Accuracy Metric.  Another goal of the decision maker is to maximize the
probability of selecting a qualified applicant. Therefore, we define the
accuracy of a selection algorithm as follows.

######  Definition 3.

A selection algorithm is $\theta$-accurate if $\Pr(\tilde{Y}=1)=\theta$.

Here, $\theta\in[0,1]$ quantifies the accuracy level, and the larger $\theta$
implies the higher accuracy.

##  3 Fair Selection Using Binary Classifier

###  3.1 Fair selection without privacy guarantee

In this section, we assume that $r(\cdot,\cdot)$ is a binary classifier and
$R_{i}=r(X_{i},A_{i})\in\\{0,1\\}$. At time step $t\in\\{1,2,\ldots\\}$, if
$R_{t}=1$, then individual $t$ is selected and the decision maker stops the
process. Otherwise, the selection process continues until one applicant is
being selected. First, we identify a condition under which the perfect ES
fairness is satisfied.

######  Theorem 1.

When the pre-trained model $r(\cdot,\cdot)$ is a binary classifier, the
perfect ES fairness (1) is satisfied if and only if the following holds,

$\Pr\\{R=1,A=0,Y=1\\}=\Pr\\{R=1,A=1,Y=1\\}.$ (3)

######  Corollary 1.

If the pre-trained binary classifier $r(\cdot,\cdot)$ satisfies Equal
Opportunity fairness defined as $\Pr\\{R=1|Y=1,A=0\\}=\Pr\\{R=1|Y=1,A=1\\}$
[10], then the selection procedure is perfect ES fair if and only if
$\Pr\\{A=0,Y=1\\}=\Pr\\{A=1,Y=1\\}$.

Note that the condition in Corollary 1 generally does not hold. It shows that
equal opportunity (EO) and equal selection (ES) are not compatible with each
other.

ES-Fair Selection Algorithm. We now introduce a post-processing approach to
satisfying ES fairness. Suppose a fair predictor $Z\in\\{0,1\\}$ is used to
accept $(Z=1)$ or reject $(Z=0)$ an applicant. The predictor $Z$ is derived
from sensitive attribute $A$ and the output of pre-trained classifier
$R=r(X,A)$ based on the following conditional probabilities,

$\alpha_{a,\hat{y}}:=\Pr\\{Z=1|A=a,R=\hat{y}\\},\hat{y}\in\\{0,1\\},a\in\\{0,1\\}.$

Therefore, the fair predictor $Z$ can be found by finding four variables
$\alpha_{a,\hat{y}},\hat{y}\in\\{0,1\\},a\in\\{0,1\\}$. We re-write accuracy
$\Pr\\{\tilde{Y}=1\\}$ using variables $\alpha_{a,\hat{y}}$ as follows.

$\displaystyle\Pr\\{\tilde{Y}=1\\}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\infty}\Pr\\{{Z}_{i}=1,Y_{i}=1,\\{{Z}_{j}=0\\}_{j=1}^{i-1}\\}=\sum_{i=1}^{\infty}\Pr\\{Z_{i}=1,Y_{i}=1\\}\prod_{j=1}^{i-1}\Pr\\{Z_{j}=0\\}$
$\displaystyle=$
$\displaystyle\frac{\Pr\\{Z=1,Y=1\\}}{1-\Pr\\{Z=0\\}}=\Pr\\{Y=1|Z=1\\}=\frac{\sum_{\hat{y},a}\alpha_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}{\sum_{\hat{y},a}\alpha_{a,\hat{y}}\cdot\Pr\\{A=a,R=\hat{y}\\}},$

where $\sum_{\hat{y},a}:=\sum_{\hat{y}\in\\{0,1\\},a\in\\{0,1\\}}$. To further
simplify the notations, denote $\sum_{\hat{y}}:=\sum_{\hat{y}\in\\{0,1\\}}$,
$P_{A,R}(a,\hat{y}):=\Pr\\{A=a,R=\hat{y}\\}$ and
$P_{R,Y,A}(\hat{y},y,a):=\Pr\\{R=\hat{y},Y=y,A=a\\}$. Unlike [10], the problem
of finding an optimal ES-fair predictor $Z$, which maximizes the accuracy, is
a non-linear and non-convex problem. This optimization problem can be written
as follows,444In Appendix A.2, we will explain how we can write the ES
fairness constraint in terms of $\alpha_{a,\hat{y}}$.

$\displaystyle\max_{\\{\alpha_{a,\hat{y}}\in[0,1]\\}}$
$\displaystyle\frac{\sum_{\hat{y},a}\alpha_{a,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,a)}{\sum_{\hat{y},a}\alpha_{a,\hat{y}}\cdot
P_{A,R}(a,\hat{y})}$ s.t. $\displaystyle(ES)\leavevmode\nobreak\
\leavevmode\nobreak\ \sum\nolimits_{\hat{y}}\alpha_{0,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,0)=\sum\nolimits_{\hat{y}}\alpha_{1,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,1).$ (4)

Even though (3.1) is a non-convex problem, it can be reduced to a linear
program below and solved efficiently using the simplex method.

######  Theorem 2.

Assume that
$\left[\min\nolimits_{\hat{y}\in\\{0,1\\},a\in\\{0,1\\}}P_{A,R}(a,\hat{y})\right]$
is not zero. Let $\hat{\alpha}_{a,\hat{y}},a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$
be the solution to the following linear problem,

$\displaystyle\max_{\\{\alpha_{a,\hat{y}}\in[0,1]\\}}$
$\displaystyle\sum\nolimits_{\hat{y},a}\alpha_{a,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,a)$ s.t. $\displaystyle(ES)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\sum\nolimits_{\hat{y}}\alpha_{0,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,0)=\sum\nolimits_{\hat{y}}\alpha_{1,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,1),$ (5)
$\displaystyle\sum\nolimits_{\hat{y},a}\alpha_{a,\hat{y}}\cdot
P_{A,R}(a,\hat{y})=\min\nolimits_{\hat{y}\in\\{0,1\\},a\in\\{0,1\\}}P_{A,R}(a,\hat{y}).$

Then, $\hat{\alpha}_{a,\hat{y}},a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ is the
solution to optimization (3.1). If linear program (2) does not have a
solution, then optimization (3.1) has no solution.

Note that the quality (i.e., accuracy) of predictor $Z$ obtained from
optimization problem (2) depends on the quality of predictor $R$. Let $Z^{*}$
be the optimal predictor among all possible predictors satisfying ES fairness
(not among the predictors derived from $(A,R)$). In the next theorem, we
identify conditions under which the accuracy of $Z$ is close to accuracy of
$Z^{*}$.

######  Theorem 3.

If $|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|R=1\\}|\leq\epsilon$ and
$\Pr\\{A=a|Y=1,R=1\\}=\Pr\\{A=a|R=1\\},\forall a\in\\{0,1\\}$, then
$|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|Z=1\\}|\leq\epsilon$.

Note that $\Pr\\{Y=1|Z^{*}=1\\}$ and $\Pr\\{Y=1|Z=1\\}$ are accuracy of
$Z^{*}$ and $Z$, respectively. This theorem implies that under certain
conditions, if the accuracy of pre-trained model $R$ is sufficiently close to
the accuracy of $Z^{*}$, then the accuracy of predictor $Z$ is also close to
the accuracy of $Z^{*}$.

###  3.2 Fair selection using differentially private sensitive attributes

In this section, we assume the applicants have privacy concerns, and their
true sensitive attributes cannot be used directly in the decision-making
process.555Sometimes the decision-maker cannot use the true sensitive
attribute by regulation. Even if there is no regulation, the applicants may be
reluctant to provide the true sensitive attribute. Such a scenario has been
studied before in classification problems [30, 31]. We adopt local
differential privacy [16] as the privacy measure. Let
$\tilde{A}_{i}\in\\{0,1\\}$ be a perturbed version of the true sensitive
attribute $A_{i}$. We say that $\tilde{A}_{i}$ is $\epsilon$-differentially
private if
$\frac{\Pr\\{\tilde{A}_{i}=a|A_{i}=a\\}}{\Pr\\{\tilde{A}_{i}=a|A_{i}=1-a\\}}\leq\exp\\{\epsilon\\},\forall
a\in\\{0,1\\},$ where $\epsilon$ is the privacy parameter and sometimes is
referred to as the privacy leakage, the larger $\epsilon$ implies a weaker
privacy guarantee.

Diffrentially private $\tilde{A}_{i}$ can be generated using the randomized
response algorithm [39], where $\tilde{A}_{i}$ is generated based on the
following distribution,666Note that $\tilde{A}$ is derived purely from $A$. As
a result, $(X,Y)$ and $\tilde{A}$ are conditional independent given $A$.

$\Pr\\{\tilde{A}_{i}=a|A_{i}=a\\}=\frac{e^{\epsilon}}{1+e^{\epsilon}},\leavevmode\nobreak\
\leavevmode\nobreak\
\Pr\\{\tilde{A}_{i}=1-a|A_{i}=a\\}=\frac{1}{1+e^{\epsilon}},\leavevmode\nobreak\
\leavevmode\nobreak\ i\in\\{1,2,\ldots\\}.$ (6)

We assume the decision maker does not know the actual sensitive attribute
$A_{i}$ at time step $i$, but has access to the noisy, differentially private
$\tilde{A}_{i}$ generated using the randomized response algorithm. Hence, the
decision maker aims to find a set of conditional probabilities
$\Pr\\{Z=1|\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\},\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}$
to generate a predictor $Z$ that satisfies the ES fairness constraint.

We show in Lemma 1 that even though the true sensitive attribute ${A}$ is not
known to the decision maker at the time of decision-making, the predictor $Z$
derived from $(r(X,\tilde{A}),\tilde{A})$ and the subsequent selection
procedure can still satisfy the perfect ES fairness. Denote
$P_{A,Y,r(X,\tilde{a})}(a,y,\hat{y}):=\Pr\\{A=a,Y=y,r(X,\tilde{a})=\hat{y}\\}$
and $P_{r(X,\tilde{a})|A}(\hat{y}|a):=\Pr\\{r(X,\tilde{a})=\hat{y}|A=a\\}$ to
simplify notations.

######  Assumption 1.

The true sensitive attributes $A$ are included in the training dataset and are
available for training function $r(\cdot,\cdot)$. Therefore, $\forall
a,\tilde{a},\hat{y},\Pr\\{A=a,Y=1,r(X,\tilde{a})=\hat{y}\\}$ is available
before the decision making process starts. However, sensitive attribute
$A_{i}$ is not available at time step $i$.

######  Lemma 1.

Let
$\beta_{\tilde{a},\hat{y}}=\Pr\\{Z=1|\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}$.
Predictor $Z$ derived from $(r(X,\tilde{A}),\tilde{A})$ satisfies the ES
fairness notion if and only if the following holds,

$\displaystyle\sum\nolimits_{\hat{y}}\beta_{0,\hat{y}}\cdot e^{\epsilon}\cdot
P_{A,Y,r(X,0)}(0,1,\hat{y})+\sum\nolimits_{\hat{y}}\beta_{1,\hat{y}}\cdot
P_{A,Y,r(X,1)}(0,1,\hat{y})$ (7) $\displaystyle=$
$\displaystyle\sum\nolimits_{\hat{y}}\beta_{0,\hat{y}}\cdot
P_{A,Y,r(X,0)}(1,1,\hat{y})+\sum\nolimits_{\hat{y}}\beta_{1,\hat{y}}\cdot
e^{\epsilon}P_{A,Y,r(X,1)}(1,1,\hat{y}).$

A trivial solution satisfying (7) is
$\beta_{\tilde{a},\hat{y}}=0,\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}$, under
which the predictor $Z$ is a constant classifier and assigns 0 to every
applicant, i.e., it rejects all the applicants. It is thus essential to make
sure that constraint (7) has a feasible point other than
$\beta_{\tilde{a},\hat{y}}=0,\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}$. The
following lemma introduces a sufficient condition under which (7) has a non
trivial feasible point.

######  Lemma 2.

There exists a feasible point except
$\beta_{\tilde{a},\hat{y}}=0,\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ that
satisfies (7) if

$\epsilon>\max\nolimits_{a\in\\{0,1\\}}-\ln\Pr\\{R=1,A=a,Y=1\\}.$ (8)

Using Lemma 1, a set of conditional probabilities $\beta_{\tilde{a},\hat{y}}$
for generating the optimal ES-fair predictor $Z$ can be found by the following
optimization problem.

$\displaystyle\max\nolimits_{\\{\beta_{\tilde{a},\hat{y}}\in[0,1]\\}}$
$\displaystyle\Pr\\{\tilde{Y}=1\\}\leavevmode\nobreak\ \leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{ Equation
}\eqref{eq:DPfair}$ (9)

While optimization problem (9) is not a linear optimization (see the proof of
the next theorem in the appendix), the optimal $\beta_{\tilde{a},\hat{y}}$ can
be found by solving the following linear program.

######  Theorem 4.

Assume that $\min\nolimits_{\tilde{a},\hat{y}}[P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})]>0$. Let
$\hat{\beta}_{\tilde{a},\hat{y}},\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ be
the solution to the following optimization problem.

$\displaystyle\max_{\\{\beta_{\tilde{a},\hat{y}}\in[0,1]\\}}$
$\displaystyle\sum\nolimits_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\Big{[}e^{\epsilon}P_{A,Y,r(X,\tilde{a})}(\tilde{a},1,\hat{y})+P_{A,Y,r(X,\tilde{a})}(1-\tilde{a},y,\hat{y})\Big{]}$
s.t.
$\displaystyle\sum\nolimits_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\Big{[}P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})\Big{]}$ (10)
$\displaystyle=\min\nolimits_{\tilde{a},\hat{y}}\Big{[}P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})\Big{]},$
$\displaystyle\mbox{\text{Equation}}\leavevmode\nobreak\
\eqref{eq:DPfair},\hskip 142.26378pt$

where $P_{A}(\tilde{a}):=\Pr\\{A=\tilde{a}\\}$,
$P_{A}(1-\tilde{a}):=\Pr\\{A=1-\tilde{a}\\}$, and
$\sum_{\tilde{a},\hat{y}}:=\sum_{\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}}$.
Then,
$\hat{\beta}_{\tilde{a},\hat{y}},\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ is
the solution to optimization (9). If linear program (4) does not have a
solution, then optimization (9) has no solution neither.

##  4 Selection Using Qualification Score

###  4.1 Fair selection without privacy guarantee

In this section, we consider the case where $\mathcal{R}=[0,1]$ and the
supervised model $r(\cdot,\cdot)$ generates a qualification score, which
indicates an applicant’s likelihood of being qualified. The decision maker
selects/rejects each applicant based on the qualification score. We consider a
common method where the decisions are made based on a threshold rule, i.e.,
selecting an applicant if its qualification score $R=r(X,A)$ is above a
threshold $\tau$. In other words, prediction $Z_{\tau}$ is derived from
$(R,A)$ based on the following,
$Z_{\tau}=\left\\{\begin{array}[]{ll}1&\mbox{if}\leavevmode\nobreak\
R\geq\tau\\\ 0&\mbox{o.w.}\end{array}\right.$. To simplify the notations,
denote $F_{R}(\tau):=\Pr\\{R\leq\tau\\}$,
$F_{R|a}(\tau):=\Pr\\{R\leq\tau|A=a\\}$,
$F_{R|a,y}(\tau):=\Pr\\{R\leq\tau|A=a,Y=y\\}$ and
$P_{A,Y}(a,y):=\Pr\\{A=a,Y=y\\}$. Then we have,

$\displaystyle\Pr\\{E_{a},\tilde{Y}=1\\}=\sum_{i=1}^{\infty}P_{A,Y}(a,1)\cdot(1-F_{R|a,1}(\tau))\cdot(F_{R}(\tau))^{i-1}=\frac{P_{A,Y}(a,1)(1-F_{R|a,1}(\tau))}{1-F_{R}(\tau)}.$

Predictor $Z_{\tau}$ satisfies the ES fairness notion if and only if,

$P_{A,Y}(0,1)\cdot(1-F_{R|0,1}(\tau))=P_{A,Y}(1,1)\cdot(1-F_{R|1,1}(\tau)).$
(11)

Since a threshold $\tau$ that satisfies (11) may not exist, we use group-
dependent thresholds for two demographic groups. Let $\tau_{a}$ be the
threshold used to select an applicant with sensitive attribute $A=a$. Then, ES
fairness holds if and only if the following is satisfied,

$\displaystyle
P_{A,Y}(0,1)\cdot(1-F_{R|0,1}(\tau_{0}))=P_{A,Y}(1,1)\cdot(1-F_{R|1,1}(\tau_{1})).$
(12)

The decision maker aims to find the optimal thresholds for two groups by
maximizing its accuracy subject to fairness constraint (12). Under thresholds
$\tau_{0}$ and $\tau_{1}$, the accuracy is given by,

$\displaystyle\Pr\\{\tilde{Y}=1\\}=\frac{P_{A,Y}(0,1)(1-F_{R|0,1}(\tau_{0}))+P_{A,Y}(1,1)(1-F_{R|1,1}(\tau_{1}))}{1-\eta_{\tau_{0},\tau_{1}}},$

where
$\eta_{\tau_{0},\tau_{1}}=F_{R|0}(\tau_{0})\cdot\Pr\\{A=0\\}+F_{R|1}(\tau_{1})\cdot\Pr\\{A=1\\}$.
To find the optimal $\tau_{0}$ and $\tau_{1}$, the decision maker solves the
following optimization problem,

$\displaystyle\max_{\tau_{a}\in[0,1]}$
$\displaystyle\frac{P_{A,Y}(0,1)(1-F_{R|0,1}(\tau_{0}))+P_{A,Y}(1,1)(1-F_{R|1,1}(\tau_{1}))}{1-\eta_{\tau_{0},\tau_{1}}}$
s.t. $\displaystyle
P_{A,Y}(0,1)(1-F_{R|0,1}(\tau_{0}))=P_{A,Y}(1,1)(1-F_{R|1,1}(\tau_{1})).$ (13)

If $\mathcal{R}=[0,1]$ and the probability density function of $R$ conditional
on $A=a$ and $Y=1$ is strictly positive over $[0,1]$, optimization problem
(4.1) can be easily turned into a one-variable optimization over closed
interval $[0,1]$ and the fairness constraint can be removed (see Appendix A.3
for more details). An optimization problem over a closed-interval can be
solved using the Bayesian optimization approach [40]. In Appendix A.3, we
further consider a special case when $R|A,Y$ is uniformly distributed and find
the closed form of the optimal thresholds.

When score $R$ is discrete (i.e.,
$\mathcal{R}=\\{\rho_{1},\ldots,\rho_{n^{\prime}}\\}$), optimization problem
(4.1) can also be solved easily using exhaustive search with the time
complexity of $\mathcal{O}((n^{\prime})^{2})$.

Next, we show that maximizing $\Pr\\{\tilde{Y}=1\\}$ subject to the equal
opportunity fairness notion can lead to an undesirable outcome.

######  Theorem 5.

Let $Z$ be the predictor derived by thresholding
$R\in\\{\rho_{1},\ldots,\rho_{n^{\prime}}\\}$ using thresholds
$\tau_{0},\tau_{1}$. Moreover, assume that accuracy (i.e., $\Pr\\{Y=1|Z=1\\}$)
is increasing in $\tau_{0}$ and $\tau_{1}$, and
$\Pr\\{R=\rho_{n^{\prime}}|A=a,Y=1\\}\leq\gamma,\forall a\in\\{0,1\\}$. Then,
under $\gamma$-EO (i.e.,
$|\Pr\\{Z=1|A=0,Y=1\\}-\Pr\\{Z=1|A=1,Y=1\\}|\leq\gamma$), one of the following
pairs of thresholds is fair optimal.

  * •

$\tau_{0}>\rho_{n^{\prime}}$ and $\tau_{1}=\rho_{n^{\prime}}$ (in this case,
$\Pr\\{R\geq\tau_{0}|A=0,Y=1\\}=0$).

  * •

$\tau_{1}>\rho_{n^{\prime}}$ and $\tau_{0}=\rho_{n^{\prime}}$ (in this case,
$\Pr\\{R\geq\tau_{1}|A=1,Y=1\\}=0$).

Theorem 5 implies that under certain conditions, it is optimal to reject all
the applicants from a single demographic group under EO fairness notion. In
other words, the EO fairness cannot improve diversity among the selected
applicants. We can state a similar theorem for the SP fairness notion (See
Appendix A.4).

###  4.2 Fair selection using qualification score and private sensitive
attributes

Similar to Section 3.2, we consider the case where the decision maker uses
differentially private $\tilde{A}$ instead of true sensitive attribute $A$
during the decision-making process. Let $\tilde{Z}$ be the predictor derived
from $r(X,\tilde{A})$ and $\tilde{A}$ according to the following,
$\tilde{Z}=\left\\{\begin{array}[]{ll}1&\mbox{if}\leavevmode\nobreak\
r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{A}}\\\
0&\mbox{o.w.}\end{array}\right.,$ where
$\tilde{\tau}_{\tilde{A}}=\tilde{\tau}_{0}$ if $\tilde{A}=0$, and
$\tilde{\tau}_{\tilde{A}}=\tilde{\tau}_{1}$ otherwise. Lemma 3 introduces a
necessary and sufficient condition under which predictor $\tilde{Z}$ satisfies
the perfect ES fairness. Let
$\overline{F}_{r(X,\tilde{a}),A,Y}(\tilde{\tau}_{\tilde{a}},a,y):=\Pr\\{r(X,\tilde{a})\geq\tilde{\tau}_{\tilde{a}},A=a,Y=y\\}$
and
$\overline{F}_{r(X,\tilde{a}),A}(\tilde{\tau}_{\tilde{a}},a):=\Pr\\{r(X,\tilde{a})\geq\tilde{\tau}_{\tilde{a}},A=a\\}$
and
$\overline{F}_{r(X,\tilde{a}),A,\tilde{A}}(\tilde{\tau}_{\tilde{a}},a,\tilde{a}):=\Pr\\{r(X,\tilde{a})\geq\tilde{\tau}_{\tilde{a}},A=a,\tilde{A}=\tilde{a}\\}$.

######  Lemma 3.

Predictor $\tilde{Z}$ satisfies the perfect ES fairness if and only if
$\tilde{\tau}_{0}$ and $\tilde{\tau}_{1}$ satisfy the following,

$\displaystyle\leavevmode\resizebox{450.96794pt}{}{$e^{\epsilon}\cdot\overline{F}_{r(X,0),A,Y}(\tilde{\tau}_{0},0,1)+\overline{F}_{r(X,1),A,Y}(\tilde{\tau}_{1},0,1)=e^{\epsilon}\cdot\overline{F}_{r(X,1),A,Y}(\tilde{\tau}_{1},1,1)+\overline{F}_{r(X,0),A,Y}(\tilde{\tau}_{0},1,1)$}.$
(14)

Accuracy $\Pr\\{\tilde{Y}=1\\}$ can be written as a function of
$\tilde{\tau}_{0}$ and $\tilde{\tau}_{1}$ (see Section A.5 for details),

$\displaystyle\Pr\\{\tilde{Y}=1\\}$ $\displaystyle=$
$\displaystyle\frac{\Pr\\{\tilde{Z}=1,Y=1\\}}{\Pr\\{\tilde{Z}=1\\}}=\frac{\sum_{a,\tilde{a}}\overline{F}_{r(X,\tilde{a}),A,Y,\tilde{A}}(\tilde{\tau}_{\tilde{a}},a,1,\tilde{a})}{\sum_{a,\tilde{a}}\overline{F}_{r(X,\tilde{a}),A,\tilde{A}}(\tilde{\tau}_{\tilde{a}},a,\tilde{a})}$
(15) $\displaystyle=$
$\displaystyle\frac{e^{\epsilon}\sum_{a}\overline{F}_{r(X,{a}),A,Y}(\tilde{\tau}_{{a}},a,1)+\sum_{a}\overline{F}_{r(X,{a}),A,Y}(\tilde{\tau}_{{a}},1-a,1)}{e^{\epsilon}\sum_{a}\overline{F}_{r(X,{a}),A}(\tilde{\tau}_{{a}},a)+\sum_{a}\overline{F}_{r(X,{a}),A}(\tilde{\tau}_{{a}},1-a)},$

where $\sum_{a}:=\sum_{a\in\\{0,1\\}}$ and
$\sum_{a,\tilde{a}}:=\sum_{a,\tilde{a}\in\\{0,1\\}}$. Following Lemma 3, the
optimal thresholds $\tilde{\tau}_{0}$ and $\tilde{\tau}_{1}$ can be found by
maximizing accuracy $\Pr\\{\tilde{Y}=1\\}$ subject to fairness constraint
(14). That is,

$\displaystyle\max\nolimits_{\tilde{\tau}_{0},\tilde{\tau}_{1}}\leavevmode\nobreak\
\leavevmode\nobreak\ \Pr\\{\tilde{Y}=1\\}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\mbox{ Equation }\eqref{eq:DPfair2}.$ (16)

Similar to optimization (4.1), if
$\mathcal{R}=\\{\rho_{1},\rho_{2},\ldots,\rho_{n^{\prime}}\\}$, then solution
to (16) can be found through the exhaustive search with time complexity
$\mathcal{O}((n^{\prime})^{2})$.

##  5 Numerical Example

FICO credit score dataset [41].777The datasets used in this paper do not
include any identifiable information. The codes are available here. FICO
credit scores have been used in the US to determine the creditworthiness of
people. The dataset used in this experiment includes credit scores from four
demographic groups (Asian, White, Hispanic, and Black). Cumulative density
function (CDF) $\Pr(R\leq\tau|A=a)$ and non-default rate $\Pr(Y=1|R=\tau,A=a)$
of each racial group can be calculated from the empirical data (see [10] for
more details). In our experiments, we normalize the credit scores from
[350,850] to [0,100] and focus on applicants from White ($A=0$) and Black
($A=1$) demographic groups. The sample sizes of the white and black groups in
the dataset are 133165 and 18274 respectively. Therefore, we estimate group
representations as $\Pr(A=0)=1-\Pr(A=1)=\frac{133165}{133165+18274}=0.879$.

Figure 1(a) illustrates the CDF of FICO scores of qualified (i.e., non-
default) applicants from White and Black groups. Since
$\Pr\\{R\leq\rho|Y=1,A=0\\}$ is always below $\Pr\\{R\leq\rho|Y=1,A=1\\}$,
black qualified (non-default) applicants are likely to be assigned lower
scores as compared to the white qualified applicants. Therefore, selecting an
applicant based on FICO scores will lead to discrimination against black
people. We consider three fairness notions in our sequential selection
problem: equal opportunity (EO), statistical parity (SP), and equal selection
(ES). We say the selection satisfies $\gamma$-equal opportunity ($\gamma$-EO)
if
$\linebreak\big{|}\Pr\\{R\geq\tau_{0}|A=0,Y=1\\}-\Pr\\{R\geq\tau_{1}|A=1,Y=1\\}\big{|}\leq\gamma.$
Similarly, we say the decision satisfies $\gamma$-SP if
$\big{|}\Pr\\{R\geq\tau_{0}|A=0\\}-\Pr\\{R\geq\tau_{1}|A=1\\}\big{|}\leq\gamma.$

Table 1 summarizes the selection outcomes under ES, SP, and EO. It shows that
the accuracy under EO and SP is almost the same as the accuracy under ES
fairness. However, the probability that a qualified person is selected from
the Black group (i.e., selection rate of Black) under EO and SP is almost
zero. This is because the Black group is the minority group (only $12\%$ of
the applicants are black). This issue can be addressed using ES fairness which
tries to improve diversity.

Table 1: Equal Opportunity (EO) v.s. Statistical Parity (SP) v.s. Equal Selection (ES) Fairness metric | $\tau_{0}$ | $\tau_{1}$ | $\Pr\\{E_{0},\tilde{Y}=1\\}$ | $\Pr\\{E_{1},\tilde{Y}=1\\}$ | Accuracy
---|---|---|---|---|---
0.01-EO | 99.5 | 99.5 | 0.990 | 0 | 0.990
0.001-EO | 99.5 | 99.5 | 0.990 | 0 | 0.990
0.01-SP | 99.5 | 99.5 | 0.990 | 0 | 0.990
0.001-SP | 99.5 | 99.5 | 0.990 | 0 | 0.990
0.01-ES | 98.5 | 84.5 | 0.483 | 0.491 | 0.974
0.001-ES | 98.0 | 65.0 | 0.483 | 0.483 | 0.966

Notice that the optimal thresholds $\tau_{0},\tau_{1}$ in Table 1 are close to
the maximum score 100, especially under EO and SP fairness notions. This is
because in optimization (4.1), we have assumed there is no time constraint for
the decision maker to find a qualified applicant (i.e., infinite time
horizon), and the selection procedure can take a long time. To make the
experiment more practical, we add the following time constraint to
optimization (4.1): the probability that no applicant is selected after 100
time steps should be less than $\frac{1}{2}$, i.e.,

$\displaystyle\Pr\\{\mbox{No one is selected in 100 time
steps}\\}=\big{(}\Pr\\{R<\tau_{A}\\}\big{)}^{100}$ $\displaystyle=$
$\displaystyle\big{(}\Pr\\{A=0\\}\Pr\\{R<\tau_{0}|A=0\\}+\Pr\\{A=1\\}\Pr\\{R<\tau_{1}|A=1\\}\big{)}^{100}\leq
0.5.$ (17)

Table 2 summarizes the results when we add the above condition to (4.1). By
comparing Table 2 with Table 1, we observe that $\Pr\\{E_{1},\tilde{Y}=1\\}$
slightly increases under EO ans SP fairness after adding time constraint (5).
Nonetheless, the probability that a qualified applicant is selected from the
black community under EO ans SP fairness is still close to zero. More
discussions and numerical results about the time constraint are provided in
Appendix A.7.

Table 2: Equal Opportunity (EO) v.s. Statistical Parity (SP) v.s. Equal Selection (ES) after adding time constraint (5) Fairness metric | $\tau_{0}$ | $\tau_{1}$ | $\Pr\\{E_{0},\tilde{Y}=1\\}$ | $\Pr\\{E_{1},\tilde{Y}=1\\}$ | Accuracy
---|---|---|---|---|---
0.01-EO | 98.0 | 97.5 | 0.947 | 0.042 | 0.989
0.001-EO | 98.0 | 97.0 | 0.931 | 0.058 | 0.989
0.01-SP | 98.0 | 98.0 | 0.976 | 0.013 | 0.989
0.001-SP | 98.0 | 94.0 | 0.873 | 0.115 | 0.988
0.01-ES | 98.0 | 65.5 | 0.487 | 0.480 | 0.967
0.001-ES | 98.0 | 65.0 | 0.483 | 0.483 | 0.966

Adult income dataset [42]. Adult income dataset contains the information of
48,842 individuals, each individual has 14 features including gender, age,
education, race, etc. In this experiment, we consider race (White or Black) as
the sensitive attribute. We denote White race by $A=0$ and Black race by
$A=1$. After removing the points with missing values or with the race other
than Black and White, we obtain 41,961 data points, among them 37376 belong to
the White group. For each data point, we convert all the categorical features
to one-hot vectors. In this experiment, we assume the race is individuals’
private information, and we aim to evaluate how performances of different
selection algorithms are affected by the privacy guarantee. The goal of the
decision maker is to select an individual whose annual income is above $\$50K$
and ensure the selection is fair.

We first train a logistic regression classifier (using sklearn package and
default parameters) as the pre-trained model. Then for each privacy parameter
$\epsilon$, we calculate the probability mass function
$P_{\tilde{A}}(\tilde{a})$ using Equation (6). Then, we calculate the joint
probability density $P_{A,Y,r(X,\tilde{a})}({a},1,\hat{y})$ and solve
optimization problem (4) to generate a fair predictor for our sequential
selection problem. Repeating the process for different privacy loss
$\epsilon$, we can find
$\Pr\\{\tilde{Y}=1\\},\Pr\\{E_{0},\tilde{Y}=1\\},\Pr\\{E_{1},\tilde{Y}=1\\}$
as a function of privacy loss $\epsilon$. As a baseline, we compare the
performance of our algorithm with the following scenarios: 1) Equal
opportunity (EO): replace the ES fairness constraint with the EO constraint in
(9) and find the optimal predictor.888See Appendix A.6 for more details about
expressing the EO constraint as a function of $\beta_{\tilde{a},\hat{y}}$. 2)
No fairness constraint (None): remove the fairness constraint in optimization
(9) and find a predictor that maximizes accuracy $\Pr\\{\tilde{Y}=1\\}$.

Figure 1(b) illustrates the accuracy level $\theta=\Pr\\{\tilde{Y}=1\\}$ as a
function of privacy loss $\epsilon$. Based on Lemma 2, optimization problem
(4) has a non-zero solution if $\epsilon$ is larger than a threshold. This is
verified in Figure 1(b). It shows that if $\epsilon\geq 2.7$, then problem (4)
has a non-zero solution. Note that the threshold in Lemma 2 is not tight
because $\max_{a\in\\{0,1\\}}-\ln\Pr\\{R=1,A=a,Y=1\\}=4.9>2.7$. Under ES
fairness, accuracy $\Pr\\{\tilde{Y}=1\\}$ starts to increase at
$\epsilon=2.7$, and it reaches $0.66$ as $\epsilon\to\infty$. Lastly, when
$\epsilon\geq 3$, the accuracy under ES fairness is almost the same as that
under EO or under no fairness constraint.

Figure 1(c) illustrates $\Pr\\{E_{0},\tilde{Y}=1\\}$ and
$\Pr\\{E_{1},\tilde{Y}=1\\}$ as functions of privacy loss. In the case with EO
fairness and the case without a fairness constraint, the selection rate of
black people always remains close to zero. In contrast, under ES fairness, the
available position is filled from Black and White people with the same
probability. Figure 1(d) shows the disparity (i.e.,
$|\Pr\\{E_{0},\tilde{Y}=1\\}-\Pr\\{E_{1},\tilde{Y}=1\\}|$ ). As expected,
disparity remains 0 under ES while it is large in the other cases.

(a)

(b)

(c)

(d)

Figure 1: (a) CDF of FICO scores for non-default applicants from White and
Black groups. (b) Accuracy $\Pr\\{\tilde{Y}=1\\}$ as a function of $\epsilon$
for the adult dataset. (c) $\Pr\\{\tilde{Y}=1,E_{a}\\}$ of each group. (d)
Disparity $\gamma=|\Pr\\{E_{0},\tilde{Y}=1\\}-\Pr\\{E_{1},\tilde{Y}=1\\}|$ as
a function of $\epsilon$.

Limitation and Negative Societal Impact:  1) We made some assumptions to
simplify the problem. For instance, we considered an infinite time horizon and
assumed the individuals can be represented by i.i.d. random variables. 2) The
proposed fairness notion and the results associated with it are only
applicable to our sequential selection problem. This notion may not be
suitable for other scenarios.

## References

  * [1] K. Crockford, “How is face recognition surveillance technology racist?” http://bit.ly/2MWYiBO, 2020.
  * [2] A. Najibi, “Racial discrimination in face recognition technology,” https://bit.ly/39Ps5Fl, 2020.
  * [3] J. Dressel and H. Farid, “The accuracy, fairness, and limits of predicting recidivism,” _Science advances_ , vol. 4, no. 1, p. eaao5580, 2018.
  * [4] N. Vigdor, “Apple card investigated after gender discrimination complaints,” http://nyti.ms/39NPtmx, 2019.
  * [5] X. Zhang and M. Liu, “Fairness in learning-based sequential decision algorithms: A survey,” _arXiv preprint arXiv:2001.04861_ , 2020.
  * [6] A. J. Biega, K. P. Gummadi, and G. Weikum, “Equity of attention: Amortizing individual fairness in rankings,” in _The 41st international acm sigir conference on research & development in information retrieval_, 2018, pp. 405–414.
  * [7] C. Jung, M. Kearns, S. Neel, A. Roth, L. Stapleton, and Z. S. Wu, “Eliciting and enforcing subjective individual fairness,” _arXiv preprint arXiv:1905.10660_ , 2019.
  * [8] S. Gupta and V. Kamble, “Individual fairness in hindsight,” in _Proceedings of the 2019 ACM Conference on Economics and Computation_ , 2019, pp. 805–806.
  * [9] X. Zhang, M. M. Khalili, C. Tekin, and M. Liu, “Group retention when using machine learning in sequential decision making: the interplay between user dynamics and fairness,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 15 243–15 252.
  * [10] M. Hardt, E. Price, and N. Srebro, “Equality of opportunity in supervised learning,” in _Advances in neural information processing systems_ , 2016, pp. 3315–3323.
  * [11] V. Conitzer, R. Freeman, N. Shah, and J. W. Vaughan, “Group fairness for the allocation of indivisible goods,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 1853–1860.
  * [12] X. Zhang, M. M. Khalili, and M. Liu, “Long-term impacts of fair machine learning,” _Ergonomics in Design_ , vol. 28, no. 3, pp. 7–11, 2020.
  * [13] M. M. Khalili, X. Zhang, M. Abroshan, and S. Sojoudi, “Improving fairness and privacy in selection problems,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 9, 2021, pp. 8092–8100.
  * [14] C. Dwork, C. Ilvento, and M. Jagadeesan, “Individual fairness in pipelines,” _arXiv preprint arXiv:2004.05167_ , 2020.
  * [15] X. Zhang, R. Tu, Y. Liu, M. Liu, H. Kjellstrom, K. Zhang, and C. Zhang, “How do fair decisions fare in long-term qualification?” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 18 457–18 469, 2020.
  * [16] B. Bebensee, “Local differential privacy: a tutorial,” _arXiv preprint arXiv:1907.11908_ , 2019.
  * [17] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization.” _Journal of Machine Learning Research_ , vol. 12, no. 3, 2011.
  * [18] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , 2016, pp. 308–318.
  * [19] X. Zhang, M. M. Khalili, and M. Liu, “Improving the privacy and accuracy of admm-based distributed algorithms,” in _International Conference on Machine Learning_ , 2018, pp. 5796–5805.
  * [20] F. Kamiran and T. Calders, “Data preprocessing techniques for classification without discrimination,” _Knowledge and Information Systems_ , vol. 33, no. 1, pp. 1–33, 2012.
  * [21] R. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork, “Learning fair representations,” in _International Conference on Machine Learning_ , 2013, pp. 325–333.
  * [22] A. Agarwal, A. Beygelzimer, M. Dudik, J. Langford, and H. Wallach, “A reductions approach to fair classification,” in _International Conference on Machine Learning_ , 2018, pp. 60–69.
  * [23] M. B. Zafar, I. Valera, M. Gomez-Rodriguez, and K. P. Gummadi, “Fairness constraints: A flexible approach for fair classification.” _Journal of Machine Learning Research_ , vol. 20, no. 75, pp. 1–42, 2019.
  * [24] G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, and K. Q. Weinberger, “On fairness and calibration,” in _Advances in Neural Information Processing Systems 30_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. Curran Associates, Inc., 2017, pp. 5680–5689. [Online]. Available: http://papers.nips.cc/paper/7151-on-fairness-and-calibration.pdf
  * [25] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, “Fairness through awareness,” in _Proceedings of the 3rd innovations in theoretical computer science conference_ , 2012, pp. 214–226.
  * [26] S. Corbett-Davies, E. Pierson, A. Feller, S. Goel, and A. Huq, “Algorithmic decision making and the cost of fairness,” in _Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining_ , 2017, pp. 797–806.
  * [27] L. Cohen, Z. C. Lipton, and Y. Mansour, “Efficient candidate screening under multiple tests and implications for fairness,” in _1st Symposium on Foundations of Responsible Computing (FORC 2020)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [28] R. Cummings, V. Gupta, D. Kimpara, and J. Morgenstern, “On the compatibility of privacy and fairness,” in _Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization_ , 2019, pp. 309–315.
  * [29] D. Xu, S. Yuan, and X. Wu, “Achieving differential privacy and fairness in logistic regression,” in _Companion Proceedings of The 2019 World Wide Web Conference_ , 2019, pp. 594–599.
  * [30] M. Jagielski, M. Kearns, J. Mao, A. Oprea, A. Roth, S. Sharifi-Malvajerdi, and J. Ullman, “Differentially private fair learning,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 3000–3008.
  * [31] H. Mozannar, M. I. Ohannessian, and N. Srebro, “Fair learning with private demographic data,” _arXiv preprint arXiv:2002.11651_ , 2020.
  * [32] S. Wang, W. Guo, H. Narasimhan, A. Cotter, M. Gupta, and M. I. Jordan, “Robust optimization for fairness with noisy protected groups,” _arXiv preprint arXiv:2002.09343_ , 2020.
  * [33] N. Kallus, X. Mao, and A. Zhou, “Assessing algorithmic fairness with unobserved protected class using data combination,” _arXiv preprint arXiv:1906.00285_ , 2019.
  * [34] P. Awasthi, M. Kleindessner, and J. Morgenstern, “Equalized odds postprocessing under imperfect group information,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 1770–1780.
  * [35] J. Kleinberg and M. Raghavan, “Selection problems in the presence of implicit bias,” in _9th Innovations in Theoretical Computer Science Conference (ITCS 2018)_ , vol. 94. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, p. 33.
  * [36] S. Jabbari, M. Joseph, M. Kearns, J. Morgenstern, and A. Roth, “Fairness in reinforcement learning,” in _International Conference on Machine Learning_. PMLR, 2017, pp. 1617–1626.
  * [37] M. Joseph, M. Kearns, J. Morgenstern, and A. Roth, “Fairness in learning: Classic and contextual bandits,” _arXiv preprint arXiv:1605.07139_ , 2016\.
  * [38] B. Metevier, S. Giguere, S. Brockman, A. Kobren, Y. Brun, E. Brunskill, and P. Thomas, “Offline contextual bandits with high probability fairness guarantees,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [39] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” _SIAM Journal on Computing_ , vol. 40, no. 3, pp. 793–826, 2011.
  * [40] P. I. Frazier, “A tutorial on bayesian optimization,” _arXiv preprint arXiv:1807.02811_ , 2018.
  * [41] U. F. Reserve, “Report to the congress on credit scoring and its effects on the availability and affordability of credit,” 2007.
  * [42] R. Kohavi, “Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid.” in _Kdd_ , vol. 96, 1996, pp. 202–207.

##  Appendix A Appendix

###  A.1 On the ES fairness notion

In this paper, we defined the ES fairness notion as follows,

$\Pr\\{E_{0},\tilde{Y}=1\\}=\Pr\\{E_{1},\tilde{Y}=1\\}$

Similarly, we could define another fairness notion as follows,

$\displaystyle\Pr\\{E_{0}\\}=\Pr\\{E_{1}\\}$ (18)

This definition implies that the probability that a position is filled by an
applicant from group $A=0$ should be the same as the probability that the
position is filled by an applicant from group $A=1$. Consider classifier
$R=r(X,A)$. We have,

$\displaystyle\Pr\\{E_{a}\\}=\sum_{i=1}^{\infty}\Pr\\{R_{i}=1,A_{i}=a\\}\Pr\\{R_{i-1}=0\\}\times\cdots\times\Pr\\{R_{1}=0\\}=\frac{\Pr\\{R=1,A=a\\}}{1-\Pr\\{R=0\\}}$

This implies that (18) is satisfied if and only if

$\Pr\\{R=1,A=0\\}=\Pr\\{R=1,A=1\\}.$ (19)

Therefore, if equation (18) is our fairness notion, we should design a
classifier that satisfies (19). This implies that all the results in this
paper can be easily extended to the fairness notion defined in (18).

###  A.2 Deriving the ES constraint in terms of $\alpha_{a,\hat{y}}$

Based on Theorem1, $Z$ satisfies the ES if the following holds,

$\displaystyle\Pr\\{A=0,Z=1,Y=1\\}=\Pr\\{A=1,Z=1,Y=1\\}\implies$
$\displaystyle\sum_{\hat{y}\in\\{0,1\\}}\Pr\\{A=0,Z=1,Y=1,R=\hat{y}\\}=\sum_{\hat{y}\in\\{0,1\\}}\Pr\\{A=1,Z=1,Y=1,R=\hat{y}\\}\implies$
$\displaystyle\sum_{\hat{y}\in\\{0,1\\}}\Pr\\{Z=1,Y=1|A=0,R=\hat{y}\\}\times\Pr\\{A=0,R=\hat{y}\\}=$
$\displaystyle\sum_{\hat{y}\in\\{0,1\\}}\Pr\\{Z=1,Y=1|A=1,R=\hat{y}\\}\times\Pr\\{A=1,R=\hat{y}\\}\implies$
$\displaystyle\sum_{\hat{y}\in\\{0,1\\}}\alpha_{0,\hat{y}}\Pr\\{Y=1|A=0,R=\hat{y}\\}\times\Pr\\{A=0,R=\hat{y}\\}=$
$\displaystyle\sum_{\hat{y}\in\\{0,1\\}}\alpha_{1,\hat{y}}\Pr\\{Y=1|A=1,R=\hat{y}\\}\times\Pr\\{A=1,R=\hat{y}\\}\implies$
$\displaystyle\sum_{\hat{y}\in\\{0,1\\}}\alpha_{0,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,0)=\sum_{\hat{y}\in\\{0,1\\}}\alpha_{1,\hat{y}}\cdot
P_{R,Y,A}(\hat{y},1,1).$

Note that $Z$ and $Y$ are conditionally independent given $A$ and $R$, and we
used this fact in the above derivation.

###  A.3 On the solution to optimization problem (4.1)

In this part, first we show that optimization problem (4.1) can be easily
turned into an optimization problem with one variable. If the probability
density function of $R$ given $A=a$ and $Y=1$ is non-zero and continuous over
interval $[0,1]$, then $F_{R|1,1}(.)$ and $F_{R|0,1}(.)$ are both strictly
increasing and their inverse functions exits. For the notional convenience,
Let $p_{a,y}=P_{A,Y}(a,y)$ and assume $p_{0,1}\leq p_{1,1}$. Then, based on
the constraint presented in (4.1), $\tau_{1}$ can be calculated as a function
of $\tau_{0}$,

$\displaystyle\tau_{1}=F_{R|1,1}^{-1}\left(1-\frac{p_{0,1}}{p_{1,1}}(1-F_{R|0,1}(\tau_{0}))\right),\tau_{0}\in[0,1].$
(20)

Therefore, optimization problem (4.1) can be written as a one-variable
optimization problem in interval [0,1] and can be efficiently solved using the
Bayesian Optimization algorithm [40].

Now we solve optimization problem (4.1) for a case where $R|A=a,Y=1$ follows
the uniform distribution.

Case 1: consider the following scenario,

  * •

$R|A=0,Y=0$ follows $Uniform(0,b_{0})$. 999$Uniform(p,q)$ denotes the uniform
distribution in interval $[p,q]$.

  * •

$R|A=1,Y=0$ follows $Uniform(0,b_{1})$.

  * •

$R|A=0,Y=1$ follows $Uniform(c_{0},1)$.

  * •

$R|A=1,Y=1$ follows $Uniform(c_{1},1)$.

  * •

$c_{0}<b_{0}<1$ and $c_{1}<b_{1}<1$.

Since $b_{0}<1$ and $b_{1}<1$, $\Pr\\{\tilde{Y}=1\\}=1$ if
$\tau_{0}\in[b_{0},1]$ and $\tau_{1}\in[b_{1},1]$. Therefore, the optimal
thresholds satisfies the following,

$\displaystyle p_{0,1}\cdot(1-F_{R|0,1}(\tau_{0}))$ $\displaystyle=$
$\displaystyle p_{1,1}\cdot(1-F_{R|1,1}(\tau_{1})),$ (21) $\displaystyle
p_{0,1}(\frac{1-\tau_{0}}{1-c_{0}})$ $\displaystyle=$ $\displaystyle
p_{1,1}(\frac{1-\tau_{1}}{1-c_{1}}).$ (22)

For instance, if $p_{0,1}\cdot\frac{1-b_{0}}{1-c_{0}}\leq
p_{1,1}\cdot\frac{1-b_{1}}{1-c_{1}}$, then $\tau_{0}=b_{0}$ and
$\tau_{1}=1-\frac{p_{0,1}}{p_{1,1}}\frac{1-c_{1}}{1-c_{0}}$ are the solution
to (4.1).

Case 2: consider the following scenario,

  * •

$R|A=0,Y=0$ follows $Uniform(b_{0},1)$.

  * •

$R|A=1,Y=0$ follows $Uniform(b_{1},1)$.

  * •

$R|A=0,Y=1$ follows $Uniform(c_{0},1)$.

  * •

$R|A=1,Y=1$ follows $Uniform(c_{1},1)$.

  * •

$b_{0}<c_{0}<1$ and $b_{1}<c_{1}<1$.

Without loss of generality, assume that $p_{0,1}\leq p_{1,1}$. Using (21), we
can see that $\tau_{1}$ and $\tau_{0}$ satisfy the following,

$\displaystyle p_{0,1}\frac{1-\tau_{0}}{1-c_{0}}$ $\displaystyle=$
$\displaystyle p_{1,1}\cdot\frac{1-\tau_{1}}{1-c_{1}}\implies$
$\displaystyle\frac{1-\tau_{1}}{1-\tau_{0}}$ $\displaystyle=$
$\displaystyle\frac{p_{0,1}}{p_{1,1}}\frac{1-c_{1}}{1-c_{0}},\tau_{0}\in[c_{0},1],\leavevmode\nobreak\
\tau_{1}\in[c_{1},1].$ (23)

Moreover, we can write $\Pr\\{\tilde{Y}=1\\}$ as follows,

$\displaystyle\Pr\\{\tilde{Y}=1\\}$ $\displaystyle=$
$\displaystyle\frac{p_{0,1}\cdot(\frac{1-\tau_{0}}{1-c_{0}})+p_{1,1}\cdot\frac{1-\tau_{1}}{1-c_{1}}}{p_{0,1}\cdot\frac{1-\tau_{0}}{1-c_{0}}+p_{0,0}\cdot\frac{1-\tau_{0}}{1-b_{0}}+p_{1,0}\cdot\frac{1-\tau_{1}}{1-b_{1}}+p_{1,1}\cdot\frac{1-\tau_{1}}{1-c_{1}}}\implies$
$\displaystyle\Pr\\{\tilde{Y}=1\\}$ $\displaystyle=$
$\displaystyle\frac{p_{0,1}\cdot\frac{1}{1-c_{0}}+p_{1,1}\cdot\frac{1-\tau_{1}}{1-\tau_{0}}\frac{1}{1-c_{1}}}{p_{0,1}\cdot\frac{1}{1-c_{0}}+p_{0,0}\cdot\frac{1}{1-b_{0}}+p_{1,0}\cdot\frac{1-\tau_{1}}{1-\tau_{0}}\frac{1}{1-b_{1}}+p_{1,1}\cdot\frac{1-\tau_{1}}{1-\tau_{0}}\frac{1}{1-c_{1}}}$

Since $\Pr\\{\tilde{Y}=1\\}$ is a function of $\frac{1-\tau_{1}}{1-\tau_{0}}$,
$\tau_{0}$ and $\tau_{1}$ are optimal if they satisfy (23). For instance,
$\tau_{0}=c_{0}$ and $\tau_{1}=1-\frac{p_{0,1}}{p_{1,1}}(1-c_{1})$ are optimal
thresholds.

###  A.4 Restating Theorem 5 for the statistical parity (SP) fairness notion

Here we restate Theorem 5 for the statistical parity. The proof is similar to
the proof of Theorem 5.

######  Theorem 6.

Let $Z$ be the predictor derived by thresholding
$R\in\\{\rho_{1},\ldots,\rho_{n^{\prime}}\\}$ using thresholds
$\tau_{0},\tau_{1}$. Moreover, assume that accuracy (i.e., $\Pr\\{Y=1|Z=1\\}$)
is increasing in $\tau_{0}$ and $\tau_{1}$, and
$\Pr\\{R=\rho_{n^{\prime}}|A=a\\}\leq\gamma,\forall a\\{0,1\\}$. Then, under
$\gamma$-SP (i.e., $|\Pr\\{Z=1|A=0\\}-\Pr\\{Z=1|A=1\\}|\leq\gamma$), one of
the following pairs of thresholds is fair optimal.

  * •

$\tau_{0}>\rho_{n^{\prime}}$ and $\tau_{1}=\rho_{n^{\prime}}$ (in this case,
$\Pr\\{R\geq\tau_{0}|A=0\\}=0$).

  * •

$\tau_{1}>\rho_{n^{\prime}}$ and $\tau_{0}=\rho_{n^{\prime}}$ (in this case,
$\Pr\\{R\geq\tau_{1}|A=1\\}=0$).

###  A.5 Deriving $\Pr\\{\tilde{Y}=1\\}$ in terms of $\tilde{\tau}_{0}$ and
$\tilde{\tau}_{1}$

Note that $(X,Y)$ and $\tilde{A}$ are conditionally independent given $A$.

$\displaystyle\Pr\\{\tilde{Y}=1\\}=\frac{\Pr\\{\tilde{Z}=1,Y=1\\}}{\Pr\\{\tilde{Z}=1\\}}=\frac{\sum_{a,\tilde{a}\in\\{0,1\\}}\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{a}},Y=1,A=a,\tilde{A}=\tilde{a}\\}}{\sum_{a,\tilde{a}\in\\{0,1\\}}\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{a}},A=a,\tilde{A}=\tilde{a}\\}}.$
$\displaystyle\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{{a}},Y=1,A=a,\tilde{A}=a\\}=\Pr\\{A=a\\}\cdot\Pr\\{r(X,a)\geq\tilde{\tau}_{{a}},Y=1,\tilde{A}=a|A=a\\}=$
$\displaystyle\Pr\\{A=a\\}\cdot\Pr\\{r(X,a)\geq\tilde{\tau}_{{a}},Y=1|A=a\\}\cdot\Pr\\{\tilde{A}=a|A=a\\}=\frac{e^{\epsilon}}{1+e^{\epsilon}}\overline{F}_{r(X,{a}),A,Y}(\tilde{\tau}_{{a}},a,1).$

Similarly, we have,

$\displaystyle\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{{a}},Y=1,A=1-a,\tilde{A}=a\\}=\frac{1}{1+e^{\epsilon}}\overline{F}_{r(X,{a}),A,Y}(\tilde{\tau}_{{a}},1-a,1).$
$\displaystyle\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{{a}},A=a,\tilde{A}=a\\}=\frac{e^{\epsilon}}{1+e^{\epsilon}}\overline{F}_{r(X,{a}),A}(\tilde{\tau}_{{a}},a).$
$\displaystyle\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{{a}},A=1-a,\tilde{A}=a\\}=\frac{1}{1+e^{\epsilon}}\overline{F}_{r(X,{a}),A}(\tilde{\tau}_{{a}},1-a).$

As a result,

$\displaystyle\Pr\\{\tilde{Y}=1\\}=\frac{e^{\epsilon}\sum_{a}\overline{F}_{r(X,{a}),A,Y}(\tilde{\tau}_{{a}},a,1)+\sum_{a}\overline{F}_{r(X,{a}),A,Y}(\tilde{\tau}_{{a}},1-a,1)}{e^{\epsilon}\sum_{a}\overline{F}_{r(X,{a}),A}(\tilde{\tau}_{{a}},a)+\sum_{a}\overline{F}_{r(X,{a}),A}(\tilde{\tau}_{{a}},1-a)}.$
(24)

###  A.6 Deriving equal opportunity fairness constraint in terms of
$\beta_{\tilde{a},\hat{y}}$

For the equal opportunity, we have,

$\displaystyle\Pr\\{Z=1|Y=1,A=0\\}=\Pr\\{Z=1|Y=1,A=1\\}.$
$\displaystyle\Pr\\{Z=1|Y=1,A=0\\}=\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1|Y=1,A=0,\tilde{A}=\tilde{a},r(Z,\tilde{A})=\hat{y}\\}\Pr\\{\tilde{A}=\tilde{a},r(Z,\tilde{A})=\hat{y}|Y=1,A=0\\}$
$\displaystyle=\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1|Y=1,A=0,\tilde{A}=\tilde{a},r(Z,\tilde{A})=\hat{y}\\}\Pr\\{\tilde{A}=\tilde{a}|A=0\\}\Pr\\{r(X,\tilde{a})=\hat{y}|Y=1,A=0\\}$
$\displaystyle=\sum_{\hat{y}}\beta_{0,\hat{y}}\frac{e^{\epsilon}}{1+e^{\epsilon}}\Pr\\{r(X,0)=\hat{y}|Y=1,A=0\\}+\sum_{\hat{y}}\beta_{1,\hat{y}}\frac{1}{1+e^{\epsilon}}\Pr\\{r(X,1)=\hat{y}|Y=1,A=0\\}$

Similarly, we have,

$\displaystyle\Pr\\{Z=1|Y=1,A=1\\}=\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1|Y=1,A=1,\tilde{A}=\tilde{a},r(Z,\tilde{A})=\hat{y}\\}\Pr\\{\tilde{A}=\tilde{a},r(Z,\tilde{A})=\hat{y}|Y=1,A=1\\}$
$\displaystyle=\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1|Y=1,A=1,\tilde{A}=\tilde{a},r(Z,\tilde{A})=\hat{y}\\}\Pr\\{\tilde{A}=\tilde{a}|A=1\\}\Pr\\{r(X,\tilde{a})=\hat{y}|Y=1,A=1\\}$
$\displaystyle=\sum_{\hat{y}}\beta_{0,\hat{y}}\frac{1}{1+e^{\epsilon}}\Pr\\{r(X,0)=\hat{y}|Y=1,A=1\\}+\sum_{\hat{y}}\beta_{1,\hat{y}}\frac{e^{\epsilon}}{1+e^{\epsilon}}\Pr\\{r(X,1)=\hat{y}|Y=1,A=1\\}$

Therefore, the equal opportunity fairness notion can be written as follows,

$\displaystyle\sum_{\hat{y}}\beta_{0,\hat{y}}\frac{1}{1+e^{\epsilon}}\Pr\\{r(X,0)=\hat{y}|Y=1,A=1\\}+\sum_{\hat{y}}\beta_{1,\hat{y}}\frac{e^{\epsilon}}{1+e^{\epsilon}}\Pr\\{r(X,1)=\hat{y}|Y=1,A=1\\}$
$\displaystyle=\sum_{\hat{y}}\beta_{1,\hat{y}}\frac{1}{1+e^{\epsilon}}\Pr\\{r(X,1)=\hat{y}|Y=1,A=0\\}+\sum_{\hat{y}}\beta_{0,\hat{y}}\frac{e^{\epsilon}}{1+e^{\epsilon}}\Pr\\{r(X,0)=\hat{y}|Y=1,A=0\\}$

###  A.7 Numerical Experiment

We compared EO and ES fairness notions in Table 2 after adding the following
constraints to (4.1).

$\displaystyle\Pr\\{\mbox{No one is selected in 100 time
steps}\\}=\big{(}\Pr\\{R<\tau_{A}\\}\big{)}^{100}$ $\displaystyle=$
$\displaystyle\big{(}\Pr\\{A=0\\}\Pr\\{R<\tau_{0}|A=0\\}+\Pr\\{A=1\\}\Pr\\{R<\tau_{1}|A=1\\}\big{)}^{100}\leq\psi,$
(25)

where $\psi$ was equal to 0.5 in that experiment. The above condition makes
the experiment more practical and implies that there is a time limit in
selecting an individual/applicant.

In this part, we study the effect of probability $\psi$ on the selection rate
and accuracy. Smaller $\psi$ implies that the time constraint is more strict.
Figure 2(a) illustrates the accuracy as a function of $\psi$. As expected,
smaller $\psi$ worsens the accuracy under EO and ES. However, the parameter
$\psi$ has relatively stronger impact on the accuracy under ES.

Figure 2(b) illustrates $\Pr\\{E_{a},\tilde{Y}=1\\}$ as a function of $\psi$.
It shows that smaller $\psi$ is able to improve the disparity (i.e.,
$\gamma=|\Pr\\{\tilde{Y}=1,E_{0}\\}-\Pr\\{\tilde{Y}=1,E_{1}\\}|$) under EO.

(a) Accuracy as a function $\psi$

(b) $\Pr\\{E_{a},\tilde{Y}=1\\}$ as a function $\psi$

Figure 2: Effect of the time constraint on the accuracy and disparity.

###  A.8 Proofs

###### Theorem1.

$\displaystyle\Pr\\{E_{a},\tilde{Y}=1\\}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\infty}\Pr\\{A_{i}=a,R_{i}=1,Y_{i}=1\\}\times\Pr\\{R_{i-1}=0\\}\times\cdots\times\Pr\\{R_{1}=0\\}$
$\displaystyle=$ $\displaystyle\frac{\Pr\\{A=a,R=1,Y=1\\}}{1-\Pr\\{R=0\\}}$

To ensure that $\Pr\\{E_{0},\tilde{Y}=1\\}=\Pr\\{E_{1},\tilde{Y}=1\\}$, we
must have,

$\displaystyle\Pr\\{E_{0},\tilde{Y}=1\\}=\Pr\\{E_{1},\tilde{Y}=1\\}$
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{\Pr\\{A=0,R=1,Y=1\\}}{1-\Pr\\{R=0\\}}=\frac{\Pr\\{A=1,R=1,Y=1\\}}{1-\Pr\\{R=0\\}}$
$\displaystyle\Leftrightarrow$
$\displaystyle\Pr\\{A=0,R=1,Y=1\\}=\Pr\\{A=1,R=1,Y=1\\}.$

∎

###### Corollary 1.

Suppose the binary classifier $r(\cdot,\cdot)$ satisfies equal opportunity
fairness, i.e., $R$ satisfies the following constraint,

$\Pr\\{R=1|A=0,Y=1\\}=\Pr\\{R=1|A=1,Y=1\\}.$ (26)

Based on Theorem 1, equation (26) implies equation (3) if and only if

$\Pr\\{A=0,Y=1\\}=\Pr\\{A=1,Y=1\\}.$

∎

###### Theorem 2.

Let $\hat{\alpha}_{a,\hat{y}}$ be the solution to (2) and
$\sum_{\hat{y},a}:=\sum_{\hat{y}\in\\{0,1\\},a\in\\{0,1\\}}$. Note that
$\hat{\alpha}_{a,\hat{y}}$ is also a feasible point for (3.1). We prove the
theorem by contradiction. Assume that $\hat{\alpha}_{a,\hat{y}}$ is not the
optimal solution for (3.1). Therefore, there exists
$\overline{\alpha}_{a,\hat{y}},a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ such that,

$\frac{\sum_{\hat{y},a}\overline{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}{\sum_{\hat{y},a}\overline{\alpha}_{a,\hat{y}}\cdot\Pr\\{A=a,R=\hat{y}\\}}>\frac{\sum_{\hat{y},a}\hat{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}{\sum_{\hat{y},a}\hat{\alpha}_{a,\hat{y}}\cdot\Pr\\{A=a,R=\hat{y}\\}}.$

Let $\alpha_{\max}=\max_{a,\hat{y}}\overline{\alpha}_{a,\hat{y}}$.We define
$\tilde{\alpha}_{a,\hat{y}}$ as follows,

$\tilde{\alpha}_{a,\hat{y}}=\frac{\overline{\alpha}_{a,\hat{y}}}{\alpha_{\max}}\frac{\min_{\hat{y},a}\Pr\\{A=a,R=\hat{y}\\}}{\sum_{\hat{y},a}\frac{\overline{\alpha}_{a,\hat{y}}}{\alpha_{\max}}\cdot\Pr\\{A=a,R=\hat{y}\\}}.$
(27)

It is easy to see that
$\tilde{\alpha}_{a,\hat{y}}\in[0,1],a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$, and it
is a feasible point for optimization problem (2). Moreover, we have,

$\displaystyle\frac{\sum_{\hat{y},a}\overline{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}{\sum_{\hat{y},a}\overline{\alpha}_{a,\hat{y}}\cdot\Pr\\{A=a,R=\hat{y}\\}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{\hat{y},a}\tilde{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}{\sum_{\hat{y},a}\tilde{\alpha}_{a,\hat{y}}\cdot\Pr\\{A=a,R=\hat{y}\\}}$
$\displaystyle>$
$\displaystyle\frac{\sum_{\hat{y},a}\hat{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}{\sum_{\hat{y},a}\hat{\alpha}_{a,\hat{y}}\cdot\Pr\\{A=a,R=\hat{y}\\}}.$

Note that since $\tilde{\alpha}_{a,\tilde{y}}$ and
$\tilde{\alpha}_{a,\tilde{y}},a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ are feasible
for problem (2), we conclude that,

${\sum_{\hat{y},a}\tilde{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}}>\sum_{\hat{y},a}\hat{\alpha}_{a,\hat{y}}\cdot\Pr\\{R=\hat{y},Y=1,A=a\\}.$

This implies that $\hat{\alpha}_{a,\hat{y}},a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$
is not optimal for (2). This is a contradiction, and
$\hat{\alpha}_{a,\hat{y}},a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ is the solution
for both (3.1) and (2).

Next, we prove the second part of the theorem.

Proof by contradiction. Assume that optimization problem (2) does not have a
solution, and
$\overline{\alpha}_{a,\hat{y}}\in[0,1],a\in\\{0,1\\},\hat{y}\in\\{0,1\\}$ is
the solution to (3.1). It is easy to see that $\tilde{\alpha}_{a,\hat{y}}$
define in (27) is a feasible point for (2). This is a contradiction because a
linear optimization with a closed and bounded and non-empty feasible set has
an optimal solution. This concludes the proof. ∎

###### Theorem 3.

Let predictor $Z$ be the solution to optimization problem (3.1). Without loss
of generality, suppose $\Pr\\{R=1,Y=1,A=0\\}\leq\Pr\\{R=1,Y=1,A=1\\}$.
Consider the following feasible point of optimization problem (3.1):

$\hat{\alpha}_{00}=0,\hat{\alpha}_{10}=0,\hat{\alpha}_{01}=1,\hat{\alpha}_{11}=\frac{\Pr\\{R=1,Y=1,A=0\\}}{\Pr\\{R=1,Y=1,A=1\\}}.$

Using these parameters, we can derive a new predictor noted as $\hat{Z}$. Note
that $\Pr\\{R=1|\hat{Z}=1\\}=1$ holds. Moreover, Since $\hat{Z}$ is a
suboptimal solution to optimization problem (3.1),
$\Pr\\{Y=1|\hat{Z}=1\\}\leq\Pr\\{Y=1|{Z}=1\\}$ and we have,

$|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|Z=1\\}|\leq|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|\hat{Z}=1\\}|\leq$
$|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|R=1\\}|+|\Pr\\{Y=1|\hat{Z}=1\\}-\Pr\\{Y=1|R=1\\}|\leq$
$\epsilon+|\Pr\\{Y=1|\hat{Z}=1\\}-\Pr\\{Y=1|R=1\\}|.$

Moreover, we have,

$\Pr\\{Y=1|\hat{Z}=1\\}=\Pr\\{Y=1|\hat{Z}=1,R=1\\}\cdot\underbrace{\Pr\\{R=1|\hat{Z}=1\\}}_{1}=\frac{\Pr\\{Y=1|R=1\\}}{\Pr\\{\hat{Z}=1|R=1\\}}\Pr\\{\hat{Z}=1|Y=1,R=1\\},$
$\Pr\\{\hat{Z}=1|R=1\\}=P(A=0|R=1)+P(A=1|R=1)\hat{\alpha}_{11},$

$\Pr\\{\hat{Z}=1|Y=1,R=1\\}=\Pr\\{A=0|Y=1,R=1\\}+\Pr\\{A=1|Y=1,R=1\\}\hat{\alpha}_{11},$

$\implies|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|Z=1\\}|\leq$
$\epsilon+|\Pr\\{Y=1|R=1\\}\underbrace{(1-\frac{\Pr\\{A=0|Y=1,R=1\\}+\Pr\\{A=1|Y=1,R=1\\}\hat{\alpha}_{11}}{P(A=0|R=1)+P(A=1|R=1)\hat{\alpha}_{11}})}_{0}|.$

Since we assumed $\Pr\\{A=a|Y=1,R=1\\}\in\Pr\\{A=a|R=1\\},\forall a\\{0,1\\}$,
the second term in above equation is zero, and the theorem has been proved.

$\implies|\Pr\\{Y=1|Z^{*}=1\\}-\Pr\\{Y=1|Z=1\\}|\leq\epsilon.$

∎

###### Lemma 1.

Based on the Theorem 1, predictor $Z$ satisfies the ES fairness notion if

$\Pr\\{Z=1,A=0,Y=1\\}=\Pr\\{Z=1,A=1,Y=1\\}.$

We use the law of total probability to rewrite the above condition using
$\beta_{a,\hat{y}}$. Note that $\tilde{A}$ is derived directly from $A$ and is
conditionally independent of $(X,Y)$ given $A$. We have,

$\displaystyle\Pr\\{Z=1,A=1,Y=1\\}$ $\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1,\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y},A=1,Y=1\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1|\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y},A=1,Y=1\\}\cdot\Pr\\{\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y},A=1,Y=1\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1|\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}\cdot\Pr\\{\tilde{A}=\tilde{a},r(X,\tilde{a})=\hat{y}|A=1,Y=1\\}\Pr\\{A=1,Y=1\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Pr\\{\tilde{A}=\tilde{a}|A=1,Y=1\\}\Pr\\{r(X,\tilde{a})=\hat{y}|A=1,Y=1\\}\Pr\\{A=1,Y=1\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\frac{\exp\\{\epsilon\cdot\mathbb{I}(\tilde{a}=1)\\}}{1+\exp\\{\epsilon\\}}\Pr\\{r(X,\tilde{a})=\hat{y},A=1,Y=1\\},$

where indicator function $\mathbb{I}(s)=1$ if statement $s$ is true, otherwise
$\mathbb{I}(s)=0$. Similarly, we have,

$\displaystyle\Pr\\{Z=1,A=0,Y=1\\}=\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\frac{\exp\\{\epsilon\cdot\mathbb{I}(\tilde{a}=0)\\}}{1+\exp\\{\epsilon\\}}\Pr\\{r(X,\tilde{a})=\hat{y},A=0,Y=1\\}.$

Therefore, $Z$ satisfies the ES fairness notion if the following holds,

$\displaystyle\Pr\\{Z=1,A=0,Y=1\\}=\Pr\\{Z=1,A=1,Y=1\\}$
$\displaystyle\Leftrightarrow$ $\displaystyle\beta_{0,0}\cdot
e^{\epsilon}\cdot\Pr\\{r(X,0)=0,A=0,Y=1\\}+\beta_{0,1}\cdot
e^{\epsilon}\cdot\Pr\\{r(X,0)=1,A=0,Y=1\\}$
$\displaystyle+\beta_{1,0}\cdot\Pr\\{r(X,1)=0,A=0,Y=1\\}+\beta_{1,1}\cdot\Pr\\{r(X,1)=1,A=0,Y=1\\}$
$\displaystyle=$
$\displaystyle\beta_{0,0}\cdot\Pr\\{r(X,0)=0,A=1,Y=1\\}+\beta_{0,1}\cdot\Pr\\{r(X,0)=1,A=1,Y=1\\}$
$\displaystyle+\beta_{1,0}\cdot e^{\epsilon}\Pr\\{r(X,1)=0,A=1,Y=1\\}\
+\beta_{1,1}\cdot e^{\epsilon}\cdot\Pr\\{r(X,1)=1,A=1,Y=1\\}.$

∎

###### Lemma 2.

We rewrite (A.8) as follows,

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\beta_{0,0}\cdot(e^{\epsilon}\cdot\Pr\\{r(X,0)=0,A=0,Y=1\\}-\Pr\\{r(X,0)=0,A=1,Y=1\\})$
$\displaystyle+\beta_{0,1}\cdot(e^{\epsilon}\cdot\Pr\\{r(X,0)=1,A=0,Y=1\\}-\Pr\\{r(X,0)=1,A=1,Y=1\\})$
$\displaystyle+\beta_{1,0}\cdot(\Pr\\{r(X,1)=0,A=0,Y=1\\}-e^{\epsilon}\Pr\\{r(X,1)=0,A=1,Y=1\\})$
$\displaystyle+\beta_{1,1}\cdot(\Pr\\{r(X,1)=1,A=0,Y=1\\}-e^{\epsilon}\Pr\\{r(X,1)=1,A=1,Y=1\\}).$

If Equation (8) holds, then
$e^{\epsilon}\cdot\Pr\\{r(X,a)=1,A=a,Y=1\\}>1,\forall a\in\\{0,1\\}$.
Therefore,
$(e^{\epsilon}\cdot\Pr\\{r(X,0)=0,A=0,Y=1\\}-\Pr\\{r(X,0)=0,A=1,Y=1\\})$ is a
positive coefficient and
$(\Pr\\{r(X,1)=1,A=0,Y=1\\}-e^{\epsilon}\Pr\\{r(X,1)=1,A=1,Y=1\\})$ is a
negative coefficient. Therefore, above linear equation has a feasible point
other than $\beta_{0,0}=\beta_{0,1}=\beta_{1,0}=\beta_{1,1}=0$. ∎

###### Theorem 4.

First, we find $\Pr\\{\tilde{Y}=1\\}$ as a function of
$\beta_{\tilde{a},\hat{y}}$. We have,

$\displaystyle\Pr\\{\tilde{Y}=1\\}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\infty}\Pr\\{Z_{i}=1,Y_{i}=1\\}\times\Pr\\{Z_{i-1}=0\\}\times\cdots\times\Pr\\{Z_{1}=0\\}$
$\displaystyle=$
$\displaystyle\frac{\Pr\\{Z=1,Y=1\\}}{1-\Pr\\{Z=0\\}}=\frac{\Pr\\{Z=1,Y=1\\}}{\Pr\\{Z=1\\}}=\Pr\\{Y=1|Z=1\\},$
$\displaystyle\Pr\\{Z=1,Y=1\\}$ $\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\Pr\\{Z=1,Y=1|\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}\cdot\Pr\\{\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Pr\\{Y=1|\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}\cdot\Pr\\{\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Pr\\{Y=1,\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y}\\}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Big{(}\Pr\\{Y=1,\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y},A=\tilde{a}\\}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
+\Pr\\{Y=1,\tilde{A}=\tilde{a},r(X,\tilde{A})=\hat{y},A=1-\tilde{a}\\}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Big{(}\Pr\\{\tilde{A}=\tilde{a}|A=\tilde{a}\\}\Pr\\{Y=1,r(X,\tilde{a})=\hat{y}|A=\tilde{a}\\}\Pr\\{A=\tilde{a}\\}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
+\Pr\\{\tilde{A}=\tilde{a}|A=1-\tilde{a}\\}\Pr\\{Y=1,r(X,\tilde{a})=\hat{y}|A=1-\tilde{a}\\}\Pr\\{A=1-\tilde{a}\\}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Big{(}\frac{e^{\epsilon}}{1+e^{\epsilon}}\Pr\\{Y=1,r(X,\tilde{a})=\hat{y}|A=\tilde{a}\\}\Pr\\{A=\tilde{a}\\}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
+\frac{1}{1+e^{\epsilon}}\Pr\\{Y=1,r(X,\tilde{a})=\hat{y}|A=1-\tilde{a}\\}\Pr\\{A=1-\tilde{a}\\}\Big{)}$
$\displaystyle\Pr\\{Z=1\\}$ $\displaystyle=$
$\displaystyle\sum_{\tilde{a},\hat{y}}\beta_{\tilde{a},\hat{y}}\cdot\Big{(}\frac{e^{\epsilon}}{1+e^{\epsilon}}\Pr\\{r(X,\tilde{a})=\hat{y}|A=\tilde{a}\\}\Pr\\{A=\tilde{a}\\}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
+\frac{1}{1+e^{\epsilon}}\Pr\\{r(X,\tilde{a})=\hat{y}|A=1-\tilde{a}\\}\Pr\\{A=1-\tilde{a}\\}\Big{)}.$

We can see that $\Pr\\{\tilde{Y}=1\\}$ is not a linear function in
$\beta_{\tilde{a},\hat{y}}$. As a result, optimization problem (9) is not a
linear program.

Now we prove the first part of the theorem using contradiction. Note that
$\hat{\beta}_{\tilde{a},\hat{y}}$ is a feasible point for optimization problem
(9). If $\hat{\beta}_{\tilde{a},\hat{y}}$ is not optimal for (9), then there
exists $\overline{\beta}_{\tilde{a},\hat{y}}$ such that the objective function
of (9) at $\overline{\beta}_{\tilde{a},\hat{y}}$ is higher than that at
$\hat{\beta}_{\tilde{a},\hat{y}}$. With the similar approach as the proof of
Theorem 1, we can show that the existence of
$\overline{\beta}_{\tilde{a},\hat{y}}$ implies that
$\hat{\beta}_{\tilde{a},\hat{y}}$ is not optimal for (4) because
$\tilde{\beta}_{\tilde{a},\hat{y}}$ defined as follows is feasible and
improves the objective function in (4).

$\tilde{\beta}_{\tilde{a},\hat{y}}=\frac{\overline{\beta}_{\tilde{a},\hat{y}}}{\beta_{\max}}\cdot\frac{\min_{\tilde{a},\hat{y}}P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})}{\sum_{\tilde{a},\hat{y}}\frac{\overline{\beta}_{\tilde{a},\hat{y}}}{\beta_{\max}}\Big{(}P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})\Big{)}},$

where
$\beta_{\max}=\max_{\tilde{a}\in\\{0,1\\},\hat{y}\in\\{0,1\\}}\overline{\beta}_{\tilde{a},\hat{y}}$
and
$P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a}):=\Pr\\{r(X,\tilde{a})=\hat{y}|A=\tilde{a}\\}$,
$P_{A}(\tilde{a}):=\Pr\\{A=\tilde{a}\\}$ are defined to simplify notations.

This contradiction shows that $\hat{\beta}_{\tilde{a},\hat{y}}$ is optimal for
optimization problem (9).

The proof of the second part of the theorem is similar to the first part.
Proof by contradiction. Assume that $\overline{\beta}_{\tilde{a},\hat{y}}$ is
the solution to optimization problem (9), and (4) does not have a solution. In
this case, we can show that $\tilde{\beta}_{\tilde{a},\hat{y}}$ defined as
follows is a feasible point for (4).

$\tilde{\beta}_{\tilde{a},\hat{y}}=\frac{\overline{\beta}_{\tilde{a},\hat{y}}}{\beta_{\max}}\cdot\frac{\min_{\tilde{a},\hat{y}}P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})}{\sum_{\tilde{a},\hat{y}}\frac{\overline{\beta}_{\tilde{a},\hat{y}}}{\beta_{\max}}\Big{(}P_{A}(\tilde{a})\cdot
e^{\epsilon}\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|\tilde{a})+P_{A}(1-\tilde{a})\cdot
P_{r(X,\tilde{a})|A}(\hat{y}|1-\tilde{a})\Big{)}}.$

Since (4) is a linear program and with a bounded and non-empty feasible set,
it has at least a solution. This is a contradiction which proves the second
part of the theorem. ∎

###### Theorem 5.

Note that the assumption that accuracy $\Pr\\{Y=1|Z=1\\}$ is increasing in
$\tau_{0}$ and $\tau_{1}$ implies that an applicant with a higher score is
more likely to be qualified and the policy with a larger threshold leads to
higher accuracy. In other words, under this assumption, the decision-maker
should make thresholds as large as possible to maximize the accuracy. We have,

$\displaystyle\Pr\\{Y=1|Z=1\\}=$
$\displaystyle\Pr\\{Y=1|R\geq\tau_{0},A=0\\}\Pr\\{A=0|Z=1\\}+\Pr\\{Y=1|R\geq\tau_{1},A=1\\}\Pr\\{A=1|Z=1\\}.$

Since $\Pr\\{Y=1|Z=1\\}$ is increasing in thresholds $\tau_{0}$ and
$\tau_{1}$, it is optimal to select $\tau_{0}=\rho_{n^{\prime}}$ and
$\tau_{1}>\rho_{n^{\prime}}$ if
$\Pr\\{Y=1|R=\rho_{n^{\prime}},A=0\\}\geq\Pr\\{Y=1|R=\rho_{n^{\prime}},A=1\\}$.
That is, no one with sensitive attribute $A=1$ is selected, and only an
applicant with sensitive attribute $A=0$ and the highest possible score is
selected. Note that $\tau_{0}$ and $\tau_{1}$ satisfy EO because we assumed
that $\Pr\\{R=\rho_{n^{\prime}}|A=a,Y=1\\}<\gamma$.

Similarly, it is optimal to select $\tau_{1}=\rho_{n^{\prime}}$ and
$\tau_{0}>\rho_{n^{\prime}}$ if
$\Pr\\{Y=1|R=\rho_{n^{\prime}},A=1\\}\geq\Pr\\{Y=1|R=\rho_{n^{\prime}},A=0\\}.$
∎

###### Lemma 3 .

Based on Theorem 1, to satisfy the ES fairness notion, the following should
hold,

$\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{A}},A=0,Y=1\\}=\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{A}},A=1,Y=1\\},$

where

$\displaystyle\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{A}},A=a,Y=1\\}$
$\displaystyle=$
$\displaystyle\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{A}},A=a,Y=1,\tilde{A}=a\\}+\Pr\\{r(X,\tilde{A})\geq\tilde{\tau}_{\tilde{A}},A=a,Y=1,\tilde{A}=1-a\\}$
$\displaystyle=$
$\displaystyle\Pr\\{r(X,a)\geq\tilde{\tau}_{a}|Y=1,{A}=a\\}\cdot\Pr\\{\tilde{A}=a|Y=1,{A}=a\\}\cdot\Pr\\{Y=1,A=a\\}$
$\displaystyle+\Pr\\{r(X,1-a)\geq\tilde{\tau}_{1-a}|Y=1,{A}=a\\}\cdot\Pr\\{\tilde{A}=1-a|Y=1,{A}=a\\}\cdot\Pr\\{Y=1,A=a\\}$
$\displaystyle=$
$\displaystyle\Pr\\{r(X,a)\geq\tilde{\tau}_{a}|Y=1,{A}=a\\}\cdot\frac{e^{\epsilon}}{1+e^{\epsilon}}\cdot\Pr\\{Y=1,A=a\\}$
$\displaystyle+\Pr\\{r(X,1-a)\geq\tilde{\tau}_{1-a}|Y=1,{A}=a\\}\cdot\frac{1}{1+e^{\epsilon}}\cdot\Pr\\{Y=1,A=a\\}$

Therefore, the ES fairness notion is satisfied if and only if

$\displaystyle\Pr\\{r(X,0)\geq\tilde{\tau}_{0}|Y=1,{A}=0\\}\cdot\frac{e^{\epsilon}}{1+e^{\epsilon}}\cdot\Pr\\{Y=1,A=0\\}$
$\displaystyle+$
$\displaystyle\Pr\\{r(X,1)\geq\tilde{\tau}_{1}|Y=1,{A}=0\\}\cdot\frac{1}{1+e^{\epsilon}}\cdot\Pr\\{Y=1,A=0\\}$
$\displaystyle=$
$\displaystyle\Pr\\{r(X,1)\geq\tilde{\tau}_{1}|Y=1,{A}=1\\}\cdot\frac{e^{\epsilon}}{1+e^{\epsilon}}\cdot\Pr\\{Y=1,A=1\\}$
$\displaystyle+$
$\displaystyle\Pr\\{r(X,0)\geq\tilde{\tau}_{0}|Y=1,{A}=1\\}\cdot\frac{1}{1+e^{\epsilon}}\cdot\Pr\\{Y=1,A=1\\}$

∎