Optimal data-driven hiring with equity for underrepresented groups

Optimal data-driven hiring with equity for underrepresented groups

\affil[1]{Department of Economics, Brandeis University} \affil[2]{Robert H. Smith School of Business, University of Maryland}

{.5\baselineskip}

Introduction

We have just received an application for a job, or perhaps for admission to an academic program. From the application, we obtain a vector $X\in\mathds{R}^p$ describing the qualifications of the applicant -- educational background, years of work experience, GPA, test scores, and other information relevant to our decision. Suppose that the performance of the applicant, if hired or admitted, can be quantified and predicted using the linear regression model

where $\beta\in\mathds{R}^p$ is a vector of fixed effects, and $\varepsilon$ is an independent, zero-mean noise term. Although $\beta$ is unknown, let us suppose that it can be estimated using the observed performance of past applicants. Given an estimator $\hat{\beta}$, we can calculate the predicted performance $\hat{\beta}^\top X$ and use this to make our decision.

The situation becomes more complicated when, in addition to $X$, the application provides an additional protected attribute $Z\in\left\{0,1\right\}$ which indicates whether or not the applicant belongs to a certain disadvantaged demographic or socioeconomic group. Many such attributes are explicitly indicated in job or academic applications; in other cases, the protected information can be obtained with extremely high accuracy from the applicant's publicly observable social media presence KoStGr13. Either way, let us suppose that this information is known to the decision-maker. Now, for ethical and legal reasons, we must ensure that the hiring or admissions decision is fair with respect to the protected attribute.

However, the word “fair” has many meanings. The decision is based on model ((ref)), in which $Z$ is not present; in other words, $Z$ has no direct or causal effect on the performance $Y$. Thus, two applicants with different values of $Z$, but identical values of $X$, will have the same expected performance under the model and will be ranked identically. One could therefore argue that such an approach, where the ranking has no functional dependence on $Z$, is fair. This concept, known as “parity of treatment,” continues to be one of the most prominent criteria used to assess fairness (see Section (ref) for a detailed discussion).

The problem is that functional independence does not ensure probabilistic independence: there may be correlations in the joint (“data-generating”) distribution of $\left(X,Z\right)$, arising from causal factors that are not observable to the decision-maker. For example, evidence indicates that test scores are influenced by structural bias in education PeRuOsSi16, in the design of the tests themselves SaWi10, and in unequal access to opportunity LuSa20, but to the decision-maker in our motivating example, all these factors will show up only as a negative correlation between test scores and membership in a disadvantaged group. Consequently, the random variable $\beta^\top X$ will also be correlated with $Z$, and any decision based solely on expected performance will systematically disfavor applicants who belong to that group. Thus, parity of treatment will end up reinforcing inequality, a problem well-known to legal Ha00 and moral Th15 philosophy. In this paper, we show analytically how this occurs: when the candidate pool is large, the hiring decision is determined by the extreme values of $\beta^\top X$, which has the effect of amplifying even seemingly minor disparities.

Various solutions have been debated, e.g., reducing reliance on test scores SpRa19, or redacting the names of applicants from r\'{e}sum\'{e}s to prevent discrimination BeMu04. However, experimental evidence suggests that such policies may have unintended adverse impact BeCrBa15, while meeting with resistance among hiring managers FoWi18 who interpret them as a sign that the organization does not trust them. In an effort to approach disparities more systematically, firms are turning to AI and machine learning tools to guide hiring and other decisions (see Finocchiaro21 for a high-level overview). Such tools are likely to become more prevalent with time: RaBaKlLe20 discusses the legal considerations and argues that “the ready availability of algorithmic techniques might effectively create a legal imperative to use them.” Practical results, however, have not always lived up to expectations SuHiLa21. In one widely publicized instance, an AI tool at Amazon was found to favor certain features of r\'{e}sum\'{e}s that were more likely to appear on applications submitted by men BlEs20, a clear example of the pitfall of probabilistic dependence. In our view, these issues demonstrate the need for a transparent prescriptive framework that does not withhold information from decision-makers, but rather uses it fairly while also provably meeting firms' objectives (such as hiring the best candidates).

This paper proposes such a framework. We use a stylized model of the hiring problem, where ((ref)) is used to predict performance, and the goal is to select a candidate from a pool that is drawn randomly from a population. We create a hiring policy that depends on $Z$ functionally, but is independent of $Z$ probabilistically -- far from “redacting” protected attributes, it is necessary to use them in order to ensure fairness. This policy is not only fair, but also optimal with respect to the employer's objective, and it is transparent and interpretable: the employer can see exactly how performance and fairness are considered. Our approach proceeds in three parts:

A key insight of our work is that the presence of an explicit decision problem (optimizing over the candidate pool) has a profound and surprising impact on the structure of the ideal fair policy. As explained in Section (ref), recent work has studied optimal fair prediction of expected performance, i.e., finding the closest approximation of $\beta^\top X$ that is independent of $Z$. We prove, however, that ranking candidates by optimal fair predictions of their performance is not optimal in the hiring problem, because the decision requires us to compare across subgroups as well as within them. This result strongly distinguishes our work from the rich literature on fair prediction.

Our theoretical results are complemented by numerical experiments on both synthetic (simulated) data as well as real data describing over $20,000$ law students. In these experiments, the incidence of the protected group ranges from as low as $6\%$ to as high as $43\%$. In all cases, our method scales well, is easy to implement, and significantly outperforms alternative approaches in reducing discrimination. In many practical situations, fairness is achievable with negligible performance reduction: in other words, it is possible to uphold employers' interests while also reducing harm to minority candidates.

The OR/OM community has become increasingly aware of diversity, equity, and inclusion as a subject for research JoCh20. Recent surveys and tutorials, such as FuHuSi20 and BjAn20, draw heavily from the machine learning community, where fairness has been a subject of active research. Our work uses the stylized hiring problem to rigorously demonstrate the crucial and subtle distinction that arises when fairness is viewed from an operations perspective, i.e., in the context of a decision problem, where the goal is to find an optimal solution and not only to improve predictive power.

Related work

In the OR/OM literature, “fairness” has generally referred to equitable outcomes across a given set of entities BeFaTr11, e.g., retailers in a supply chain game HaRaZh07, locations served by a doctor McLe14,Rea21, or clients of an investment firm Diana21. Here, fairness is viewed in a game-theoretic, rather than statistical sense; the set of entities is pre-specified, not sampled from a population, and data collection is usually not explicitly modeled. On the other hand, there is also a growing body of empirical/experimental literature on bias and discrimination in, e.g., the sharing economy CuLiZh20,MePa21, as well as on algorithmic bias LaTu19. This work complements ours, by showing that the problem exists, but it generally does not propose analytical methods to alleviate it.

Our work is closer to the literature on prescriptive analytics and data-driven decision-making MiPe20, which uses statistical methods ranging from linear regression BeOhReSi16 to classification ChWaWa18 and machine learning BeKa20 to learn optimal decisions Mi20 from observational data HoLiWa18. This work sees prediction, not as an end in itself, but rather as a means for improved decision-making ElGr21. Data-driven methods have provided new insight into classical optimization problems such as the newsvendor LePeUi15,BaRu19. However, this active area of research has not yet explored fairness. Conversely, recent work by SaGu19 on fair decisions does not model data (regression features describing individual observations).

Many, perhaps most, existing data-driven models of fairness originate from the computer science and machine learning communities. Although there are hundreds of references on “algorithmic bias” or “fair prediction” (see BaGoLo20 for one survey), the precise definition of “fairness” varies greatly from one group of papers to the next. There are inherent, unavoidable tradeoffs between these types of fairness KlMuRa17. It is useful to identify four broad categories of papers and assess each respective definition of fairness in the context of data-driven hiring:

1) “Fairness” as “making similar decisions for similar individuals.” Studies in this category have considered prediction HeKr18 as well as decision-making GuKa21, with one specific context being auctions IlJaCh20,ChJa21. The unifying theme of these papers is that two individuals with the same attributes should receive the same treatment (or as close to it as possible). This issue arises in online decision-making GiJuKeRo18 where one wishes to avoid penalizing candidates who appeared early on, when the data were not sufficient to accurately assess them.

We do not consider this notion of fairness because it cannot help disadvantaged groups. In fact, a policy that consistently discriminates against certain values of $Z$ technically does treat similar candidates in the same way. Forcing such a policy to ignore $Z$ will not help either, because $Z$ is correlated with $X$, so candidates with similar values of $X$ are more likely to have the same $Z$ as well. Our goal in this work is to ensure a measure of equity for candidates who are different.

2) “Fairness” as parity of treatment. Parity of treatment BaSe16 means that our decision is conditionally independent of $Z$ given $X$. This notion was considered in such decision-making contexts as bandit problems JoKeMoRo16, reinforcement learning Jabbari17, and subset selection KeRoWu17. It is sometimes called “meritocratic” fairness; in the specific context of hiring, it was succinctly described by JoKeMoRo16 as, “a worse applicant is never favored over a better one.”

Unfortunately, the situation is not so simple. When an applicant is perceived to be “worse” because of structural bias, this approach to decision-making simply reinforces that bias. What is more, as shown in Section (ref) of our paper, the disparity between groups is amplified by the competitiveness of the position: even if this disparity is small on an individual level, a “meritocratic” policy will end up completely excluding the disadvantaged group when the number of applicants is large. In our view, this poses a serious ethical problem.

3) “Fairness” as parity of error. We use the term “parity of error” to collectively refer to several related notions such as equality of opportunity HaPrPrSr16, equality of chances LoHeHe21, and predictive parity Ch17. Studies in this category primarily focus on building a prediction $\hat{Y}$ of $Y$, though, e.g., Blum18 has applied this concept to decision-making. Their main goal is to eliminate bias in the estimation error: for example, in risk adjustments in healthcare ZiRo20, predictions may systematically under- or over-estimate costs for various patient classes, and it is necessary to balance the estimation error between them. In classification problems, where the response $Y$ is binary, this can be expressed simply as balancing false positives and/or negatives across different $Z$ values CaVe10,GoBaFaLo19,BlLy20.

Parity of error can be important when each individual is considered in isolation, e.g., the decision to offer a loan, or to grant parole, is based only on that particular person's predicted risk. Feldman15 uses hiring to motivate parity of error, but interprets it as a yes/no decision made for each individual separately, thus reducing the decision problem to a prediction problem. In actuality, however, the hiring decision selects between candidates, and the rule for making this selection is a higher-priority issue than estimation. If $\beta$ in ((ref)) is known, there is no estimation error at all, but using $\beta^\top X$ to rank candidates is still unfair for the reasons discussed previously. Our numerical experiments show that existing parity of error methods are unable to ensure representation for disadvantaged groups.

4)“Fairness” as statistical parity. Statistical parity means that our decision is independent of $Z$. This is the criterion adopted in our paper. It has been criticized in the literature on the grounds that it can be easily gamed Dwork2012,KeNeRoWu18, for example by hiring at random from the protected group, or through other manipulations that reduce population-wide measures of disparity (see AnBjDeRo19 for some examples in the context of the gender pay gap). In our setting, however, these issues are overcome by the presence of a decision problem with an economic objective function: among all policies that are fair in this sense, we wish to find the best-performing one with respect to the employer's interests.

The literature on promoting diversity in algorithmic decision-making, in contexts such as ranking CeStVi18,Zehlike18 and admissions Borgs19, has a similar goal of ensuring fair representation of disadvantaged groups. However, these papers take a “deterministic” approach to the problem by simply placing hard lower bounds on the proportion of candidates to be selected from the protected subgroup, regardless of their performance. By contrast, our decision is based on both the number and performance of candidates in each subgroup, and we only hire candidates who meet a (fair) performance threshold.

Among those papers that directly adopt statistical parity as the fairness criterion, many focus on prediction, and find it convenient to turn the fairness condition into a regularization penalty that can be added to any standard statistical model (see, e.g., Zemel13). This makes fairness into a soft constraint, which can be made stricter or looser by tuning a parameter. KaZh21 has an explicit decision problem (pricing), but similarly introduces a kind of budget constraint that allows for some tunable degree of unfairness. There is some difficulty in interpreting such solutions, as it is not clear how much unfairness should be considered “acceptable.” This is why, in our work, we first characterize an ideal fair policy, then approximate it in an optimal manner: the unfairness of the approximation vanishes to zero at a provably optimal rate.

A different approach is to transform the data $X$, or the performance $\beta^\top X$, in a way that removes the dependence on $Z$. Two pioneering papers on this topic are JoLu19 and Chzhen20. Both adopt statistical parity as their fairness criterion and derive an “ideal” transformation that is provably fair when the problem inputs are known. In that sense, these studies are the closest to our work among all the literature surveyed here; furthermore, Chzhen20 proves that this transformation technique is optimal in the sense of minimizing prediction error. The crucial difference is that these papers do not formulate any decision problem. In Section (ref), we give a counter-example proving that the “cdf-transformation” technique that gives optimal fair predictions is not guaranteed to lead to optimal hiring decisions. The core methodological contribution of our paper is a fair hiring policy that is provably optimal, not in the sense of predictive power, but with respect to the economic objective of the employer. Our results show that these two types of problems have very different solutions.

Fair decisions and their properties

Let $\left(X,Z\right)$ be a sample from the data-generating process, with $X$ taking values in $\mathcal{X}\subseteq\mathds{R}^p$ and $Z$ taking values in $\left\{0,1\right\}$. Let $Y$ be related to $X$ through the linear regression model ((ref)), and let $\rho = P\left(Z=1\right)$ denote the mean of $Z$. Throughout this section, we treat $\beta$ and the joint distribution of $\left(X,Z\right)$ as being known. Our first goal is to identify a notion of fairness that is suitable for the hiring problem. Once we characterize fair decisions in this ideal setting, we can then (in Section (ref)) discuss how to estimate them in practice.

The hiring problem is formalized as follows. We receive $K$ independent job applications from the general population, that is, we observe i.i.d. samples $\left\{X^k,Z^k\right\}^K_{k=1}$ from the data-generating process. For notational convenience, let $\bm{X} = \left(X^1,...,X^K\right)$ and $\bm{Z} = \left(Z^1,...,Z^K\right)$. A hiring policy $\pi$ maps $\left(\bm{X},\bm{Z}\right)$ into $\left\{1,...,K\right\}$. To reduce notational clutter, we will often write the index $\pi\left(\bm{X},\bm{Z}\right)$ of the selected candidate as simply $\pi$.

We define the ideal fair policy as

where $\Pi$ is the set of all measurable functions $\pi$ satisfying $\pi\left(\bm{X},\bm{Z}\right) \perp \bm{Z}$, with the symbol $\perp$ denoting independence. The independence condition can be equivalently written as $P\left(\pi=k\mid \bm{Z}\right) = P\left(\pi=k\right)$ for any $k=1,...,K$ and $\pi\in\Pi$. To rule out trivial policies such as $\pi\equiv 1$, we further require $P\left(\pi=k\right) \equiv\frac{1}{K}$, because the candidates are i.i.d. and, if nothing is known about them, any one should be equally likely to be chosen.\footnote[1]{Another way to interpret this condition is that the policy should be invariant with respect to permutations of the indices $1,...,K$.} The fairness condition says that this must still hold even if $\bm{Z}$ (but not $\bm{X}$) is known. At the same time, among all policies that are fair in this sense, we wish to select the one that maximizes expected performance. There may be many fair but suboptimal policies; Section (ref) presents a non-trivial example.

In the following, Section (ref) explains why unconstrained maximization of $\mathbb{E}\left(\beta^\top X^{\pi}\right)$ causes serious ethical concerns in hiring, thus justifying the choice of ((ref)) as the target. Section (ref) shows a fundamental difference between ((ref)) and the well-studied fair prediction problem; specifically, we prove that it is not optimal to rank applicants by optimal fair predictions of their performance. Section (ref) then gives a complete characterization of $\pi^*$.

Why we do not use parity of treatment

It may not be obvious why we see the policy $\pi^{\max} = \arg\max_k \beta^\top X^k$ as being unfair. It selects the best-performing candidate and does not functionally depend on $\bm{Z}$, thus appearing to be blind to the protected attribute.\footnote[2]{For example, anonymizing r\'{e}sum\'{e}s so that hiring managers cannot see the names of applicants may be seen as an attempt to implement this policy in practice.} It also meets the parity of treatment criterion: $\pi^{\max}$ is conditionally independent of $\bm{Z}$ given $\bm{X}$.

What makes $\pi^{\max}$ unfair is the competitiveness of the job opening. Only one applicant will be hired. As $K$ increases, the outcome is decided by competition, not between “typical” applicants in each subgroup, but between extreme values. This insight is made very stark by the following formal result, whose proof is deferred to the Appendix.

To illustrate the import of Proposition (ref), consider the following example. Suppose, for the sake of argument, that the conditional distribution of $\beta^\top X$, given $Z = z$, is $\mathcal{N}\left(0,\tau^2_z\right)$ with $\tau_0 > \tau_1$ (the difference may be arbitrarily small). The average performance of a single individual is the same in either subgroup. However, Proposition (ref) implies that $P\left(Z^{\pi^{\max}} = 1\right)\rightarrow 0$ as $K\rightarrow\infty$. Although more and more minority candidates are applying, the chance that any of them will be hired is vanishing.

The reliance of $\pi^{\max}$ on the tails of the data-generating distribution has the effect of amplifying disparities between the two groups. Even when the disparity appears to be small on an individual level (e.g., if $\tau_0$ is only slightly greater than $\tau_1$), it effectively prevents the disadvantaged group from being represented at all when the applicant pool is large. We see this as a serious ethical concern with using parity of treatment in hiring.

Why we do not use fair prediction

In the literature on fair prediction, we have a single $\left(X,Z\right)$ pair (i.e., $K=1$) and wish to solve

where $\Psi$ is the set of all measurable functions $\psi$ satisfying $\psi\left(X,Z\right)\perp Z$. While this formulation has some resemblance to ((ref)), the function $\psi$ is an estimator of $\beta^\top X$, not a policy that chooses between candidates; the goal is simply to estimate the performance of a single candidate in a fair way without any decision problem.

Chzhen20 showed that ((ref)) has a closed-form solution. Denote by

the conditional cdf of the performance $\beta^\top X$ of an applicant with attributes $X$, given $Z = z$. Then, the random variable $U = F_Z\left(\beta^\top X\right)$ follows a uniform distribution on $\left[0,1\right]$ and is independent of $Z$. This quantity represents the percentile rank of the applicant relative to their subgroup (on the population level). The optimal fair prediction is given by

a simple weighted average of the two conditional inverse cdfs, and a monotonic function of $U$.

A natural extension of this idea to the hiring problem is the simple policy $\pi^U = \arg\max_k U^k$, where $U^k = F_{Z^k}\left(\beta^\top X^k\right)$, which ranks applicants based on optimal fair predictions of their performance. Clearly $\pi^U \perp \bm{Z}$ and $P\left(\pi^U=k\right)\equiv \frac{1}{K}$, so the fairness condition is satisfied. It turns out, however, that $\pi^U$ is not optimal, as shown in the following counter-example.

\noindentProof: Take $K=2$, and let $F^{-1}_0\left(u\right) = \frac{3}{8}+\frac{1}{4}u$ and $F^{-1}_1\left(u\right) = u$. Suppose that $\bm{Z}=\left(0,1\right)$ is given. Then,

We then calculate

Analogously,

whence $\mathbb{E}\left(\beta^\top X^{\pi^U}\mid \bm{Z}=\left(0,1\right)\right) = \frac{29}{48}$.

Now define another policy $\pi$ as follows. When $\bm{Z} \neq \left(0,1\right)$, the policy is identical to $\pi^U$. When $\bm{Z} = \left(0,1\right)$, the policy chooses candidate $2$ if $U^2 > \frac{1}{2}$, and candidate $1$ otherwise. This policy satisfies the fairness condition because $P\left(\pi=1\mid\bm{Z}\right)=\frac{1}{2}$ for all $\bm{Z}$. Then, similarly to the previous computations,

where

and $\mathbb{E}\left(U^21_{\left\{U^2\leq \frac{1}{2}\right\}}\right) = \frac{1}{8}$. Thus, $\mathbb{E}\left(\beta^\top X^{\pi}\mid \bm{Z}=\left(0,1\right)\right) = \frac{5}{8}$, which is greater than the value obtained by $\pi^U$. Therefore, $\pi^U$ is not optimal. $\Box$

Ranking candidates by their percentile within subgroup is not optimal because (as is also the case in the counter-example) the conditional distributions $F_z$ may have very different tails, and a lower percentile in one subgroup may actually be farther out on the positive tail of performance. As we will see next, the optimal fair policy directly compares the best-performing candidates from each subgroup.

Characterization of the ideal fair policy

For convenience, let us introduce the notation

These quantities can be computed from $\left(\bm{X},\bm{Z}\right)$ and thus are known to the policy when the decision is made. Without loss of generality, suppose that the policy is given a set of candidates with $K_0,K_1 > 0$ (if all the candidates belong to the same subgroup, the decision is trivial).

For any fair policy $\pi$, we can write

Intuitively, this bound suggests that problem ((ref)) can be simplified by maximizing ((ref)) directly. The idea (which will be justified rigorously further down) is that it is sufficient to compare two candidates, namely $\arg\max_{k:Z^k=1} \beta^\top X^k$ and $\arg\max_{k:Z^k=0} \beta^\top X^k$, and the only question is when to choose which subgroup.

In the absence of any constraints, we would follow the parity of treatment policy, which indeed has this structure, with $\left\{Z^{\pi^{\max}}=1\right\}=\left\{R^{(1)}\geq R^{(0)}\right\}$. The fairness condition, however, requires

which straightforwardly follows from $P\left(\pi=k\mid\bm{Z}\right)\equiv \frac{1}{K}$. Intuitively, if we are comparing the top candidates from each subgroup, we should choose group $1$ on a set of outcomes covering a proportion $\frac{K_1}{K}$ of the largest values of $R^{(1)}-R^{(0)}$. The following result confirms our intuition.

\noindentProof: Pick any fair policy $\pi$ and let $A = \left\{Z^{\pi}=1\right\}$. By ((ref)), we have $P\left(A\mid\bm{Z}\right) = \frac{K_1}{K}$. We compare $A$ with the set

which satisfies $P\left(A^*\mid \bm{Z}\right)=\frac{K_1}{K}$ by construction. Note that $\pi^*$ satisfies the fairness condition $P\left(\pi^*=k\mid\bm{Z}\right)\equiv\frac{1}{K}$ because, conditionally on $\bm{Z}$, the policy selects subgroup $z\in\left\{0,1\right\}$ w.p. $\frac{K_z}{K}$, and each individual within that subgroup has the same conditional probability $\frac{1}{K_z}$ of being the best, independently of $R^{(z)}$.

For policy $\pi^*$, the bound ((ref)) holds with equality, and

Taking conditional expectations, we obtain

where the second line follows because $P\left(A\mid\bm{Z}\right)=P\left(A^*\mid\bm{Z}\right)=\frac{K_1}{K}$. Then, $\mathbb{E}\left(\beta^\top\left(X^{\pi^*}-X^{\pi}\right)\mid \bm{Z}\right) \geq 0$, whence $\mathbb{E}\left(\beta^\top\left(X^{\pi^*}-X^{\pi}\right)\right) \geq 0$, as desired. $\Box$

From ((ref)), we see that the ideal fair policy directly compares the best-performing candidates from each subgroup. The decision is made based on the difference $R^{(1)}-R^{(0)}$, which favors minority candidates both when they are performing well and when non-minority candidates are under-performing. This difference must be above the threshold $q\left(\bm{Z}\right)$, which ensures that we do not hire under-qualified candidates only to satisfy the fairness constraint. However, to correct for the effects of systemic and structural bias, this threshold is adjusted, and may be negative in some problem instances. Note also that ((ref)) is completely different from the optimal fair prediction discussed in Section (ref), which starkly illustrates the distinction between fair prediction and fair decisions.

Theorem (ref) gives us the optimal policy in an ideal situation where the underlying model is known, and thus gives us a standard to aim for. Computing this policy can be quite difficult, as we would then need the $\frac{K_0}{K}$-quantile of a fairly complicated distribution for each possible value of $\bm{Z}$. However, when $\beta$ and $F_z$ are no longer known, it is only necessary to estimate the policy, which turns out to be a much more tractable task.

Finite-sample policy and analysis

We will now suppose that $\beta$ and $F_z$ are unknown, but can be estimated from historical data. These data are not the same as the information $\left(\bm{X},\bm{Z}\right)$ about the pool of $K$ candidates from which the selection decision $\pi$ is made. We now suppose that we have access to

For each $m \leq n$, the pair $\left(X_m,Z_m\right)$ with $X_m = \left(X_{m,1},...,X_{m,p}\right)$ is an i.i.d. sample from the data-generating distribution, with $Y_m$ obtained from ((ref)) applied to $X_m$ and an i.i.d. noise $\varepsilon_m$. The response variable is only observed for the historical data points, and not for the data $\left\{X^k,Z^k\right\}^K_{k=1}$ describing the new candidates.

Note that $\bm{X}_n$ and $\bm{Z}_n$, which were observed in the past, are distinct (and independent) from $\bm{X}$ and $\bm{Z}$, which have just now been observed. In order to visually distinguish between the historical and new data, we use $k$ in the superscript to denote one of the new data points, and $m$ or $n$ in the subscript to denote a historical one. Thus, $X^k$ is a $p$-vector containing the features of the $k$th new candidate, while $X_m$ is the $m$th row of the historical data matrix $\bm{X}_n$. For shorthand, when it is necessary to refer to all of the historical data together, we write $\bm{H}_n = \left(\bm{X}_n,\bm{Z}_n,\bm{Y}_n\right)$. The definition of a policy is now extended to functions $\pi$ that map $\left(\bm{H}_n,\bm{X},\bm{Z}\right)$ into $\left\{1,...,K\right\}$, so that the decision is now based on the historical data.

In this paper, we assume that the decision is only made once, i.e., the problem is clearly separated into a training stage (using the historical data) followed by a decision stage (given $\bm{X}$ and $\bm{Z}$). Such a setup is sometimes called “offline.” Consequently, in our notation we will suppress the dependence of policies on the sample size $n$, since the dataset is fixed. This two-stage model is a natural first step for developing a fundamental understanding of fairness in decision-making; other recent work on prescriptive analytics, such as BeKa20, also separates training and decision-making in a similar way. We do not consider online (sequential) decision-making in this work, but the results of BaBaKh21 suggest that this setting can be handled relatively easily as long as the data-generating process is sufficiently rich.

Section (ref) first fixes a finite $n$ and proves that any non-trivial $\pi$ constructed from the training data cannot be guaranteed to satisfy $\pi\left(\bm{H}_n,\bm{X},\bm{Z}\right) \perp \bm{Z}$. In other words, it is not possible to be completely fair in finite sample. This motivates the study of an empirical approximation of ((ref)), formally stated in Section (ref). This empirical policy is also not completely fair, but we prove that it is the best possible approximation of the ideal fair policy: Section (ref) gives an upper bound on the asymptotic convergence rate of the probability that the empirical policy deviates from ((ref)), and Section (ref) proves a lower bound of the same order.

Fairness is unachievable in finite sample

The main result of this subsection is that, in finite sample, any perfectly fair policy $\pi\left(\bm{H}_n,\bm{X},\bm{Z}\right)$ cannot depend on $\bm{X}$. In other words, the only possible fair policies in finite sample are trivial ones, e.g., the policy that always selects the index of the first candidate.

Without loss of generality, suppose $K=2$, so $\bm{X} = \left(X^1,X^2\right)$ and $\bm{Z} = \left(Z^1,Z^2\right)$. Let $\pi$ be a policy that is fair in finite sample, i.e., satisfies $\pi\left(\bm{H}_n,\bm{X},\bm{Z}\right) \perp \bm{Z}$. For any $z =\left(z^1,z^2\right)$ with $z^1,z^2\in\left\{0,1\right\}$, define

to be the set of all possibly new data points that would lead the policy to select the first candidate under the given, fixed $z$ values. The fairness condition on $\pi$ requires

under any choice of conditional distribution of $\bm{X}$ given $\bm{Z}$. Note that, conditional on $\bm{H}_n$, both $A\left(1,1,\bm{H}_n\right)$ and $A\left(0,1,\bm{H}_n\right)$ are known (can be treated as fixed sets).

Let $g_z$ denote the conditional density of $X$ given $Z = z$ for $z\in\left\{0,1\right\}$. Then, recalling that $\left(X^1,Z^1\right) \perp \left(X^2,Z^2\right)$, ((ref)) is equivalent to the requirement

for any choice of $g_0,g_1$. The key to the result is that, given fixed data $\bm{H}_n$, the sets $A\left(1,1,\bm{H}_n\right)$ and $A\left(0,1,\bm{H}_n\right)$ in ((ref)) cannot have any additional dependence on the densities $g_0,g_1$. Then, the only way to make the fairness condition ((ref)) hold for all possible data-generating distributions is to have $\pi$ ignore $\bm{X}$ completely. If we knew the data-generating distribution exactly, then we could design $\pi$ to explicitly depend on $g_0,g_1$, but this is not allowed in finite sample.

To state the result more precisely, if $Z^2 = 1$ and $\pi$ picks the first candidate with nonzero probability, then it must always pick the first candidate (regardless of $\bm{X}$). We can also obtain the same result with $Z^2 = 0$ by rewriting ((ref)) with $A\left(1,0,\bm{H}_n\right)$ and $A\left(0,0,\bm{H}_n\right)$, and repeating the same arguments.

The implication of Theorem (ref) is that, for any finite sample size $n$, it is not possible to achieve near-optimal (or even good) empirical performance and simultaneously maintain perfect fairness. This motivates the study of empirical policies that are not perfectly fair in finite sample, but are guided by the ideal fair policy, i.e., approximate it as closely as possible given the data. In the remainder of this section, we present one such policy $\hat{\pi}$ and show that $P\left(\hat{\pi}\neq\pi^*\right)$ converges to zero at the fastest possible rate.

Empirical policy and performance bound

We propose to approximate ((ref)) by

where

and $\hat{\beta},\hat{q}\left(\bm{Z}\right)$ are estimators of $\beta,q\left(\bm{Z}\right)$ constructed from the data $\bm{H}_n$. For the first quantity, we use the ordinary least squares estimator

To construct the estimated quantile $\hat{q}\left(\bm{Z}\right)$, first recall that $q\left(\bm{Z}\right)$ is the $\frac{K_0}{K}$-quantile of the conditional distribution of $R^{(1)}-R^{(0)}$ given $\bm{Z}$. Note that we know $\bm{Z}$, and thus $K_0,K_1$, when the hiring decision is made. Then, we can let $\hat{q}\left(\bm{Z}\right)$ be the quantile of the corresponding empirical distribution. That is, for $z \in\left\{0,1\right\}$, let $m_1,...,m_{K_z}$ be $K_z$ indices, drawn uniformly with replacement, from the set $\left\{m\leq n:Z_m=z\right\}$, and let $\tilde{R}^{(z)} = \max_{k=1,...,K_z} \hat{\beta}^\top X_{m_k}$. The data (and therefore the estimator $\hat{\beta}$) are fixed, so if $\bm{Z}$ is given, these indices are the only source of randomness in $\tilde{R}^{(z)}$. Then, $\hat{q}\left(\bm{Z}\right)$ is the $\frac{K_0}{K}$-quantile of the distribution of $\tilde{R}^{(1)}-\tilde{R}^{(0)}$.

This empirical quantile can be estimated very easily using the bootstrap method EfTi94, as one can repeatedly sample the indices $m_1,...,m_{K_z}$ and calculate samples of $\tilde{R}^{(1)}-\tilde{R}^{(0)}$, then take the $\frac{K_0}{K}$-quantile of these bootstrapped values. This is sufficient for practical implementation. However, it is also possible to compute $\hat{q}\left(\bm{Z}\right)$ exactly, and we give an algorithm for doing so in the Appendix. Our theoretical analysis uses the exact value of $\hat{q}\left(\bm{Z}\right)$.

The empirical policy $\hat{\pi}$ is not perfectly fair, but from Section (ref) we also know that it is impossible for a nontrivial policy to be fair in finite sample. We evaluate the relative fairness of $\hat{\pi}$ in terms of the probability $P\left(\hat{\pi} \neq \pi^*\right)$ that $\hat{\pi}$ deviates from ((ref)). We first prove an upper bound on this probability, and provide a lower bound of the same order in Section (ref).

The assumptions on the data-generating process required for the bound are stated below. By and large, they are quite standard; for example, we require the matrix $\mathbb{E}\left(XX^\top\right)$ to be positive definite to ensure consistency of the OLS estimator $\hat{\beta}$. The most important assumptions are that the residual noise $\varepsilon$ is sub-Gaussian and the data $X$ are bounded. Both of these conditions are quite common in recent work on data-driven decision-making in the management science community; examples include, but are not limited to, BaBa20 and BaBaKh21.

There are two versions of the upper bound: the first is conditional on $\left(\bm{X},\bm{Z}\right)$ and has an exponential rate, and the second is unconditional (averaged over all possible new data) and has the rate $\mathcal{O}\left(n^{-\frac{1}{2}}\right)$. For readability, we will state and discuss the bounds here. Section (ref) provides further details on the key arguments of the proofs.

Thus, given any fixed group of candidates, the empirical policy converges to the ideal fair policy exponentially, but the rate exponent is a function of $\left(\bm{X},\bm{Z}\right)$. In the unconditional version, this exponent varies randomly, and may be arbitrarily small, making it more difficult to rank the candidates on average over all possible realizations from the data-generating process.

The distinction between the conditional and unconditional bounds is noteworthy because it does not arise in other problem classes where decisions are ranked using estimated values, such as ordinal optimization ShBrZe18. In many such problems, the true values of the decisions are fixed (though unknown to the decision-maker), and the only noise comes from estimation error. In such problems, one can often obtain exponential decay rates for error probabilities, but the precise exponents also depend on the values Ru20. In the present setting, these values are not fixed, but are determined by sampling from the data-generating process, which introduces additional noise. Essentially, the policy now has to separate the estimation error from the variation in the candidate pool, so it is not surprising that the convergence rate becomes slower.

Minimax lower bound

We now establish a lower (minimax) bound of $\mathcal{O}\left(n^{-\frac{1}{2}}\right)$ on the probability of deviating from the fair decision. The precise meaning of such a bound is that, for any empirical policy, one can always find at least one data-generating process that makes the deviation probability vanish at the indicated rate. We may impose additional restrictions on the data-generating process without loss of generality -- if we can find a sufficiently “bad” distribution from the restricted class, the ensuing lower bound will still hold for a more general class. To put it another way, the worst case can only become worse if a more general class of data-generating processes is permitted.

Since we are free to impose additional structure on the data-generating process, let us assume that $X \perp Z$ with $\mathbb{E}\left(Z\right) = \frac{1}{2}$ and $X\sim \mathcal{N}\left(0,\bm{I}_p\right)$, where $\bm{I}_p$ is the $p\times p$ identity matrix. Suppose that $Y$ is related to $X$ through ((ref)) with $\varepsilon\sim\mathcal{N}\left(0,\sigma^2\right)$. Let us fix $\sigma > 0$ to an arbitrary strictly positive value. Thus, the distribution of $\left(\bm{H}_n,\bm{X},\bm{Z}\right)$ is parameterized by $\beta$. In our proof we will further restrict ourselves to $\beta \in \left\{\beta_0,\beta_1\right\}$ for suitable choices of $\beta_0,\beta_1$.

Without loss of generality, suppose that $K=2$, so $\bm{X} = \left(X^1,X^2\right)$ and $\bm{Z} = \left(Z^1,Z^2\right)$. Because $F_0=F_1$ in this setting, the ideal fair policy ((ref)) reduces to the indicator function $I_{\beta}\left(\bm{X}\right) = 1_{\left\{\beta^\top X^1 \geq \beta^\top X^2\right\}}$. We can now state the minimax bound (the proof is given in the Appendix).

Theorem (ref) shows that it is not possible to improve on the $\mathcal{O}\left(n^{-\frac{1}{2}}\right)$ rate obtained in ((ref)) for the empirical policy $\hat{\pi}$. In other words, $\hat{\pi}$ converges to the ideal fair policy $\pi^*$ at the best possible rate with respect to the sample size $n$. Together with the relative ease of computing $\hat{\pi}$, this constitutes a strong argument for the practical implementation of the empirical policy.

Proof of upper bound

In this section, we give the main arguments justifying Theorem (ref). Assumption (ref) is assumed throughout. We use the notation $F_{z,\theta}\left(r\right) = P\left(\theta^\top X \leq r\,|\,Z=z\right)$ to distinguish between conditional cdfs obtained under different values $\theta$ for the regression coefficients $\beta$.

Let $\bm{Z}$ be given and suppose that $K_0,K_1 > 1$, as the policy becomes trivial otherwise. For $z\in\left\{0,1\right\}$, the conditional cdf of $R^{(z)}$ given $\bm{Z}$ is denoted by $G_{z,\beta} = \left(F_{z,\beta}\right)^{K_z}$. Then, for any $t$,

Viewing $K_0,K_1$ as fixed and letting

we see that the desired quantile is the value $q$ satisfying $T\left(q\right) = 0$.

Let $n_z = \sum^n_{m=1} 1_{\left\{Z_m=z\right\}}$ and replace $F_{z,\beta}$ by the empirical cdf

Define

We can take $\hat{q} = \arg\min_t \left|\hat{T}\left(t\right)\right|$. Given enough data, this quantity will converge to $q$.

From ((ref)), we see that there are two basic ways in which the empirical policy $\hat{\pi}$ may fail to match the ideal fair policy $\pi^*$. First, $\hat{\pi}$ may fail to select the same subgroup as $\pi^*$. Second, $\hat{\pi}$ may select the correct subgroup, but choose the wrong candidate from this group due to estimation error in $\hat{\beta}$. Therefore,

Then, to obtain the desired result, it is sufficient to bound each term on the right-hand side of ((ref)) by an exponentially decaying quantity of the form ((ref)). The exponents do not need to match, since we can simply take $g\left(\bm{X},\bm{Z}\right)$ in ((ref)) to be the smallest among them. The same is true for the unconditional bound ((ref)), as we may simply take expectations of both sides of ((ref)).

Conceptually, each of the two types of error occurs due to error in the relevant estimated parameters: within-subgroup error is caused by estimation error in $\hat{\beta}$, whereas subgroup selection error is caused by estimation error in both $\hat{\beta}$ and $\hat{q}$. The latter quantity, in turn, is derived from the estimators $\hat{F}_z$ and $\hat{T}$. Thus, we first have to establish sufficiently strong exponential decay rates on each type of estimation error. We then connect the two types of wrong decisions in ((ref)) to these concentration inequalities to arrive at the desired bounds.

Bound on error within subgroup

Take $z\in\left\{0,1\right\}$ and let $j_1,j_2$ be the indices of the largest and second-largest values in the set $\left\{\beta^\top X^k: Z^k = z\right\}$. We derive

where $W = \kappa_4 \|\hat{\beta}-\beta\|_2$ is obtained by applying Assumption (ref)(iii). Note that $W$ is independent of the difference $\beta^\top \left(X^{j_1}-X^{j_2}\right)$, because $W$ is computed from the historical data $\bm{H}_n$, which is independent of the new data $\left(\bm{X},\bm{Z}\right)$.

We then establish the following tail bound on the estimation error of $\hat{\beta}$. The argument for the bound is quite technical and not central to what follows, so we state the result here and give the proof in the Appendix.

Using Theorem (ref), we can find constants $C_3,C_4$ such that

where the last line follows by Assumption (ref)(iii). This completes the proof of the conditional bound.

To obtain the unconditional bound, we first observe that $\left(F^{-1}_z\right)' = \left(F'_z\circ F^{-1}_z\right)^{-1}$. By Assumption (ref)(v), it follows that $\left(F^{-1}_z\right)' \geq \kappa^{-1}_6$. Consequently, ((ref)) yields

The quantity $F_z\left(\beta^\top X^{j_1}\right)-F_z\left(\beta^\top X^{j_2}\right)$ is precisely the difference between the top two uniform order statistics from a sample of size $K_z$, and therefore follows the distribution $Beta\left(1,K_z\right)$. Because $K_z\leq K$, the density of this distribution is bounded by $K$ on $\left[0,1\right]$. We then derive

for some $C_5>0$. This completes the proof of the unconditional bound.

Bound on subgroup selection error

It remains to bound the last term on the right-hand side of ((ref)). We require a concentration inequality on $\hat{q}$, similar to what was obtained for $\hat{\beta}$ in Theorem (ref). This quantile, however, is obtained from $\hat{T}$, an estimator of the cdf of $R^{(1)}-R^{(0)}$ which itself is derived from the empirical cdfs $F_z$. Thus, we successively derive exponential bounds on all of these quantities. As in Section (ref), the proofs of these results are given in the Appendix.

Recall from ((ref)) and ((ref)) that $T,\hat{T}$ depend on $K_0,K_1$, which are derived from $\bm{Z}$. We prove the following results for $K_0,K_1$ fixed, but since the bounds that we obtain do not depend on these quantities, this makes no difference.

We now derive the conditional bound. Note that $q,K_0,K_1$ can be treated as fixed when $\left(\bm{X},\bm{Z}\right)$ is given. Intuitively, we will select the incorrect subgroup if the estimation error in $\hat{q},\hat{\beta}$ is greater in some sense than the gap $\left|R^{(1)}-R^{(0)}-q\right|$. Formally, we write

The estimation errors $\hat{\beta}-\beta$ and $\hat{q}-q$ are independent of $\left(\bm{X},\bm{Z}\right)$, so we can apply Theorem (ref) to obtain

where the last equality follows by Assumption (ref)(iii), which also implies $\left|q\right|\leq 2\kappa_4$.

Similarly, we apply Theorem (ref) to obtain

where $C_{14} = \min\left\{1,\frac{1}{4}\kappa^{-2}_4\right\}$. Combining ((ref)) with ((ref))-((ref)), we obtain

where $C_{15} = \min\left\{\frac{C_2}{16\kappa^2_4},\frac{1}{4}C_{13}C_{14}\right\}$ and $C_{16}=8\left(C_1+1\right)$. This completes the proof of the conditional bound.

We now turn to the unconditional bound. First, let us write

using the fact that $G_{1,\beta} = \left(F_{1,\beta}\right)^{K_1}$. The interchange of differentiation and integration at $t=q$ is valid by Thm. 2.27 of Fo99 because the density $F'_{z,\beta}$ is bounded by $\kappa_6$ due to Assumption (ref)(v). By the same assumption, the conditional density of $R^{(1)}-R^{(0)}$ given $\bm{Z}$ is bounded by $K\kappa_6$. Applying this bound to ((ref)), and using arguments similar to those at the end of Section (ref), yields the unconditional bound.

Computational experiments

We present numerical experiments demonstrating the practical potential of our approach for making decisions that are both optimal and fair. Section (ref) describes two benchmarks, based on regularized estimation, from the literature on fair prediction, which were also implemented in the experiments. Section (ref) considers a setting with synthetic (simulated) data. Section (ref) presents results using real data on law students; separate experiments are conducted with two different protected attributes.

Benchmark policies

Many of the models and procedures in the extensive literature on fair prediction were designed for classification problems, where the response variable $Y$ is binary. Though our approach can potentially handle such problems as well (since it does not impose much structure on the cdf $F_z$ connecting the linear model to the response), our primary focus in this paper is on linear regression. Among those papers that are able to handle this setting, the predominant method of computing fair predictions is to solve a modified version of the usual statistical estimation problem (choosing regression coefficients that minimize total statistical error across the given dataset) with additional constraints that impose a bound on some measure of unfairness, such as the correlation between the prediction and the protected attribute. One can also reformulate such constrained optimization problems by turning the constraint into a regularization term; in the context of linear regression, one thus solves

where $L$ is the chosen measure of unfairness, and $\lambda \geq 0$ is a tunable parameter governing the tradeoff between fairness and accuracy. In the hiring context, having obtained an estimator $\hat{\theta}$ from the regularized problem, our decision is given by $\arg\max_k \hat{\theta}^\top X^k$.

Many penalties have been proposed in the literature and evaluated empirically on various datasets. We choose two penalties from recent papers that we believe to be representative of this class of methods. The first penalty, proposed by Berk17, is written as

where the authors recommend to set the weights $w\left(y,y'\right) = e^{-\left(y-y'\right)^2}$. The goal of this method is to make similar predictions for similar response variables, for either group. The second penalty, considered by ZiRo20, has the simpler form

which seeks to balance the prediction error between the two groups. Both papers also consider other modified versions of these penalties, and still others can be found in other papers, but there is much similarity between them (for example, every such approach requires a tunable parameter), and no consensus on which specific version is the best. In fact, as will become clear later in this section, both of the above penalties lead to very similar performance as far as decision-making is concerned, which suggests that the nuances between penalties are not the central issue in our problem.

An important practical issue, which we encountered in our experiments, but which does not seem to have attracted much attention in the literature, is the computational cost of solving the penalized regression problem. Both Berk17 and ZiRo20 used the CVX convex optimization package cvx to solve their respective problems. We did this as well, and found that the computation time was non-negligible even for a single problem, to say nothing of the multiple problems one has to solve in order to tune $\lambda$. In particular, the penalty of Berk17 adds up a large number of terms, and thus is time-consuming to evaluate even for a fairly small sample size of $n=1000$. We reduced this cost by using sparse matrices and setting the weights $w\left(y,y'\right)$ to zero whenever the recommended distance $e^{-\left(y-y'\right)^2} < 10^{-5}$. Even so, the resulting problem was significantly slower to solve than that of ZiRo20. By contrast, our proposed policy ran much faster. To give an example, in the setting of Section (ref), the time required to compute a single decision for a sample size of $n=1000$ was approximately $1.25$s for the method of Berk17, $0.25$s for the method of ZiRo20, and $0.001$s for our method. Our experiments were conducted in MATLAB, but we used the interface between CVX and the commercial solver MOSEK to solve the penalized problems; this was much faster than CVX's default solver, but still much slower than our method.

Synthetic data

We present one synthetic scenario that cleanly illustrates how our approach can address certain important practical concerns, with the caveat that many of the specifics of actual hiring decisions are abstracted away. First, let $\mathbb{E}\left(Z\right) = 0.15$. Let $p = 30$ be the dimensionality of the problem. Given $Z = z$, we assume that $X\sim\mathcal{N}\left(0,\bm{C}_z\right)$, where the $p\times p$ covariance matrix is chosen according to $\bm{C}_z = \tau_z \bm{A}_z\bm{A}^\top_z$, where $\bm{A}_z$ is a matrix of independent standard normal random variables, and

As a result, realizations of $X$ given $Z = 1$ tend to have somewhat lower spread than given $Z = 0$, even though the conditional mean of the performance $\beta^\top X$ is the same in both cases.\footnote[3]{It bears repeating that this difference between distributions is the effect of numerous structural and systemic factors that are not directly visible to the decision-maker.} Since we are choosing the best among $K$ candidates, however, this means that parity of treatment (as discussed in Section (ref)) will underrepresent the minority group.

We generated the historical data $\left(\bm{X}_n,\bm{Z}_n\right)$ from the above-described distributions with a sample size of $n = 1000$. A single vector $\beta$ was generated from a $\mathcal{N}\left(0,\bm{I}_p\right)$ distribution and fixed at the beginning of the experiment; the covariance matrices $\bm{C}_z$ were also generated once and then fixed. The historical responses $\bm{Y}_n$ were calculated according to ((ref)) with i.i.d. standard normal residual errors. The new data $\left(\bm{X},\bm{Z}\right)$ used for decision-making were also sampled from the data-generating distribution with $K = 10$ candidates per decision.

In our experiments, the empirical policy $\hat{\pi}$ from Section (ref) is shown the first $m \leq n$ of the historical data points, uses these data to compute the relevant estimators, then selects from among a new independently generated set of $K$ candidates. The precise sequence of selection decisions does not influence the historical data; the purpose of varying $m$ is simply to show the effect of sample size on performance. The performance metrics are the objective value $\mathbb{E}\left(\beta^\top X^{\hat{\pi}}\right)$, as well as the probability $P\left(Z^{\hat{\pi}}=1\right)$ of hiring a minority candidate, both estimated empirically by averaging over $10,000$ macro-replications at each $m$ value (the large number of macro-replications renders the standard errors negligible). We also implemented parity of treatment, given by $\arg\max_k \hat{\beta}^\top X^k$, in the same manner.

With regard to the two regularization-based methods used as benchmarks, it was not practically feasible to run them for every $m$ value (with multiple macro-replications) due to the high computational cost of running convex programming solvers. Thus, we only ran them for the entire sample size of $1000$ data points and reported the results (averaged over $100$ macro-replications) for the best of the two as horizontal lines in Figure (ref). In this way, we do not see how the performance of these methods varies with sample size, but we can see their “best” performance with the largest possible sample size and compare this to the trajectories of the other two methods.

In Figure (ref), we see that both parity of treatment and the proposed empirical fair policy show improved performance over time as $m$ increases and $\beta$ is estimated more accurately. Unsurprisingly, the fair policy lags slightly behind during this period, because parity of treatment is able to maximize reward without any constraints, and because our policy also has to estimate a difficult cdf in addition to $\beta$. What is remarkable, however, is that this gap closes almost completely for larger sample sizes: at $m = 1000$, the objective value achieved by the fair policy is $99.76\%$ of the value achieved by the unfair one! At the same time, Figure (ref) shows that the unfair policy hires significantly fewer minority candidates than there are in the candidate population ($9.92\%$ at $m = 1000$), while the fair policy has achieved statistical parity.

It is interesting to observe that neither of the regularization-based benchmarks was able to improve over parity of treatment to any appreciable degree. We ran both methods over a wide range of magnitudes of the regularization parameter $\lambda$, but found that the results (shown in Table (ref)) were both remarkably insensitive and very similar between the two methods. For this reason, only the best performance values in the table are shown in Figure (ref).

The ineffectiveness of the regularization-based methods highlights the distinction between fair prediction and fair decision-making. Both of these methods minimize an adjusted form of prediction error in order to reduce bias in the prediction: for example, a proposed vector $\theta$ of regression coefficients may lead to bias if the random variable $\left(\beta-\theta\right)^\top X$ is correlated with $Z$. In our setting, however, it is possible to have no prediction error (i.e., $\theta = \beta$) and still make an unfair decision. Furthermore, if we have $K$ candidates to choose from, the prediction error for most of these candidates is of little importance; if we incorrectly rank some candidates in the middle or bottom of the pool, this in itself does not matter much. The key issue is how well we can distinguish between candidates on the tails of the distributions of their respective groups. Because regularization-based formulations do not have any notion of decision-making built in, they turn out to show no tangible improvement over parity of treatment.

From this example, we see that fairness does not have to come at the expense of performance. As explained in Section (ref), the ideal fair policy favors minority candidates in those situations where they are very strong relative to non-minority candidates (i.e., the best minority candidate is strong, or the best non-minority candidate is weak). In this way, the employer's interests are taken into account while guaranteeing equity for the underrepresented group.

Real data

We also evaluated our approach on real data\footnote[4]{Publicly available at: \url{http://www.seaphe.org/databases.php}} from the LSAC National Longitudinal Bar Passage Study Wi98. The dataset describes (in anonymized form) over $27,000$ students from various US law schools. For our purposes, we let $X$ consist of those attributes that could be observed when the students first applied (family income, LSAT score, undergraduate GPA, birth year, and whether they were applying to a part-time or full-time program), and we used students' final GPA in law school as the response variable $Y$. As described in Wi98, the original study had already adjusted final GPA to correct for differences between schools. We considered two possible choices for the protected attribute $Z$, namely gender (female) and race (Black/Hispanic). In the following, we ran a separate set of experiments for each of these two attributes. After removing entries with missing data, we were left with $N = 22,337$ students.

We do not know the true distribution of the population that was sampled in this study. For the purpose of these experiments, we chose to treat the sample of $N$ students as the entire population. Rather than fit a vector $\beta$ to the population, we use the observed response value $Y$ of each candidate to measure performance. We also treat the empirical distribution of $\left(X,Z\right)$ over the population of $N$ students as the data-generating process from which a smaller sample of size $n$ can be drawn and used to train different methods. Essentially, the history $\bm{H}_n$ and the new data $\left(\bm{X},\bm{Z}\right)$ are all being bootstrapped from the original dataset.

We used $K = 30$ in both experiments. The proportion $\mathbb{E}\left(Z\right)$ was $0.4383$ for women, and $0.0642$ for Black/Hispanic applicants. In this way, our method can be tested on settings whose respective proportions of minority candidates are relatively high and low. Overall, we followed the same approach for implementing and evaluating methods as in Section (ref).

Figure (ref) presents results for the setting where race was used as the protected attribute, with $n = 2000$ as the largest sample size. The data reflect a significant disparity between subgroups, with $\mathbb{E}\left(Y\mid Z=1\right)-\mathbb{E}\left(Y\mid Z=0\right)=-1.0809$ (again, the expectation here is over the empirical distribution in the data). Nonetheless, as seen in Figure (ref), the gap between the objective values of the fair policy and the unfair parity of treatment policy has a much smaller magnitude of $0.05$. The fair policy achieves $90\%$ of the objective value of the unfair policy. At the same time, the difference in equity between the two policies (Figure (ref)) is particularly striking: all of the benchmarks\footnote[5]{Again, we ran both regularization-based methods for a range of $\lambda$ values, and reported the best performance across all cases in Figure (ref). We do not repeat Table (ref) again as the numbers are not particularly informative.} virtually never hire minority candidates. Only the proposed policy is able to mitigate this problem.

Figure (ref) presents analogous results with gender as the protected attribute and $n = 3000$ as the largest sample size. This time, the data reflect a smaller disparity between subgroups, with $\mathbb{E}\left(Y\mid Z=1\right)-\mathbb{E}\left(Y\mid Z=0\right)\approx 0$. Consequently, as shown in Figure (ref), the fair policy incurs virtually no loss in objective value relative to the unfair policy. However, this does mean that there is no fairness issue: as seen in Proposition (ref), the hiring decision is influenced by the tails of the conditional distributions, not by their means. We see in Figure (ref) that the unfair policy underrepresents women, who comprise $43.84\%$ of this population but are selected by the policy only $40\%$ of the time.\footnote[6]{Regarding the regularization-based methods, we could only run the penalty of ZiRo20 when gender was the protected attribute. The approach of Berk17 did not scale, with over $2$ million terms in the objective function even after the tweaks described in Section (ref).} The fair policy completely corrects this disparity.

To summarize, the proposed policy achieves statistical parity, with realistic sample sizes, across all examples, which include both synthetic and real data, as well as varied frequency of the protected attribute (as low as $0.0642$ and as high as $0.4383$). A major insight of these experiments is that the firm can ensure fairness with only minor reduction in objective value, and often (as shown in Figures (ref) and (ref)) with virtually no reduction at all.

Conclusion

We have presented a data-driven prescriptive framework for fair decisions in a stylized hiring problem where applicants are drawn independently from a population, and the firm evaluates their expected performance based on their observable attributes. Our main contribution is a hiring policy that is both fair with respect to a protected attribute of the candidates, and optimal (among all possible fair policies) with respect to the firm's objective of hiring the best talent. Crucially, this policy does not ignore the protected attribute; on the contrary, it depends on the attribute functionally in order to ensure that the decision does not depend on it probabilistically. The policy is transparent, interpretable, and easy to estimate empirically in a provably optimal manner. Our numerical results show that the policy is highly practical and performs well even with fairly small sample sizes. Furthermore, in many situations, fairness is achievable with negligible effect on objective value -- that is, decisions can be made much less damaging to minority candidates at very little cost to the firm.

Our work contributes to the growing literature on data-driven decision-making, which aims to integrate ideas from statistics and machine learning into OR/OM models rather than simply applying ML algorithms out of the box. In particular, we offer a new perspective on how fairness may be studied within a decision problem, and we show that fair decisions are very different from fair predictions. The presence of an economic objective function guides the selection of a fair policy and helps obtain decisions that meet firms' expectations while reducing the destructive effects of bias. We view fair decision-making as a rich problem class, separate from fair prediction, and we envision many possible extensions of the ideas presented in this paper to other classes of decision problems in revenue management, service operations and other areas.