Fair and Useful Cohort Selection
Authors: Konstantina Bairaktari
Paul Tsela Langton
Huy Nguyen
Niklas Smedemark-Margulies
Jonathan Ullman
Venue: Accepted by TMLR ()

Abstract: A challenge in fair algorithm design is that, while there are compelling notions of individual fairness, these notions typically do not satisfy desirable composition properties, and downstream applications based on fair classifiers might not preserve fairness. 
To study fairness under composition, Dwork & Ilvento (2019) introduced an archetypal problem called fair-cohort-selection problem, where a single fair classifier is composed with itself to select a group of candidates of a given size, and proposed a solution to this problem.

In this work we design algorithms for selecting cohorts that not only preserve fairness, but also maximize the utility of the selected cohort under two notions of utility that we introduce and motivate. We give optimal (or approximately optimal) polynomial-time algorithms for this problem in both an offline setting, and an online setting where candidates arrive one at a time and are classified as they arrive.

Published in Transactions on Machine Learning Research (09/2023)
Fair and Useful Cohort Selection
Konstantina Bairaktari
buimakkarik&hhurtlossleeaa.
Khoury College of Computer Sciences Northeastern University
Paul Langton
lungton.p@hhotthasstee..m
Khoury College of Computer Sciences
Northeastern University
Huy Le Nguyen
bm..ggugendhhorrhennttee...
Khoury College of Computer Sciences Northeastern University
Niklas Smedeemak-Margulles
Khoury College of Computer Sciences Northeastern University
Jonathan Ullman
jullman@ccs.neet new. edu
Khoury College of Computer Sciences Northeastern University
Reviewed OpenReview:
Abstract
challenge in fair algorithm design is that, while there are compelling notions of individual fairness, these notions typically do satisfy desirable composition properties, and down- stream applications based fair classifiers might not preserve fairness. To study fairness under composition, Dwork & Ilvento (2019) introduced an archetypal problem called fair- cohort-selection problem, where single fair classifier is composed with itself to select group of candidates of a given size, and proposed solution to this problem. In this work we design algorithms for selecting cohorts that not only preserve fairness, but also maximize the utility the selected cohort under two notions utility that we introduce and motivate. We give optimal (or approximately optimal) polynomial- time algorithms for this problem in both offline setting, and online sctting where candidates arrive are classified they arrive.
time and
1 Introduction
The rise of algorithmic decision making has created a need for rescarch on the design of fair algorithms, especially for machine-learning lasks like classification and prediction. Beginning with the seminal work of Dwork et al. 22012), there is now large body of algorithms that preserve various notions of fairness for individuals. These notions of individual fairness capture the principle that similar people should be troated similarly, according to some task-specific measure of similarity.
While these algorithms satisfy compelling notions of individual fairness in isolation, they will often be used as parts of larger systems. To address this broader context, Dwork & Tlvento (2019) initiated the study of fairness under composition, where one or more fair classifiers will be combined to make multiple decisions, and want these decisions to preserve the fairness properties of those underlying classifiers. Their work

---

Published in Transactions on Machine Learning Research (09/2023)
introduced number of models where fair mechanisms must be composed, demonstrated that naive methods of compasing fair algorithms do not preserve fairness, and identified strategies for preserving fairness in these settings. Importantly, these strategies treat the underlying classifiers as a black-bor so that composition can be modular, eliminating the need to redesign the underlying classifier for every possible use.
Our work studies the archetypal fair cohort selection problem introduced by Dwork & TIvento (2019) In this problem, we would like to select k candidates for job from a universe of possible candidates. We are given classifier that assigns a score 8; E [0. 1] to each candidate [ with the guarantee that the scores are individually fair with respect to some similarity metric D. We would like to select a set of & candidates such that the probability p; of selecting any candidate should be fair with respect to the same metric.
Preserving Fairness. Since our goal is to treat the scores ,,,..., 8n as a black-box, without knowing the underlying fairness metric, we posit that the scores are fair with respect to some D, i.e. they satisfy
Vi,j, |s, - أرد S D(i,)),
(1)
but that this metric is unknown. Thus, we will design our cohort selection algorithm so that its output probabilities Pi,...,Pa Pn will satisfy
Vi |p. |p- pyl S s; 1.5-ssh sy D(i.j)
(2)
as this guarantees that we preserve the underlying fairness constraint. Without further assumptions about the fairness metric, the only way to preserve fairness is to satisfy
We can trivially solve the fair cohort selection problem by ignoring the scores and selecting a uniformly random set of k candidates, so that every candidate is chosen with the same probability k/n. Thus, in this paper we propose to study algorithms for fair cohort selection that produce a cohort with optimal (or approximately optimal) utility subject to the fairness constraint. Specifically, we consider two variants of the problem:
Linear Utilities. For the linear utility model, we assume that
the utility for selecting a cohort is the sum of independently assigned utilities for cach member, and
2. the scores given by the original classifier accurately reflect the utility of cach member of the cohort.
Assumption 1 essentially says that members of the cohort are not complements or substitutes and assumption 2 makes sense if the task that we designed the classifier to solve and the task that the cohort is being used for are closely related. Under these assumptions, it is natural to define the utility for a cohort selection algorithm to be Pis,, which is the expectation over the choice of the cohort of the sum of the scores across members in the cohort.
Ratio Utilities. For the ratio utility model, we continue to rely on assumption 1, but we now imagine that the expected utility for the cohort is some other linear function Σ, P:u, where the variables u; are some wnknown measure of utility in [0, 1]. Assuning that for every candidate i the score 8; is generally correlated with the utility even if they are not exactly the same, we normalize by Σ, s;u4, as the original scores can still be a reasonable choice of selection probabilities that satisfy the fairness constraint. Since the utility function unknown, our goal is now to produce a cohort that maximizes the utility in the worst case over possible utility functions. As we show (Lemma 2.1). maximizing the worst-case utility amounts to assigning probabilities that maximize the quantity min; pt/s.. Optimizing the ratio utility implies a lower bound on the cohort utility under any utility function that satisfics assumption 1, including our linear utility above. However, it does not necessarily optimize the linear utility, thus the two utility models are distinct.
Our technical contributions are polynomial-time algorithms for fair and useful cohort selection with both linear and ratio utilities, in two different algorithmic models.
In the model of Dwork al. (2012) fairness requires that the classifier be randomized, so we can think of the output of the classifier as cont inous scores rather than binary decisions.
2

---

algorithm for Published in Transactions on Machine Learning Research (09/2023)
Offline Setting. In this setting, we are given all the scores $.,..., Sn at once, and must choose the optimal cohort. We present a polynomial-time algorithm for each model that computes a fair cohort with optimal expected utility.
Online Setting. In this setting, we are given the scores $1, 82, as a stream. Ideally, after receiving s, we would like to immediately accept candidate to the cohort or reject them from the cohort. However, this goal is too strong (Dwork& & IIvento 2019), ; so we consider a relaxation where candidate i can be either rejected any point during the online process, kept on hold until later, and would like to output fair cohort the end of the stream with optimal expected utility while minimizing the number of candidates who are kept on hold. We must keep at least & candidates pending in order to fill our cohort. For ratio utilities we give a fair and optimal algorithm in this setting that keeps at most (k) candidates on hold. For linear utilities, we give an approzimately fair and optimal algorithm. Specifically, we present a polynomial this online setting where the fairness constraints are satisfied with an e additive error and utility is optimized up to an additive error of OlkVE), for any desired > O, while ensuring that the number of users on hold never exceeds O + 1/e). To interpret our additive error guarantee, since the fairness constraint, applies to the probabilities Pi..... ,p, allowing the fairness constraint to be violated by additive error of, say, = 0.01 means that every candidate is selected with probability that is within +1% of the probability that candidate would have been selected by some fair mechanism.
1.1 Techniques
We start with a brief overview of the key steps in our algorithus for each setting. The formal description of All omitted proofs are in the appendix.
the algorithms can be found in Sections 3 and 4
Offline Setting. Our offline algorithm is based on two main properties of the fair cohort selection problem. First, we use a ceependent-rouddeee h and outputs a random cohort C, represented by indicator random variables ;1,...: Pn E {0, 1} with E. P. = k such that E (f.) = Pu for every candidate u. Thus, it is enough for our algorithm to come up with a set of marginal probabilities for each candidate to appear in the cohort, and then run this rounding process, rather than directly finding the cohort.
procedure that takes a set of probabilities pı..... Ps such that Σi= P: =
To find the marginal probabilities that maximize the linear utility with respect to the scores ,n E [0, 1]. we would like to solve the linear program (LP)
maximize
Σ 1= P:8i
s.t. Σ P; S k
Ji Ip: p,l S |s; 10---)) -8yl
Vi, pı 1
In this LP, the first and third constraints ensure that the variables pa represent the marginal probability of selecting candidate in a cohort of size k. The second constraint ensures that these probabilities p are fair with respect to the same measure D as the original scores s (i.e. 1P.-P=l S s. - sal S D(u, v)). Although we could have used the stronger constraint [P.. - Pal < D(u, v), writing the LP as we do means that our algorithm does not need to know the underlying metric, and that our solution will preserve any stronger fairness that the scores s happen to satisfy.
While we could use a standard linear program solver, we can gel faster solution that also useful for extending to the online setting by noting that this LP has specific closed form solution based on "water- filling.. Specifically, if Σ 8; I k, then the optimal solution simply adds some number 2 0 to all scores and sets P., = min c 1}, and an analogous solution works when Σ 8 > k.
For the ratio utility, although computing the optimal marginal probabilities does not correspond to solving a lincar program, the solutions for the two utility functions are the same when Σn 8; S k. When Σn 8; > k. we maximize the ratio of marginal probability over score by scaling all the scores down by the same factor k/ Ei= 8i-
3

---

Published in Transactions on Machine Learning Research (09/2023)
Online Setting. In the online setting we do not have all the scores in advance, thus for the linear utility we cannot, solve the linear program, and do not even know the value of the constant that determines the solution. We give two algorithms for addressing this problem. The basic algorithm begins by introducing some approzimation, in which we group users into 1//E groups based on their scores, where group contains users with scores in ((a- - gel. This grouping can only reduce ulility by O(kVE), and can only lead to violating the fairness constraint by e. Since users in cach bucket are treated identically, we know that when we reach the end of the algorithm, we can express the final cohort as containing a random set of ny members from each group 9. Thus, to run the algorithm most & candidates from each group, reject all other members, and then run the offline algorithm at the end to determine how many candidates to select from each group.
use reservoir sampling to maintain a random set of at
The drawback of this method is that it keeps as many as k/ee candidates on hold until the end. Thus, we develop an improved algorithm that solves the linear program an online fashion, and uses the information it obtains along the way to more carcfully choose how many candidates to keep from each group. This final algorithm reduces the number of candidates on hold by as much as quadratic factor, down to 2 + !
For ratio utility, we are able to fully maximize the utility due to the way we decrease scores when the sum is greater than k. When the sum of scores is less than k, we must be careful in order to avoid being unfair to candidates eliminated early on. Thus, we maintain three groups; the top candidates, candidates undergoing comparisons, and candidates given uniform probability. The groups are dynamic and candidates can move from the first to the second and then the third group before getting rejected. Once the sum of scores exceeds k the groups are no longer needed. The algorithm considers at most (I)) candidates at any time.
1.2 Related Work
Individual Fairness and Composition. Our work fits into the line of work initiated by Dwork et al. (2012) individual fairness, which imposes constraints on how algorithms may distinguish specific pairs of individuals. Within this framework, difficulties associated with composing fair algorithms were first explored by Dwork & Ilvento (2019), which introduced the fair-cohort-selection problem that we study. Issues of composition in pipelines were further studied by Dwork et al. (2020)
Bocause the scores figure into both our fairness constraint and utility measure, our work has some superficial similarity to work on meritocratic fairness. At high-level meritocratic fairness (Joseph et al. 2016 Kearns et al. 2017 Joseph et al. 2017 Kleine Buening et al. 2022) is kind of individual fairness where we assume there exists an intrinsic notion of merit and requires that candidates with higher merit be given no less reward than candidates with lower merit. In this work, we study a notion of individual metric fairness that, intuitively, tries to preserve the distances between the scores and not necessarily their order. Our algorithms turn out to also preserve the ordering, but meritocratically fair algorithms will not, in general, preserve the distances. We note that in our cases the scores 81,...,88 might or may not be reflective of true merit, since we assume that these scores satisfy individual fairness with respect to some underlying metric D, which may or may not reflect meritocratic values. The work by Kleine Buening et al. (2022 set selection under meritocratic fairness is the most related to our work. Yet, their setting is different
the authors make the assumption that the utility function is non-linear and it depends on the combination of the selected candidates. One of our main assumptions is that every individual contributes to the cohort utility separately. The differences between the two problems are also highlighted in their work.
Individually Fair Ranking and Cohort Selection. Our problem has some similarity to fair ranking, where we have produce permutation over all n candidates instead of just selecting small cohort of k < candidates. Any algorithm for ranking implics an algorithm for cohort selection, since can select the top & elements in the ranking as cohort, and a cohort selected this way may inherit some notion of fairness from the ranking. However, we do not know of any ranking algorithms that can be used in this way to satisfy the notions of fairness and oplimality we study in this work. In particular, the most closely related work on individually fair ranking by Bower et al. (221)) uses an incomparable formulation of the ranking problem, and is not clear how to express our constraints their framework. In addition to the difference in how fairness and utility are defined, we are not aware of any fair ranking papers that work in an online model similar to the one we study.
4

---

Published in Transactions on Machine Learning Research (09/2023)
Group Fairness. A complementary line of work, initiated by Hardt al. (0116) considers notions of group fairness, which imposes constraints on how algorithms may distinguish in aggregate wetween individuals from different groups. While our work is technically distinct from work on group fairness, cohort/set selection has also been studied from this point of view (Zehlike et al.] 2017 Stoyanovich et al.) 2018 and different approaches for fair ranking have been proposed (Yang & Stoyanovich 2017; [Celis el al. 2018 Singh &
Joachims 2018 Yang al. 2019 Zehlike & | 2200). Issues of composition also arise in this setting,
as noted by several works (Bower et al. 2017 Kannan et al., 2019
Arunachaleswaran et al. 2021
2 Preliminaries
2.1 Models
We consider the problem of selecting a cohort using the output of individually fair classifier as defined in Dwork& & 1lvento (2019).
Definition 2.1 (Individual Fairness (Dwork et al. 2012)). Given universe of individuals U and metric D, randomized binary classifier U {0, 1] is individually fair if and only if for all u E U, IP(C(u)
1) - P(C(v) = 1)1 < v(,,v).
We restate the formal definition of the problem for convenience.
Definition 2.2 (Fair Cohort Selection Problem). Given universe of candidates U, an integer h and a metric D, select a set S of k individuals such that the selection is individually fair with respect to D, Lee for all pairs of candidates u, U E U, [P(u E 5) - P(e E S) s D(,,
In this work, we are interested in the setting of fairness under composition, and designing algorithms that exploit the fairness properties of their components instead of having direct access to D. An algorithm which solves this problem will cither preserve or shrink the pairwise distances between the selection probabilitics of candidates. We can think of the probability of C. selecting candidate w as continuous score Su-
Cohort Selection Problem). Given a classifier C who assigns score $t to candidate i, select a cohort of individuals where each individual i has marginal selection probability pe such that for any pair of individuals i, lp; p,l S |s; syy-
Definition 2.3
In some contexts that define below, we consider relaxation of this definition by adding small error to the pairwise distances.
Definition 2.4 (s- Apppooxxintee Shirness-Preservine Cohort Selection Problem). Given classifier C who assigns score 8; to any individual i and a parameter E E (0, 1], select a cohort of h individuals where cach individual i has marginal selection probability p; such that for all pairs of individuals i, pp-Ppy < (st-8j] +s.
When the initial classifier C is individually fair and the cohort selection algorithm preserves fairness E- approximately, then the cohort selection probabilities satisfy e-individual fairness.
Definition 2.5 (e-Individual Fairness). Given a universe of individuals U, a metric D and an e in [0, 1], a randomized binary classifier C > 1) is g-individually fair if and only if for all u, E U, [P(C(()) = - P(C()) = =1] < D(u,v). +
The problem of tairness-peservvngg cohort selection may be studied an offline setting, where the universe of candidates is known in advance, as well as in an online setting, in which candidates arrive ono-at-a- time. Dwork & Ilvento (2019) prove that making immediate selection decisions while preserving fairness is impossible, so relax this to setting in which do not need to give immediate decisions candidates arrive. To control the degree of relaxation, we consider the number of candidates who wait for a response during the selection stage; we seek to minimize the number of these pending candidates.
Individual fairness can be achieved by making uniform random selections among candidates, which is trivially possible the offline case, and can be implemented in the online setting using reservoir sampling (Vitter) 1985). Therefore, is important to consider an extension to the cohort selection problem in which we also want to maximize the utility of the selected cohort. We consider two measures of utility and construct
5

---

Published in Transactions on Machine Learning Research (09/2023)
algorithms for cohort selection which optimize these measures. Let the selection scores for individuals under classifier C' be $1,-.., 8n, and let their marginal probabilities of selection under an algorithm A be P1.-...Pr.
Utilities Correlated with Classifier Output. We may consider that the classifier scores s directly indicate the qualifications of an individual and that the utility of a cohort the sum of the scores of each member. Then, our evaluation measure becomes the expected utility of the selected cohort.
Definition 2.6 (Linear Utility). Consider a set of n candidates whose scores from classifier C' are $1,...,- 8n and whose selection probabilities by algorithm A are PI.....Pn. We define the linear utility of A to be ULility (A, {ai]) = Σi= 8tPr.
As seen in Example 2.1] the maximum linear utility under the fairness- preeeeriig constraint is not a monotone function of the input scores; as the score 8; incrcases, the maximum linear utility may either increase, decrease, or stay constant. Yet, we show in Lemma 3.1 that it is robust to small input perturbations. Therefore, it can handle minor noise or errors in the input value. We exploit this property to develop s-individually fair algorithm for online cohort selection.
Example 2.1. Suppose we want to select people from set of 4 candidates and classifier C' assigns scores $1 0.1, $2 0.3, = 0.6 and $4 0.9. The optimal fairness- fairness-preservee preserving solution has marginal selection probabilities p1 0.125, P2 0.325, P3 0.625 and p1 0.925 and utility Σ:= P&s, 1.3175. By increasing the score of the first individual to s = 0.3, the cohort selection probabilities become pt = 0.275, p22 0.275, p/3 0.575 and p4 0.875. The new utility is Ei= p/s/ 1.2975, which is lower than the previous one.
Arbitrary Utilities. Alternatively, may consider the where there exists arbitrary, unknown utility value for each candidate "1,..., the in [0, 1], which may differ from the scores Given and ue, simple quantity to study the ratio utility achieved by an algorithm A: Σ
Pil: Since we do not know the
distribution of utility, we must consider the utility achieved by an algorithm A for a worst-case utility vector iz.
Lemma 2.1. The worst case ratio utility is equal to the minimum ratio of selection probability and classifier min; Ps 5,
score of one candidate ming P:n
We use this equivalence to redefine the ratio utility as follows.
Definition 2.7 (Ratio Utility). Given candidates with scores s; and a cohort selection algorithm A with marginal selection probabilities Pt, let the ratio utility of an algorithm A be defined according to the coordinate with the minimum ratio: Utility (A, {ssh) min, P:
Of course other utility measures exist; we study the measures defined above because they capture a natural intuition about real world scenarios. We present an example to demonstrate the properties of these two utility functions and the performance of pre-existing cohort selection algorithms.
Example 2.2. Consider the case where we would like to select 2 out of 3 candidates with scores 81 = 0.5, = 0.5, $3 = 1. The optimal solution in terms of ratio and linear utility is to pick [1,3} and (2,3), each with probability 0.5. This solution achioves ratio utility 1 and linear utility 1.5. The weighted sampling algorithm by Dwork & Ilvento (2019) selects each subset with probability proportional to its weight, and would select [1,2} with probability 1/4, (1,3) with probability 3/8, and {2,3] with probability 3/8. The ratio utility of this solution is 3/4 and its linear utility is 11/8. PermuteTThnnCleee
by Dwork Ilvento (2019) selects {1,2} with probability 1/12 and (1,3) (2,3) with probability 11/24 each. This solution achieves ratio utility 11/12 and linear utility 35/24. Hence, we see that weighted sampling and CremutteTeenCMnn are sub-optimal for both utility definitions.
2.2 Dependent Rounding
Our cohort selection algorithms for ratio and linear utility in the offinne and online settings are based on a simple dependent rounding algorithm described in the appendix. This algorithm makes one pass over list
6

---

Published in Transactions on Machine Learning Research (09/2023)
of numbers in [0. ml, where E IR, and rounds them so that their sum is preserved and the expected value of each element after rounding is equal to its original value. The algorithm operates on two entries at a time call these a and b. If a a m, the algorithm randomly rounds one of them to a + b and the other one to 0 with the appropriate probabilitics. If a + b > m, it rounds one to m and the other to the remainder.
This rounding procedure a special case of rounding a fractional solution in a matroid polytope (in this case, we have uniform matroid). This problem has been studied extensively with rounding procedures satisfying additional desirable properties (see e.g. [Cekkur et al. (2010)). Here use simple and very efficient rounding algorithm for the special case of the problem arising in our work.
Lemma 2.2. Let a1...., an be a list of numbers in [0, m] with x = Ei= as There is a randomized algorithm that outpuls 01,...,0h Un E [0, m] such that L of the ag will be equal to m, one a will be x - L Im, the rest will be equal to O, and for all E mI,, B[āā]] when a1...., On natural numbers we call it round-nat.
= a, When m 1, we call this algorithm round-pr and
We use the rounding procodure in two ways. We call round-pr when we want to round a list of real numbers in [o, 1] which represent selection probabilities and round-nat to round natural numbers which correspond to counts.
Corollary 2.1. If m = 1 and Σi=1a a = k E N, then after the dependent rounding of round-pr k elements will be equal to 1 and the rest will be equal to O.
3 Linear Utility
The first definition of utility we study is that of linear utility. In this setting, the aim of the cohort selection is to maximize the expected sum of scores of the group of k people selected while preserving fairness. We can formulate this problem
linear program, as shown in Section 1.1
The key idea of the solution is to move all the selection scores up or down by the same amount, depending on the value of their sum, and clip the probabilitics that are less than zero or over onc. The algorithm we propose for the online setting solves approximately a relaxation of the cohort selection problem, where the probabilities of two candidates can differ by at most the given metric plus a small constant E. The new problem is defined as the linear program presented in Section I.] where the second constraint, Vi,j e [n]. p,| |s; 8yl, is replaced by Vi,j E [m], lp: Pı| S |s +
3.1 Offline Cohort Selection
In the offline setting, the algorithm has full access to the set of candidates and their scores from classifier C. By Corollary 2. if the classifier's scores sum up to k, then the rounding algorithm can form cohort by simply using the input scores as the marginal probabilities of selection. Yet, the sum of the scores assigned by C might not be k. If it is less than k, Algorithm I moves all the probabilitics up by the same amount and clips those that exceed 1, so that their sum becomes equal to k. In more detail, the marginal selection probability of candidate i becomes ps = min(s; + c, 1}. where constant c is such that E Pt k. This adjustment preserves the probability differences between the pairs of candidates, unless some candidate gets assigned probability 1, in which case some differences decrease. As result, the differences of the new probabilities will be bounded by the same metric as the scores. The case where the sum of scores is greater than k is treated similarly. More specifically, the new marginal probabilities are of the form p. = max(0, (000),-44 -c. After the adjustment, Algorithm [ selects the cohort by running the dependent rounding procedure.
Thcorem 3.1. For any classifier C that assigns scores $1,...; to n candidates, Algorithum D solves the fairness- preserving cohort selection problem by selecting k condidales with marginal probabililies pt,..... Pn. which achieve optimal linear utility Σ PiS;.
Corollary 3.1. If C is individually fair, then Algorithm 1 is individually fair.
3.2 Online Cohort Selection
For the online setting of the problem with linear utility, we present Algorithm 2 which reads C's output from stream and selects cohort with high utility while deferring the decision for a small number of candidates.
7

---

Published in Transactions on Machine Learning Research (09/2023)
Alg. 1: Offline Cohort Selection for Linear Utility
Input: scores $1,..., Sn E [0, 1] from C, cohort size
Output: set of accepted candidates
sum t 2i=18
if sum < k then
// move scores up
Ct k-sum Pi t 8 + e, Vi [n]
while Sp. > do
SK1 [j:p;<]] < 1
6
Pj - P2 + p:-
Sal Vj E Sce
Ps 1
else
// move scores down
c sum-k. Pj t 8, -, vi E [r]
10
while 3p; <0 do
11
S>0 {j:p,> 0}
12
Pj g Pj + [S Vj S
13
// Now list sums to and all P; E [0
[p:} <-round-pr(pn: Pu: 1) // select cohort of size k
return candidates with non-zero P.
While processing the stream, this algorithm only rejects candidates and releases all the acceptances at the end of the stream. The main difference in comparison to the offline cohort selection algorithm is that Algorithm 2 splits the candidates into groups with similar scores, within an interval, and treats any member of a group as equivalent. Hence, the final probability of being selected in the cohort equal for any candidate of the same group. This leads to a relaxation of the problem, which we call e-approximate prennessirrreriinnggg cohort selection problem.
As mentioned, the algorithm splits the candidates from the stream into groups according to their score from C. Particularly, the interval (0, 1] is divided into m intervals of size E cach, where m 1 The i-th candidate gets assigned to group 0 if 8, = 0 or group E (l,...,,) m} if 8 E ((g - 1)e, ge). Once candidate is in the group, their score gets rounded up and their new score & is the same as that of all the other members of the group, 89 = gg. The use of the groups affects the performance of the algorithm in terms of not only individual fairness, but also utility. Lemma 3.1 shows that the decrease utility is caused only by the use of rounding, as Algorithm 2 achieves the same linear utility the corresponding ofline algorithm when the scores rounded to multiples s.
Lemma 3.1. Given selection scores $1...., Sn from C, for set of n candidates and a parameter E (0, 1], we split (0, 1] into m 1 intervals of length ε and for all [[]] we set 8, = gE, where g is such that 8; ((g 1)e, gE). When Algorithm | runs for input $1...., and cohort size k it solves the E-approrimate muirness-presereing cohort selection problem with marginal selection probabilities p1....,Pry and il achieves linear utility E Pis. 2 En= s; K(E + 2/E), where ,i,...,," is the optimal solution for the offtine problem for input Sp....,
Since for each group we keep only some people on hold, we preserve the probability information of the rejected candidates by considering that each pending candidate represents themselves and a fraction of the rejected people from their group. The fraction of people represented by the i-th candidate is denoted by n4- One approach is to maintain at most & people pending per group uniformly at random and have every candidate within a certain group represent the same fraction of people. This basic algorithm keeps k/e candidates hold. Our algorithm reduces the number of people pending by allowing candidates of the
8

---

Published in Transactions on Machine Learning Research (09/2023)
Alg. 2: Online Cohort Selection for Linear Utility
Input: stream of scores $1,.... Sn E [0, from C, cohort size k, constant E (0, 1]
Output: set of accepted candidates
0; sum 0// number of candidates and sum of scores
0, for all groups E /// size of group
for condidate in stream do add group 9 where E (ly 1),,ge) n +- n +1
$; + gE; sum t sum &
Th - 1; +
// Compute group scores for this input
if sum k then
C + k-sum
10
3 gE + c, for all groups g
while 3 group g with 8 > 1 do
Fx1 t {group ss <1}
n< EIEFeL n³
13
sf +s + n n9(6"-1) Vfe Rei
14
15
88 1
16
else if sum then
C+ sum-k n 8 ge c, for all groups g
17
19
while 3 group g with 8 < 0 do
20
Fso - (group f > 0}
2>o Ejerso nd
22
sf + of + + 5
Vf E Fs0
23
8 0
24
else
8 +- ge, for all groups
25
for group g do
26
if 89 > then
27
(n. i in g] + round-nat(fn; : in g7, v == [1,+]
we ensure n,v $ reject candidate i n4
28
29
else
30
reject all candidates in g
31 8; + n4 for all groups g and candidates in g
// Now candidate scores sum up to k and all 3; in [0,1]
32 { + round-pr(($;; in any group), 1)// select cohort of size k
38 return candidates with non-zero 8;
same group to represent varying fractions of people. Procedure round-nat is used to climinate candidates and determine what fraction of people's selection probabilities each candidate represents.
Theorem 3.2. For any classifier that assigns scores $1,-..,8p to n. candidates, Algorithm g solves the online e-approzimate barness-preseroing cohort selection problem for any E E (0, by selecting a cohort of size k with marginal probabilities Pi....,Po. uchieves linear ulility Ei-piss pis; 2 Σ p/ k(s + 2 (where pi.....P? P,, is the optimal solution for the offline keeps at most O !) candidates pending.
problem for input ....... sn), and
Corollary 3.2. Tf C is individually fair, then Algorithm 2 is E-individually fair.

---

Published in Transactions on Machine Learning Research (09/2023)
4
Ratio Utility
In Definition 2.7 we consider the ratio utility obtained by selection algorithm, and show that this is controlled by the minimum ratio of ps and 82.
4.1 Offline Cohort Selection
We begin with the scenario of selecting k of n individuals when all candidates are known in advance. Dwork & livento (2019) give a solution to this scenario (with non-optimal utility, as shown in Example 2.2 we present Algorithm 3 an alternate one that achieves the optimal ratio utility. Notice that the sum of classifier scores Σ, 8; need not add up k. If the sum exceeds k, the algorithm simply scales down all probabilities that the new is k. It. is not hard to show that this operation preserves fairness and gives optimal utility. This multiplicative scaling will not work when the sum is smaller than k however, since it increases the probability difference among candidates and can be unfair. Intuitively, the solution in this case is to additively increase all probabilities by the same amount, thus preserving fairness. However, some care is needed, as no probability can exceed 1.
Alg. 3: Offline Cohort Selection for Ratio Utility
Input: scores $1,..., Sn E [0, 1] from C, cohort size Output: set of accepted candidates
sum Σ Ei=1s;
if sum k then
// move scores up
c+ k-sum P; + 8; + c, E [n]
while -p: > do
Sx1 [j:p}<1] <}
Pj + Pj + P-11
Sall Vj:pj <1
P: 1
else
// move scores down
t Vi E [n]
Ps - sum
// Now list sums to l and all p; E [0
10 { pround-pr(PI..... Pu. 1) // select cohort of size k
11 return candidates with non-zero p;
Lemma 4.1. If sum < k Algorithm S increases each input score s; to a final output = 8; + a; 2 s; such that all of the condidates with Pj < receive the same cumulative adjustment value aj- = V.
Theorem 4.1. For any classifier that assigns scores $1,...,8n n candidates, Algorithum solves the fairness- fairness-preservin preserving cohort selection problem by selecting k candidates with marginal probabilities Pl Pa. that achieve the optimal value of ratio utility min, Ri.
Corollary 4.1. If C is individually fair, then Algorithm 3 is individually fair.
4.2 Online Cohort Selection
We consider the online scenario, in which our goal is to keep few candidates pending possible. It is clear that the number of candidates hold must be at least & since need to accept & candidates at the end. We provide an algorithm that achieves optimal ratio utility for the online hainess-preserving cohort selection problem, while leaving only O(k) candidates pending. We use a parameter E [0. 1/2), which controls the number of candidates pending, with a = 1/2 by default. The update procedure depends on the sum of scores of the candidates seen so far. We maintain set of k/a candidates with highest scores called TOP, and two REST and RAND of the remaining candidates. A new candidate i added either TOP (and thus bumps some other candidate from TOP to REST), or they are added to REST. We make sure
10

---

Published in Transactions on Machine Learning Research (09/2023)
Alg. 4: Online Cohort Selection for Ratio Utility
Input: stream of scores $1,..., 8n E [0, 1] from C, cohort size k, constant a E [0,1/2]
Output: set of accepted candidates sum +0
TOP + 0; REST < 0; RAND <
for condidate in stream do
sum t sum + Sü Ps <-
if sum < k then
if |TOp| < [k/a] then add i to TOP else if min(s;) in TOP < 8; then move min element from TOP to REST add to TOP
10
else add REST {pe:i : E REST) -rounnd-prll (r(pp: : E REST ).1 a))
for j in REST with Py do
13
remove j from REST
14
add to unif. reservoir sample of size k reject candidate that was eliminated from the unif. reservoir sample
15
16
set RAND to unif. reservoir sample else
17
18
if first occurrence of sum 2 k then reject all candidates in RAND and remove RAND store TOP and REST in PENDING
19
20
21
incr +
k scale +
22
else
23
incr sum-$1, scale <- scale incr
24
Ps < Pt scale
25
Pş < Pj iner, Vj E PENDING
26
add to PENDING
27
{pr : PENDING] -rounddpr(fp: : i PENDING], 1)
28
reject j and remove from PENDING if pj =0
29
if sum < k then k-sum
30
Pi + Pi GG, Vi E TOP U REST
31
p.-
RAND
ViE E RAND
32
while 3pp > do
33
S(2)) + c
Stan
P--
34
Pj - P, + tc, Vj E TOP U REST with pj < 1
35
Amoditied to number of modified people
38
Pj 2 P
|RADD|
Vj E RAND
37
P4 1
(pa:ie E TOP REST U RAND) r-runnd-rrd prppprr((ppp : TOP U REST U RAND), 1)
39
set PENDING to indices of nonzero P4
return PENDING
the list REST is not too big by rounding and eliminating candidates. Eliminated candidates are sampled uniformly to enter RAND, which has size k.
During the online phase, is tempting use the idea from the offiine case to eliminate candidates; take two candidates from REST with scores and and round them to b and O. However, must be careful
11

---

Published in Transactions on Machine Learning Research (09/2023)
when rounding REST to ensure that probabilities will not later exceed 1 if the stream ends with sum < k. The key idea. (and motivation for having TÖP) is that candidates not in TOP have increments at most o, which we can see as follows. For REST to be non-empty, we must have at least n > k/a candidates. Let æ be the number of candidates who are in TOP when the algorithm finishes and achieve probability 1. For cach of the other candidates, the increment P4 - 8, is less than (k - #)/(n - x) < k/n, since < n. Thus that cumulative increment is at most a, and is safe to round probabilities in REST to and a.
If the stream ends with E. < k, we will increase the scores of everyone pending, and use RAND to compensate for already eliminated candidates. Let A be the set of candidates in TOP and REST and A be the set of all others seen. As in the offline case, we will evenly increase the probabilities of all candidates by adding the appropriate с to each candidate, and using water-filling where some candidates reach 1. For candidates in A, this proceeds exactly as in the offline case. For candidates in A, we increase the probabilities without explicitly storing all of them by maintaining set called RAND consisting of k uniformly random candidates. Each member of RAND receives probability equal to 1/k times the sum of the probabilities of the candidates in A. Since everyone in À has the same probability, this rounding clearly preserves the marginal probabilities. Finally, we use the offline algorithm to select the cohort from the union of RAND and A.
The case where the sum of probabilities exceeds k is simpler. The algorithm always scales down all proba- bilities so that they add up to exactly k. When a new candidate appears, they receive a probability equal to what C gives them, times the current scaling factor, and get added to TOP U REST. The algorithm then scales down all probabilities so that the sum exactly and reduces the size of TOP U REST by repeatedly rounding pairs of candidate as in the offiine setting. In this case, the set RAND is not used.
Theorem 4.2. For any classifier C that assigns scores $1....,5n to n condidates, Algorithm A solves the preseroing cohort selection problem by selecting & candidates with marginal probabilities Pi..... Pn that achieve the optimal value of ratio utility. The algorithm leaves no more than O(k) candidates pending at any lime.
Corollary 4.2. If C is individually fair, then Algorithm 4 is individually fair.
5 Conclusion
In this work, we defined two notions of utility for the problem of cohort selection, linear and ratio utility, and designed polynomial time algorithms that optimize them (or approximately optimize them) while preserving the fairness of the given classifier. This means that if the given classifier is individually fair, then our cohort selection algorithus are also individually fair with respect to the same metric. We studied two settings, the standard offline setting and an online setting where we can reject candidates at any stage of the process and accept candidates only at the end, keeping the number of candidates that are waiting for the decision low. While our algorithms for ratio utility and offline linear utility are optimal in terms of fairness and utility, our online algorithm for linear utility achieves e-individual fairness with an additive error in the utility and the number of candidates kept hold.
Overall, our approach is based on the assumptions that every candidate contributes to the utility of the cohort separately and that the candidate utilities are correlated with their selection scores given by the individually fair classifier. As the linear utility requires the assumption that the utilities of the candidates are their classification scores, we tried to relax it by defining the ratio utility in which the utilitics are unknown but still correlated with the classification scores. The natural extension of this work would be to design algorithms that optimize utility function where the candidate utilities are known and decoupled from the classification scores. Another interesting direction would be to relax our first assumption and study utility functions where the candidates do not contribute separately, but the cohort utility depends on the combination of candidates selected.
Acknowledgments
KB and JU were supported by NSF awards CCF-1750640 and CNS-2120603. KB and HN were supported by NSF grant CCF-1750716.
12

---

Published in Transactions on Machine Learning Research (09/2023)
References
Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, and Juba Ziani. Pipeline Interventions. In Innovations in Theoretical Computer Science Conference, ITCS '21, 2021. https://arxiv org/ abs/
Amanda Bower, Sarah N Kitchen, Laura Niss, Martin Strauss, Alexander Vargas, and Suresh Venkata- subramanian. Fair pipelines, 2017. htttps//arxiv.. wttp 170pp/0917700011111
Amanda Bower, Hamid Eftekhari, Mikhail Yurochkin, and Yuekai Sun. Individually fair rankings. In 9th
International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 8-7, 2021. OpenReview.nel, 2021. httpaa///aaziiv.og/bbbbb////////
L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. In 45th International Colloqucium Automata, Languages, and Programming, ICALP 2018, July 9-18, 2018, Prague, Czech Republic, volume 107 of T.IPTcs, pp. 28:1-28:15. Schloss Dagstuhl Teibniz-Zentrum für Informatik, 2018. doi: 10.4200/LIPIssICAAPPPP. 2018.28. URL https:///// htttps://ao..orr/100.. www.:..422/IIIII.... ICALP.
2018. 28 https://ar wttp:/o////ab////o/a http:://arrav.orrr/bb///...... 06840
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange prop- ertics of combinatorial structures. In IEEE Symposium on Foundations of Computer Science, FOCS '10. TEFE, 2010. https://arxiv http://axxxvo../abbaa/// wtw.orgg//a/aeeeeee/eeeee 0909/0999..444 4348
Cynthia Dwork and Christina Ilvento. Fairness under composition. In Innovations in Theoretical Computer Science, ITCS '19, 2019.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovalions in Theorelical Computer Science, ITCS '12. ACM, 2012. httpa://arxiv.orgg Abb//110.39913
Cynthia Dwork, Christina Ilvento, and Meena Jagadeesan. Individual Fairness in Pipelines. In Symposium on Foundations of Responsible Computing, FORC '20, 2020.
05167
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In Conference on Neural Information Processing Systems, NIPS '16, 2016.
Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. In Advonces in Neural Information Processing Systems 29: Annual Conference on Newral Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 325-333, 2016.
orggaba/160a 001160000011999
Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. Fair algorithms for 09559
infinite and contextual bandits, 2017.
Sampath Kannan, Aaron Roth, and Juba Ziani. Downstream effects of affirmative action. In Conference on Fairness, Accountability, and Tronsparency, FAT* '19. ACM, 2019. https://arxiv.org orgg/bs//88888
09004
Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Meritocratic fairness for cross-population selection. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. JMLR.org, 2017. https://arxitn httpp://aarr...orr//bb////88 08716
Thomas Kleine Buening, Meirav Segal, Debabrota Basu, Anne-Marie George, and Christos Dimitrakakis. On meritocracy in optimal set selection. In Equity and Access in Algorithms, Mechanisms, and Optimization, F.AAMO '22, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450394772. doi: 1L1145//355124433553005 URL https://doi. httpp://doo..or////// org/10.gg/..oo 1145//51114 15555/5555162.33355555
Ashudeep Singh and Thorsten Joachims. Fairness exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 2219 2228, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355520. doi: 10. 10.1145/3219810 3220088. URL httph::t/:/att orgg 1111:/1111111111999911111 3220088 h http::/arrrrerrrraaa///B0O00-.
13

---

Published in Transactions on Machine Learning Research (09/2023)
Julia Stoyanovich, Ke Yang, and H. V. Jagadish. Online set selection with fairness and diversity constraints. In Advances in Database Technology EDBT 2018, Advances in Database Technology EDBT, pp. 241- 2018. doi: 10.5441 /0t///0e2./221..2222...
252.
Jeffrey S. Vitter. Random sampling with a reservoir. ACM Trans. Math. Softu., 11(1):37-57 March 1985. ISSN 0098-3500 doi: 10.1145/3147.35 URL http://doi..cm www.m...g//...00 111g//0.1145/1147. 31165
Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In Proceedings of the 29th Interna- tional Conference on Scientific and Statistical Database Management, SSDBM '17, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450352826. doi: 10. 1 15/3385550440055566 URL http:///axxvvvv..//a// 11111111188888 08559.
Ke Yang. Vasilis Gkatzelis, and Julia Stoyanovich. Balanced ranking with diversity constraints. In Proceedings of the Twenty-Eine Fighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 6035 6042. International Joint Conferences Artificial Intelligence Organization, 7 2019. https:
7/arxiv. wwwpi//.rrggbb////990//// 01747
Meike Zehlike and Carlos Castillo. Reducing disparate exposure in ranking: A learning to rank approach. In Proceedings of The Web Conference 2020, pp. 2849 2855, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450370233. URL https:///ol..or//000111/////// htt.://////011111101110300600010 3380048
https://arxiv. wwwpp/wwwwwg//////....../
Meike Zehlike, Francesco Bouchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza- Yates. Fatir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM '17, pp. 1569 1578, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349185. doi: 10.1145/313284 33332938. URL httts::/doi..rr org/
10. 00.1145/3132847 3132938
313299999 https://arxiv.orr/aaae
06368
A Proofs and Algorithm from Section
2
A.1 Proof of Lemma 2.1
Lemma 2.1. The worst case ratio utility is equal to the minimum ratio of selection probability and classifier score of one candidate ming
PEn
min;
Pi 5,
Proof. Let j be the index of the candidate with the smallest ratio of model output and classifier score, i.e. Ei < Rt Vi # j. Compare the minimum over all utility vectors to a particular choice utility vector u'
satisfying u² = 1, and Wizs = 0. We know that the ratio for any particular vector will be at least as large as
pene Σ pent P5n Σ,
the minimum: min, Σ. 8944
min; Pi
Σ. su, 4545
We can also obtain bound from the other direction. Let m be the smallest ratio between model output and classifier score = min; pi/s; and u E [0, 1]m be any utility vector with Σ, ue > 0. Then, for all i E [M]
we have p.u 2 ms,u, Therefore, ming p44 2 min; P
s:N:
A.2 Dependent Rounding Algorithm
Here we include a detailed description of the dependent rounding algorithm (Algorithm 5
mentioned in
Scction 2.2
A.3 Proof of Lemma 2.2
Lemma 2.2. Let on....;a, be list of numbers in [0, m] with Σn= a, There is randomized algorithm that outputs 01,..., ān [0, m) such that. ] of the as will be equal to m, one Og will be - m, the
14

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 5: Rounding
Input: a list of n numbers d1, d2. .2......0 On R20 and the maximum value rounded number m Rg0 Output: list of rounded numbers 21, ........ . an E Rz0
pendinglndex +-1 for i from 2 to n do
if a; = 0 and Opendinglndex = then continue to next a < a; -- ApendingIndex
choose u randomly from Uni 1) if + m then
if a+b then
a + b OpendingIndex < pendingIndex i else
d2 t 0: Opendingtudex a a++1
11
end
12
else
if < m then b-
13
14
a, t @pendingIndex f- +
15
elsc
16
a, t + b - m OpendingIndex f- m pendinglndex f-
17
end
18
end
end
20
return d1, ...
rest will be equal to O, and for all i E (I,...,m,) n), B[ā.] a.. When 1, we call this algorithm round-pr and when a1....y On natural numbers call it round-nat.
At step we have two numbers a and b which get rounded and obtain new values denoted by and b, respectively. The rounding depends on the value of a a-b a + b less than or equal to B, then E[a] = (a + a4 = a. If a + is greater than / and at most 3-a 2)
Proof. We begin by showing that for all i E [n], E[ã,]
Since the expected values remain constant throughout the process, we conclude that for all i E [m]. B[ā,] = a;-
28, then E[a] v
3-b 22 + (a
a. Similarly, we obtain E
We notice that for any step of the algorithm and for all j that are smaller than but are not the pendingIn- dex, aj or a, = B. As result, at the end of the algorithm all elements with index such that n and j * pendingIndex and one of the n-th or the pendingIndex elements
rounded to either 0 The remaining element is the only one that can have a value in all [0, 3]. Since Σ/= a; sum, _ elements
are 8 and the remainder sum
sum 3
| is non-zero, assigned to the remaining element.
A.4 Proof of Corollary 2.1
Corollary 2.1. If m = and Σn= 0; = k E N, then after the dependent rounding of round-pr k elements will be equal to and the rest will be equal to
Proof. The proof follows directly from Lemma
2.2
15

---

Published in Transactions on Machine Learning Research (09/2023)
B Proofs from Section 3
B.1 Proof of Theorem 3
Theorem 3.1. For any classifier C. that assigns scores $1....,88 to candidates, Algorithm | solves the fairness-preserving preserving cohort selection problem by selecting k candidates with marginal probabilities P Pn which achieve optimal lincar utility Ei=1P:s;.
Proof. Algorithm I consists of two parts, In the first part, it modifies the input scores so that they sum up to k; which is the size of the cohort, and for the second part it randomly selects & individuals by calling the round-pr subroutine. We can simplify the first part by rewriting it in a more concise way. If the sum of C's scores 8,,..., Sn is less than k then for any candidate i [nx] we set p; = min(s; + b, 1}, with b in [0, 1] such that Σi= P: = k. More specifically, P; are initially set to s; + c so that their sum is equal to k. Their sum will remain equal to h; because the following loop only redistributes probability mass among candidates. If at any iteration some candidate i has p; 1, then their marginal selection probability is set to 1 and the excess probability mass is redistributed evenly to all candidates with marginal probabilities less than 1. At the end, any probability that is less than 1 is equal to s plus a constant b that consists of the initial e and the fractions of the probabilitios that exceoded 1. Similarly, we have that if the sum of C's scores is greater than k, then for any candidate i, Pr = max( 8; - b, 0} for a real nunber E [0, 1] such that Σ Pi k. If the sum is equal to k the cohort selection marginal probabilities are equal to C's scores. Finally, by Lemma 2.2 we obtain that for any i [n] the expected value of indicator p; is Pt, and since p; is either 0 or 1, the i-th candidate is selected with probability/ ps-
First, we want to show that the cohort formed by Algorithm 1 preserves fairness. Depending on the value of E 8i, we have three cases.
Ex S = k. The input scores are used unaltered as the marginal probabilities for the cohort selection and, thus, we have that for any pair of indices i, lp; pyl = [s; -syl.
2. Ei=1s < k. The cohort selection marginal probabilities are of the form p: min b, 1). For any pair of individuals i, j, if both have probability of being selected 1, then [p; - Pyl = 0. Else, if
pa 1 and p, = 8j + b, we have pp Pyl < |s, syl because s; + b 2 1. Finally, if p. s, + b and
Pj = Sj + b, then it holds that [p; Pj = |s: syl- As a result, we conclude that for any pair of individuals i, we have lp; p,l S |s; - sزر-
3. Σ 8, > k. In this case, the cohort selection probabilities are of the form p; = max (s; - b, 0,03. For any pair of individuals j, if both have zero probability of being selected then Ip: - pyl = 0. Flse,
if ppp=0 =0 0 and pj = 8, - b, we have [p. py1
-Ppl < [s; - syl- Finally, if p; = 5; - and pj = Sj - b, then it
holds that Ip: pyl |ss - syl. Thus, for any pair of individuals i, we have lp. Pyl S |s 8j
Second, we show that this cohort optimizes linear utility. The fairness- fairness-preserving solution that optimizes linear utility solves the linear program defined in Section 1.1 and satisfies the first constraint with equality, i.e. ET P = k. This holds because otherwise we would be able to increase p; by setting 1/ = (p: 1}, for some d E (o, 11, so that E p. = l and obtain greater utility while not violating any constraint.
We assume that there exists different prenesss-r solution p'.....,p', which achieves higher utility, i.e. Ex
E/= pis;. Without loss of generality we can assume that the original probabilities s; are sorted in increasing order. Specifically, we have 8 I $2 S... sn, The solution of Algorithm [ maintains the same order, i.e. Pi S P2 S ... I Pn. Let i be the individual with the smallest index for whom the two solutions differ. There are two possible cases. If pb < P:, then since E Pi = E P/: = k there exists an individual with j >> i such that 1/ > Pj- In addition, we see that ps >> O and Pj < 1. The values of the probabilities depend on the sum of the input scores in comparison to k. If the sum is greater than k, all p; that are not zero are of the form p. = s; b. Hence, considering that E < P. S P3 < <P', we obtain 1P/-p/í = p/z - p/ > b--bb(ss; (s-bb) = =sy-S 8, = [s; syl Similarly, if the sum is less than l. the values of pa that are not one are of the form P. 8; +b, therefore giving p/'-1',1
p111 = F'y pl > 83 bb+b (st+ +b++) 8j 8; = 18:- syl-
16

---

Published in Transactions on Machine Learning Research (09/2023)
p/- > Pj Ps 83 83 =|s-- -syl- In all three cases the If the sum is equal to k, have 1p4 1 p/11 pl} constraints of the optimization are violated.
If pf > Pi, then there exists an individual with j > i such that p/_ < P,. Let be the smallest such index. If there exists another index j such that pi 2 Pt, then by the previous argument the constraints are not satisfied. Therefore, for any candidate 1 after p/ < pt- This solution achieves non-optimal utility because there exist candidates with h [ and p/ Ph: such that we can move probability mass from candidates h to individuals without violating the constraints. By constructing a solution p"....,P% which gives greater utility than .'...., Pr: we arrive at contradiction. Therefore, Algorithm [ finds the optimal prireess-reeervvng solution.
B.2 Proof of Corollary 3.1
Corollary 3.1. If C' is individually fair, then Algorithm | is individually fair.
Proof. The individual fairness condition for Algorithm I is satisfied by the assumption that the input scores are individually fair. More specifically, if the individual scores from C are individually fair with respect to a metric D, we obtain that Vi,j E [n], lp: - pyl z 1s+ ر, S D(i,j).
B.3 Proof of Lemma 3.1
Lemma 3.1. Given selection scores .1,...,8,, 8n from C, for a set of n candidates and parameter E (0, 1], we split (0,1) into m = = intervals of length s and for all i E [m] we set 8, = ge, where g is such that 8; E ((g- - 1),, ge]. When Algorithm [ runs for input $1,..., &n and cohort size it solves the e-approximate prireess-preservingg cohort selection problem with marginal selection probabilities pı.... PP,, and achieves linear utility Ei=Piss; 2 2.=1P, k(E + 2/E), where pi....,P, - is the optimal solution for the offline fairness-preserving problem for input ,8.
Proof. We have that for all individuals i in [m], 0 S - 5: S s. Therefore, we obtain that for any pair of individuals i,j, |& -3,-8y1- $ |s; syl + By Thcorem 3.1 we have that 1p: pyl S |s; Syl- Combining the two inequalities, we obtain that fairness is preserved c-approximately.
Note that Algorithm D always adjusts the scores of candidates such that its final output probabilities sum to k. For any candidate we observe that since the rounded score & is greater than 8; by at most E, the two output probabilities, pt and pt are also close, at most & apart. Depending on the sum of the input scores there are three cases.
If E.= 8, S l and Σi_ & S k then Algorithm ] shifts all the probabilities up. More specifically, we have that p = min [1, + x) and p. = min 8 + y), for some non-negative x and y. Suppose that y x, then for any candidate i whose marginal selection probability pt has not been clipped obtain that k = >E= Pf Σ P: h. which is not feasible. Similarly, suppose that > y + e, then for any candidate i whose marginal selection probability pt is has not been clipped, P = 8; + x > 8 + Pt- As a result, we get that Σi-P > E Pi, which is again false. Hence, we see that y S S &
to 1, P: à; + > s, + pf By summing up for all candidates
2. 12 2 k and E &; 2 hs then Algorithm I shifts all the probabilities down, so that both sums become equal to k. Thus, p. = max(0, s; x and p. max(0, 8; y}, for some non-negative x and y. Suppose that y < x, then for any candidate í who has non-zero marginal selection probability p.. By summing up for all candidates we obtain that k k= Einr P. EE=1. P; = k; which not feasible. Similarly, suppose that y > x + E, then for any candidate whose marginal selection probability p; not 0, P: = 8; - y << st -a--r = pf. As result, get that En P > Em Pi, which is false. Thus, we see that x S Kysz x
p, we have that p = 8;
8
If D' 8, S and ΣTh 8, 2 k, then Algorithm sots p = min (1, 8; + +x) and p. = max v). for some nen-negative x and y. Suppose that x + y > E, then for any candidate i who has non-zero marginal selection probability Pt, we have that pt 8 y < 8; + and Pt < 1; therefore p, < p..
17

---

Published in Transactions on Machine Learning Research (09/2023)
By summing up the selection probabilities of all the candidates obtain that = Ei=1P: Σi= P. = k, which is not feasible. Similarly, suppose that x + < 0, then for any candidate whose marginal selection probability p is not 1, P s; t < 8, y pf As a result, we get that Ei=1 < Ei=1Pt Pi, which is false. Therefore, we know that S x x y
In all three cases we see that for any candidate the selection probabilities of the two solutions satisfy pi pil 1 e. Now, consider any coordinate for which p 2 Vē. Since pi 2 p e, we have that pi (1 V and, thus, p;s; 2 (1 se Let E be the set of all individuals who have p < Ve.
If E 8: I h then p. = min s; + z}. Thus, 0 S 8 + < VE because both 8, and x are non-negative. Since both pi and D sun up to k; we obtain that -kx S Eieg P:8; S kvE kx and -kx S DiEEDia KVE- kr. Therefore, Eieg Pis; Pis; 2 EiEE P, KVE.
If E 8 k and Σ 2 K then D ma, s; and p; max (0, 8,- y}. Thus, 8, < VE. Furthermore, both solutions assign zero probability to candidates with 8, x < -e. As a result, all individuals in E whose 8 1, we have that EiEg P:8; 2 EiEE +(vE+
-E, have 8, within an interval of length VE + Similarly to case
If we split the linear utility to the utility of individuals in and not in E, we see that
k(E + VE) 2 n
Σ pis +
Σ P;s; 2 (1
Σ
Σpi pis:
Σ pist k(s + +2/E)
P:s.
EEE
E
B.4 Proof of Theorem 3.2
Theorem 3.2. For any classifier C' that assigns scores Sp to candidates, Algorithm 2 solves the online e-approximate fairness-preserving cohort selection problem for any (0, by selecting a cohort of size & with marginal probabilities PI,..., Pn, achieves linear utility Σ P;8; 2 E k(e + 2/²) (where Pr, is the optimal solution for the offline fairness- preeeesvip problem for input $1, .i,...,,,, sn), and keeps at most O(k + }) candidates pending.
Proof. We want to prove that Algorithm 2 and the algorithm described in Lomma 3.1 compute the same solution. In other words, we show that the probability p; that individual i selected by Algorithm is equal the probability qi that where ge if 8 ((g - I)e, ge). The first step prove that the scores 51, .,,.., 5n which are the input of the final rounding in line 28 satisfy the following properties:
selected by Algorithm applied the modified individual scores $1,..., 8n.
E 8 = k
2. E[a] = 44 vi E [m).
We saw in the proof of Thcorem 3.1 that for the offline algorithm all candidates of the same group have the same selection probability qi We will show that for any person i we have yi 59, where 8 is the final caleulated probability of any member of group g to which i belongs. The 8 we are referring to is calculated by the final execution of lines 6-22. These lines of Algorithm 2 describe the same procedure as lines 2-15 of Algorithm ! but from the point of view of groups instead of individual candidates. We consider three cases that depend on the value of the sum of scores from C.
Case 1: Ei. 8 = k. The offline algorithm considers the scores as selection probabilities and, thus, assigns probability qi 8, = ge to candidate of group g. Similarly, Algorithm 2 assigns probability s ga group g and in line 27 sets n28" n,ge n,G for the people who have not been rejected.
18

---

Published in Transactions on Machine Learning Research (09/2023)
Case 2: Ei=1 <.. The process that calculates s starts by setting 8 gE gE+ c. The offiine algorithm initializes the probability of i who is member of g as 4: = 8; + = g + c. Tf for all groups 9, ge c S 1, then the adjustment stops for both algorithms and we have that for any group 9, any member i of g has = s If there exists g such that qi > 1, then the corresponding 8 exceeds 1 by the same amount. Additionally, at this point the probabilities of all people in the same group as i will exceed 1 by this amount. Therefore, the ne1 of the two algorithms is the same. The offline algorithm runs the loop for all members of all groups that have individuals with qi 1. The online version aggregates the excess mass from all nº members of group g and redistributes it all at once instead of rumning separate iterations for every member of the group as the offline does. No extra mass is added after the initialization but it is only moved from group to group. Hence, we obtain that at the end of this process qi- = =
Case 3: 8 > k. Similar to case 2, if candidate is a member of group g, then q, = s9. Those who were rejected have 8; = 0 and n, = As a result, we see that for any person i, 8, = n,gi- From this we can infer that
n
TI
m
m
8
nilh
Σ 9
n
ΣΣ 4 = g
9 IEg
As new people are added to the groups, the group probabilities 8 become smaller in order for the sum of probabilities y to be equal to k. Therefore, the maximum number v of people that can be represented by a candidate in a given group either stays the same or increases after every iteration. By Lemma 2.2 we obtain that the rounding process maintains the expected value of the number of people cach candidate represents equal to their initial value. Since every person begins by representing only themselves, we have that for the i-th candidate E[n]] 1. Finally, we obtain [[[:]] E[n.q:] = Elm.]g:
di, because the calculation of s is deterministic. The final rounding procedure makes the final decisions and outputs 0 if the candidate is rejected and if the candidate is selected. Due to propertics 1 and 2, the probability of candidate i being selected by the online algorithm is qs- Thus, Algorithm 2 and the offline algorithm with input scores rounded to multiples of & have the same selection probabilities. By Lemma 3.1 Algorithm 2 preserves fairness e-approximately and achieves linear utility Σ;= P;s; 2 >i=1 - k(s + 2/E), where Pi. the optimal solution for the offline carness-preserveee problem for input ,
have that for 2 h the equal to k at the end of each loop. Therefore, we have 2g ng59 k. If of > 0, each person can represent at most [ candidates. By Lemma 2, the number of representatives per group is most
Because of the online probability adjustments,
of all the probabilities is
no
n2 <
+1 1
8 +
.8
since B2 < 2ngs9 If we sum up the number of representatives for all groups we obtain
m
n
m
1 1
(2n +1) 2k
+1.
g=u
This completes the proof.
B.5 Proof of Corollary 3.2
Corollary 3.2. If C is individually fair, then Algorithm 2 is s-individually fair.
Proof. If the individual probabilities of selection by C are individually fair with respect to metric D, we obtain that Vi.j E [n]
1p. PP-p5s S |s; -syl + S D(i.)) te.
19

---

Published in Transactions on Machine Learning Research (09/2023)
C Proofs from Section 4
C.1 Proof of Lemma 4.1
Lemma 4.1. If sum < k Algorithm 3 increases each input score 8; to a final output p; 5; + ag 2 such that all of the candidates j with Py < receive the same cumulative adjustment value ay D.
Proof. First we observe that p: 2 8, Vi. At each step of the algorithm the value of p. either increases, or is clipped at 1. Since 8; E [o, 1], Vi, we therefore know that, pt 2 8i.
Algorithm 3 initially adds a constant amount e to every candidate, then repeatedly redistributes overflow evenly across all candidates with t, < 1. We prove by induction that for all candidates i with p; < 1, their increment a are the same. Consider two candidates i,j such that their final Pa.P; < 1. As argued above, both Pi.Py are smaller than throughout the exccution of the algorithm. At the beginning, a, = aj the claim holds.
Given that these candidates are equal at a certain step d, we also know they will remain equal at the next step d + 1. By assumption, neither candidate reaches 1 on either of these steps; therefore they will both receive an adjustment. When an adjustment is made, all candidates are affected equally.
C.2 Proof of Theorem
Theorem 4.1. For any classifier C' that assigns scores $1....,8p Sn to candidates, Algorithm 3 solves the priseriinn cohort selection problem by selecting & candidates with marginal probabilities P1.--.:20 Pa that achieve the optimal value of ratio utility min;". p: a;"
Proof. We first show that Algorithm 3 either preserves decreases the difference between any pair of individuals. Let p; denote the probability that candidate is selected by Algorithm 3 Thus we must show, for all ú.j, Ip; pyl I |s; syl. We apply Algorithm 3 to a set of candidates and obtain two disjoint sets of output candidates: let. T(=1) be the set of candidates whose output = 1, and let T(<)) be the set of candidates whose output
1. Let Tau be the union of these two disjoint sets. The algorithm behaves differently depending on the value of Σ; Sg.
1. First, consider when Σ, < k. Let as be the cumulative adjustment received by candidate during the algorithm. The adjustments are exactly chosen such that E,(s; + a;) = k. Then we apply round-pr, where we know by Lemma 2.2 that the probability of being selected is preserved during rounding Pr(round-pr selects 1) = p: s; + 0g We thus need cover three cases:
(a) First, consider two elements Sy E T(=1):
lp: pa--, = [1 1/ S [s: -zl.
(b) Next, we have 8i, 8j E T<<)) By Lemma 4.1 these candidates all receive the same adjustment.
Let this adjustment be called b, lp: - Py s; + (s, + b)] |st - syl.
(c) Finally we have 8; E &;= E T(=1)- Note that a; S aj, and st > 8j. We see that (p: - psl =
$ a: (s, + a.)) = ss S, + a4 ayl S [s szl.
2. Next, consider Σ, 8: 2 k. Here we know
Σ, 41
I 1. By Lemma 2.2
Pi =
Σ at
k
St.
Then, for
candidates i and j, we have:
k
Ip: - py|
Σ 31
8,
Σ
8)
=
Σ S1
[s
83)
-8y
Thus see that |s; sy| 2 lp. ppyl
We next show that among fairness- preserving solutions to the cohort selection problem, Algorithm Jaciieves the maximum value of min; P. Let T(<1) and T(=1) be defined as above, and note that T(=)) may be empty. Consider for contradiction an arbitrary algorithm A' with probabilities of selection p which also preserves
fairness while achieving better utility: min; p min; 2
20

---

1 8, which is the same ratio Published in Transactions on Machine Learning Research (09/2023)
1. First, consider the case where Σ, 8 k and ((=1) is nonempty. Let individual have the most extreme ratio: Pt = min; R. Consider how to make this ratio minimal. For all individuals in T(<)): 3y
e = 1 1++ b. If any individuals j are in T(=1): they will have received some adjustment aj I b, and thus they will have an even smaller ratio. Therefore, we know that individual j must have 8j 2 8, vi and be a member of ((=)), and we have that for Algorithm A, min, P - By"
increasing 8; will reduce this ratio:
By our definition of A', there is some potentially different most extreme element providing better utility: gí min; gi Pi.
(a) If 81 = 8jz the largest minimum ratio pi that A' can achieve is = 51
as Algorithm A and contradicts our assumption.
(b) If st # 8,, we know 81 < 8j, since we already know that s, is at least as big as all other elements. This contradicts our assumption that A' has greater Since is 1, we know that Pi ri Mi utility than A.
2. Next, consider the case where E. 8 < k and T(=) group is empty. Again, let element j be the most extreme element for algorithm A, i.e. min, Pi Pi. Consider A' on its most extreme element I constructed as in Item 1
(a) This time, 81 = 8j, we may have p\ > Pt, achieving greater utility. To preserve the distances, if A' adjusts element by certain amount, it must adjust all smaller elements by least the same amount. However,
know that E, P, k, this required extra adjustment will mean that E > k. and A' will not be selecting exactly & candidates.
(b) If < 8j, then person j has the largest score, and similar to (2a), if p'J > Pj we see that Ed > k. p/ S Pj we have the contradiction in (1b).
3. Finally, consider the case where E. > k. Algorithm 3 all elements will be multiplied by factor of E. and then by Lemma 2.2 any element will satisfy Ps Σ. S,, so we have
min; pi/s: min, E (
Σ. Notice that in this case, all elements adjusted by
the same constant ratio. Using extreme element I for algorithm A' constructed previously, and again supposing that this element is more extreme than any element in algorithm A, we derive that pi Since clement was the minimum ratio for algorithm A', it follows that for all i,
p 85 Taking the sum on both sides we see E,r E, E )
k. As before, the number of elements chosen by algorithm A' will be more than k, which is contradiction.
Thus we conclude that A' cannot exist.
C.3 Proof of Corollary 41
Corollary 4.1. If C' is individually fair, then Algorithm 3 is individually fair.
Proof. The proof is analogous to that of Corollary 3.1
C.4 Proof of Theorem 4.2
Theorem 4.2. For any classifier that assigns scores $1,...,S, Sy to n candidates, Algorithm ! solves the haincsss-pesserve cohort selection problem by selecting candidates with marginal probabilities Pi...., Pn. that achieve the optimal value of ratio utility. The algorithm leaves no more than O candidates pending at any time.
21

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. We first show that, for list of candidate scores $1....,8m; 8n: the selection probability given by the offline Algorithm B for any candidate i is the same as that given by Algorithm 4 and therefore provides an optimal utility solution to the problem. Let Algorithm be denoted A and let A have probability of selecting candidate i. Let Algorithm
g be denoted B with probability qi selecting candidate i. A never accepts candidates until the end of the stream, thus there are two major cases.
The stream ends with sum 2 k, and A selects all candidates in PENDING. candidate i is added to PENDING in one of three ways:
(a) Candidate was in TOP when the sum reached &. At each round after the sum exceeded k they must survive round-pr, which by Lemma 2.2 always preserves their marginal probability. Therefore we only need to consider the effect of the incremental scaling adjustments. First, let scale,, sum, and incr,, represent the values of these variables at some step when the sum first exceeds k. We initialized scale, + sum. Consider the value of scale1+1:
scale:+1 = incr, scale, = sum4-1 S1+1
sum
k
scale;
Sum0+1
sum sum;
SUM1++1
Thus, we can see by induction that for all time steps t, scale; sum, express the final value of single element 8;, which by definition is at position i in the stream, as:
k
Furthermore, we can
k sum; 8,
Pi 8, scale,
II t=i+1
incr, 8: sum;
II tmi+1
sum;
II 1=1+1
k
8;
Sum,
sum,
sum,
Thus we see that the final pæ is adjusted exactly the same way as it would be in the offine case, (b) Candidate i was already in REST or arrived at the moment when the sum reached k. For each iteration, they must survive round-pr, which respects their marginal by Lemma 2.2 From that point forward, they are part of PENDING and treated the same as in la
(c) Candidate i was encountered when sum 2 k. In this case, they are treated the same as in part la above.
In either case, when A ends, a subset of candidates are selected from pending using round-pr, which again preserves their marginal probability. Thus p. qi in these cases.
2. The stream ends with sum < h. A has three sets at this point: TOP (the greatest [k/a] elements of the stream), REST (at most [k/a] elements rounded to 1 a) and RAND (a randomly selected group of & candidates, disjoint from TOP and REST).
No acceptances are made until the stream ends. The top candidates are placed into TOP, and elements are added REST via round-pr, which preserves original marginal probabilities exactly by Lemma 2.2 The only change in probabilities then comes from the additive adjustments made when the stream ends. The main difference between the additive adjustments here and the water- filling behavior in B is how treat the people in RAND.
For the purpose of proof, consider conceptual algorithm A' that behaves exactly the same as A, except instead of RAND it has ZEROS, list of all candidates outside of TOP and REST. When this conceptual algorithm ends, all the mass from water-filling in ZEROS will be collected into a set of k random candidates, which becomes the equivalent of the list RAND in A.
In more detail, at the end of A', each member of TOP, REST, and ZEROS is given kmsum and any overflow is redistributed using water-filling Any candidate now has the same probability of selection by both A' and B: s; + a, A' then performs final round-pr step to select the outputs. Thus, in A', TOP, REST, and ZEROS are given the same treatment they would receive in B. Before the final step of selecting candidates by round-pr, A' collects all of the mass accumulated in ZEROS
22

---

Published in Transactions on Machine Learning Research (09/2023)
from water-filling into random subset of l members from ZEROS. Thus the only difference between A and A' is that, A' first kept everyone and later uniformly sampled subset of k people, whereas A immediately keeps a random subset of k. This subsampling step does not change the marginal probabilitics of any element in ZEROS; their probability before and after collecting the mass of ZEROS At the end, A selects candidates using round-pr on the entire set TOP REST U RAND, which does not affect the adjusted marginals 8; + 04. Thus p. = 8; + a, = q.i.
Next, we show that the algorithm keeps at most O(k) candidates pending. Any candidate not in one of: тОP, REST, RAND, PENDING is considered rejected. The sizes TOP and RAND are explicitly bounded by [k/a]. REST not bounded in size explicitly, but nole that the set maintained by constantly applying (fp.-ess 1- a). After rounding, most person in REST has a value (1 -a). If we ever have more than [k/(1 - a:] elements, have sum 2 [ a1 a) > k. This goes to the sum 2 k case, which no longer adds elements to REST, thus it is bounded in length by [k/(1-a)]. PENDING is created initially by adding TOP and REST ([t((1 a)] + [k/a] pending), but for subsequent steps is never longer than k by Lemma 2.2 Thus the worst we can do is remain under a sum of k for the entire stream. TOP, REST, and RAND will all be kept pending until the end of the stream, but still we have at most [k/a] + [k/(1 a)] + [k/a] = O(k) candidates pending.
C.5 Proof of Corollary 4.2
Corollary 4.2. Tf C is individually fair, then Algorithm is individually fair.
Proof. The proof is analogous to that of Corollary 4.1
23


Reviews:
[{"review_id": "VKwtTw65vj", "reviewer": "Reviewer_3ZmY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n1. The paper addresses a timely problem of individually fair and utility maximising cohort selection while scores over the candidates are yielded from an individually fair classifier.\n\n2. The authors uses ratio utility (a proxy of worst-case utility function) to show a case where the proposed method of Dwork & Ilvento (2019) fails to be utility maximising and the proposed approach triumphs.\n\n3. The idea of using dynamic programming followed by dependent rounding constructs a clear and simple basis for the proposed algorithms.\n\n4. The interesting algorithmic idea of this paper is to maintain a queue of pending applicants so that they can be considered in future while not growing the queue above $O(k)$.\n\n\n# Weaknesses\n\n1. The paper invents ratio utility as a proxy of the worst-case utility function and use it further to show benefits of the proposed method. I am not sure where it really matters in practice. Specifically, \n\ni. it is not clear how does it correspond to the fair-utility maximising cohort selection problem under general individualistic utility, i.e. $\\max \\sum_i p_i u_i(s_1, ..s_n)$ with the constraints similar to the LP program in page 3.\n\nii. it is also not clear how does it correspond to the fair-utility maximising cohort selection under any collective utility, , i.e. $\\max \\sum_i p_i u_i(\\mathrm{cohort}_k, s_1, ..s_n)$ as in Equation (2) in [1]. In brief, when the utility of an individual in the cohort depends on the other selected candidates.\n\nA clear understanding of these relations, theoretically and/or numerically, would provide us a motivation to study the ratio utility. Right now, it is not clear.\n\n2. Though the paper studies such a practical problem with existing literature in meritocratic fair selection/ranking, it is surprising that there is no numerical comparison or illustration of the goodness of this method. Without that, it is hard to accept that the proposed methods are effective in practice for general utility functions, as claimed.\n\n3. The paper should at least numerically compare with the meritocratic fair selection and fair ranking algorithms. The justification that meritocratic fairness papers need scores to be reflective of 'true merit' is not agreeable. We can replace the $x_{ij}$ in [1] with scores and still the algorithm in [1] works. [2] shows that meritocratic fair selection can be generalised to include any utility function and any score representing a proxy of 'merit' to conduct fair and utility-maximising cohort selection. Also the argument against not comparing to [3] is weak if a numerical experimentation is conducted. This is the biggest missing link to judge the effectiveness of this work.\n\n4. In reality, no classifier is completely individually fair. They are rather $\\epsilon$-individually fair. What happens to the fairness of the proposed algorithms then?\n\n\n[1] Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Meritocratic fairness for cross-population selection. In International Conference on Machine Learning - Volume 70, pp. 1828–1836. 2017.\n\n[2] Thomas Kleine Buening, Meirav Segal, Debabrota Basu, Anne-Marie George, and Christos Dimitrakakis. \"On Meritocracy in Optimal Set Selection.\" In Equity and Access in Algorithms, Mechanisms, and Optimization, pp. 1-14. 2022.\n\n[3] Amanda Bower, Hamid Eftekhari, Mikhail Yurochkin, and Yuekai Sun. Individually fair rankings. In International Conference on Learning Representations. 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of cohort selection, i.e. selecting $k$ candidates out of $n$, which achieves both fairness and utility. This problem is studied in the offline and online full-information setting, and with linear and ratio utilities. Specifically, the approach considered is to compose predictions of a single classifier to select the cohort. The paper proposes two polynomial-time algorithms for offline settings and two utility functions, and their corresponding online versions. The interesting part of the algorithms are that they are individually fair if the classifier is individually fair. For the online algorithms, the interesting idea is to keep a queue of $O(k)$ candidates pending at any time for future comparison and fair selection. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can you add a justification against choosing the ratio utility? Where it will be useful in practice (by showing some theoretical or numerical results), or is it just a theoretical tool to prove the worst-case performance for any utility?\n2. Can you show experimental results on some (real-world or real-like) selection dataset, where the proposed online or offline algorithms demonstrate benefit over existing algorithms for fair cohort selection? Specifically, given practicality of the problem under investigation and known experimental results in the literature, can you compare against existing individually meritocratic cohort selection techniques like [1] or collective meritocratic cohort selection techniques like [2]? \n3. Can you please add results on the fairness of the proposed algorithms when the underlying classifier is only $\\epsilon$-individually fair?\n\n[1] Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Meritocratic fairness for cross-population selection. In International Conference on Machine Learning - Volume 70, pp. 1828–1836. 2017.\n\n[2] Thomas Kleine Buening, Meirav Segal, Debabrota Basu, Anne-Marie George, and Christos Dimitrakakis. \"On Meritocracy in Optimal Set Selection.\" In Equity and Access in Algorithms, Mechanisms, and Optimization, pp. 1-14. 2022.", "broader_impact_concerns": "The proposed algorithms, specially the ones in the online setting, can be interesting to ensure fairness in online selection platforms. But without a numerical demonstration or a practical case study, it is hard to conclude about their applicability.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Jbj9PIs0xy", "reviewer": "Reviewer_QhfX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- This type of issue of fairness with composition is vastly understudied and I think it is nice that the authors are tackling some of the problems arising there. These types of settings where the decision we make on each individual also depends on the decision on other individuals are seldom studied (the usual framework looks at classifying/scoring people independently with no capacity constraint)\n-There is something interesting about how the authors’ algorithms deal with the impossibility to obtain fairness in a fully online setting, by delaying decisions on a fraction of people and trading-off fairness vs how many people the algorithm has to put on “hold”. \n- It is nice that the paper looks at several types of utilities, and in particular about not having full information about the utility of a candidate/agent. \n- The algorithms work with a relatively small number of candidates pending for both ratio and linear utilities (of the order of k, the number of people selected in the cohort. In a hiring process, I would imagine that k is very small compared to the number of candidates, so this represent a small fraction of the population)\n\nWeaknesses: \n- Can Algorithm 1 be implemented through a linear program? If so, can the authors discuss a bit more how Algorithm 1 helps over solving the LP directly? Is it because it provides a basis for the online algorithm? It might be nice to highlight this.\n- My main concerns however are with respect to the ratio utility:\ni) The ratio utility is a bit weird. I understand why we care about $\\sum_i p_i u_i$ where $u_i$ is unknown, I am not sure what the renormalization factor in the ratio represents, however. It would be nice for this to have more discussion. I understand $\\sum_i s_i u_i$ as the utility we get if we use the scores directly as probability of selection, but why is that the right benchmark? \nii) Related to the above, the results for ratio utilities, starting from Lemma 2.1., seem to heavily rely on optimizing this specific ratio expression. This would not appear if for example we wanted to optimize just $\\sum_i p_i u_i$. It’s also very worst case in a weird way; basically the worst case can only happen if the utility is 1 for a single agent and 0 for all others, which seems unrealistic. In fact, if the scores themselves were obtained through a reasonable process (not just fair, but also with some level of accuracy), there should be some correlation between $s_i$ and $u_i$ that would prevent such cases. It would be nice to develop this a bit more. \n\nOverall, I think the main idea is interesting and the algorithms are nice, but I think the paper may need a bit more framing/justifying its assumptions before it is published. I think adding more justification and discussion of the ratio utility would be sufficient, in my opinion, to have this at TMLR!\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper starts by motivating the problem of composition in algorithmic fairness. It is known that composition of fair decisions may not lead to a fair composed algorithm, and this has been addressed in the context of dependent composition and cohort selection. The authors provide offline and online algorithms for cohort selection under two different utility setups.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses", "broader_impact_concerns": "No concern here. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "X5QJnOKOpx", "reviewer": "Reviewer_zKWw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n1. The paper considers an important setting for fair classification and improves significantly on prior work.\n2. The relaxation of online cohort selection to place candidates 'on hold' is an elegant path around the impossibility results. One suggestion for future work could be to consider whether there are methods that reduce the time on hold or ensure that similar candidates spend similar time on hold if additional opportunities to revisit candidates are intermixed, rather than held to the end of the stream. \n\n**Weaknesses**\n1. Although the relaxation for online cohort selection is nice, the reader is left wondering whether its complementary version (outputting acceptances throughout the stream and only rejecting at the end) would also work and whether this would be more realistic for some settings. For example, in hiring, the firm may want to make offers to candidates quickly to avoid the candidate accepting an offer from a different firm. Furthermore, it would be helpful to characterize whether similar candidates are left 'on hold' for similar amounts of time in the constructions presented (it seems that this might not hold for adversarial ordering).\n2. The algorithms are difficult to parse and would be greatly improved with inline comments/pseudocode. For example, several constants are left without type, which can be inferred but interrupts the flow of reading. There are also places where it is unclear whether and how values are updated, for example, the $n_i$ seem to be updated as a result of the roundnat procedure, but this isn't clear from the notation. There are also several mismatches with the terminology in the text, for example, does \"delete all $i$ ...\" in line 26 of Algorithm 2 mean \"reject\"? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work considers the fair cohort selection problem, that is, selecting a set of $k$ individuals while satisfying individual fairness. The main contributions are\n* A relaxation of the online cohort selection problem (when candidates arrive in an online fashion) that allows putting candidates 'on hold', rather than requiring an immediate response.\n* High utility methods for selecting cohorts (online or offline) for two notions of utility. Linear (which matches the case where there exists a fair classifier with probability of selection closely correlated to the utility of each individual) and Ratio Utility (which aims to capture arbitrary utilities assigned to individuals).\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Requested Changes prior to recommendation**\n* Clarify whether instances of \"for any\" in algorithms should be \"for all\".\n* Clarify in the introduction that the relaxation for the offline setting does not necessarily immediately reject candidates.\n* Clarify in the introduction whether the $u_i$ are assigned independently to each $i$ or if they can be a function of the whole cohort. (Presumably it is independent.)\n\n**Recommended Changes to Strengthen the Work**\n* Consider devoting more space/words to the new setting proposed for online cohort selection. \n* Consider revising the algorithm notation and including inline comments to make them more readable and to match the prose descriptions provided.\n* Consider restating lemmas/theorems in the appendix alongside the proofs, this will make them easier to follow.", "broader_impact_concerns": "None - the work considers the problem of fair classification/cohort selection in the abstract.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The three reviewers have positive views on the manuscript. There are however several suggestions to improve the manuscript before it is published, particularly:
1) Strengthening discussion and explanation about ratio utility, and its relationship to the fair-utility maximising cohort selection problem under general individualistic utility and under any collective utility;
2) Positioning better the work with respect to existing literature in meritocratic fair selection/ranking. Explicitly mentioning that a meritocratic notion of fairness tries to preserve the order of the scores, whereas this work studies a stronger fairness criterion that preserves the distances between the scores. Cross-referencing with Buening et al. 2022 would be beneficial for the readers. 

The matters mentioned above were addressed in the rebuttal; however, the manuscript has not been revised accordingly. A conclusion and discussion section would be appropriate to discuss those points. Additionally, there are several suggested modifications from the reviewers that need to be integrated.

Decision: Accept (poster)