Fair Sequential Selection Using Supervised Learning Models
Authors: Mohammad Mahdi Khalili
Xueru Zhang
Mahed Abroshan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Supervised Learning
Fairness
Sequential Selection

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 \textit{perfect} ES fairness can still be attained under certain conditions.

Fair Sequential Selection Using Supervised Learning Models
Mohammad Mahdi Khalili
Xueru Zhang CSE Department Ohio State University Columbus, OH, USA zhang. 12807 edu
Mahed Abroshan Alan Turing Institute London, UK
CIS Department University of Delaware Newark, DE, USA khalili@udel. edu
mabroshan@turingg.co
Abstract
We consider selection problem where sequentially arrived applicants apply for a limited number of positions/jobs. At each time step, decision maker accepts 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 (c.g., equal opportunity, statistical parity, etc.) that are commonly used in classifica- tion problems 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 selection problem where the applicants compete for limited number of positions. We introduce new fairness notion, "Equal Selection (ES)," suitable for sequential selection problems and propose 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 the noisy version of sensitive attributes. In this setting, we can show that the perfect ES faireess 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 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 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
To measure and remedy the unfairness issues 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: requires that certain statistical
measures to be equal across different groups [9 10 [I 12
13 [4] [5]. In this work, mainly focus on the notions of group fairness. We consider a sequential selection problem where a set of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

applicants compete for limited positions and sequentially enter the decision -aainn system 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 's features to a predicted qualification state (qualified or unqualificd) 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 satisty certain group faimess 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 noisy version of the sensitive attribute to the decision maker. We adopt the notion of local differential privacy []6] to measure the applicant's privacy. This notion has been and has been implemented by Apple, Google, Uber, etc.
widely used by researchers [7 18. [9]
In this paper, we say the decision is fair if the probability that each position is filled by qualified applicant from one demographic group 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 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 predictor satisfying the ES fairness notion. Our contributions can be summarized as follows.
1. We introduce Equal Selection (ES), 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. We show that decisions made based on a pre-trained model satisfying statistical parity or equal opportunity faireess 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- post-processing approach which solves a linear program and is applicable to any pre- pre-trained model.
3. We also consider scenario where the applicants have privacy concerns and only report the differentially private version of sensitive attributes. We show that the perfect ES fairness still attainable even when applicants' sensitive attributes are differentially private.
4. The experiments 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 finding a fair predictor,
1. Pre-processing: remove pre-existing biases by modifying the training datasets before the training process (20 211:
2. In In-processing: impose certain faimess constraint during the training process, e.g., solve con- strained optimization problem or add a regularizer to the objective function [22 23
3. Post-processing: mitigate biases by changing the output of an existing algorithm 10,244
Among fairness constraints, statistical parity, equalized odds, and equal opportunity have gained an increasing attention in supervised learning. Dwork et al. (5 studies the relation between individual fairness and statistical parity. They identify conditions under which individual fairness implies statistical parity. Hardt et al. in [0] introduce post-processing algorithm to find an optimal
'Rolling admission, job application, and award nomination are examples of sequential selection problems with limited approvals/posttion.. On the other hand, there is no competition in the credit card application as the number of approvals is unlimited.
2

---

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 faimess 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 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 more accurate than 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 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 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 's representation and the decision maker's s utility. Dwork et al. [14] also study the selection problem but consider individual fairness notion. Khalili et al. [3] study the compatibility of fairness and privacy in selection problems. They use the exponential mechanism and show that 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 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 only if arm i has higher mean reward than arm in round t. This notion is not applicable to our selection problem with 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 faimess 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 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 V for jobs/tasks in a sequential manner. At time step i, individual 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,, A,, Y.). where Y, E {0, 1} is the hidden state representing whether individual i is qualified (Y; = 1) for the position or not (Y; = 0). X; E X is the observable feature vector, and A, E (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 yn times. We assume tuples (X;, A., Y:), = 1, 1,2,... are i.i.d. random variables following distribution fx,A,y (2. a, y). For the notational convenience, we sometimes drop index i and use tuple (X, A, Y), which has the same distribution as (X,, Ar, Yi), = 2......
apply
3

---

Pre-trained supervised learning model. We assume the decision maker has access to a pre- pre-trained
supervised learning model r : X {0, + S [0, 1] that maps (X,, A,) to R, r(x,, A,), i... the predicted qualification state or the qualification score indicating the likelihood of being qualified.
In particular, if R {0, 1}. then r(..)) -) a binary classifier and R, = 0 (resp. R. = 1) implies that applicant is predicted as unqualified (resp. qualified); if R. & (0.1) 1), then R3 r ,,,,, A,) indicates the qualification score and a higher R; implies that the individual is more likely to be qualified.
Selection Procedure. At time step i, an applicant with feature vector X, and sensitive attribute A; arrives, and the decision maker uses the output of supervised learning model r(X,, A.) to select or reject the individual. If rf+, -) is a binary classifier (i.e.. R = {0, 1)), then the decision maker selects applicant if r(X,, A:) and rejects otherwise. If R + {0. 1}. then r (X,, A.) indicates
the likelihood of being qualified and the decision maker uses threshold E [0, 1] to accept/reject the applicant, i.e., accept applicant if r(X,, A.) 2 T.
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) (TO) can improve faimess. However, in our selection problem, where the number of positions is limited, those fairess 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 EO. This shows that EO and SP do not improve diversity among the selected applicants. This motivates us to propose the following faimess notion for (sequential) selection problems, which improves diversity among the selected applicants.
Definition (Equalized Selection (ES)). Let X x {0, + {0, 1} be an algorithm used by a decision maker at every time step to reject/select applicant until one applicant is selected. Let E. denote the event that an applicant with sensitive altribute A = a (a E 1)) is selected, and Ý = 1 (resp. Y = 0) the event that a qualified (resp. unqualified) applicant is selected under (l M.). Then
the selection algorithm M' (.) satisfies Equal Selection (ES
Pr(Eo, Ý = 1) P
(1)
To compare the ES notion with SP and EO and understand why SP and EO may lead to undesirable outcomes in 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 faimess is satisfied when Equation to an approximate version as follows.
| holds. The ES faimess notion can also be relaxed
Definition 2 (7-Equal Selection).
A.))) satisfies F-Equl Selection (7-ES) if
Pr Ý PP 131
Note that 7 E [0, 1] quantifies the fairness level, the smaller y 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 algorithum is O-accurate if Pr(Ý 1) O.
Here, 0 E [0, 1] quantifies the accuracy level, and the larger 0 implies the higher accuracy.
"Similar to EO fairness classifications, ES fairness only concems the equity among the qualified applicants. If the qualification of selected applicants doesn't 't matter, we can consider Pr bo} = Pr( } as the faimess notion. While our paper focuses on the notion in Equation (I). all the analysis and results can be extended for Pr[Eo} = Pr( E. See Appendix A.I for more details.

---

3 Fair Selection Using Binary Classifier
3.1 Fair selection without privacy guarantee
In this section, we assume that r(::) is a binary classifier and R; = r r(X;, A.) E {0, 1}. time step & E 2,, ..,, if R2 1, then individual 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(.,-) is a binary classifier, the perfect ES fairness T is
satisfied if and only the following holds,
Pr(R A O, 1) = L,A-R-,
Corollary 1. the pre-trained binary classifier r(::) satisfies Equal Opportunity fairness defined
as Pr(R = 1| 1, A = 0) ( = 1 1. = 1} 100Y, then the selection procedure is Pr(A
perfect ES fair if and only -,P
Note that the condition in Corollary generally does not hold. shows that equal opportunity (EO) and equal selection (ES) are not compatible with each other.
ES-Fair Selection Algorithm. We now introduce a pest-processing approach to satisfying ES fairness. Suppose fair predictor Z f0, is used to accept (Z 1) reject (Z 0) an applicant. The predictor Z is derived from sensitive attribute A and the output of pre- pre-trained classifier R = A) based the following conditional probabilities,
Dla. Pr(Z 1/A = a, R ú), ý E {0,1), (0,1)
Therefore, the fair predictor Z can be found by finding four variables aa,i ÿ (0,1), 10, We write accuracy Pr(ý 1} using variables Cra.ğ as follows.
Pr(Y = 1) Σ
Pr(Z: = 1,Y, = 1,, 03 Σ 1,,, Pr[Z; 0}
i=1
j=1
= 1,y =1] Pr(Y = 1 Eg.o aaii Pr(R 8, 1, o}
1- Pr 0}
Σge Ga.j Pr = R = 1
where Σga= Eie(0.))aE To further simplify the notations, denote Σg = (0.1 (a, == Pr(A= R 9) and (n, v.a) Pr(R- ú,
(0.1)
y, A a}. Unlike [TO]
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 be written follows
Eg.o Ga,ÿ P 1,
max {o E 0.1}
Eg,0 aai PA.R(
s.t.
(ES) E, 0o.g (f. E, ai. PR.Y..((.111)..
(4)
Even though (4) a non-convex problem, can be reduced to a linear program below and solved efficiently using the simplex method.
Theorem 2. Assume that (0.1 PA, 0)) not zero. Let dag a {0, (0,1).0 (0, 1) be the solution to the following linear problem.
Σ Ga.ÿ PR...A(Ñ.1,0 1,a)
max far..g E(0,1]]
v.a
s.f.
(ES) E, 00.6 PR.Y. 1,0) 1,0) E, an
PR,
Σ ga Gaj (A.n(a, 9) minge(0.1).e PA.
(5)
Then, Ga.g, a E (0, 1), 9 E 10,1} is the solution to optimization
④4. linear program 5 does not
have a solution, then optimization 4 has no solution.
Because Z is derived from and Z and X are conditionally independent given R and A. Moreover, are also conditionally independet given R and A.
In Appendix A.2 will explain how can write the ES fairness constraint in terms of 0a.g.
5

---

Note that the quality (i.e,, accuracy) of predictor Z obtained from optimization problem ( 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|2 = = Pr(Y = R = = S c and Pr(A A = a|Y = -1
Pr(A = R = 1}, Va E (0, 13, then Pr{[Y = 1 = - Pr(Y = 1 = 5 S.
Note that Pr(Y = 1 1 = 1) and Pr(Y = 1|2 = 1} are accuracy of Z" and Z, respectively. This theorem implies that under certain conditions, if the accuracy of pre 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 reciiion-maakine process Such a scenario has been studied before in classification problems [30 31. We adopt local differential privacy [16] as the privacy measure. Let Á; E {0, 1) be a perturbed version of the true sensitive attribute A,. We say that A; is e-differentially Pr(A private if Pr( Pr(1:=a/A==1-aa S exp(c), Va E {0, 1}, where e is the privacy parameter and sometimes referred as the privacy leakage, the larger implies a weaker privacy guarantee.
Diffrentially private A; can be generated using the randomized response algorithm (39. where A, is generated based on the following distribution!"
e
1
(6) We assume the decision maker does not know the actual sensitive attribute A; at time step i, but has access to the noisy, differentially private A, generated using the randomized response algorithm. Hence, the decision maker aims to find a set of conditional probabilities Pr(Z = 1|Ā = ā, r(X, A) = ū),ā 1, E {0, 1}.0 E {0,1) to generate a predictor Z that satisfies the ES fairness constraint.
Pr Pr( a Itee
1 A,A, = -
I+ iE (1,2....)
We show in Lemma T that even though the true sensitive attribute A is known the decision maker at the time of decision-making, the predictor derived from (r(X, A), A) and the subsequent selection procedure can still satisfy the perfect ES fairness. Denote PA.y,=(X.a)) (a, 9) == Pr(A- = a, Y = y. r(x, a) = ú) and (((xaa)a(((aa) == Pr(r(X, ā) = g = a} to simplify notations. Assumption 1. The true sensitive attributes A are included in the training dataset and are available fodininguunctio
for training function ). Therefore, Va, ā, Ú, Pr(A = Y = 1,,1 r,,( = ÿ is available before the decision making process starts. However, sensitive attribute A, is not available at time step i.
Lemma 1.
Let Bā.g PriZ- 1|Ā = ā,r(X, A) ÿ). Predictor Z derived from (r(X, A), A) satisfies the ES fairness notion if and only if the following holds,
E, Bo.g 8ns e (0, Σ, B1.0 (AX,
B0B Boss PAY..(( 0) (1) Σ, BIS (Ay. (,,
trivial solution satisfying 77) is Pa.g = 0, (0, 1).0 j E (0, 1}. under which the predictor Z is a constant classifier and assigns 0 to every applicant, i.c., it rejects all the applicants. It is thus essential
to make sure that constraint 7 has a feasible point other than Bagg g = 0, E {0, & E {0, 1}. The
following lemma introduces sufficient condition under which 7 has non trivial feasible point.
Lemma 2. There exists a feasible point except Ba.g = 0, ā E {0, 11. 9 E {0, that satisfies 7 if
<> (o.1 In Pr
a. Y 11.
(8)
a set of conditional probabilities $a.j for generating the optimal ES-fair predictor Z can be found by the following optimization problem.
Using Lemma D
max (9, s
Pr(ý = s.t. Equation
'Sometimes the decision- maker cannot use the sensitive attribute by regulation. Even if there no
regulation, the applicants may reluctant to provide the true sensitive attribute.
"Note that Á is derived purely from A. As result, (X, Y) and A are conditional independent given A.

---

While optimization problem ② is not linear optimization (see the proof of the next theorem in the appendix), the optimal Bag can be found by solving the following linear program.
Theorem 4. Assume that mina, (Pa() -e' ( Pa(1-a) Pr(xaaaA( a)]
Let Ba.g ā E {0,1),0 E {0, 1 be the solution to the following optimization problem.
max {(0,1E(
Σ a.
Pa.0
(A..r((.,)),1..00) P PAYY.(X.))) - -. V.
E a.
Pa(ā) e" Pr(x.a)aa( + PA(1 a) Pr(x,a)aa(ill a)
s.1.
mina.
Pa(ā) e" Pr(x,a)aa(0a) Pa ā) Pr(x,a)ia -a)
Equation
(10)
where PA(a) == Pr(A= Pa(1 == Pr(A 1- a-. and Ea.g Ede(0.1), Then, Ba.g. a E [0.1).0c (0,1} is the solution to optimization solution, then optimization (9) has solution neither.
( If linear program (10) does not have
4 Selection Using Qualification Score
4.1 Fair selection without privacy guarantee
In this section, consider the where R [0, 1] and the supervised model r(.;-) generates a qualification score, which indicates an applicant's s likelihood of being qualified. The decision maker selects/rejects each applicant based on the qualification score. We consider 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 threshold т. In other words, prediction Z, is derived
if R
from (R, A) based on the following, Z,
To simplify the notations, denote (R(T) = Pr(R < 7). (T) = Pr(R < T|A a}, Fr(a((T) = Pr(R < T/A a.Y = y}
0 o.W.
and P PA,Y (a. y) = Pr(A A = a, Y = y}. Then we have,
Σ PAY -(1 (1- (T)a, ( (a, 1)(1 - FRIA, (T))
2
Pr(Ea; y
= Y=
1 1 FR((T
Predictor Z, satisfies the ES fairness notion if and only if,
(0,1 (T)) = (1
(11)
Since a threshold 7 that satisfies (TT) may not exist, we use group-dependent thresholds for two demographic groups. Let To be the threshold used to select applicant with sensitive attribute = a. Then, ES fairness holds if and only if the following satisfied,
(o, 1) (1 Fnjo.
(L, (1 (1-Fim) (T).)
(12)
The decision maker aims to find the optimal thresholds for two groups by maximizing its accuracy subject to fairness constraint (2)). Under thresholds To and Tı, the accuracy given by,
Pr(ý = 1] PA, (0, 1)(1 FRIO, (To)) (1, (RI,)(T))
1 1/7.7
where Tro. = FRIO(TO) Pr(A- 0} (f) Pr[A
1}. To find the optimal To and Tı, the decision maker solves the following optimization problem,
PA,Y (0, 1)(1 - FRI. (70)) + PA.Y 1) - - (RI,((T))
max Ta [0.1]
1ra.
s.t.
(0, 1)(1 - FRIO. (7o) = PAY (1, 1)(1 - FRI.I((1)))
(13)
If R [0. and the probability density function of R conditional on A = and Y 1 is strictly positive over [0. 1], optimization problem (13) 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
7

---

for more details). An optimization problem over glosed-interval can be solved using the Bayesian optimization approach [40]. In Appendix A.3 we further consider 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., R = {pr,... - }) optimization problem L3 also be solved
easily using exhaustive search with the time complexity of ((n')²).
Next, we show that maximizing Pr(Y = 1 subject to the equal opportunity fairness notion can lead to undesirable outcome.
Theorem 5. Let Z be the predictor derived by thresholding R E {PI....,PP'' | using thresholds
TO, T1. Moreover, assume that accuracy (i.e. Pr(Y 1|2 = =1] (1)) is increasing in To and 7ı, and
Pr(R Pae A = a, Y 1} S 7, Va E {0. Then, under 7-EO (i.e., [r = A = 0, Y 13 Pr(z =
1, = 1)1 7) one of the following pairs of thresholds is fair optimal.
> Prt and T Pnt (in this case, Pr(R 2 Tol 0, Y =1 =
. > Pwt and = Par (in this case, Pr R 2 1 = 1, 1 0).
Theorem [ implies that under certain conditions, is optimal to reject all the applicants from a single demographic group under EO fairness notion. In other words, the EO fairesss 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 À instead of true sensitive attribute during the decision decision-making process. Let Ž be the predictor
if A) 2 A where O.W.
derived from r(X, A) and Á according to the following. 2
x = To if Ā O, and A - otherwise. Lemma introduces necessary and sufficient condition under which predictor satisfies the perfect ES fairness. Let F Fx. a,y) y) = Pr(r(X,ā) 2 Fa, A Y = y} and F Fr(x.a).AFaa. F F. a. Pr(r(X,ā) 2 ia A a, A = ā}.
= Pr(r(X,ā) 2 Fa. A = a} and
Lemma 3. Predictor Ž satisfies the perfect ES fairness if and only i and &j satisfy the following. e F..ooo 0) + F........vv....... = F.x.nA(. 1,1) ( A, 1,1). (14)
Accuracy Pr(f 1) can be written as function of in and +i (see Section A.5 for details),
-11=111=11 E., Sa.FFxan A 1, Pr(f = Pr(2=1]
Eea F F....)...ddaaa.a a, Σ. T Frix))Ay(faa a, 1) E,, Σ. (fa + (fa 1f
(15)
where E. E. and E., == Ea.e(u.1) Following Lemma 3 the optimal thresholds ño and 7, can be found by maximizing accuracy Pr(y 1} subject to faimess constraint
[4] That is,
max Pr(ý= 13 s.t. Equation 14
(16)
Similar to optimization 133 if R {pi, P....., Pwr): then solution to 166) can be found through the exhaustive search with time complexity ((n')
Numerical Example
FICO credit score dataset creditworthiness of people. The dataset used in this experiment includes credit scores from four
7 FICO credit scores have been used in the US to determine the
The datasets used in this paper do not include any identitiable information. The codes available here

---

demographic groups (Asian, White, Hispanic, and Black). Cumulative density function (CDF) Pr(R < 7|A a) and non-default rate Pr(Y 1 T. A = a) of each racial group can be calculated from the empirical data (see [T0] 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) = 13310G 1 Pr(A- 1) 133165+ 18274 0.879.
Figure la illustrates the CDF of FICO scores of qualified (i.e., non-default) applicants from White and Black groups Since Pr(R V ,|Y 1,A 0} is always below Pr(R s p|Y = A 1}. black qualified (non-default) applicants are likely to be assigned lower scores as compared
the white qualified applicants. Therefore, selecting an applicant based on FICO scores will lead to discrimination against black people. We consider three fair- ness notions in our sequential selection problem: equal opportunity (EO), statistical parity (SP), and equal selection (ES). We say the selection satisfies 7-equal opportunity (>-EO) if Pr(R 2 TolA O. = 1) Pr(R 2 π. sion satisfies S-SP if Pr(R 2 To/ = 0} - Pr(B 2 -
1.Y = 1} S y. Similarly, we say the deci-
S 7.
Table T 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 faimess which tries to improve diversity. Notice that the
Table 1: Equal Opportunity (EO) v.s. Statistical Parity (SP) v.s. Equal Selection (ES)
Fairness metric
To
T1
Pr(Eg,> Y = =}}
Pr(E,, Ý = 1} Accuracy
0.01-EO
99.5
99.5
0.990
0
0,990
0,001-E0
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.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
optimal thresholds To, Tj in Table are close to the maximum score 100, especially under EO and SP fairness notions. This is because in optimization (13), we have assumed there is no time constraint for the decision maker find qualified applicant (i.e., infinite time horizon), and the selection procedure can take long time. To make the experiment more practical, we add the following time constraint to optimization (33 the probability that no applicant is selected after 100 time steps should be less than 5. i.e..
Pr(No one is selected in 100 time steps) (Pr Ta))
OP < ro/A- 0} + 1| R < T <1 13) 100
S 0.5. (17)
Table 2 summarizes the results when we add the above condition to 13 By comparing Tath Table we observe that Pr( Fr(E,, = 1} slightly increases under EO ans SP fairness after adding time constraint (7).. 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..
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 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.
race by

---

Table 2: Equal Opportunity (EO) v.s. Statistical Parity (SP) v.s. Equal Selection (ES) after adding
time constraint
Fairness metric
T0
T1
Pr(Eo, Y 1}
Pr(E,, Y 1}
Accuracy
0.01-EO
98.0
97.5
0.947
0.042
0,989
0,001-E0
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
0.8
0.6
0.2
Slack
0.0
20
Score (2)
40
30
80
100
P-Wacy
Friveyy Loos
Friuary loss
(a)
(b)
(c)
(d)
Figure 1: (a) CDF of FICO scores for non-default applicants from White and Black groups (b)
Accuracy Pr(Y 1} function of for the adult dataset. (c) Pr(ý 1, E.} of each group. (d)
Disparity 7 Er Y
Pr(E1, 1} function of e.
We first train logistic regression classifier (using sklearn package and default parameters) as the pre- trained model. Then for each privacy parameter 6, we calculate the probability mass function (ā) using Equation (6). Then, we calculate the joint probability density PA, "A.Y.r(X.a)) (a, 1, () and solve optimization problem (10) to generate a fair predictor for our sequential selection problem. Repeating process for different privacy loss e, we can find Pr(ý = Pr(Fo, y = 1}, Pr(Fi, ==11 as function of privacy loss As baseline, we compare the performance of our algorithm with the following scenarios: 1) Equal opportunity (EO): replace the fairness constraint with the EO constraint in (9) and find the optimal predictor 2) No fairness constraint (None): remove the fairness constraint in optimization (9) and find predictor that maximizes accuracy Pr(ý 1}.
Figure 1b illustrates the accuracy level 0 -Pr(Ý- }} as function of privacy loss c. Based on optimization problem (10) has non-zero solution if is larger than a threshold. This verified in Figure lb It shows that if 2 2.7, then problem (10) has a non-zero solution. Note that the threshold in Lemma is not tight because maxae In Pr R 1, = a, = 1} 4.9 2.7. Under ES fairesss, accuracy Pr(ý= 1} starts to increase at 2.7, and it reaches 0.66
Lemma 2
co.
Lastly, when 2 3, the accuracy under ES fairness is almost the same that under EO or under no fairness constraint.
Figure Ic illustrates Pr 1} and Pr(Ei, Ý = 13 functions of privacy loss. In the case with EO Tairness and the case without a faimess constraint, the selection rate of black people always remains close to zero. In contrast, under ES faimess,, the available position filled from Black and White people with the same probability. Figure id shows the disparity (i.e., Pr Y 1] Pr(Er, 1}1) As expected, disparity remains under ES while it large the other cases.
Limitation and Negative Societal Impact: We made assumptions 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 are only applicable to our sequential selection problem. This notion may not be suitable for other scenarios.
SSee Appendix A.6 more details about expressing the EO constraint function of $a.9.
10

---

References
[1] K. Crockford, "How is face recognition surveillance technology racist?" http://bitlly22MWYBBBB 2020.
[2] A. Najibi, "Racial discrimination in face recognition technology," https:/biit.ly339P555]]] 2020.
[3] J. Dressel and H. Farid, "The accuracy, fairesss, and limits of predicting recidivism," Science advances, vol. 4, no. I, p. caao5580, 2018.
[4] N. Vigdor, "Apple card investigated after gender discrimination complaints." http://nyti..m 39NPtmx 2019.
[5] X. Zhang and M. Liu, "Fairness in learning-base -hanid sequential decision algorithms: A survey," arXiv preprint
N0V:2001.0486//1 2020.
[6] A. Biega, K. Gummadi, and G. Weikum, "Equity of attention: Amortizing individual fairness in rankings," in The s/ international acm sigir conference on research & development information retrieval, 2018, pp. 405-414,
[7] C. Jung, M. Kearns, Neel, A. Roth, L. Stapleton, and Z. S. Wu, "Fliciting 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 faimesss," in Advances in Neural Information Processing Systems, 2019, pp- 15 243 15232.
[10] M. Hardt, E. Price, and N. Srebro, "Equality of opportunity in supervised learning," in Advances in nearal information processing systems, 2016, pp. 3315-3323.
[11] V. Conitzer, R. Freeman, N. Shah, and J. W. Vaughan, "Group faimess 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 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.088 05 167, 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 Neural Information Processing Systems, vol. 33, pp. 18457-18 469, 2020.
[16] B. Bebensee, "Local differential privacy: a tutorial," arXiv preprint arXiv: 2019.
[17] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, "Differentially private empirical risk mini- mization." " Journal of Machine Learning Research, vol. 12, no. 3, 2011.
[18] M. Abadi, A. Chu, Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and 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 Machine Learning, 2018, pp. 5796- 5805.
[20] Kamiran and T. Calders, "Data preprocessing techniques for classification without discrimi- nation," 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.
11

---

[23] M. B. Zafar, I. Valera, M. Gomez Rodrigzzd and K. P. Gummadi, "Fairness constraints: A flexible approach for fair classification." " Journal of Machine Learning Research, vol. 20, no. 75,
pp. 1 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: hitp
Saapers.ips.cccaape//15--- -on-anannsssss- Tairness- and canddcabbrrtioo...l
[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 fairesss," in Proceedings of the 23rd acm sigkdd international conference 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-Leibnizz 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 faimess in logistic regression." in Companion Proceedings of The 2019 World Wide Web Conference, 2019, pp. 594 594-5544555 559. [30] M. Jagielski, M. Kearns, Mao, A. Oprea, A. Roth, S. Sharifi- -alvii--aalajjrrii, 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. 2020.
[32] S. Wang, W. Guo, H. Narasimhan, A. Cotter, M. Gupta, and M. Jordan, "Robust optimization for fairness with noisy protected groups," arXiv preprint arXf::2002.09333, 2020.
[33] N. Kallus, X. Mao, and A. Zhou, "Assessing algorithmic faimess with unobserved protected class using data combination," " arXiv preprint urXiv: 106.00000.5... 2019.
[34] Awasthi, M. Kleindessner, and J. Morgenstern, "Equalized odds postprocessing under imper- fect 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 Dagsuhl-Leeiniiz-Zentun 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. Morgenstemn and A. Roth, "Fairness in learning: Classic and contextual bandits." arXiv preprint arXiv:
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 2011.
learn privately?" SIAM Journal on Computing, vol. 40, no. 3, pp.
[40] P. I. Frazier, "A tutorial on bayesian optimization," " arXiv preprint
[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. pp.2022201 202-207.
12


Reviews:
[{"review_id": "IQWlEUrfFW1", "reviewer": "Reviewer_DxNT", "summary": "This paper introduces a new task of making fair decisions in sequential selection problems. The authors have shown that existing fairness notions are not suitable for this problem and could lead to discrimination. Then the authors propose a new fairness notion called \"Equalized Selection Rate (ESR)\" for sequential selection problems and a post-processing approach is designed to satisfy the ESR constraint. The paper considers 2*2 different settings, i.e., whether the pre-trained model provides a binary decision or a continuous score, and whether the actual or noisy sensitive attribute is accessed. The paper also conducts experiments on FICO and Adult datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies a novel setting in fair machine learning. I can see that there are a lot of theoretical works done by this paper. However, I feel that this paper is not quite well-written as some key points are not explained or missing. In addition, how each section in the appendix is responding to each part in the main paper is not explicit (the authors should refer to the appendix sections in the main paper). These factors lower my score. My detailed comments are as follows.\n\n1. Theorem 1 and A.1 need more explanations in the paper. The derivation of the first equation to Theorem 1 and the equation between Eq. (18) and (19) could show the key difference between the sequential selection setting and traditional supervised learning setting.\n\n2. In the proof to Theorem 2, how the second constraint in Eq. (5) is used? I believe that it is hidden somewhere in the proof but the authors should explicitly show that.\n\n3. The paper defines accuracy as Pr{\\tide{Y}=1}. But to me this is just the true positive rate, not the accuracy, since it only considers the case where the individual is predicted positive. Could the authors clarify this?\n\n4. The logic of Sections 4.1 and 3.1 are not consistent. In Section 3.1, the paper defines a probability to flit the decision of the pre-trained model. But in Section 4.1, the paper “trust” the score made by the pre-trained model and only aims to learn a threshold for making decisions. \n\nI don’t have the expertise to check the differential privacy part of this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "F8ZjUi7CvTT", "reviewer": "Reviewer_ffFj", "summary": "The paper proposes a notion of algorithmic fairness for the setting of sequential selection. Namely, a situation where candidates arrive one after the other, and a learner aims to select some number of whom. The authors propose a notion they term “Equalized Selection Rate (ESR)\" which requires that the probability of an accepted qualified candidate is the same across groups in the distribution. The authors further suggest a post-processing approach for deriving a predictor that obeys the ESR constraint via solving a linear program (for fair selection using a binary classifier) or using a Bayesian optimization approach (for fair selection using qualification score). Additionally, the authors consider a case where for privacy concerns, the protected attribute is only accessible after noise is added (for predicted individuals), and show that perfect ESR is still attainable (when training the model on individuals for which the unnoisy protected attributes are included). The paper concludes with empirical evaluation of the proposed approaches.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem formulation studied in the paper is interesting. Rather than considering classification in its most general form, the authors focus on a sequential selection problem, inspired by various real-life scenarios. I appreciate this novel problem formulation and believe it is well-motivated and is worthy of further attention. The paper is well-written and is easy to follow and understand. In terms of novelty of the considered notion, to the best of my understanding, ESR is essentially equivalent to a condition regarding the true positive rates, weighted by the marginal group sizes for qualified individuals. The technical contributions are mainly through the suggested post-processing algorithms, which operate through a reduction to a linear programming problem or using a Bayesian optimization approach, and the extensions to the private case. This solution scheme seems elegant and easy to operationalize, however, as is the case with prior post-processing approaches (e.g. Hardt et al. 2016), it seems like the resulting accuracy-fairness trade-off could be sub-optimal.\n\nIn terms of technical contribution, there is no analysis or bounds regarding the accuracy loss that may result from taking the suggested post-processing approach for achieving the ESR notion, as opposed to an in-processing approach. I believe providing such bounds, even under additional assumptions, can significantly strengthen the results of paper. The authors do not have a discussion as for their choice to focus on a post-processing approach with a pre-trained classifier assumption rather than an in-processing approach. One could imagine, for example, attempting to cast the objective of accuracy under the ESR condition as a series of cost-sensitive optimization problems, as done in the reductions approach to fair learning (Agarwal et al. 2018) or one of the online variants. \n\nThe proposed ESR notion should be better motivated. For example, consider a case where the distribution consists of two groups, one with probability 0.9 and the other with probability 0.1. Assume further that the fraction of qualified individuals across both groups is 0.9. Under the ESR condition, it is necessarily the case where qualified candidates from the larger group are denied at a much higher rate. A discussion regarding the advantages and disadvantages of the proposed notion of fairness should appear in the paper.\n\nQuestions to authors:\n\n1. Prior work has suggested a post-processing scheme for a different yet closely related fairness definition, equal opportunity, by solving a linear program (Hardt et al. 2016). Can you elaborate on the differences between the approach in the paper and previously suggested post-processing approaches, and especially Hardt et al. 2016, in terms of the difficulty of achieving EO vs. ESR and how does the different objective alter the required solution method?\n\n2. In line 83, the paper states \"Hardt et al. in [9] introduce a post-processing algorithm to find an optimal binary classifier satisfying equal opportunity\". It is important to notice that the approach of Hardt et al. does not in general guarantee optimality of the equal opportunity predictor learned, but only in very specific cases (Woodworth et al. 2017). Optimality is rather with regards to the class of post-processed predictors, which can be far from general optimality under the equal opportunity condition. Can you discuss how taking a post-processing approach affects the resulting level of accuracy for the notion of ESR comparing to the optimal, not necessarily post-processed, solution over a given base class of predictors? \n\nThe submission appears to be technically sound, although I have only glanced at proofs in the appendix. The paper cites the relevant prior work. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As stated in the main review, I would like to see a more elaborate discussion about the potential societal effects of the proposed ESR condition, and a discussion regarding taking a post-processing approach rather than an in-processing one.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "5RFQX7ebn_u", "reviewer": "Reviewer_wyEe", "summary": "This paper introduces a new fairness notion called Equalized Selection Rate (ESR) for sequential selection problems in which individuals are seen by the decision-maker sequentially, and there are a limited number of positive decisions available. For example, in a job acceptance setting, individuals are applicants submitting resumes sequentially, and the process ends when the decision-maker has accepted $m$ applicants. The authors show that a pre-trained model able to satisfy statistical parity or equal opportunity can be unfair in this sequential setting. A post-processing method is provided to circumvent this issue. Moreover, the authors show that when sensitive attributes are perturbed according to a local differential privacy notion, ESR fairness is still obtainable. Lastly, an empirical analysis is performed comparing equalized odds and ESR over two real data sets. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "originality -- I thank the authors for the extensive related work section---related work in classification fairness, selection, and differential privacy is discussed. Work related to sequential decision making is briefly mentioned (a single RL algorithm). To add, the bandit literature is another large area in sequential decision making with numerous works in fairness, e.g., Joseph et al. Fairness in Learning: Classic and Contextual Bandits, which focuses on individual fairness. More closely related to the classification setting (does not deal w/ exploration problem) might be batch bandit/RL algorithms that enforce fairness, e.g., Metevier et al. Bandits with High Prob. Guarantees. ESR is a fairness notion based on predicted outcome and not actual outcome (the selection made and not the \"selection that should have been made\"), and can be thought of as the action taken by the bandit. To summarize, along with reinforcement learning, I suggest mentioning bandit literature in the related work, as it is another important area in sequential decision making. Discussing the differences in the RL/bandit settings and the one being considered in this work can also strengthen the related work section. \n\nclarity/quality -- The paper is readable, but there is some room for improvement. In line 183 \"It shows that even with the seemingly fair...\" this requires more explanation, e.g., an example or intuition. Line 147 offers good motivation for the need of a fairness definition for the sequential setting. Also, notation for probabilities seem to change in Theorem 2 (from brackets to parentheses). I did not view the supplementary material but looked at the work in the main text. Is there a reason the authors switch between parens and bracket notation for probability? \n\nsignificance -- The authors assert in the introduction that they show that models enforcing statistical parity / equal opportunity may still be fair in the sequential setting they consider. I only see this in (1) after Corollary 1, line 183, \"Note that he condition in Corollary 1 generally does not hold. It shows that...we may still be discriminatory,\"  and (2) the comparison to equal opportunity in the experimental section. A comparison to statistical parity seems to be missing entirely in the empirical section of the main text, although it is listed as a contribution. Otherwise, the empirical analysis seems to support the claims made by the paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "-iSOW-7FohG", "reviewer": "Reviewer_hV6x", "summary": "This paper studies how to \"fairly\" select a single candidate from a repeated i.i.d. classification perspective \"selection process\". They contribute a new fairness notion that is unique in the selection setting, however, it is not that different from previously contributed group fairness notions. They provide sound technical methods to post-process predictors to satisfy the fairness notion and consider selection in the private attribute setting. \nHowever, the selection setting is not interesting enough without decisions at time step i affecting those at time step i+1, moreover, as the paper studies the  single selection setting, it is not that different from just classification. \nThe paper is novel and interesting in it's combination of all those elements, but there is no sufficient novelty in each direction alone to stand out. The paper is clearly written and easy to follow and technically sound. I think if the paper had a slightly more realistic selection setting (any sort of dynamics from one step to another), then it would be a clear accept. But without that, I think the paper is borderline. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The paper considers a new fairness criterion for selection problems of finite resources. The fairness notion is similar to existing notions and has the same form of equality of group wise probabilities. Fairness in selection problems has previously been studied. Guaranteeing fairness when only privatized attributes are available has been studied in classification. The novelty in this paper is studying this new fairness notion in the selection setting (repeated i.i.d. classification) with private attributes (only at test time).  The postprocessing approach is a very interesting technical result and approach, and not obvious. However, the selection setting considered is only studied for a single selection, does not study dynamics of selections on each other (because it studies single selections) and only studies the setting for binary sensitive attributes (but I understand this may only complicate theory but not the approach). \n\nQuality: The theorems and technical details are sound and complete. Some crucial experimental details are missing especially how 1) they simulated selection problems from the static datasets and 2) how the optimization was performed and thresholds chosen for EO and the baselines and 3) how exactly they computed the statistics. Furthermore, I am unsure about one of the results in table 1. \n\nClarity: The paper is clearly written and easy to follow. The basis of the paper is the following sentence  “decisions are fair if the (qualified) applicants from different groups are\nselected at the same rate.”,  this implies in classification that P(R=1|Y=1,A=0)=P(R=1|Y=1,A=1) (EO) but Theorem 1 says otherwise, what the authors actually mean is that decisions are fair if we select the same number of qualified individuals from different groups and not “rates”. I think the proposed notion (ESR) is fundamentally very very different from EO as it is not a conditional statement . \n\nSignificance: I think this paper misses out an incredible opportunity to study selection problems by only focusing on the m=1 case and assumes i.i.d. selections and no impact of previous selections on the following ones. Due to this, I feel the \"selection\" aspect of the paper is not that novel and so it goes back to studying the ESR notion in classification problems and trying to argue for it (from theorem 1). However, the paper does not attempt to justify ESR in the classification  from an ethical perspective or long term perspective but only cites the EEOC.\n\nLimitations:  1) studying binary attributes, 2) m=1 setting \"single selection\", 3) i.i.d. between selections which is not a reasonable assumption in reality, 4) not enough argumentation, especially from a societal perspective, for why one wants ESR instead of EO. \n\nComments:\n\n re footnote 1: College admission is a subset selection problem and not sequential selection, hiring can be argued as sequential selection.\n\nHow calibrated is the pretrained model?\n\nESR extension to m>1 is not obvious what it means, also authors don’t write in words what ESR signifies: The probability that we select a qualified A=0 individual vs A=1 individual should be the same, that is not the natural extension of EO.\n\nTheorem 1 is illustrative but is obvious from the definition 1 and so is corollary 1. \n\nTheorem 2 is nice, I think the proof needs to have all the steps written out (cancelling of terms more clearly) to be more easily readable. \n\nI want to see a comparison or a theoretical attempt at the difference between post-processing and in-processing with fairness, something like Theorem 5.6 in Equality of Opportunity in Supervised Learning  (Hardt et al., 2016).\n\nI think it is reasonable to remove Assumption 1 and assume one only observes the noisy attribute at test and train, if not I would like to see an impossibility result to justify assumption 1 as it is not reasonable to assume a discrepancy between train and test in observing the sensitive attribute.\n\nIn table 1, the result of the 0 probability of selecting the minority group is a bit odd. Consider the following  test: at each step, we sample a random individual from the population, the probability that this individual is Black and qualified is P(A=0,Y=1), if a classifier satisfies EO, then it cannot be the case that the probability of selecting a Black individual is 0 if we repeat this selection process. I need more details on how the testing was accomplished. \n\nConstraint 17 is too artificial with the ½ threshold. I think it is okay to consider m=1 in theorems, but in experiments not showing m>1 is a big limitation.\n\nWhat can make the paper really improve: \n1) considering m>1\n2) Considering that decisions at time step i, affect the distribution of individuals at time step i+1. \n3) theoretical results to showcase the issue with EO shown in the experiments\n\n\n\n---------------------------------------------\n\nPost response: I have read the authors responses. The authors do acknowledge and address some of the limitations of their study, however, I remain on my previous score as the current problem studied is still limited by the lack of any dynamics governing the population or meaningful experimental study.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The papers introduces a fairness constraint on selection problems. Downstream impact of this fairness condition or it's ethical viability are not adequately discussed in the paper. Especially in selection problems, it is important to understand long term impact of a fairness notion rather than short term. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer all agreed that the paper formulates and partially addresses an interesting and practically relevant question: namely, how to define and guarantee an appropriate notion of fairness in sequential decision-making settings where a limited number of positions are available and diversity among the selected is an important consideration. However, among other suggestions for improvement, reviewers urge the authors to expand their discussion of the related work, the motivation behind proposed fairness notion, and the post-processing approach. Assuming that the authors will add the necessary discussions and revise the paper to reflect the reviewers’ suggestions, I recommend acceptance.
Decision: Accept (Poster)