{'fraction_non_alphanumeric': 0.04706514833097111, 'fraction_numerical': 0.012576772070442957, 'mean_word_length': 4.050518347869014, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline

Consider an actor making selection decisions using a series of classifiers, which we term a sequential screening process. The early stages filter out some applicants, and in the final stage an expensive but accurate test is applied to the individuals that make it to the final stage. Since the final stage is expensive, if there are multiple groups with different fractions of positives at the penultimate stage (even if a slight gap), then the firm may naturally only choose to the apply the final (interview) stage solely to the highest precision group which would be clearly unfair to the other groups. Even if the firm is required to interview all of those who pass the final round, the tests themselves could have the property that qualified individuals from some groups pass more easily than qualified individuals from others. Thus, we consider requiring Equality of Opportunity (qualified individuals from each each group have the same chance of reaching the final stage and being interviewed). We then examine the goal of maximizing quantities of interest to the decision maker subject to this constraint, via modification of the probabilities of promotion through the screening process at each stage based on performance at the previous stage. We exhibit algorithms for satisfying Equal Opportunity over the selection process and maximizing precision (the fraction of interview that yield qualified candidates) as well as linear combinations of precision and recall (recall determines the number of applicants needed per hire) at the end of the final stage. We also present examples showing that the solution space is non-convex, which motivate our exact and (FPTAS) approximation algorithms for maximizing the linear combination of precision and recall. Finally, we discuss the `price of' adding additional restrictions, such as not allowing the decision maker to use group membership in its decision process.


Introduction
Consider what we will term sequential screening processes. In this setting a decision maker (e.g. a company seeking to hire applicants) makes a decision, like hiring, by using a sequence of intermediate decision-making steps that each filter out some candidates, in order to ideally produce a pool of mostly qualified candidates at the final step.
We assume some people are truly qualified for the position being filled, and we call them positive examples, and others are truly unqualified and we call them negative examples. And then the various intermediate steps have different probabilities of qualified/unqualified applicants passing each step, which could be different for different demographic groups. We also assume that the final (interview) stage of the process is particularly expensive for the decision-maker, and reveals the true label of the applicant.
To illustrate a concern that could arise in this setting, suppose there are two demographic groups A and B, and just one test t in the screening process prior to the final stage. Suppose that test t and the underlying base rates of the two groups have the property that P (y = 1|t(x) = 1, x ∈ A) ≥ P (y = 1|t(x) = 1, x ∈ B) + ǫ for some ǫ > 0. That is, the pool of group-A applicants who pass the test has a higher fraction of positive examples than the pool of group-B applicants who pass the test. Since the cost of final interviews is assumed to be high, in this case a rational decision maker would be sensitive to even a small ǫ gap, in order to minimize the expected number of interviews made per hire. In particular, small gaps between these groups in the population would be amplified in that the rational decision-maker would then choose not to promote any individuals from group B to the final interview round, which clearly violates common sense fairness norms. There is empirical evidence that similar phenomenon occurs in real world settings, when employers have limited information [Bertrand and Mullainathan, 2004].
A second concern is that even if the decision-maker interviews all individuals who make it to the final round (and more generally, at each level promotes all individuals who pass the test to the next round), the tests themselves could have the property that qualified individuals from some groups pass them more easily than qualified individuals from others. So, in the end, a qualified individual from one group might have a much lower chance of making it to the final interview round than a qualified individual from another.
Because of fairness violations of this kind, we consider a regulator that requires the screening process to satisfy Equal Opportunity [Hardt et al., 2016], that is, qualified individuals of each group have the same chance of receiving an interview. This requirement motivates the problem of how to satisfy such a condition in the most efficient way, minimizing the number of interviews needed per successful hire as well as the number of overall applicants needed to enter the screening process per hire. This is the question we address in our paper.
We assume that the tests themselves and their order in the process are fixed beforehand and the action space of the firm (of our algorithm) is solely modifying how individuals move through the pipeline in response to their test outcomes (the promotion policy). More specifically, for each test, we need to decide the probability that an individual from a given group who passes or fails the test should continue on to the next stage. One can satisfy the fairness requirement with simple promotion policies (such as promoting all individuals regardless of whether they pass or fail each test), but the tension is how to do so in a way that results in a useful process.
This captures the scenario of performing modifications to pre-existing screening systems (the test themselves are fixed) in order to respond to fairness issues. We assume we are given, for each test, its statistical properties for each group (the probability that a random qualified or unqualified individual will pass the test). 1

Our Results
We study how to implement the fairness requirement of Equal Opportunity in this sequential screening setting and what method of implementing it would achieve a high efficiency. One core result in our paper is that there is a solution that maximizes precision (minimizes the number of interviews needed per successful hire) subject to maintaining Equal Opportunity, that is given by promoting individuals from each group according to what we call the opportunity ratio. Moreover, it is possible to maximize overall precision subject to satisfying Equal Opportunity by a policy in which each level in the process satisfies Equal Opportunity individually (this property will not hold for the more general objective below).
Then we consider the more general case of satisfying Equal Opportunity while maximizing a linear combination of precision and recall (1/precision is the expected number of interviews needed per successful hire, and 1/recall is proportional to the number of overall applicants needed to enter the screening process per hire). This problem is challenging because, as we show, the space of Equal-Opportunity solutions is non-convex. Moreover, the optimal way to use one test to optimize a linear combination of precision and recall may depend on all other available tests.
Nonetheless, we are able to achieve an FPTAS for maximizing any linear combination of precision and recall, as well as an exact algorithm with running time that is 'only' exponential in the number of levels k and the number of the groups. This latter result relies on certain structural properties of optimal solutions that we develop in our analysis. Finally, we discuss extensions to our model such as requiring the screening process to be group-blind, and considering the requirement of satisfying Equalized Odds. Unfortunately, the optimal fair group-blind policy may be much worse than the optimal fair group-aware policy. For example, in some cases it may require a policy that completely bypasses all the tests.

Related Work
Fairness in pipelines was initiated by Bower et al. [2017] and follow up work by Dwork and Ilvento [2019], Dwork et al. [2020]. This paper differs from [Dwork et al., 2020] in several keys ways. We both use the word 'pipelines' but our work is more focused on the specific case of hiring pipelines in which we are looking at the fairness of the final outcome for a given individual, drawn from the population, rather than considering the individual fairness [Dwork et al., 2012] of the cohort context to which one is assigned. We do not consider cohort based scoring rules.
The structure of our model is very close to that of Kannan et al. [2019], but the objective in that work is jointly designing college admission and grading schemes that satisfy Equal Opportunity over the admissions/college process and in particular incentivize a rational employer to use a group blind hiring policy. In contrast, our work considers maximizing precision or a linear combination of recall and precision while satisfying Equal Opportunity.
Another related work by Arunachaleswaran et al. [2021] is the idea of pipeline interventions. In that paper there is a wide pipeline with a finite number of states at time t and the goal of the algorithm designer is to modify the transition probabilities from state to state in order to maximize a reward at the final step. This corresponds to efficiently allocating a government subsidy to aid dis-advantaged individuals, from the perspective of maximizing social welfare.
Intriguingly, the paper by [Khalili et al., 2021] argues that Equal Opportunity is misaligned with fairness in screening allocation problems with a finite number of available items (think hiring a small number of engineers at a start-up vs accepting applicants for a credit card). In our work, we do not focus on modeling a finite number of available positions (e.g., we are in the case with a larger number of available items).
Most closely related to our work is Cohen et al. [2020], in which there is noisy Bernoulli feedback in a hiring setting with sequential tests. In contrast to our scenario, they assume both underlying candidate skill levels and test results are sampled independently from Bernoulli distributions. Furthermore, they allow hiring an applicant before the end of the pipeline (e.g., if you pass the first three of five tests and those tests have high signal, you may skip the next two tests). In our model, we assume each stage of the process is memoryless (the probability of making it to stage 3 from stage 2 depends only on the result of the stage-2 test and group membership, and not the result of the stage-1 test) and we allow tests to be asymmetric (e.g., it could be that positive examples from a given group pass with probability 0.75 and negative examples pass with probability 0.5). In our motivation, we model the initial tests as cheap while the ultimate interview is expensive and accurate, while in Cohen et al. [2020], each test is equally accurate and costly and additionally they want to minimize the expected number of tests to hire a candidate. Consistent with our perspective, the authors exhibit an impossibility result arguing that satisfying Equal Opportunity requires group dependent thresholds if the tests have different noise rates.
Additionally, there are connections between our work and classical economic discussions of statistical discrimination [Arrow, 2015, Phelps, 1972 in that both perspectives model disparities in outcomes that derive from strategic actors making decisions to allocate goods differently based on perceived differences in predicted outcomes (termed statistical discrimination). Our models do not capture taste based discrimination.

Roadmap
In Section 2 we formally describe our model and present some examples that show key phenomena. In Section 3 we prove and discuss our first main theorem, about how to maximize precision (at the end of the screening process) subject to Equal Opportunity.
Then we consider the more general case of satisfying Equal Opportunity while maximizing a linear combination of precision and recall. This problem is challenging because, as we show in Section 2.2, the space of Equal-Opportunity solutions is non-convex. Moreover, how to effectively utilize a test may depend on all other available tests (Section 4.1.2). On the other hand, as we show in Section 4.2, the solution space does satisfy certain useful structural properties. We then use these structural results to to achieve an exact optimal algorithm, and in Section 4.3 to achieve an FPTAS for maximizing linear combination of precision and recall, as well as other functions of precision and recall.
Finally, in Section 5 we discuss extensions to our model such as requiring the screening process to be group-blind, and considering the requirement of satisfying Equalized Odds.

Preliminaries
Now we formally define our model and introduce some informative examples. As mentioned above, the scenario to keep in mind is a stylized hiring process, consisting of a sequence of tests or interviews. Each candidate takes a test, and depending on their outcome on that test at that stage, is possibly promoted to the next stage of the screening process. We focus on modifying this promotion policy in response to satisfying the fairness constraints and achieving a high objective value or a low cost value. This is a constrained optimization problem, with structure.

Definitions
We use X to denote the set of demographic groups, and X ∈ X to denote a specific group. We assume group membership is known to the algorithm, groups are disjoint, and an individual from group X is promoted based on both their test performance and a promotion policy (defined below) for that corresponding group. We assume individuals are either truly qualified or truly unqualified, and use label y = 1 to denote a trulyqualified individual and label y = 0 to denote a truly-unqualified individual. For each group X, let q X denote the base rate for that group, namely Pr(y = 1|x ∈ X).
Definition 2.1 (Test Statistics). For each test t and each group X ∈ X , we define τ X1 := Pr[t(x, y) = 1|y = 1, x ∈ X] to be the probability a qualified candidate from group X passes the test, and τ X0 := Pr[t(x, y) = 1|y = 0, x ∈ X] to be the probability an unqualified candidate from group X passes the test. We assume all tests are minimally effective for all groups in that positive examples are more likely to pass than negative examples. More precisely, Note that we assume that the probability of an individual passing a given test depends only on their true qualification y and their group membership X. We also assume test statistics are given and known to our algorithm.
We use τ j X1 , τ j X0 to denote the test statistics at stage j of the interview process. For convenience, we define T j X = (τ j X1 , τ j X0 ) as useful shorthand to capture the test statistics at stage j for group X. Note that the same test may have different effectiveness per group.
Definition 2.2 (Post-Processing Modification). We would like to modify the outcomes of the tests in the screening process so that some fairness goal (to be specified later) is achieved at the end of the screening (i.e., in the final interview stage). Further, we assume as part of the problem setting that the only 'allowed' correction is to modify how candidates are promoted to the next stage. The promotion probability of each candidate only depends on their group membership and performance at the current test (whether they passed or failed the test). Formally, for each group X ∈ X , let π j X1 denote the probability a candidate x ∈ X who passes the test at stage j is promoted to stage j + 1, and π j X0 the probability that a candidate who fails the test at stage j is promoted to stage j + 1. 2 We describe a policy for a given stage j as {(π j X1 , π j X0 )} X∈X .
2 Note, in general randomized promotion policies will be necessary to satisfy the fairness criteria.
For instance, a naive fairness respecting solution is to simply ignore the tests and promote all examples to the end of the pipeline, i.e., {(π j X1 = 1, π j X0 = 1)} X∈X ,j∈ [k] where k is the number of tests in this screening process. However, this would result in a useless process from the perspective of the decision maker. The most straightforward use of tests is to promote all who pass and none who fail, i.e., {(π j X1 = 1, π j X0 = 0)} X∈X ,j∈ [k] . However, this might not satisfy required fairness properties. We now formally describe the fairness properties we consider.
Definition 2.3 (Equal Opportunity and Equalized Odds [Hardt et al., 2016]). Our paper primarily discusses two fairness notions, specifically Equal Opportunity and Equalized Odds. The first notion, Equal Opportunity requires that the classifier have equal True Positive Rates for each group in the population. Equivalently, for a classifier h and true labels y, P (h(x) = 1|y(x) = 1, x ∈ A) = P (h(x) = 1|y(x) = 1, x ∈ B). Equalized Odds is similar but it also requires that the False Positive Rates are equal; formally, In our problem, Equal Opportunity is motivated by a desire that qualified individuals should have the same shot at an interview regardless of their group membership. In our problem, there is additionally a critical distinction between the fairness criteria (e.g. Equal Opportunity or Equalized Odds) being satisfied at the end pipeline and alternatively that requiring these criteria hold for every transition between stages as individuals move through the pipeline, a stronger notion. Now that we have described the terms that characterize a problem instance and the action space of the algorithm, we describe the objective value that captures the usefulness of a screening process. We term these multiple different objective functions 'pipeline efficiency'.
Definition 2.4. Pipeline Efficiency In our work we focus on two core notions of efficacy from the perspective of the firm deploying the screening process. Interview efficiency (equivalently, precision) is the fraction of candidates in the last round who are qualified, i.e., the fraction of interviews that lead to hires (or at least to job offers). Throughput efficiency (equivalently, recall) is fraction of qualified candidates who make it to the final round, and determines the expected number of applicants needed to enter the pipeline to hire one candidate. In this paper, we study cost functions that are functions of these two quantities only.
We model the last available test as highly discriminative but extremely expensive per each test utilization and this is what motivates the interview efficiency. In particular, if we assume that the k stages prior to the interview round have zero or negligible cost per test, and there are many available candidates, then we presume that the goal of the firm is to maximize the interview efficiency (precision, at the final round).

Formal Problem Statement and Illustrative Examples
Now, we combine the above into a formal statement. Given a screening process/pipeline P with k stages, this pipeline consists of a collection of disjoint groups X and tests statistics T X = (T 1 X , T 2 X , . . . T k X ) for every group X ∈ X .
The goal of the algorithm designer is to exhibit a method to find promotion policies {(π j X1 , π j X0 )} X∈X ,j∈[k] denoted as π such that the overall policy satisfies the relevant fairness notion (either at the end of the screening process or at the end of each stage) and maximizes the given pipeline efficiency. Now we move into illustrative examples.
Observe that the policy of promoting individuals if and only if they pass the test does not satisfy Equal Opportunity. Instead, two policies that satisfy Equal Opportunity are P = ((π A1 , π A0 ), (π B1 , π B0 )) = ((0.8, 0), (1, 0)) and policy Q = ((1, 0), (1, 1)). In words, the policy P would promote all individuals who passed the test from group B, but would only promote 80% of those from group A. This down-weighting of group A would suffice to satisfy Equal Opportunity. In contrast, policy Q promotes all individuals from group A who pass the test and promotes everyone from group B, regardless of their test score. In this example, P is the optimal Equal Opportunity policy with respect to precision.
Requiring Equalized Odds at each level can significantly harm performance: The above example also shows that requiring Equalized Odds at each level can significantly harm performance. Notice that policy P above satisfies Equalized Odds overall and has perfect precision and fairly high recall. However, the only way to satisfy Equalized Odds at each level is to completely bypass both tests, which would be much worse for precision.
Interestingly, as we show below, requiring Equal Opportunity at each level does not harm precision relative to requiring it for the pipeline as a whole (though it can hurt recall).

Maximizing Precision Subject to Equal Opportunity
In this section, we exhibit a policy π that maximizes precision at the end of the screening process while satisfying Equal Opportunity over the entire process. To do this, we prove that the optimal method for this objective is given by promoting individuals from each group according to the Opportunity Ratio (which we will define shortly).
Furthermore, for a k-stage screening process Observation 3.2. Recall that q X denotes the base rate for group X, and let u X = 1 − q X . For a single-stage pipeline with test τ and promotion policy π, the interview efficiency (i.e., precision) is equal to (2) Similarly, when we consider the extension to a k-stage pipeline, the interview efficiency is equal to Now, we formally define the policy given by the opportunity ratio as follows.
Definition 3.2 (Opportunity Ratio Policy). Consider a screening process with k stages. For each The Opportunity Ratio policy, at the first stage for each X ∈ X , promotes ρ X fraction of those who pass the test and none of those who fail the test. For the remaining stages (i = 2, 3, ..., k), the Opportunity Ratio policy fully trusts the result of the tests; a candidate is promoted to the next stage iff they pass the test at the current stage. Formally, for every X ∈ X , π 1 X1 = ρ X , π 1 X0 = 0 and π i X1 = 1, π i X0 = 0, ∀i ≥ 2. In the rest of this section, we study the task of maximizing interview efficiency under different settings and fairness requirements.

Maximizing Interview Efficiency subject to Equal Opportunity at the Final Stage
As a warm-up, we start with the simplest setting where the screening process has only one test before the interview stage.
) be a test satisfying the minimally effectiveness property. The maximum precision policy satisfying Equal Opportunity is the opportunity ratio policy. Moreover, for any group X ∈ X , it is always sub-optimal to promote any candidates who failed the test (i.e., in any optimal policy, π X0 = 0, ∀X ∈ X ).
Proof. First, for any policy π, we upper-bound the interview efficiency (i.e., precision) for a screening process with parameters q, u, τ . To bound the interview efficiency, for each X ∈ X , we lower-bound the False Positive Rate N X,τ,π in terms of the True Positive Rate M X,τ,π .
By Equal Opportunity of π and employing Eq. (4) in the formula for the interview efficiency, Eq. (2), Note that the inequalities are tight when π X0 = 0 for all X ∈ X . Next, we show that the opportunity ratio policy satisfies Equal Opportunity and achieves the bound in Eq. (5). In the opportunity ratio policy π * , only a ( τ X * 1 τX1 )-fraction of candidates in group X who pass the test t (picked uniformly at random) are promoted to the next stage. In other words, for any group X ∈ X , we set π * X1 = τ X * 1 τX1 , π * X0 = 0. Then, Hence, π * is an equal opportunity policy with the maximum interview efficiency for any screening process with parameters q, u, τ, π.
Next, we state our result for the general setting in which there are multiple stages and multiple groups in the screening process. The proof of the theorem is similar to the single test version and is deferred to Appendix A.
Theorem 3.4 (Multi-Stage Screening Process). Consider a k-stage screening process whose all tests are minimally effective. The maximum interview efficiency policy satisfying Equal Opportunity is the Opportunity Ratio policy and has interview efficiency equal to

Maximizing Interview Efficiency Subject to Equal Opportunity at the End of Each Stage
Here, we consider the setting in which the goal is find a policy that maximizes interview efficiency and satisfy Equal Opportunity at the end of each stage-not only at the interview stage. Following Theorem 3.4, the maximum interview efficiency in this setting is at most ). Next, we show that the following slightly modified opportunity ratio policy π that satisfies Equal Opportunity at the end of each stage maximizes the interview efficiency. The policy π applies the opportunity ratio at each stage of the pipeline.
Again, it is straightforward to verify that π satisfies the Equality of Opportunity. Moreover, The only difference compared to the policy of Theorem 3.4 is that in the former policy the recall can be higher.
Remark 2. Adding the condition to satisfy the Equality of Opportunity at the end of each stage does not harm interview efficiency. However, this condition may decrease the recall of the optimal policy.

Pipeline Efficiency: Maximizing Linear Combinations of Precision and Recall
Now we shift our focus to exhibiting a promotion policy that satisfies Equal Opportunity and maximizes a linear combination of precision and recall given by the positive weight α ∈ R ≥0 ; f α (π) := (1 − α) · recall(π) + α · precision(π). As in Definition 2.4, higher precision corresponds to higher interview efficiency, and higher recall corresponds to higher throughput efficiency. We start with a simple 2-approximation algorithm for maximizing any given linear of precision and recall. Proof. Note that the policy that bypasses all tests is an Equal Opportunity policy and maximizes recall-it achieves recall equal to one. Moreover, by Theorem 3.4, the Opportunity Ratio is an Equal Opportunity policy maximizing precision. Hence, the better of the "bypassing all tests" policy and the Opportunity Ratio policy is a 2-approximation of any given linear combination of precision and recall.
In order to obtain better performance for maximizing linear combinations of precision and recall, we develop structural properties of optimal solutions, and then use them to get an exact algorithm with running time that is exponential only in k and the number of groups. Additionally, by a dynamic programming approach we exhibit a fully polynomial time approximation scheme (FPTAS).
One challenge is that as shown in Section 2.2, the space of Equal Opportunity solutions is non-convex. Another is that as shown in Section 4.1.1 below, Opportunity Ratio is no longer optimal, and as shown in Section 4.1.2 below, there exists no function ranking the efficacy of tests solely based on their statistics.
We begin by presenting the examples mentioned above, and then developing the structural properties we will use.

Opportunity Ratio not Optimal for Linear Combination of Precision and Recall
In the previous sections, our key algorithmic strategy is to use the Opportunity Ratio to re-weight the promotion policy. Since this policy satisfied Equal Opportunity and maximized precision (among Equal Opportunity policies), if our objective is to only maximize precision, then the Opportunity Ratio is sufficient. Now we exhibit an example where the Opportunity Ratio solution is not optimal when maximizing any linear combination of precision and recall when there is any nonzero weight on recall. Specifically, in this example there is an alternative policy with the same precision as the Opportunity Ratio solution but strictly higher recall.

Optimal Policy Non-Locality for Linear Combination of Precision and Recall
Suppose we have one group in the population and want to optimize a linear combination of recall and precision. A baseline idea is whether we can solve this problem with a natural greedy algorithm that makes local decisions in a single pass of the test statistics 3 .
We answer this question in the negative in by exhibiting an example pipeline with test statistics such that when two of three tests are available, using only the first test is strictly optimal, while when all three tests are available, the optimum is instead to use the other two tests and not the first test. This shows that an algorithm that maximizes a linear combination of precision and recall cannot simply assign separate scores to each test and then use only the highest-scoring tests. Our example is only for one group.
The counterexample is as follows. The base-rate in the population is P (y = 1) = 1/2. Consider test t 1 = (1/2, 0) and tests t 2 = t 3 = (1 − δ, 1/2) where δ = 1 100 . The objective function is f (π) = 1 3 · recall(π) + 2 3 · precision(π). In the following, let f (t 1 ) to denote the score of the policy that only promotes those who pass t 1 and bypasses all other tests while f (t 2 t 3 ) denotes bypassing t 1 and promoting individuals if and only if they pass tests t 2 and t 3 . In the Appendix E we show while f (t 1 ) is larger than any policy using t 1 and t 2 (possibly in fractions), f (t 2 t 3 ) is strictly larger than any policy using t 1 , t 2 and t 3 (again, possibly in fractions).

An Exact Algorithm
In this section, we give an exact algorithm for maximizing any given linear combination of precision and recall subject to satisfying Equal Opportunity by the end of the screening process.
First we show that for any k-stage screening process over a population specified by a collection of groups X , there exists a set of Equal Opportunity policies P k,X that weakly Pareto dominate (w.r.t. precision and recall) any policy satisfying Equal Opportunity. In particular, we show that each policy π := (π 1 , · · · , π k ) ∈ P k,X has the following structure, (1 − π i X1 )π i X0 = 0, ∀i ∈ [k], X ∈ X . Definition 4.1 (Pareto Dominant Policy). For a given screening process, a policy π weakly Pareto dominates a policyπ w.r.t. precision and recall iff, recall(π) ≥ recall(π) and precision(π) ≥ precision(π). Moreover, π strictly Pareto dominatesπ if at least one of the above inequalities holds strictly.
Furthermore, a set of policies P weakly Pareto dominates a policyπ w.r.t. precision and recall iff there exists a policy π ∈ P that π weakly Pareto dominatesπ.
Lemma 4.2. For any k-stage screening policy that satisfies the "minimally effectiveness" property, the set of Equal Opportunity policies in P : } weakly Pareto dominates all equal opportunity policies w.r.t. precision and recall.
In other words, any equal opportunity policy violating (1 − π i X1 )π i X0 = 0 for a group X ∈ X and a stage i ∈ [k] is weakly Pareto dominated by P.
Proof. First, we show that in any policy π which is not strictly Pareto dominated (w.r.t. precision and recall), . Hence, we can only consider policies π where π X1 > 0 for all X ∈ X . The proof of the following claim is deferred to Appendix B.
Claim 4.3. Consider a k-stage screening process whose tests satisfy the "minimal effectiveness" property. In any optimal policy of this screening process that satisfies Equal Opportunity, for all X ∈ X and i ∈ [k], π i X1 > 0. Now, for the sake of contradiction, suppose that there exist a level i ∈ [k] and a group X ∈ X such that π i X0 > 0 and π i X1 < 1. Note that w.l.o.g., we can assume that τ i X1 < 1; otherwise, by setting π X0 = 0, the recall of the policy does not decrease and the precision strictly increases. Hence, there exist ǫ 1 , ǫ 0 > 0 such that . We define a new policyπ, which differs from π only in level i of group X, as follows: π satisfies Equal Opportunity and has the same recall as π. Moreover, Hence the precision ofπ is not less than the one of π. This contradicts the strict Pareto optimally of policy π. Thus the statement holds and for any level i ∈ [k] and any group X ∈ X , (1 − π i X1 )π i X0 = 0.
Next, we show additional structures of the set of Equal Opportunity policies P k,X that weakly Pareto dominates all Equal Opportunity policies.
In other words, any Equal Opportunity policy π of the screening process is weakly Pareto dominated bỹ π ∈ S (in every policyπ ∈ S, for each group X ∈ X , there exists at most one level i such that 0 <π i X0 < 1). Proof. Suppose for contradiction that there exist a group X ∈ X and levels i, j such that 0 < π i X0 , π j X0 < 1. Next, we show that we can modify π in levels i and j and replace π i X0 , π j X0 withπ i X0 ,π j X0 such that Note that Eq. (6) guarantees that the new policyπ satisfies Equal Opportunity and has the same recall as the policy π. Moreover, Eq. (7) shows that precision of the new policy is not less than than the precision of π. Next, we show that in the new policy, eitherπ i X0 ∈ {0, 1} orπ j X0 ∈ {0, 1}. Without loss of generality, we can assume that the feasible range of values forπ i X0 to satisfy Equal Opportunity is where M X = M X,τ i ,π i M X,τ j ,π j = M X,τ i ,π i M X,τ j ,π j . By the "minimally effectiveness" . Then, satisfying Equal Opportunity is equivalent to satisfy the following con- Case 1: max(τ i X1 , τ j X1 ) = 1. Without loss of generality, suppose τ i X1 = 1. Then, we can simply setπ i X0 = 0 and the resulting policyπ will maintain Equal Opportunity. Moreover, since 1−τ i X0 > 0, N X,τ i ,π i ≤ N X,τ i ,π i . In the other case, we can similarly setπ j X0 = 0.
Case 2: τ i X1 , τ j X1 < 1. The task of findingπ i X0 is as follows: Next, we show that for any y To prove it note that the minimal "effectiveness property" of the tests the minimum value of f in this interval obtained in one of its endpoints. In other words, the maximum precision corresponds to the case eitherπ i X0 ∈ {0, 1} or π j X0 ∈ {0, 1}. Finally, we show that each group can only have at most one level that partially uses its corresponding test.
The proof is similar to the proof of Lemma 4.4 and we defer it to Appendix B. The above lemma enforces a very restricted structure on the set P k,X of Equal Opportunity policies that weakly Pareto dominate all Equal Opportunity policies. To summarize, in each policy π ∈ P k,X , for each group X ∈ X , the restriction of π on X has the following properties 1. There is at most one level i * ∈ [k] such that π partially uses the test τ i * ; i.e., either 0 < π i * X1 < 1 and π i * X0 = 0, or π i * X1 = 1 and 0 < π i * X0 < 1. 2. In any remaining level i, π i either bypasses τ i (i.e., π i X1 π i X0 = 1), or fully exploits τ i (i.e., π i X1 = 1, π i X0 = 0). Theorem 4.6 (Exact Algorithms for Linear Combination of Precision and Recall). Given any linear objective function of form f α (π) := α · precision(π) + (1 − α) · recall(π), There exists an exact algorithm that runs in time O(k |X | ·2 k|X | ) and finds an Equal Opportunity policy of the screening process with parameters (q, u, τ, X ) that maximizes f α .
Proof. Using the aforementioned set P k,X of weakly Pareto optimal policies (w.r.t. precision and recall) that satisfy the Equality of Opportunity, we enumerate over all policies in P k,X as follows.
• For each group X ∈ X , pick a level i X ∈ [k] (i.e., k |X | possible configurations).
• Fix an "integral" policy π for the rest of levels in each group X ∈ X , -In each group X ∈ X , for each level i = i X , we decide whether to fully use the test (π i A1 = 1, π i A0 = 0) or to bypass the test (π i X1 = π i X0 = 1) (i.e., 2 (k−1)|X | possible configurations).
• For each X ∈ X , i X ∈ [k], we fix the policy π iX partially as follows, -(1 − π iX X1 )π iX X0 = 0, ∀X ∈ X (i.e., 2 |X | possible configurations). In each of the policies π as constructed above, we set the remaining π values (i.e., π iX ) so that Equality of Opportunity is satisfied and the objective function f α is maximized. Finally, we maintain the configuration π that maximizes f α . Note that the whole process takes O(k |X | · 2 k|X | ) time.
Similarly, we can show the following.
Theorem 4.7 (Exact Algorithms for Linear Combination of reciprocal of Precision and Recall). Given any objective function g α (π) := α/precision(π)+(1−α)/recall(π), There exists an exact algorithm that runs in time O(k |X | · 2 k|X | ) and finds an Equal Opportunity policy of the screening process with parameters (q, u, τ, X ) that minimizes g α .

An FPTAS Algorithm
In this section, we present FPTAS algorithms for maximizing a given pipeline efficiency objective (resp., minimizing a given pipeline cost function) while satisfying the Equal Opportunity requirement. We consider two regimes. In this section, as in previous sections, we consider the regime where we are allowed to treat individuals from different groups differently; more precisely, we can set π j Xi = π j Y i for j ∈ [k], i ∈ {0, 1}.
Next, in Section 5.1, we consider a new regime where the goal is to achieve Equal Opportunity while treating individuals from both groups similarly; ∀i ∈ [k], X = Y ∈ X , π i X1 = π i Y 1 , π i X0 = π i Y 0 . To exploit our algorithm in different settings, we describe it for the most basic setting of the problem. Given a single group of applicants with parameters q, u and a pipeline P = {τ i } i∈ [k] , the goal is find a policy π that maximizes a given pipeline efficiency objective f (recall(π, P), precision(π, q, u, P)). Our approach works for a quite general set of objective functions; more notably, as in the previous section, for two natural settings: maximizing a linear combination of precision and recall and minimizing a linear combination of reciprocals of precision and recall.
High-level Description of Algorithm. Now we write a dynamic program (DP) to optimize a given pipeline efficiency objective f up to a given accuracy parameter ǫ. We create a DP-table M [i, tpr, fpr] where i ∈ [k], tpr ∈ [0, ℓ tpr := log 1−ǫ L tpr ] and fpr ∈ [0, ℓ fpr := log 1−ǫ L fpr ] where L tpr , L fpr are lower bounds on True Positive Rate and False Positive Rate respectively. For each set of parameters (i, tpr, fpr), M [i, tpr, fpr] will be a Boolean value indicating whether there exists a policy such that by the end of level i, the true positive rate becomes at least (1 − ǫ) tpr and the False Positive Rate becomes at most (1 − ǫ) fpr . Without loss of generality and for the simplicity of the exposition, we assume L tpr and L fpr are powers of (1 − ǫ); otherwise we can simply round the lower bounds to largest powers of (1 − ǫ) smaller than actual bounds.
Solving the DP We fill out the DP table starting from i = 1 as follows. First, for any j 0 ∈ [0, ℓ fpr ], j 1 ∈ [0, ℓ tpr ], M [1, j 1 , j 0 ] = true iff the following system of linear inequalities has a feasible solution.
Next, we describe the update rule for i > 1. For any tpr where F i+1 is a set of (j 0 ≤ fpr, j 1 ≤ tpr) for which the following linear program has a feasible solution, Note that x, y can be interpreted as π i+1 1 , π i+1 0 , respectively. Moreover, the system of linear inequalities of the update rule in level i + 1 (Eq. (9)) is similar to the rules for the base case (Eq. (8)).
In other words, if the policy π exists then the DP approach finds a policy with true positive rate at least (1 − ǫ) j1 and false positive rate at most (1 − ǫ) j0 .
The proof is deferred to Section B. ) and finds a policy π with true positive rate at least (1−ǫ) k−1 ·t and false positive rate at most min{1, max{L fpr , f}/(1− ǫ) k−1 }. ). Now we apply the DP approach and by Lemma 4.8, the solution returned by the algorithm has the true positive rate and the false positive rate satisfying the guarantee of the statement.
Implications of DP Here we present FPTAS algorithms using the described DP approach in different settings. We state the results formally and their proofs are deferred to Appendix B.
Remark 4 (General Objective Functions). In Theorem 4.10 and 4.11 we presented FPTAS for finding Equal Opportunity policies optimizing two standard pipeline efficiency objective functions. Here, we generalize the above theorems when the pipeline efficiency objective function f : [0, 1] 2 → R which maps precision and recall to efficiency scores have certain properties. Also, we define g : [0, 1] 2 → R such that for any t, f ∈ [0, 1] 2 , g(t, f) := f (recall(t), precision(t, f)). We describe the properties when the goal is to maximize f -the required conditions for the minimization version is similar.
• f is non-decreasing w.r.t. both precision and recall-equivalently, g is non-decreasing in t and nonincreasing in f.
Remark 5 (Selecting from Available Tests). Suppose that in contrast to our previous approaches, we do allow for the design of the pipeline in that we allow the firm to select some tests to create a pipeline. For instance, imagine that there is a budget and the firm is allocating this budget to buy tests. The goal of the firm is the same, e.g. to exhibit a pipeline satisfying a fairness requirement. Our algorithms can be modified to handle to this case by adding a term in the DP table corresponding to the budget remaining, with a decision point of choosing to use a given test or not. Note that the ordering of tests in the pipeline does not matter for the objectives considered.

Alternate Models
In this section we describe some alternate settings, such as using a single promotion policy for both demographic groups (which might be required by regulation), or requiring Equalized Odds.

Screening Processes with Same Policy for All Groups
One alternate fairness model is to additionally require the same policy be used for all groups. While utilizing demographic features can aid in achieving fairness goals (e.g. Dwork et al. [2012], Hardt et al. [2016]), in some regulatory regimes, this fairness-through-awareness may be illegal or problematic, even when intended to ensure equitable treatment.
In our setting, if we are constrained to follow group-blindness, there be would only one set of tests and one ordering of the tests that all applicants are tested on. Analogously to the previous setting, the action space of the algorithm remains modifying the promotion probabilities, but we now only have one set of policies to modify. We also exhibit a DP algorithm for this setting, which we defer to Section D. However, a simple example shows the inefficiencies in this regime. Suppose we have a single test with T A = (1, 0) and T B = (1/2, 0). Observe that since we are constrained to use group blindness and satisfy Equal Opportunity, there is no way to use the test without violating Equal Opportunity. Thus, the only way to satisfy Equal Opportunity is to completely bypass the test.

Equalized Odds
Next, recall that the requirement of Equalized Odds mandates equal True Positive and False Positive rates for all groups. In the appendix, we show structural properties of an optimal promotion policy that satisfies Equalized Odds. However, we also note the interview efficiency cost (precision) of requiring Equalized Odds. In particular, the gap between the interview efficiency of π EOdd and π EOpp can be as large as 1 q − ǫ for any arbitrary ǫ > 0. See Theorem C.3 for details.

Discussion Comparing Equalized Odds and Equal Opportunity
From the perspective of a decision maker in the wild, how to interpret and operationalize these results? A robust take-away is that requiring Equalized Odds and Equal Opportunity have substantially different efficiency consequences. Based on our examples, it seems unlikely that Equalized Odds is effective in this model, especially when requiring Equalized Odds at each stage. In contrast, the fact that requiring Equal Opportunity at each stage is equivalent to requiring Equal Opportunity of the overall process with respect to interview efficiency may have benefits in ensuring public confidence in the model.

Intersectionality
A natural question is how to think when the demographic groups may have an arbitrarily overlapping structure. This suggests several open questions in our model, e.g. if a person is in groups A and B, then which test parameter τ A or τ B corresponds to that person? Perhaps a direction is to assign to that person an interpolation between these values. A naive approach is when there are k groups, to create 2 k new groups and 2 k test parameters corresponding to every possible group intersection. If k is small, this may be computationally feasible, but is not responsive when the relevant sub-groups/intersections may not be known apriori. Perhaps our model could be merged with multi-calibration notions [Hebert-Johnson et al., 2018].

Conclusions
In contrast to some fairness in machine learning work, we focus on post-processing fairness modifications, rather than thinking about the fairness problem in screening processes where tests can be designed from scratch. While we believe that the more a priori design approach will have substantial benefits in practice, our approach of modifying pre-existing tests, combined with a concrete (and simple to evaluate) fairness notion, Equal Opportunity, is closely aligned with real world circumstances and models, especially in short term and iterative improvements to models. In some settings, the firm making hiring decisions will outsource some aspects of its pipeline to third party companies and the tests will be a black box, but possibly that come with statistics that can be used in our algorithms. This decoupling allows the effective implementation of fairness aware promotion policies in the short term.

A Proofs from Section 3
Proof of Theorem 3.4. First, we show that for any M ∈ (0, 1], any Equal Opportunity policy π M with recall M has interview efficiency at most where the last inequality follows from the minimally effectiveness of tests in the screening process and an argument identical to Eq. (4). Note that the inequality holds no matter what the value of M is. Next, we show that opportunity ratio policy achieves the maximum possible interview efficiency as shown in Eq. (10). Let X * = argmin X∈X Π j∈[k] τ j X1 . Recall that the opportunity ratio policy π is defined as follow.

B Proofs from Section 4
Proof of Claim 4.3. Suppose for contradiction that there exists a group X ∈ X and a level i ∈ [k] such that π i X1 = 0. First note that (1 − τ i X1 )π i X0 > 0; otherwise, the policy is useless because it prevents candidates of group X, in particular the qualified ones, from reaching the interview stage. Hence, by the Equal Opportunity requirement, no qualified candidate will reach the interview stage.
Next, we show that there exists a policyπ (which only differs from π in level i of group X) that satisfies Equal Opportunity for the given screening process and strictly Pareto dominates π;π i X1 = ( and π satisfies the Equal Opportunity,π also satisfies Equal Opportunity and has the same recall holds by the minimal effectiveness property of tests. Lemma B.1. Consider a k-stage screening process whose tests satisfy the "minimal effectiveness" property. The set of Equal Opportunity policies S ⊆ P = {π ∈ [0, 1] 2|X |k |(1 − π i X1 )π i X0 = 0, ∀X ∈ X , i ∈ [k]}, where for each group X ∈ X , there exists at most one level i ∈ [k] such that π i X1 < 1, weakly Pareto dominates all Equal Opportunity policies.
Proof. Suppose for contradiction that there are two levels i, j such that π i X1 , π j X1 < 1. First note that by Claim 4.3, π i X1 , π j X1 > 0. Moreover, by Lemma 4.2, since π i X1 , π j X1 < 1, π i X0 = π j X0 = 0. Next, we show that we can modify π in levels i and j and replace π i X0 , π j X0 withπ i X0 ,π j X0 as follows: In other words, the policyπ satisfies Equal Opportunity and has the same recall as π. Similarly, this modification does not decrease precision. Formally, N X,τ i ,π i N X,τ j ,π j = (π Hence, for each policy π, there exists another policy with at most one level i ∈ [k] such that π i X0 < 1 and weakly Pareto dominates π. Proof of Lemma 4.5. We follow a similar arguments as in the proof of Lemma 4.4. Note that by Lemma 4.4 and Lemma B.1 there is at most one level i 1 ∈ [k] such that 0 < π i1 X1 < 1 and π i1 X0 = 0, and there is at most one level i 0 ∈ [k] such that π i0 X1 = 1 and 0 < π i0 X0 < 1. Next, we show that we can modify the policy π in levels i 0 and i 1 and replace π i0 X0 , π i1 X1 withπ i0 X0 ,π i1 X1 such that Now, we show that in the new solution, eitherπ i0 X0 ∈ {0, 1} orπ i1 X1 = 1.
Next, we show that for any y ∈ [0, 1], f ′′ (y) = To prove it note that the minimal "effectiveness property" of the tests , the minimum value of f in this interval obtained in one of its endpoints. In other words, the maximum precision corresponds to the case eitherπ i0 X0 ∈ {0, 1} orπ i1 X1 = 1. Proof of Lemma 4.8. The proof is by induction. For the base case (i = 1), let t 1 and f 1 denote the true positive rate and the false positive rate of π by the end of level 1. The existence of π guarantees that the system of inequalities Eq. (8) with (j 0 = ⌊log 1−ǫ f 1 ⌋, j 1 = ⌈log 1−ǫ t 1 ⌉ ≤ ℓ tpr ) has a feasible solution. More precisely, by setting (x = π 1 , y = π 0 ), Next, we consider i > 1 and we assume that the claim holds for all values i ′ < i.
By the induction hypothesis and considering the first i − 1 levels in the pipeline, since More precisely, the algorithm finds a policyπ with true positive rate at least (1 − ǫ) j ′ 1 and false positive rate at most (1 − ǫ) j ′ 0 . Next, by setting (π i 1 = π i 1 ,π i 0 = π i 0 ) and (j 1 : Similarly, which completes the proof. Proof of Theorem 4.10. First, as we are aiming for a (1 − ǫ)-approximation, we only need to consider α ∈ (ǫ, 1 − ǫ). Otherwise, either the policy maximizing recall (i.e. bypassing all tests) or the policy maximizing precision (Opportunity Ratio policy) is a (1 − ǫ)-approximation for f α . Next we show in order to guarantee (1−ǫ)-approximations of recall and precision of the policy maximizing f α , it suffices to run the described DP and consider estimates of t (true positive rate) and f (false positive rate) of form (1 −ǭ) i for i ∈ N in intervals [L tpr , 1] and [L fpr , 1] respectively, whereǭ ≤ ǫ/(2k). We provide tight bounds for L tpr and L fpr . Note that since for any policy π, the true positive rate (t i ) and the false positive rate (f i ) are non-decreasing in i, it suffices to provide "large enough" lowerbounds L tpr and L fpr for t and f in the final stage respectively.
Bounding L tpr . Consider the policy π bypass , which bypasses all the tests in both groups, i.e., π i X0 = π i X1 = 1 for all i ∈ [k], X ∈ X . Since π bypass is an Equal Opportunity policy for the pipeline and f α (π bypass ) = (1 − α) + α q 1 , any optimal Equal Opportunity policy π * for f α has recall at least (1 − 2α + α q 1 )/(1 − α). Thus, since α ∈ (ǫ, 1 − ǫ), t ≥ (1 − 2α + α q 1 )/(1 − α) ≥ ǫ/(1 − ǫ) which implies that in our DP with accuracy parameterǭ it suffices to set L tpr = ( ǫ Bounding L fpr . For each X ∈ X , let f X denote the false positive rate of the optimal Equal Opportunity policy for group X. Similarly, let t X denote the positive rate of (i.e., recall) the optimal policy π * for group X ∈ X . By Equality of Opportunity property of π * , t X = t for each X ∈ X . Next, we consider the following cases.
For any sufficiently small ǫ > 0, we need to set L fpr so that by running the DP with accuracy parameter ǫ, we can approximate both true positive rate and false positive rate of the optimal Equal Opportunity policy within (1 − ǫ)-factor of their values. More precisely, we set L fpr so that if for each group X ∈ X and any pair (t X , f X ) with t X ≥ L tpr /(1 − ǫ/2), there exists a pair (t X ,f X ) such thatt X ≥ (1 − ǫ/2)t X , f X ≤ min(1, max(L fpr , f X )/(1 − ǫ/2)). Finally, once the above property holds for all groups X ∈ X , then for the corresponding policy π, precision(π) > (1 − ǫ) · precision(π * ). Let Finally, for each X ∈ X , we run the DP algorithm for each group with accuracy parameterǭ. By Lemma 4.8, the DP algorithm finds a set {t X = (1 −ǭ) iX , f x = (1 −ǭ) jX } X∈X (and a policy π achieving these rates) where for each X ∈ X , t X ∈ [L tpr , 1], f X ∈ [L fpr , 1] such that and for each X ∈ X , M X [k, t X , f X ] = true. Thus, by the bounds we just showed for the precision of such a policy, precision(π) ≥ (1 − ǫ) · precision(π * ). Thus, f α (π) ≥ (1 − ǫ) · f α (π * ).
Proof of Theorem 4.11. First we show that in our setting, in order to guarantee (1 + ǫ)-approximations of recall and precision, it suffices to run the described DP and consider estimates of t (true positive rate) and f (false positive rate) of form (1 −ǭ) i for i ∈ N in intervals [L tpr , 1] and [L fpr , 1] respectively, whereǭ ≤ ǫ/(2k). We provide tight bounds for L tpr and L fpr . Note that since for any policy π, tpr i,π , fpr i,π are non-decreasing in i, it suffices to provide "large enough" lowerbounds L tpr and L fpr for true positive rate and false positive rate in the final stage respectively (i.e., for t and f).
Bounding L fpr . For each X ∈ X , let f X denote the false positive rate of the optimal Equal Opportunity policy for group X. Similarly, let t X denote the positive rate of (i.e., recall) the optimal policy π * for group X ∈ X . By Equality of Opportunity property of π * , t X = t for each X ∈ X . Next, we consider the following cases.
For any sufficiently small ǫ > 0, we need to set L fpr so that by running the DP with accuracy parameter ǫ, we can approximate both true positive rate and false positive rate of the optimal Equal Opportunity policy within (1 − ǫ)-factor of their values. More precisely, we set L fpr so that if for each group X ∈ X and any pair (t X , f X ) with t X ≥ L tpr , there exists a pair (t X ,f X ) such thatt X ≥ (1 − ǫ/2)t X ,f X ≤ min(1, max(L fpr , f X )/(1 − ǫ/2)). Finally, once the above property holds for all groups X ∈ X , then for the corresponding policy π, precision(π) > (1 − ǫ) · precision(π * ). Let X 1 := {X ∈ X |f X /(1 − ǫ/2) ≥ L fpr } and let X 2 := {X ∈ X |f X /(1 − ǫ/2) < L fpr }. Note that X = X 1∪ X 2 . Then, precision(π) precision(π * ) = q 1 ·t Finally, for each X ∈ X , we run the DP algorithm for each group with accuracy parameterǭ. By Lemma 4.8, the DP algorithm finds a set {t X = (1 −ǭ) iX , f X = (1 −ǭ) jX } X∈X (and a policy π corresponding to these values) where for each X ∈ X , t X ∈ [L tpr , 1], f X ∈ [L fpr , 1] such that and for each X ∈ X , M X [k, t X , f X ] = true. Thus, by the bounds we just showed for the precision of such a policy, 1/precision(π) ≤ (1 + ǫ)/precision(π * ). Thus, g α (π) ≤ (1 + ǫ) · g α (π * ). As we need to run the DP algorithm for any of the |X | groups separately with the specified parameters L tpr , L fpr andǭ = O(ǫ/k), by Lemma 4.9, the total runtime is O( ).

C Missing Proofs of Section 5.2
Similarly to Observation 3.1, we can show the following observation for the policies that satisfies the Equalized Odds requirement.
Observation C.1. For any policy π that satisfies the Equalized Odds for a k-stage screening process with parameters ({τ i } i∈ [k] , {q X , u X } X∈X ), there exists M and N such that for each X ∈ X , Note that as computed in Observation 3.2, for policy any satisfying the Equalized Odds, the interview efficiency of a policy π for a k-stage process with parameters (q, u, In the rest of the section and for the simplicity of the exposition, we assume there are exactly two groups in the population; X = {A, B}. The result for the general setting can be derived similarly. Theorem C.2. The interview efficiency of any policy satisfying Equalized Odds for a single-stage screening process with parameters (q, u, τ ) is at most Proof. Maximizing the interview efficiency, is equivalent to minimizing N τ,π /M τ,π ; a minimizer of the inverse ratio is a maximizer of the interview efficiency and vice versa. Moreover, note that by the "minimally effective" property of the given test (i.e., Eq. (1)), N τ,π < M τ,π .
Remark 6. Note that we can generalize the result of Lemma C.2 to a k-stage screening process with multiple groups X . For any j ∈ [k], let ρ : . Any policy that satisfies Equalized Odds requirement at the end of the process (i.e., before the interview stage) has interview efficiency at most q 1 q 1 + X∈X ρuX . To see this, note that similarly to the proof of Theorem C.2 we can show that for every group X ∈ X , N X ≥ ρ · M X . Theorem C.3. Consider a k-stage screening process (q, u, τ ) with multiple groups X whose tests are minimally effective. Let π EOdd , π EOpp denote the interview efficiency maximizing policy that satisfies Equalized Odds and Equal Opportunity at the end of the process respectively. If max X∈X Π i∈[k] then IE(q, u, τ, π EOdd ) < IE(q, u, τ, π EOpp ).
Next, we show the following structure on a non-trivial optimal solution (i.e., one maximizing the interview efficiency). Note that π = 1 or π = 0 are the two trivial solutions satisfying the Equalized Odds for any given test.

D An FPTAS Algorithm for Screening Processes with Same Policy for All Groups
Here, we devise a slightly different DP algorithm. Instead of running the DP algorithm for each group separately (as in Section 4.3), we run a single DP algorithm for all groups simultaneously. Hence, all policies {π X } X∈X are the same. In our DP approach, we use the same discretization technique and only consider powers of (1 − ǫ).
Next, we describe the update rule for i > 1. For any X ∈ X , fpr X ∈ [0, ℓ fpr ] and tpr X ∈ [0, ℓ tpr ], where F i+1 is the set of {j X1 ≤ tpr X , j X0 ≤ fpr X } X∈X for which the following system of linear inequalities has a feasible solution, Lemma D.1. For any i ∈ [k], if there exists an Equal Opportunity policy π treating all groups similarly, with true positive rate t X,i ≥ L tpr /(1 − ǫ) i−1 , false positive rate f X,i for X ∈ X , then there exist In other words, if the policy π exists then the DP approach finds a policy with true positive rate at least (1 − ǫ) jX1 and false positive rate at most (1 − ǫ) jX0 for each X ∈ X .
Lemma D.2. For an accuracy parameter ǫ and lowerbounds on the false positive rate, L fpr , and the true positive rate, L tpr , the (single policy) DP algorithm runs in time O( k log 2|X | (1/Ltpr) log 2|X | (1/L fpr ) ǫ 4|X | ) and finds a policy π with true positive rate at least (1−ǫ) k−1 ·t X and false positive rate at most min{1, max{L fpr , f X }/(1− ǫ) k−1 } for each X ∈ X .
Proof. The size of ). Now we apply the DP approach and by Lemma D.1, the solution returned by the algorithm has the true positive rate and the false positive rate satisfying the guarantee of the statement.
Implications of DP Here, similarly to Section 4.3, we present FPTAS algorithms for the single policy setting with various pipeline efficiency objective using the modified DP approach described above when the number of different protected groups in the population is a fixed constant; |X | = O(1).
The proof of above theorems are identical to Theorem 4.10 and Theorem 4.11.

E Additional details in Linear Combination Counter Examples
In this section, we show that one cannot "locally score" tests when determining the optimum policy (the policy that maximizes a linear combination of precision and recall). Specifically, we give a setting with three levels of tests t 1 , t 2 , t 3 such that if only the first two levels t 1 and t 2 are available, then the optimal solution is to use t 1 and bypass t 2 , but if t 3 is also available then the optimal solution is to bypass t 1 and use t 2 and t 3 . Therefore, the question of how to best use two tests may depend on what tests are available at other levels. Note that in this example there is only one group and we do not have fairness constraints.
First, we show the following useful property of optimal policies for a pipeline where the first level has test statistics (1/2, 0) and all other levels have test statistics (1 − δ, 1/2).
Proof. By Lemma 4.2, if the False Positive rate is non-zero, in the optimal policy, for every i ∈ [k], (1 − π i 1 )π i 0 = 0. Next, we show that in this setting with only one group, for every i ∈ [k], π i 1 = 1. Suppose that there exists a level i ∈ [k] such that π i 0 = 0. Then, if π i 1 < 1, by increasing π i 1 to 1, the True Positive rate and False Positive rate increase by the same factor. Therefore, the precision remains unchanged and the recall increases; hence, the pipeline efficiency strictly increases.
Next, we consider the case where the optimal policy has precision one (i.e., its False Positive is zero). In any such policy, π 1 0 = 0. Note that once the precision is 1, the optimal policy maximizes recall. Hence, the optimal policy is to fully use t 1 (π 1 1 = 1, π 1 0 = 0) and bypass the rest of tests (for every 1 < i ≤ k, π i 1 = π i 0 = 1).
Theorem E.2. When the objective is to maximize a linear combination of precision and recall in a multistage screening process, there exist test parameters T and base rate p such that the maximal score policy switches when more tests become available. Specifically, when only tests t 1 and t 2 are available, the optimal policy is to use t 1 and bypass t 2 ((1, 0), (1, 1)), but if test t 3 is also available, the optimal policy is to bypass t 1 and use t 2 and t 3 ((1, 1), (1, 0), (1, 0)).