Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
89,486 characters · 17 sections · 64 citation commands
Testing the Fairness-Accuracy Improvability of Algorithms
As algorithms are increasingly used to guide important predictions about people (e.g., which patients to treat, or which borrowers to grant a loan to), substantial concern has emerged about their potential disparate impact---namely, that the algorithm's benefits or harms may be born unequally across different social groups. Disparate impact has been empirically documented in a range of applications ProPublica,Obermeyer2019-te,ArnoldDobbieHull,Pinkham, but the organizations that deploy these algorithms also value other objectives such as accuracy and profit. When an algorithm has a disparate impact, is it possible to reduce that disparity without compromising the organization's other objectives? The answer to this question is legally relevant barocas2016big. In many settings, a policy with a disparate impact that would otherwise be prohibited under US federal law is permissible if it is necessary to achieve a legitimate business interest (see Section (ref) for a discussion). As a result, it is essential for both external regulators and internal stakeholders to have tools that can determine when fairness is in conflict with other objectives, and when instead there exist alternative algorithms that do better on all of the specified criteria. In this paper, we provide an econometric framework and results for establishing, or refuting, the existence of such algorithms.
Our paper is organized as follows. In the first part, we formally define improvability with respect to a fairness objective and an accuracy objective (where we use “accuracy” as an umbrella term for any objective not directly related to inequities across groups). In the second part, we provide a procedure for testing the improvability of a status quo algorithm given data. In the third part, we establish the theoretical foundations of our test: We prove its large-sample validity and consistency (under appropriate conditions), and additionally demonstrate that it satisfies a form of robustness to manipulation, which we define in the context of a game between a policymaker and an analyst. Finally, we apply our procedure to test the improvability of a healthcare algorithm studied in Obermeyer2019-te.
Section (ref) presents our conceptual framework. To define improvability, we build on the algorithmic fairness literature covered in Section (ref), and more specifically the framework of liang2022algorithmic. An algorithm is defined to be a mapping from a space of observed covariate vectors (e.g., a medical profile) into a prediction (e.g., a medical diagnosis). There are two predefined groups. Algorithms are evaluated in terms of their accuracy for each group and their fairness across groups. Accuracy for each group is defined to be the group's expected utility with respect to a pre-specified utility function, e.g., the algorithm's correct classification rate or the fraction of patients in this group that get treated. Fairness is possibly based on a different utility function (but need not be); it is measured as the disparity between the expected utilities of the two groups. This very general formulation allows us to nest most objectives that have been proposed in the preceding literature on algorithmic fairness, as well as the broad range of business objectives that could be legally relevant (see Section (ref) for examples).
Our analysis allows for the analyst to pre-specify a class of permissible algorithms. We define an algorithm to be $(\Delta_r,\Delta_b,\Delta_f)$-improvable within this class if some other permissible algorithm simultaneously achieves higher accuracy for each group (respectively by factors of $1+\Delta_r$ and $1+\Delta_b$) and lower unfairness (by a factor of $1-\Delta_f$). This parameterized definition permits us to move beyond simply testing whether any improvement exists, and instead to examine specific magnitudes of potential gains. Such magnitude considerations are particularly important in legal and policy contexts when the practical significance of a disparate impact reduction is taken into consideration tobia2017disparate,DOJTitleVI2024.\footnote{In the context of employment discrimination, tobia2017disparate reports that “The First, Third, and Tenth Circuits oppose practical significance inquiries; the Second, Fourth, Fifth, Sixth, Ninth, and Eleventh Circuits endorse them; and the D.C., Seventh, and Eighth Circuits have no clear precedent.” In the context of discrimination by an organization receiving federal funding, the Department of Justice is less equivocal. In their Title VI legal manual, they write, “investigating agencies must determine whether the disparity is large enough to matter, i.e., is it sufficiently significant to establish a legal violation. The magnitude of the disparity necessary may be difficult to define in some cases, but guidance can be drawn both from judicial consideration of this question and from federal agency guidelines” DOJTitleVI2024. See Section 1.1 and Appendix Section D of this paper for a discussion of the legal framework.} By varying those parameters in our subsequent statistical procedure, we can test whether the data supports, or fails to reject, different sizes of fairness and accuracy-improvements.
We suppose that there is a status quo algorithm whose disparate impact is of interest, and the analyst would like to test the null hypothesis that this algorithm is not $(\Delta_r,\Delta_b,\Delta_f)$-improvable. The analyst has access to a sample of individuals, their covariates, and a “ground truth’’ outcome (i.e., a quantity that determines the optimal algorithm and is known ex-post). Section (ref) describes our proposed procedure: First, the analyst splits the data into a training set and a test set, and uses the training set to identify a candidate algorithm that potentially improves on the status quo algorithm. Subject to certain regularity conditions, any method for identifying a candidate algorithm---which we call a selection rule---can be plugged into this step (see examples in Section (ref)). Once a candidate algorithm has been identified, the analyst uses the test set to evaluate whether the simultaneous improvements of the candidate algorithm for both criteria are statistically significant. To avoid computing standard errors case-by-case for each specification of accuracy and fairness, we propose using the bootstrap to compute the critical values of our test. Finally, to reduce the uncertainty introduced by sample-splitting, we recommend that the analyst repeats the above process several times and aggregates the results by reporting the median $p$-value across the set of tests. The analyst rejects the null hypothesis whenever the median $p$-value falls below half of the desired significance level.
Our proposed approach overcomes a key practical challenge, which is that algorithms are often exogenously constrained for legal, logistical, or ethical reasons. The exact nature of these constraints may vary across settings, and include (among others) capacity constraints on how many individuals are admitted or treated, shape constraints such as monotonicity of the decision with respect to a given input pmlr-v108-wang20e,Felders2000,NEURIPS2020_b139aeda, and statistical constraints such as requiring independence of decisions with a group identity variable Mitchelletal,barocas-hardt-narayanan. Sample splitting and the bootstrap ensure that our test procedure is valid regardless of the specific class of algorithms, constraints, or utility functions chosen, subject to the regularity conditions given in our stated assumptions.
Sections (ref) and (ref) provide theoretical justifications for our procedure. Section (ref) establishes that our test is asymptotically valid and---whenever the selection rule satisfies a condition we call improvement convergence---it is also consistent. These results build on a bootstrap consistency lemma that we develop to handle two specific features of our setting: First, our test statistic is constructed using absolute values, and it is well-known that bootstrap consistency fails at points of non-differentiability fang2019inference; second, the fact that we impose very few restrictions on the selection rule means that the distribution of our test statistics may vary with the sample size and are not guaranteed to “settle down" in the limit. Since (to the best of our knowledge) generally available bootstrap consistency results do not cover our exact setting, we develop a new result building on the work of mammen2012does (see Appendix (ref) for details).
Section (ref) provides a game-theoretic framework to explain how our use of repeated sample-splitting leads to a test that is more robust to manipulation. We study a game between an analyst and a policymaker, where the policymaker chooses the statistical procedure, and the analyst chooses a number of times to repeat this procedure. The analyst then selects one $p$-value to report, which determines if the null hypothesis is rejected. We suppose that the analyst would like to reject the null even when it holds, and define a test to be more robust to manipulation than another if it leads to a lower probability of (incorrect) rejection under the null. We prove that aggregating $p$-values is indeed more robust to manipulation than using a single split. Although this microfoundation is particularly relevant in disparate impact testing, where the analyst may be incentivized to reject the null hypothesis even when it is true, our formal results hold for any valid test and thus apply more broadly.
Finally, to illustrate our proposed procedure, we revisit the data and setting of Obermeyer2019-te. The status quo algorithm is one used by a hospital to identify patients for automatic enrollment into a high-intensity care management program. Using our framework and test procedure, we reject the null hypothesis that it is not possible to simultaneously improve on the accuracy and the fairness of the algorithm, and we moreover quantify the extent of possible improvement. We find that large improvements in fairness are possible without compromising accuracy, while we are unable to establish that the reverse is true.
The econometric framework we develop in this paper is broadly applicable whenever a policymaker wants to examine whether it is possible to increase the fairness of a policy without sacrificing other objectives. However, we view our contribution as particularly relevant to regulators and other legal decision makers tasked with evaluating cases of alleged disparate impact under US federal law (see e.g., barocas2016big, and gillis2019big, and yang2020equal).\footnote{We focus on restrictions of private individuals (as opposed to government agents) from certain policies. As a general rule, discrimination is legally permissible by private actors except when specifically prohibited by law.} To keep this paper self-contained, we provide an independent summary of the relevant points here. We additionally contribute a brief review of Title VI of the Civil Rights Act of 1964, which is relevant for programs or activities that receive federal funding and covers our empirical application in Section (ref).
Although there is no singular discrimination law, a body of legislation, regulation, and court precedent prohibits discrimination against certain social groups (such as those defined by race, gender, or religion) called “protected classes” in settings as varied as employment, healthcare, education, and lending. US federal law generally distinguishes between two types of discrimination: disparate treatment and disparate impact. A policy has a disparate treatment if it intentionally offers different services based on an individual’s membership in a protected class. It has a disparate impact if one protected class is benefited or harmed more than another by the policy. Our paper pertains to disparate impact, which we broadly review first. Details and specific references to the US Code, the Code of Federal Regulations, and the Department of Justice's Guidelines are deferred to Appendix D.
A prototypical process for evaluating a disparate impact case has three parts. The first part is to determine whether the benefits or harms disproportionately affect members of a protected class. This is often called a “prima facie’’ case of discrimination. For this part of the process, there already exist well-established statistical frameworks hazelwood1977, shoben1978differential, groves1991, so we do not focus on it in our paper.
If the prima facie case is not successful, then the process ends and concludes that there is no disparate impact. If it is successful, then the second part of the process is to determine whether the challenged policy is a business necessity, i.e., necessary to achieve some legitimate nondiscriminatory interest. If the business necessity defense is not successful, then the process ends and concludes that the disparate impact is not permissible. If it is successful, then the third and final part of the process is to determine whether there exists a valid alternative that is less discriminatory, but still serves the same interests as the challenged policy. The policy is not permissible if such an alternative exists. Otherwise, it is. Our econometric framework is designed to assess this final part.
The exact implementation of this three-part process depends on the setting, and in particular on the specific statute, regulation, or court precedent prohibiting discrimination that is allegedly violated. For example, in the context of employment discrimination (which is prohibited by Title VII of the Civil Rights Act of 1964), the Equal Employment Opportunity Commission and/or private individuals can bring a lawsuit to court to remedy a disparate impact violation. In this setting, the three-part test is adversarial; that is, there are two opposing parties, where one party is responsible for the evidence and arguments supporting the policy, and the other party is responsible for the evidence and arguments against the policy. In contrast, in the context of discrimination by a program or activity that receives federal funding (which is prohibited by Title VI of the Civil Rights Act of 1964), investigation and enforcement instead falls on the funding agency alexander2001. Though the funding agency’s determination of disparate impact is not typically viewed as adversarial, the Department of Justice still recommends using the three-part test outlined above.\footnote{The Department of Justice is tasked with coordinating the implementation and enforcement of Title VI across federal agencies, by Executive Order 12250, 28 C.F.R. pt. 41, app. A. Their guidelines can be found in the Title VI Legal Manual available at \url{https://www.justice.gov/crt/fcs/T6manual}.}
Twenty-six funding agencies currently enforce Title VI in a variety of contexts such as education, healthcare, and transportation. In Section (ref), we apply our framework to study a potential disparate impact in access to hospital services. If the hospital receives federal funding from Medicare or Titles VI or XVI of the Public Health Service Act, this discrimination would be prohibited by Title VI of the Civil Rights Act of 1964. In this case, a likely enforcing agency would be the US Department of Health and Human Services (HHS).\footnote{Specific referrals of individual complaints to HHS can be found at \url{https://www.hhs.gov/civil-rights/for-individuals/index.html} and \url{https://www.cms.gov/about-cms/web-policies-important-links/accessibility-nondiscrimination-disabilities-notice}.} As hospitals and other healthcare providers increasingly use algorithms to allocate resources and determine patient care, we view our framework as one that could be used by HHS in order to evaluate allegations of discrimination under Title VI.
Our paper builds on the algorithmic fairness literature: see chouldechova2018frontiers, cowgill2020algorithmic, or barocas-hardt-narayanan for recent overviews.\footnote{Much of this literature is concerned with fair algorithm design. These papers typically build an explicit fairness constraint into the optimization problem, and ask how to find (or approximate) the optimum in a computationally efficient manner (e.g., dwork2012fairness, agarwal2018reductions, kusner2019making, dwork2018decoupled).} In particular, our paper is related to those papers that evaluate whether an algorithm with disparate impact can be justified by business necessity. For example, coston2021characterizing formulate an optimization problem to find the smallest attainable level of disparate impact over a given set of algorithms that satisfy an additional constraint on business necessity; viviano2023fair propose a policy learning procedure to select the fairest policy subject to a constraint on Pareto optimality of the resulting policy; BlattnerSpiess2023 use a sample-splitting approach (as we do) to find potential fairness and interpretability improvements in lending algorithms; and gillis2024operationalizing formulate a mixed integer optimization problem to find the least discriminatory linear classification model, with applications in consumer finance.
These papers focus on the computational, algorithmic and statistical aspects of how to identify an algorithm that improves on fairness, a problem that we abstract away from in our main text.\footnote{Appendix (ref) presents some novel formulations of optimization problems designed to find less discriminatory alternatives.} Indeed, any of the methods developed in this literature could be used within our proposed procedure as a means to search for candidate algorithms for fairness-improvement. Our focus is instead on the complementary problem of statistical inference. We view our main contribution as a general purpose blueprint, which allows an analyst to evaluate not just whether an alternative algorithm achieves a better performance on test data, but also whether the joint improvement on fairness and accuracy is statistically meaningful.
To do this, we formalize the property of fairness-improvability as a null hypothesis. We propose a test for this null, and show that (under suitable conditions) it is valid and consistent. Our test involves sample-splitting, an approach with a long history in statistics going back at least to the work of moran1973dividing and cox1975note. To mitigate the uncertainty introduced by sample splitting, we further recommend that the analyst performs repeated sample-splitting (as in meinshausen2009p, diciccio2020exact, wasserman2020universal, and ritzwoller2023reproducible, among others).
In Section (ref), we provide a theoretical argument that repeated sample-splitting makes our test more robust to potential manipulation by the analyst. This section is related to papers that draw conclusions about optimal research procedures based on models of a strategic researcher andrews2019identification,FrankelKasy,AndrewsShapiro2021,KitagawaVu2023,Spiess2024. In particular, our focus on selective reporting of a $p$-value is similar to the concern with $p$-hacking in jagadeesan2024publication and KasySpiess2024. Different from these papers, we focus specifically on the question of whether manipulation is reduced when $p$-values are aggregated over repeated sample splits. That is, our model does not broadly study the optimal statistical procedure, but rather provides a theoretical justification for the common use of repeated sample-splitting, which is not always justified by more standard econometric properties (e.g., power).
Finally, a closely related paper is the work of liu2024inference, which directly estimates the fairness-accuracy frontier developed by liang2022algorithmic. A full characterization of the frontier allows the analyst to answer a broad range of questions related to algorithmic fairness. In particular, once the fairness-accuracy frontier has been characterized, testing for the fairness-improvability of a status-quo algorithm amounts to testing whether or not the algorithm belongs to the frontier. While our approach focuses on the narrower question of testing for fairness-improvability (rather than characterizing the full frontier), it is more flexible in two ways---(1) it allows for definitions of accuracy and fairness with respect to different utility functions, and (2) it can automatically accommodate (almost) any exogenous constraint on the algorithm space.\footnote{The characterization of the frontier in liu2024inference is developed for the class of all possible algorithms, and (to the best of our knowledge) holds only under specific restrictions on the algorithm space, which rule out global constraints such as capacity constraints and monotonicity constraints.} Both of these features are often relevant for evaluating algorithms that are used in practice.
Consider a population of individuals, where each individual is described by a covariate vector $X$ taking values in the set $\mathcal{X} \subseteq \mathbb{R}^d$, a type $Y$ taking values in $\mathcal{Y} \subseteq \mathbb{R}$, and a group identity $G$ taking values in $\mathcal{G} = \{r,b\}$. The covariates in $X$ are the information that the algorithm can access to make a decision, the type $Y$ is a payoff-relevant unknown that the algorithm cannot directly access, and the group identity $G$ is a special covariate (which the algorithm may or may not access\footnote{The algorithm is given only $X$ as input, but we allow for the possibility that $G$ is an element of the vector $X$, or is perfectly correlated with covariates in $X$.}) that is used to evaluate the fairness of the algorithm. We use $P$ to denote the joint distribution of $(X,Y,G)$ across individuals. An algorithm $a : \mathcal{X} \rightarrow \mathcal{D}$ maps covariate vectors into $\mathcal{D}$, the set of possible decisions.\footnote{The map $a$ is often referred to as an assignment rule or policy in econometrics (where the objective of $a$ is usually to make treatment assignment decisions), and as a classifier or prediction rule in machine learning (where the objective of $a$ is typically to predict an unknown outcome). We use the more general term “algorithm” to encompass these possibilities and to evoke our motivating applications of algorithmic fairness.}
We evaluate algorithms from the perspectives of accuracy and fairness, which are defined with respect to an accuracy utility function $u_A: \mathcal{X} \times \mathcal{Y} \times \mathcal{D} \rightarrow \mathbb{R}_+$, and a (possibly identical) fairness utility function $u_F: \mathcal{X} \times \mathcal{Y} \times \mathcal{D} \rightarrow \mathbb{R}_+$. To ease exposition, we assume both utility functions are positive-valued.\footnote{This is inessential for our results, but permits an easier statement of Definition (ref), where we consider ratios of utilities.} We will consider accuracy and fairness criteria that can be formulated as
where $w_A$ and $w_F$ are (again positive-valued) normalization functions (see Examples (ref)-(ref) for possible specifications). Thus, $U_A^g$ and $U_F^g$ represent normalized expected utilities for group $g$ with respect to the accuracy and fairness utility functions, respectively. When the utility functions and normalization functions are common across accuracy and fairness, we drop the subscripts and simply write $U^g(a)$.
We say that one algorithm is more accurate than another if the value of $U_A^g$ is larger for both groups, and more fair if the value of $U^g_F$ differs less across groups.
We make some remarks on the formulations of accuracy and fairness below.
How $U^g_A$ and $U^g_F$ are defined is application-specific, and we list below example utility specifications from the prior literature (see e.g. Mitchelletal), dropping the fairness and accuracy subscripts to simplify notation. Although we refer to $U^g_A$ and $U^g_F$ as (expected) “utility” throughout, in many of these examples, what it quantifies has a unit, for example a probability of error or a dollar profit.\footnote{For this reason we do not view invariance to affine transformations as a necessary (or in some cases, desirable) property of our subsequent tests.}
For a fixed class of algorithms $\mathcal{A}$, the feasible accuracy and unfairness levels are those $(U_A^r, U_A^{b}, \vert U_F^r - U_F^{b}\vert)$ triples that can be achieved by some algorithm in $\mathcal{A}$. Our proposed testing procedure will be agnostic about the specific choice of $\mathcal{A}$, and in particular we will allow for $\mathcal{A}$ to be exogenously restricted in some way. We view this flexibility as important since (as discussed in the introduction) in practice there are often legal, logistical, or ethical constraints on which algorithms can be implemented.
There is a status quo algorithm $a_0: \mathcal{X} \rightarrow \mathcal D$ representing an algorithm that is already in use, or which has been proposed for use. The status quo algorithm $a_0$ has some level of disparate impact, $|U_F^r(a_0)- U_F^{b}(a_0)|$, which we assume throughout the paper is strictly positive.
This assumption reflects the basic motivation of our paper: If the status quo algorithm has no disparate impact (corresponding to $|U_F^r(a_0)- U_F^{b}(a_0)| = 0$), then there is no reason to look for fairness-improving alternatives. Supposing that Assumption (ref) holds, we ask whether it is possible to improve upon the disparate impact of the status quo algorithm without compromising on its accuracy. Formally, we extend Definition (ref) in the following way to quantify the extent of fairness- or accuracy-improvement.
That is, one algorithm $(\Delta_r, \Delta_b, \Delta_f)$-improves on another if its accuracy for group $r$ is at least $(1+\Delta_r)$ times as high, its accuracy for group $b$ is at least $(1+\Delta_b)$ times as high, and its disparate impact is no more than $(1-\Delta_f)$ times as high.\footnote{Analogous results to those presented in Sections (ref) and (ref) hold under a modification of Definition (ref), where we replace the ratios in this definition with differences.}
The special case of $\Delta_r=\Delta_b=\Delta_f=0$ corresponds to whether disparate impact can be reduced at all without compromising on accuracy, and we name it FA-dominance.
Some courts consider only whether discrimination can be reduced without compromising business necessity, while others examine the magnitude of potential reductions (see tobia2017disparate for a discussion of this topic in the context of Title VII workplace discrimination). The importance of magnitude is particularly emphasized in Title VI cases, where the Department of Justice's Title VI Legal Manual explicitly recommends consideration of whether the disparity is “large enough to matter” DOJTitleVI2024. Our more general Definition (ref) provides a framework that addresses both approaches: its use in our subsequent test allows us to systematically evaluate, based on observed data, both the existence and extent of feasible improvements.
We consider an analyst who does not know the joint distribution of $(X,Y,G)$, but instead observes a sample $\{(X_i,Y_i,G_i)\}_{i=1}^n$ consisting of $n$ independent and identically distributed observations from this distribution. The analyst's objective is to test $(\Delta_r,\Delta_b,\Delta_f)$-improvability of a status quo algorithm $a_0$ given such a sample. Formally, the analyst specifies a set of algorithms $\mathcal{A}$ and tests the null hypothesis
against the alternative that such an improvement exists. These parameters should be set to whatever values are relevant for the application (or varied over a range of relevant values, as in our subsequent application in Section (ref)); in a test of FA-dominance, the analyst chooses $(\Delta_r,\Delta_b,\Delta_f)=(0,0,0)$.
Section (ref) outlines the approach, Section (ref) provides details, and the subsequent Section (ref) establishes the validity and consistency of our procedure under stated assumptions.
The analyst first chooses a selection rule that maps samples into a choice of algorithm from $\mathcal{A}$, i.e., a mapping \[\rho: \mathcal{S} \rightarrow \mathcal{A}\] where $\mathcal{S} = \bigcup_{m \geq 1} \mathcal{S}_m \equiv \bigcup_{ m \geq 1} (\mathcal{X} \times \mathcal{Y} \times \mathcal{G})^m$ is the set of all finite samples of observations. Our results apply for any such rule subject to certain regularity conditions which we introduce in Section (ref).
In each round $k = 1, \dots, K$ of the procedure (where $K$ is a user-specified parameter), the analyst repeats the following steps:
1. Split the sample into train and test. The training sample $S_{train}^n$ includes $m_n = \lfloor \beta \cdot n \rfloor$ observations selected uniformly at random from $\{(X_i, Y_i,G_i)\}_{i=1}^n$, where $\beta \in (0,1)$ is a user-chosen fraction (we use $\beta=1/2$ in our application). The test sample $S_{test}^n$ consists of the remaining $\ell_n = n - m_n$ observations.
2. Find a candidate algorithm using the training sample. Apply the selection rule $\rho$ to the training sample $S_{train}^n$. To simplify notation, we use $\hat{a}^{\rho}_{1n}$ to denote the (realized) algorithm $\rho(S_{train}^n)$, which serves as a candidate algorithm in the subsequent step.
3. Test whether $\hat{a}^{\rho}_{1n}$ constitutes a $(\Delta_r,\Delta_b,\Delta_f)$-improvement relative to $a_0$. Given the status quo algorithm $a_0$ and the candidate algorithm $\hat{a}^{\rho}_{1n}$ obtained in the previous step, test the null hypothesis
using the test outlined in Section (ref) and the sample $S_{test}^n$. Let $p_k$ denote the $p$-value associated with this test (details below in Section (ref)).
4. Repeat steps 1-3 $K$ times, yielding a vector of $p$-values $(p_1, \dots, p_K)$.
5. Define $p_{\mathrm{med}}$ to be the median\footnote{An inspection of the proof of Corollary (ref) shows that the result holds for any standard definition of the median, but the formal definition of the corresponding test $\psi_n$ below fixes $p_{\rm med}$ to be the smallest such choice.} of the values $(p_1, \dots, p_K)$ and reject $H_0$ if and only if $p_{\mathrm{med}} < \alpha/2$. Our Corollary (ref) guarantees that under certain regularity conditions, this test is of level $\alpha$.
This proposed procedure is summarized in Figure (ref). When the null hypothesis is rejected, we conclude that the status quo algorithm $a_0$ is $(\Delta_r,\Delta_b,\Delta_f)$-improvable within the specified class of algorithms. This procedure does not identify a specific algorithm that achieves that improvement, but instead implies that the selection rule $\rho$ can find one. If the analyst has shown $(\Delta_r,\Delta_b,\Delta_f)$-improvability and requires a single algorithm to use as a substitute for the status quo algorithm, we recommend applying the selection rule $\rho$ to the entire dataset and using its output.
We now turn to supporting details and results for step 3 of our procedure.
In this section we propose a hypothesis testing procedure to evaluate whether a fixed algorithm $a_1\equiv \hat{a}^{\rho}_{1n}$ constitutes an improvement relative to the status quo algorithm $a_0$. Since $a_1$ was selected using the training sample $S_{train}$, it suffices to describe a test of $(\Delta_r, \Delta_b, \Delta_f)$-improvement for a fixed algorithm $a_1$ relative to $a_0$, using the test sample $S_{test}^n = \{(X_i,Y_i,G_i)\}_{i=1}^{\ell_n}$. Throughout we use $\ell_n = n - m_n$ to denote the size of the test sample. To that end, we test the null hypothesis
against the alternative \[H_1: A_{1r} > A_{0r}(1 + \Delta_r) \text{ AND } A_{1b} > A_{0b}(1 + \Delta_{b}) \text{ AND } |F_{1r} - F_{1b}| < |F_{0r} - F_{0b}| (1 - \Delta_f)~,\] for an arbitrary vector $\Delta \equiv (\Delta_r,\Delta_{b},\Delta_{f}) \in \mathbb{R}^3$, where \[(A_{0r},A_{0b},F_{0r},F_{0b}) \equiv (U_A^{r}(a_0),U_A^{b}(a_0), U_F^r(a_0), U_F^{b}(a_0))\] denotes the accuracy and fairness levels under the status quo algorithm $a_0$ and \[(A_{1r},A_{1b},F_{1r}, F_{1b}) \equiv (U_A^r(a_1),U_A^{b}(a_1),U_F^r(a_1), U_F^{b}(a_1))\] denotes the accuracy and fairness levels under the candidate algorithm $a_1$.
Since $H_0$ is formulated as a union of three conditions, a test of $H_0$ can be constructed by first constructing tests for each of the conditions individually, and then combining the individual tests using the intersection-union method.\footnote{See {casella2021statistical} for a textbook reference on the intersection-union method. Our Proposition (ref) in the appendix extends Theorems 8.3.23-24 in {casella2021statistical} to an asymptotic setting. } Specifically, we will construct tests for each of the individual conditions that make up $H_0$, and reject $H_0$ if all three tests reject at once.\footnote{We consider a test that is the union of three individual tests because it leads to a transparent test that is easy to interpret and analyze. In contrast, combining the three conditions that make up $H_0$ into one test directly would require us to make ex-ante arbitrary decisions about how to weight the different conditions, where it would be relatively difficult to understand how these weighting decisions affected the statistical properties of the test.}
First, we specify test statistics for each of the individual tests that make up $H_0$. To simplify the derivations, we introduce a slight change in notation. Let $Z_i = (X_i, Y_i, G_i)$ and define
where
The vector $\theta\in \mathbb{R}^J$ collects all of the unknown nuisance parameters $(\theta^A_{tg}, \theta^F_{tg})$ which appear as normalizations in the utility specifications. This re-writing allows for the accuracy and fairness criteria $A_{tg}$ and $F_{tg}$ to be expressed as unconditional expectations of the functions $u_{tg}$, rather than as ratios of the conditional expectations of $u_A$, $u_F$, $w_A$, $w_F$ (as defined in ((ref))). That is, $A_{tg} = E[u^A_{tg}(Z_i,\theta)]$ and $F_{tg} = E[u^F_{tg}(Z_i,\theta)]$.
In the results that follow, we will in fact allow $u^A_{tg}$ and $u^F_{tg}$ to depend on the nuisance parameter $\theta$ more generally than what is considered above (see specifically Assumption (ref)). Since $\theta$ is unknown, it will need to be estimated. We assume that $\theta$ can be written as $\theta = E[h_{i}]$ where $h_i = h(Y_i, G_i, X_i, a_{1}(X_i),a_{0}(X_i))$ for some known function $h: \mathcal{Y}\times G \times \mathcal{X} \times \mathcal{D}^{2} \to \mathbb{R}^{J}$.\footnote{This imposes few restrictions, and encompasses our four previous examples in Section (ref).} For instance, consider the following example based on the calibration utility in Example (ref).
We estimate $A_{tg}$, $F_{tg}$, and $\theta$ using their empirical analogs $\hat{A}_{tg} = \frac{1}{\ell_n}\sum_{i} u^A_{tg}(Z_i,\hat{\theta})$, $\hat{F}_{tg} = \frac{1}{\ell_n}\sum_{i}u^F_{tg}(Z_i,\hat{\theta})$ and $\hat{\theta} = \frac{1}{\ell_n}\sum_{i} h_i$. Our test statistics for the individual tests are then defined as follows. When testing whether $a_1$ is less accurate than $a_0$ for groups $r$ and $b$, let \[\hat{T}_{r,n} \equiv (\hat{A}_{1r} - (1 + \Delta_r)\hat{A}_{0r})~,\] \[\hat{T}_{b,n} \equiv (\hat{A}_{1b} - (1 + \Delta_b)\hat{A}_{0b}) ~.\] When testing whether $a_1$ is less fair than $a_0$, define \[\hat{T}_{f,n} \equiv \left(\big|\hat{F}_{1r} - \hat{F}_{1b}\big| - (1 - \Delta_f)\big|\hat{F}_{0r} - \hat{F}_{0b}\big|\right)\]
We propose using the nonparametric bootstrap to generate the critical values of our test, since this eliminates the need to compute standard errors on a case-by-case basis for each utility function. Specifically, if we fix $\alpha$ at some nominal level, then for the accuracy parts of the test, the rejection rule is given by $\phi_n^{(g)} = \mathbbm{1}\{\sqrt{\ell_n}\hat{T}_{g,n} > c^*_{g,1 - \alpha}\}$ for $g \in \{r,b\}$, where $c^*_{g,1 - \alpha} = \Psi_{g,n}^{-1}(1-\alpha)$ is the $(1 - \alpha)$-quantile of the bootstrap distribution $\Psi_{g,n}$ defined in Appendix (ref). For the fairness part of the test, the rejection rule is given by $\phi_n^{(f)} = \mathbbm{1}\{\sqrt{\ell_n}\hat{T}_{f,n} < c^*_{f,\alpha}\}$ where $c^*_{f,\alpha} = \Psi_{f,n}^{-1}(\alpha)$ is the $\alpha$-quantile of the bootstrap distribution $\Psi_{f,n}$ defined in Appendix (ref). Correspondingly, the $p$-value associated with the test $\phi_n^{(g)}$ is given by $1 - \Psi_{g,n}(\hat{T}_{g,n})$ and the $p$-value associated with the test $\phi_n^{(f)}$ is given by $\Psi_{f,n}(\hat{T}_{f,n})$. Our test of the null hypothesis (ref) is finally given by \[\phi_n(a_0, a_1) = \phi_n^{(r)}\cdot\phi_n^{(b)}\cdot\phi_n^{(f)},\] so we reject if and only if all three component tests reject. As a result, the $p$-value associated with the test $\phi_n$ is given by the maximum of the three $p$-values associated with each of the component tests.
The validity of our bootstrap procedure hinges crucially on the structure of our specific problem. Indeed, given the form of $\hat{T}_{f,n}$, it is well known that a standard nonparametric bootstrap fails to be consistent at points of non-differentiability fang2019inference. This does not affect the validity of our test for the following reason: Recall that the null is a union of three component null hypotheses. If the null holds because $A_{1g} \le A_{0g}(1+\Delta_g)$ for some $g \in \{r,b\}$, then (as we show in the proof of Theorem (ref)) it is not necessary for the fairness test $\phi_n^{(f)}$ to control size, since one of the other two tests will. Thus, the only region of the null space where the size of $\phi_n^{(f)}$ is relevant is in the region where \[\vert F_{1r} - F_{1b}\vert \geq \vert F_{0r} - F_{0b}\vert (1+\Delta_f)~.\] But Assumption (ref) implies that the RHS is strictly positive. Thus in this region of the null space, $\vert F_{1r} - F_{1b}\vert$ is strictly positive, and we are consequently bounded away from points of non-differentiability of $\hat{T}_{f,n}$.\footnote{Under the alternative, we prove consistency of the bootstrap under a mirrored assumption that the selection rule selects candidate algorithms which are not arbitrarily fair; we return to this point in the discussion following Theorem (ref).}
We now show that under certain regularity conditions the test proposed in Section (ref) is asymptotically valid when the candidate algorithm $a_1$ is selected using the data in $S^{n}_{train}$. We will also show that the test is consistent under an additional assumption on the selection rule $\rho(\cdot)$ which we call improvement convergence.
First consider $K=1$, i.e., there is only one round of sample-splitting. Let $(S_{train}^n,S_{test}^n)$ denote the realized split of training and testing samples of the data $\{(X_i, Y_i, G_i)\}_{i=1}^n$. Denote the candidate algorithm selected using rule $\rho(\cdot)$ on the training sample $S_{train}^n$ as \[\hat{a}^\rho_{1n} \equiv \rho(S_{train}^n).\] We show that the test $\phi_n(a_0, \hat{a}^\rho_{1n})$ (as defined in Section (ref)) is asymptotically valid. Our result holds under the following regularity conditions restricting the distribution $P$ and class of algorithms $\mathcal{A}$.
Assumption (ref) allows us to appropriately linearize the utility functions as a function of $\theta$, uniformly over the parameter space $\Theta$. The uniformity of the linearization is important since the true value of the nuisance parameter can fluctuate as a function of sample size. The boundedness conditions in Assumption (ref) impose implicit constraints on the parameter space $\Theta$ and the support of the data. For instance, revisiting Example (ref), we see that the support of $Y_i$ should be bounded, and that each component of $\theta$ should be bounded away from zero. Assumption (ref) ensures that the limiting variances of our test statistics are non-degenerate uniformly in the space of candidate algorithms $\mathcal{A}$. Once again, this uniform non-degeneracy is important because the candidate algorithm is allowed to vary arbitrarily as a function of sample size. Low-level conditions which guarantee Assumption (ref) are difficult to articulate at this level of generality, but Assumption (ref) intuitively requires that the variances of the utilities be bounded away from zero uniformly in the space of candidate algorithms, and that the correlation in the utilities between the status-quo and candidate algorithms be bounded away from one. We expect these conditions to be satisfied for most selection rules used in practice.\footnote{Note that, more precisely, we in fact only require Assumption (ref) to hold for the set of algorithms $\mathcal{A}' \subseteq \mathcal{A}$ which can be realized by the selection rule $\rho(\cdot)$.}
Theorem (ref) establishes that the test $\phi_n$ is asymptotically of level $\alpha$ regardless of the choice of algorithms $\hat{a}^\rho_{1n}$, as long as the nuisance parameters and utilities are well-behaved over the class $\mathcal{A}$ as described in Assumptions (ref), (ref) and (ref).
We recommend combining the test results over multiple splits of the data to reduce the unpredictability in the procedure induced by sample splitting (see Section (ref) for a theoretical justification). Formally, consider $K>1$ and let $(S_{train}^{n,k},S_{test}^{n,k})$ denote the realized split of training and testing samples in the $k$-th round of sample splitting. Further let \[\hat{a}^\rho_{1nk} \equiv \rho(S_{train}^{n,k})\] denote the candidate algorithm selected using rule $\rho$ on the training sample $S_{train}^{n,k}$. Define the test statistic $\psi_n = \mathbbm{1}\left\{\frac{1}{K}\sum_{k = 1}^K \phi_{n,k}(a_0,\hat{a}^\rho_{1nk}) \ge 1/2\right\}$ to reject if the median test statistic (across the rounds of sample splitting) rejects. We establish the following corollary of Theorem (ref):
Note that, as a consequence of Corollary (ref), to ensure that the test $\psi_n$ is asymptotically of level $\alpha$ we require that the component tests $\phi_{n,k}$ for $k = 1, \ldots, K$ are of level $\alpha/2$. Equivalently, we reject the null if the median $p$-value (across the rounds of sample splitting) satisfies $p_{\mathrm{med}} < \alpha/2$. We would in general expect this conservativeness to result in a loss of power relative to a test performed using a single split, but the local power analysis conducted in diciccio2020exact suggests that this may not always be the case if the alternative is not too close to the null. In particular, their Theorem 3.1 demonstrates this for a one-sided test of the mean, which is similar to the component nulls in (ref).
Finally, we establish the consistency of the test $\phi_{n}(a_0, \hat{a}^\rho_{1n})$ under high-level conditions on the behavior of the selection rule $\rho$.
In words, improvement convergence says that whenever the algorithm $a_0$ is $(\Delta_r,\Delta_b,\Delta_f)$-improvable in $\mathcal{A}$, the selection rule $\rho$ is guaranteed to find such an improvement given enough data. Theorem (ref) establishes that the test $\phi_n$ is consistent (that is, has power approaching one for any distribution in the set of alternatives) when the selection rule $\rho$ is improvement-convergent.
This result assumes that the selection rule $\rho$ does not select a candidate algorithm that is arbitrarily fair, even asymptotically. This is related to our discussion at the end of Section (ref): if the algorithms chosen by the selection rule converge to perfect fairness, then our bootstrap procedure is no longer consistent, and our proof strategy does not establish consistency of our test in this case. However, we emphasize that bootstrap consistency is not a necessary condition for our test to have reasonable power, and we demonstrate via simulation in Appendix (ref) that our test displays reasonable power even when employing candidate algorithms that are perfectly fair.
We expect that, for many datasets, it will be possible to reject the null using a naive selection rule that does not satisfy improvement convergence, as is the case in our empirical illustration in Section (ref). However, Theorem (ref) guarantees that the null will be asymptotically rejected (in cases where it should be) when the selection rule satisfies this property. Many of the methods developed in the literature on identifying less discriminatory algorithms (as reviewed in Section (ref)) are improvement-convergent for specific utility specifications and algorithm classes. In Appendix (ref) we propose selection rules constructed using mixed integer linear programs, which we conjecture are improvement-convergent when $\mathcal{A}$ is the set of linear classifiers.
Our recommended approach is to compute the median $p$-value across $K>1$ repeated sample splits and to reject when this $p$-value is less than $\alpha/2$ (where $\alpha$ is the level of the test). One could alternatively conduct a single sample-split and reject if the resulting $p$-value is less than $\alpha$. As our Theorem (ref) and Corollary (ref) demonstrate, both procedures are valid, and we generally expect that the use of a single split should lead to a less conservative test. However, because the resulting $p$-value can vary substantially across different splits, relying on a single train-test split introduces arbitrariness---what meinshausen2009p term the `$p$-value lottery.' This sensitivity to the sample split introduces the possibility of manipulation. As ritzwoller2023reproducible note: “Researchers are incentivized to report significant results. If there is scope to materially alter the statistics that they report through the choice of the split of their sample, should this choice be left to chance?” This concern is particularly relevant to disparate impact claims, where complainants may have incentives to find fairness violations even when they do not exist.
In this section, we thus formalize the intuition that repeated sample-splitting provides stronger safeguards against manipulation than single splits, thereby providing a theoretical justification for this methodological choice. Our microfoundation is a game between a policymaker who sets the statistical procedure and an analyst who can (secretly) repeat the procedure multiple times. Within this framework, we define what it means for a test to be robust to manipulation. Section (ref) presents this model, and Section (ref) proves that repeated sample-splitting is more robust to manipulation than single train-test splits. While our motivation comes from disparate impact testing, these results apply to any valid test, making them relevant beyond our specific setting.
Suppose a firm's algorithm is the subject of a potential disparate impact case. We consider a game between two players: an analyst auditing the firm and a policymaker. There is a fixed statistical test of exact size $\alpha \in (0,1)$, which produces a $p$-value from any given train and test split. The policymaker chooses between two procedures $s_1$ and $s_2$ based on this test. The first corresponds to a single train-test split, where the null of no fairness-improvability is rejected if the resulting $p$-value is less than $\alpha$. The second corresponds to $K$ train-test splits, where the null is rejected if the median $p$-value across these splits is less than $\alpha/2$ (i.e., our proposed method). The analyst observes which procedure is chosen, and repeats that procedure $m \in \mathbb{Z}_+$ times at a cost of $c_1(m)$ for procedure 1 or $c_2(m)$ for procedure 2, where $c_1$ and $c_2$ are increasing and weakly convex functions. (For example, the specifications $c_1(m) = \gamma m$ and $c_2(m) = \gamma K m$ would give the analyst a constant cost $\gamma$ for each train-test split.) The analyst reports the $p$-value from one of these repetitions, and this reported $p$-value determines whether the null is rejected. Crucially, we suppose that the hypothesis test is interpreted as if $m=1$, which is the standard convention.\footnote{This distinguishes our model from related works such as Henry2009, FelgenhauerLoerke, HenryOttaviani, and Herresthal2022, in which an agent gathers information through hidden testing or experimentation, and subsequently chooses whether to disclose his findings. In those papers, the principal or sender (the equivalent of our “policymaker”) updates his beliefs about an unknown payoff-relevant state given the agent's report and equilibrium strategy. In our model, payoffs are instead directly determined by whether the null is rejected at the reported $p$-value.}
We are interested in settings where the analyst would like to conclude that the algorithm is fairness-improvable even when it is not. With this kind of manipulation in mind, we condition on the state of the world in which the null hypothesis holds. The analyst's payoff is $1-c_i(m)$ if the null is rejected under procedure $s_i$ and $-c_i(m)$ otherwise, while the policymaker's payoff is 0 if the null is rejected and 1 otherwise.
To summarize the timeline:
We consider subgame-perfect equilibria.
To simplify notation, it will be useful to couple the realizations of the $p$-values under the two tests in the following way: For each repetition $i$ of the second statistical test, let $(p_i^1, \dots, p_i^K)$ denote the random $p$-values across the $K$ iterations of train-test. For each repetition $i$ of the first statistical test, let $p_i^1$ be the $p$-value in the single train-test split. Further define $\phi_{ik}^\alpha=\mathbbm{1}(p_i^k < \alpha)$ to be an indicator for whether the $p$-value from the $(i,k)$-th train-test split leads to rejection at an $\alpha$ significance level. By assumption that the statistical test for each train-test split has exact size, each random variable $\phi_{ik}^\alpha$ is Bernoulli with parameter $\alpha$.
Equilibrium actions and payoffs can be determined by backwards induction. In period 2, the analyst solves
if procedure $s_1$ was chosen, or \[\max_{m \in \mathbb{Z}_+} \left[P\left(\max_{1\leq i \leq m } \mathbbm{1}\left(\frac1K \sum_{k=1}^K \phi_{ik}^{\alpha/2}\geq \frac12 \right)=1\right) - c_2(m)\right]\] if procedure $s_2$ was chosen. Let $m_1^*$ and $m_2^*$ respectively denote the solutions to these two problems (breaking ties in favor of the smallest number of repetitions). Then in period 1, the policymaker's expected payoffs from the two procedures are \[u_P(s) = \left\{
\right.\]
We define robustness to manipulation as follows.
That is, $s_i$ is more robust to manipulation than $s_j$ if the policymaker's expected payoff from choosing $s_i$ is strictly higher. Equivalently, the probability that the null is incorrectly rejected---given the analyst's endogenous choice of how many times to re-run the procedure---is higher under $s_i$ than $s_j$. Finally, note that when $s_i$ is more robust to manipulation than $s_j$, then the policymaker chooses $s_i$ in every equilibrium.
Our main result in this section is that when $K$ is sufficiently large, then procedure $s_2$ (repeated sample-splitting) is more robust to manipulation than $s_1$ (a single train-test split) under the following assumption.
This assumption lower bounds the probability that the second repetition of $s_1$ yields a different outcome from the first. It implies that the marginal benefit of the second repetition is higher than its marginal cost, and thus ensures that the analyst will repeat the first procedure at least once. This assumption is satisfied so long as tests are not perfectly correlated, and the cost of the second repetition is not too large. (For example, if $c_1(m) = \gamma m$ is linear, then the bound can be restated as $\gamma < (1-\alpha) P(\phi_{21}^\alpha = 1 \mid \phi_{11}^\alpha = 0)$.)
The proof of this result proceeds in two parts. First, we show that
for every $m$, and moreover the inequality holds strictly for every $m>1$ (where Assumption (ref) guarantees that the analyst's solution satisfies $m_1^*>1$). This is extremely intuitive, and says that the probability of rejecting the null given $m>1$ repetitions of the first procedure is larger than with just one. (The only way it could be otherwise is if the test was perfectly correlated across repetitions, which Assumption (ref) rules out.)
The other half of the proof demonstrates that for $K$ sufficiently large
for every $m$ not too large (including $m=m_2^*$). Intuitively, for every fixed repetition $i$, the sample average $\frac1K \sum_{k=1}^K \phi^{\alpha/2}_{ik}$ approaches $P(\phi_{ik}^{\alpha/2}=1)$ as $K$ grows large. So when the probability of rejection in any single $(i,k)$ train-test split is small, it is unlikely that the test is rejected in more than half of the $K$ iterations, and thus unlikely that the median test statistic rejects. This intuition is straightforwardly formalized when the tests $\phi^{\alpha/2}_{ik}$ are i.i.d, but more care is required in our setting where $\phi^{\alpha/2}_{ik}$ are instead positively correlated. The key observation is that the tests $\phi^{\alpha/2}_{ik}$ are exchangeable, and thus (by de Finetti's theorem) the tests $\phi^{\alpha/2}_{ik}$ are i.i.d Bernoulli($q$) conditional on the realization of the random Bernoulli parameter $q$. What this means is that for each realization of $q$, we can apply the strong law of large numbers to conclude that the sample average $\frac1K \sum_{k=1}^K \phi^{\alpha/2}_{ik}$ approaches $q$. As $K$ grows large, the ex-ante probability that half of these tests reject is then simply the probability that $q\geq 1/2$, which we show is no more than $\alpha$.
These arguments formalize the intuitive sense in which it is easier to manipulate a test that depends only on one repetition of a procedure (in which case the analyst only needs to get lucky once), than a test which aggregates outcomes across many repetitions of that procedure. Our result does not use any properties of the test $\phi^{\alpha/2}_{ik}$ beyond having exact size and that the set of tests $\{\phi^{\alpha/2}_{ik}: 1 \le k \le K\}$ are exchangeable, and thus extends more broadly to many testing procedures which employ sample splitting.
Assumption (ref) is made for convenience, but is not critical for our qualitative conclusion. Specifically, if instead the policymaker optimally runs the first procedure only once (i.e., $m_1^*=1$), then our assumption that the test has exact size implies $P\left(\phi_{11}^\alpha = 1\right) = \alpha$. Moreover, our proof of Theorem (ref) shows that for every $\varepsilon$, there is a $\overline{K}$ sufficiently large such that \[P\left(\max_{1\leq i \leq m_2^* } \mathbbm{1}\left(\frac1K \sum_{k=1}^K \phi_{ik}^{\alpha/2}\geq \frac12 \right)=1\right) \leq \alpha + \varepsilon\] for every $K > \overline{K}$. Thus when Assumption (ref) fails, then for large $K$ either the policymaker prefers the second procedure (reproducing our original result) or the policymaker is approximately indifferent between the two procedures. In fact, we expect that our original result can be extended to cover the case when Assumption (ref) fails, but do not pursue it here.
Finally, although an explicit bound for $K$ is not possible without stronger assumptions, it is instructive to consider the edge case of i.i.d $p$-values. This i.i.d benchmark is independently interesting because the analyst's incentives for repeating the test are higher than in our setting of positively correlated $p$-values.\footnote{For example, consider the probability of rejecting the null under $m$ repetitions of the first procedure. By de Finetti's theorem, $P(\max_{1\leq i \leq m} \phi_{i1}^\alpha = 1)=1-\int_{q \in [0,1]} (1-q)^m d\mu(q)$ for some measure $\mu$, where $\mathbb{E}_\mu(q)=\alpha$. And by Jensen's inequality, $1-\int_{q \in [0,1]} (1-q)^m d\mu(q) \leq 1 - (1-\mathbb{E}_\mu(q))^m = 1-(1-\alpha)^m$, where $1-(1-\alpha)^m$ is the probability of rejecting when the $p$-values are instead i.i.d. Thus for every $m$, the probability of (incorrectly) rejecting the null is higher given i.i.d $p$-values than positively correlated ones. See the proofs of Theorem (ref) and Proposition (ref) for more detail.} Within this “maximal incentive for manipulation” benchmark, we can strengthen our previous result to the following.
This bound on $K$ is extremely undemanding. For example, when $\alpha=0.05$, the result holds for any $K \geq 7$.
We conclude by illustrating our approach in the setting of Obermeyer2019-te. The status quo algorithm is a commercial healthcare algorithm used by a large academic hospital to identify patients to target for a high-risk care management program. The algorithm assigns to each patient a risk score, and identifies those patients with risk scores above the 97th percentile for automatic enrollment in the program. We use our proposed approach to evaluate the improvability of the hospital's algorithm, finding that it is strictly FA-dominated within the class of linear classifiers. We further quantify the size of possible improvements by testing the null hypotheses that the hospital's algorithm is not $(\delta_a,\delta_a,\delta_f)$-improvable for different values of $\delta_a$ and $\delta_f$. We find that large improvements in fairness are possible without compromising on accuracy, while we are unable to establish that the reverse is true.
The data includes observations from 48,784 patients, among which 43,202 self-report as White and 5,582 self-report as Black. Following Obermeyer2019-te, we take these to be the two group identities, denoted $g \in \{w,b\}$. Each patient $i$'s covariate vector $X_i \in \mathcal{X}$ includes 8 demographic variables (e.g., age and gender), 34 comorbidity variables (indicators of specific chronic illnesses), 13 cost variables (claimed cost broken down by type of cost), and 94 biomarker and medication variables. Although group identity $g$ is known for each patient in the dataset, the status quo algorithm omits this variable for prediction, so we do as well. Finally, the data set reports each patient $i$'s total number of active chronic illnesses in the subsequent year, which is interpreted as a measure of the patient's true health needs.\footnote{ In principle, enrollment into the high-risk care management program may affect the outcome variable $Y$. Although we expect that a single year of enrollment in this program will have only minor effects on the patients' number of chronic illnesses (which $Y$ measures), we conduct a robustness check in Appendix (ref) in which we repeat our main analysis using the total number of active chronic illnesses in the same year as the enrollment decision. All results are qualitatively similar. } We take this to be the patient's type $Y_i \in \mathcal{Y}$.
An algorithm assigns each patient a decision $D_i \in \{0,1\}$ based on the covariate vector $X_i$, where 1 corresponds to automatic enrollment into the care management program. We respect the capacity constraint of the status quo algorithm by restricting attention to algorithms that select 3% of the population for automatic enrollment in expectation.
Following Obermeyer2019-te, we evaluate both accuracy and fairness using the calibration utility function introduced in Example (ref), i.e.
and \[\vert U^b(a) - U^w(a) \vert = \vert E[Y \mid a(X)=1, G=b] - E[Y \mid a(X)=1, G=w] \vert.\]
That is, an algorithm is more accurate if the expected number of health conditions is higher among both Black and White patients assigned to the program. It is more fair if it reduces the disparity in the expected number of health conditions among Black and White patients assigned to the program.\footnote{Here and throughout, we drop the notational distinction between $U_A^g$ and $U_F^g$, as they are identical in this example.}
We implement our proposed approach in Section (ref) to test the fairness- and accuracy- improvability of the hospital's algorithm. We use $K=7$ iterations and select a $\beta=1/2$ fraction of the data to use for training. The hospital's algorithm provides each patient with a risk score. To enroll patients to treatment according to the status quo algorithm, we first designate the $97$th percentile of the risk score distribution in the training data as our admittance threshold. Then, in the testing data, we automatically enroll ($D=1$) those patients whose risk score is above this threshold. Our candidate algorithms similarly assign risk scores to patients, and enroll those patients whose risk scores are above the $97$th percentile threshold computed in the training data, but use different risk score calculations compared to the status quo algorithm.
Specifically, to identify candidate algorithms, we first use the training data to compute an alternative risk score assignment rule $\hat{f}:\mathcal{X} \rightarrow \mathcal{Y}$, which maps each covariate vector into a predicted number of health conditions. We then set the 97th percentile of the computed risk scores $\hat{f}$ from the training data as our admittance threshold. Next, we compute the risk scores for all of the patients in the test data, and select those patients whose risk score is above the threshold.
We consider several different methods for selecting a function $\hat{f}$---as the output of a linear regression, a lasso regression, and a random forest algorithm---but find that all of these yield similar results.\footnote{The regularization parameter for LASSO is determined using 5-fold cross-validation. For random forest, we utilize a configuration of 300 trees with other hyperparameters set to their default values as specified in scikit-learn version 1.4.1. } Figure (ref) plots the average value of the utilities $U^w$ and $U^b$ (across the iterations of our procedure) under the status quo algorithm, as well as the average values for these utilities given candidate algorithms identified by each of the three methods mentioned above. This figure suggests that the candidate algorithms succeed in improving not only accuracy (each of $U^w$ and $U^b$ increase) but also fairness ($\vert U^w - U^b\vert$ decreases).
We subsequently report findings for the random forest algorithm only, deferring the (nearly identical) results for the other algorithms to Appendix (ref). Table (ref) complements Figure (ref) by reporting the $p$-values that emerge from our statistical test of the null hypothesis that the status quo algorithm is not strictly FA-dominated. Across the iterations of our procedure, the median $p$-value is $0.0001$; thus, we reject the null at the 5% significance level. (Recall that we reject at a $5\%$ significance level if the median $p$-value is less than $0.025$.) Were the hospital to defend the disparate impact of its algorithm on account of the accuracy goal in ((ref)), a federal funding agency could reject this business necessity claim with strong statistical guarantees. This finding reinforces the bottom-line takeaway from Obermeyer2019-te.\footnote{Obermeyer2019-te find that training an algorithm to predict health needs (instead of health costs, as the status quo algorithm does) leads to a more equal proportion of Black and White patients among those who are identified for automatic enrollment.}
We further explore the size of achievable improvements in accuracy and fairness by testing for $(\delta_a,\delta_a,\delta_f)$-improvability across different values of $\delta_a$ and $\delta_f$. Since our primary interest is achievable reductions in disparate impact, we restrict consideration to positive values of $\delta_f$. However we allow $\delta_a$ to take either sign: positive values of $\delta_a$ correspond to a test of whether the improvement in fairness can be achieved simultaneously to an improvement in accuracy (by at least $\delta_a$ percent), and negative values of $\delta_a$ correspond to a test of whether the improvement in fairness can be achieved by reducing accuracy (by no more than $\vert\delta_a\vert$ percent).
Figure (ref) presents $p$-values for these tests, and in particular emphasizes the 0.025 $p$-value contour, which corresponds to the conventional 5% significance level. This contour lies above $\delta_a=0$ for all $\delta_f \leq 0.64$, meaning that even with a demanding fairness-improvement standard---namely, a 64% reduction in disparate impact---it is possible to maintain, and in fact improve, accuracy for all groups. In the other direction, the contour lies above $\delta_f = 0$ only for $\delta_a \leq 0.09$, indicating that we can reject the null hypothesis when testing for accuracy improvements of up to 9% while maintaining fairness, but not beyond this level.
Finally, while we illustrated our proposed technique using the calibration utility function in ((ref)), the same analysis is possible using other definitions of accuracy and fairness. Appendix (ref) reproduces Figure (ref) for an alternative definition of accuracy that measures expected health care costs (leaving the fairness definition unchanged). That is, an algorithm improves on another if among those patients who are automatically enrolled, the disparity in the expected number of health conditions among Black and White patients is smaller, and moreover, the expected health costs are higher for both Black and White patients. For this specification, we find that we cannot reject the null hypothesis that the hospital's algorithm is FA-dominated.
When a commercial algorithm has a disparate impact, it is important to understand whether it is possible to reduce that disparate impact without compromising on other business-relevant criteria, or if this level of disparate impact is necessitated by those other goals. We have designed a statistical approach to assess this, with three practical objectives in mind. First, since the appropriate definitions of disparate impact and business-relevant criteria vary substantially across applications, we want our framework to be flexible enough to accommodate any such definitions that may emerge in practice. Second, since there are often exogenous constraints on the algorithm space, we want our procedure to apply universally across algorithm classes. Finally, we would like for the approach to be transparent and simple to use for practitioners. The statistical framework that we propose delivers on these three counts.
The main drawback of our approach is its dependence on a selection rule for choosing a candidate algorithm. When we are able to reject the null, as in our application, then the optimality properties of the selection rule (in particular, whether it satisfies improvement convergence as defined in Section (ref)) do not matter. That is, no matter how naive or heuristic our selection rule is, we can conclude that the status quo algorithm is improvable. But when our test does not allow us to reject the null, there is in general an ambiguity: It may be that there is not sufficient evidence in the data to conclude existence of an improving algorithm; or, alternatively, it may be that the selection rule is not powerful enough to find this algorithm. In the latter case, re-running the same test with a different selection rule could lead us to reject the null. This ambiguity is resolved asymptotically when the selection rule is improvement-convergent, since Theorem (ref) establishes that our proposed test is consistent under this condition. One interesting direction for future work is thus to provide sufficient conditions for a selection rule to be improvement-convergent in different applications.