The Search for Less Discriminatory Algorithms: Limits and Opportunities

Most scholarship on algorithmic discrimination over the past decade has focused on disparate impact doctrine, which allows plaintiffs to challenge facially neutral policies that nevertheless have an unjustified or avoidable disparate impact on legally protected groups. Disparate impact cases are initiated by a plaintiff who puts forward evidence that the decision-making process at issue has resulted in a disparate impact along the lines of a legally protected characteristic (e.g., race, gender, age, etc.). For example, a loan applicant must first demonstrate that there is a disparity in the approval rate for applicants according to their gender. The defendant can then put forward what is known as a “business necessity defense,” where they claim that the observed disparities are required to meet some legitimate business goal — for example, that a lender’s credit scoring model predicts default to some reasonable degree of accuracy. Finally, the plaintiff can rebut the firm’s justification by pointing to what is commonly known as a less discriminatory alternative: an alternative decision-making process that would serve the firm’s goals equally well, but with less disparate impact. If a rejected credit applicant can furnish a credit scoring model of equivalent accuracy that has a smaller gap in selection rates across gender groups, then the firm can be found liable for discrimination.

The final step in disparate impact doctrine and the notion of a less discriminatory algorithm (LDA) has attracted significant scholarly attention in recent years, as research suggests that there may be readily available less discriminatory alternatives to existing algorithms used in many contexts. One idea in particular that is attracting growing interest in both the technical and legal communities is the phenomenon of model multiplicity: it is often possible to develop many different models that all exhibit the same accuracy but make quite different predictions on individual points (i.e., a specific person) and groups of points (i.e., specific groups of people) (pmlr-v119-marx20a; black2022model). Two models might be equally accurate, but make opposite predictions for a specific person. Likewise, the first model might select members from one group more than members of another group, while the second model might select members from both groups at a similar rate, even though both models are equally accurate. Multiplicity therefore suggests that there is not always an inevitable trade-off between accuracy and fairness. Instead, practitioners will often be able to develop a large set of equally accurate models and then choose among these the one that happens to have less disparate impact across groups.

Model multiplicity speaks directly to the question of less discriminatory alternatives because it tells us that there will often be many equally accurate ways to select individuals based on some outcome of interest (e.g., loan default), some of which will have more of a disparate impact than others. In legal proceedings, less discriminatory alternatives are generally understood to serve as evidence of an avoidable disparate impact — and thus of illegal discrimination — and the burden for identifying them is today commonly thought to rest with the plaintiff (black2023less). Identifying a less discriminatory alternative is mainly a means for a plaintiff to hold a firm accountable for its past discrimination — that is, for the avoidable adverse impact already experienced by the plaintiff. But there is also growing belief that the phenomenon of multiplicity justifies placing the burden of searching for less discriminatory alternatives on firms themselves.¹¹1Plaintiffs also generally lack the necessary information to be able to recognize when firms’ practices are producing a disparate impact, let along the necessary information, expertise, and resources to identify a less discriminatory alternative that would actually serve firms’ goals equally well. Given the fact of multiplicity, there is no reason to simply accept an algorithm that has a disparate impact without first asking whether a firm has attempted to find a less discriminatory alternative (black2022model). Unless a firm has specifically taken disparate impact into account while developing its algorithms, it is extremely unlikely to land on the least discriminatory means of achieving its goals (black2023less). Thus, a failure to even attempt to identify alternatives can be treated as a decision to accept an avoidable — and thus unjustified — disparate impact. Multiplicity thus puts pressure on firms to proactively test for disparate impact and, if found, to explore whether they can identify a less discriminatory means of achieving their goal equally well. This move positions LDAs as a way to prevent avoidable disparate impacts from occurring in the first place, not simply a way to establish that they have occurred in the past.

Legal scholars and computer scientists have worked together to capitalize on the promise of multiplicity for dealing with algorithmic discrimination, exploring the full implications of multiplicity for disparate impact doctrine (black2023less) and proposing specific techniques for finding the least discriminatory alternative (gillis2024operationalizing). Civil society organizations have likewise sought to leverage this insight, calling on firms to take affirmative steps to find less discriminatory alternatives when developing their decision-making algorithms and asking regulatory agencies to clarify their expectations of regulated firms (NCRC_2022; consumerfed2024; NFHA2024). And a range of federal and state regulators have now issued statements instructing firms to search for less discriminatory alternatives while developing algorithms (cfpb2024; HUD2024; NYS2024).

Despite this apparent enthusiasm, there remains considerable uncertainty around how much can be achieved by exploiting multiplicity and how easily this can be achieved (pace2023fools). Even the scholarship championing multiplicity recognized that it is generally not possible to find the least discriminatory possible algorithm (scherer2019applying) and that the process of finding LDAs in practice is not always self-evident and may require non-trivial effort and resources (black2023less).

Attempts to operationalize or automate the search for an LDA must grapple with fundamental questions about disparate impact law: what is the purpose of the LDA and what are the appropriate way(s) it may be used or invoked? One view, for instance, might hold the LDA as a piece of evidence to be used by a plaintiff in court for establishing past discriminatory treatment. An alternative view holds the LDA search as a proactive, forward-looking process that can allow decision-makers to arrive at better policies for future populations of decision subjects. Depending on the use and meaning ascribed to the LDA, courts might apply different standards and burdens on those who search for them. Our findings suggest that, whether the LDA is held as evidence or as a proactive process for improving decision policies, there exist fundamental challenges to finding an LDA that has generalizable, improved fairness and performance properties. Best-practices informed by these challenges, however, can yield LDA searches that are reasonable and effective.

In this paper, we attempt to provide a more precise technical characterization of the limits of LDAs and we explore what these limits might mean for the law and for the practice of searching for LDAs. In so doing, we attempt to provide greater clarity about what might be reasonably expected of firms in light of multiplicity. This paper is organized by a slate of fundamental (negative) results, summarized below, which each represent limits to searching for and using LDAs.

1. [nolistsep]

2. (1)

   Statistical Limits (Section 3): Firms often design algorithms before accessing all relevant information about the particular population subjected to an algorithm, so higher performance on a fixed dataset may not mean there’s an LDA that generalizes to new populations.

3. (2)

   Mathematical Limits (Section 2): We show that there are bounds on how much one can close the gap in selection rates between groups at a certain levels of accuracy, given the size of each group and the base rate of the property or outcome of interest in each group. We further show that given the full joint distribution of data, group and outcome (X,G,Y) and an initial classifier, determining whether an LDA exists is computationally intractable in general (i.e., NP-complete).

4. (3)

   Welfare Limits (Section 4): We observe that LDAs’ narrow focus on the welfare of firms (i.e., whether they can achieve their goals equally well) fails to account for the fact that certain LDAs might leave consumers strictly worse off, even if they narrow disparities in selection rates across groups.

Each of these results might seem to provide firms with reasons to reject calls to search for LDAs or with arguments to defend themselves in a disparate impact case. However, these claims only tell part of the story. For each of our negative results limiting what is attainable in this setting, we offer positive results demonstrating that there exist effective and low-cost strategies that are remarkably powerful, if not perfect. These strategies enable firms to reliably unearth less discriminatory models that generalize to new populations, even with very simple search methods. In Section 5, we provide results from empirical tests of a particular group of methods that randomly generate alternative models in the same model class. In some observed instances, we find that these methods can reduce disparity out-of-sample, sometimes at no cost to utility.

As discussed in the prior section, in most cases, a firm can only access a single, finite dataset. This implies that conclusions about disparate impact must arise from information contained in a realized sample of data—even when we hope these conclusions hold more generally. Setting aside the statistical challenge of drawing generalizable conclusions about disparity out-of-sample, here we limit our analysis to what is attainable on already realized data or fully-known distributions. In other words, even when we remove from consideration the statistical challenges, we find certain fundamental limits and challenges still remain.

In this section, we reason about the bounds of what is mathematically possible or impossible for an LDA search process to achieve. Our strategy is as follows: By strictly expanding the information the policy designer can access, if we can show a certain algorithm or strategy is impossible or complex, then we know such shortcomings hold in the (strictly more challenging) case where the firm accesses less information.

A natural starting question one might ask in this setting is, what accuracy and fairness measures are (im)possible to jointly achieve in the fixed sample? In other words, assuming we have access to group belonging, labels, and outcome information $Y$, what can we conclude from moving errors around freely, caring only about performance in-sample? This question is considered in Section 2.2.

This inquiry uncovers a fundamental limit to the efficacy of any search for a less discriminatory alternative: at certain levels of accuracy, finding a 0-disparity classifier is impossible. In the remainder of this section, we will show that 0- or near-0 disparity classifiers are possible to achieve as long as the utility achieved by the starting classifier remains below a certain cutoff, which depends only on the sizes of the positive group 1 ($n_{1,+}$), negative group 1 ($n_{1,-}$), positive group 2 ($n_{2,+}$), and negative group 2 ($n_{2,-}$) populations.

Another question we will ask is, given access to the full distribution over discrete data, what is the computational burden of finding whether there exists a less discriminatory classifier? This question is considered in Section 2.3.

We know that achieving highly performant LDA classifiers on a fixed and labeled dataset – or a known data distribution – is much easier than guaranteeing any accuracy or disparity property out-of-sample from a finite sample. This suggests that limits and impossibility results in the ‘easier case’ hold in the realistic setting, which is only harder. To make these claims more precise, we introduce a working formalism before stating our results in formal terms.

The reality of ML-driven (‘predictive’) policies is that they are designed and deployed without perfect knowledge about the population subjected to them. Even if model A is observed to perform better than model B on a training dataset, one cannot guarantee this performance out-of-sample on unseen data. These comparisons are particularly hard when A and B are sampled from different distributions (e.g., come from different model classes). The statistical task of understanding what inferences can be made from a limited dataset is a fundamental challenge for ML research. As we will describe, this challenge is similarly present for inferences about less discriminatory alternatives. In what follows, we present two imperfect LDA definitions that illustrate the challenges introduced by statistical limits.

So far, we have focused on methods for arriving at an LDA with a single utility function, parameterized by $\lambda$. One might reasonably assume this utility function represents the interests of the firm, since disparate impact law harps on finding an alternative policy that meets the firm’s business needs. However, it is well known that firm and consumers can have divergent interests (warren2008making). When firms select whom to offer a loan, their policies aim to avoid granting credit to people who are likely to default, because the firm is unlikely to turn a profit in these cases. Granting risky loans could have deleterious consequences for the consumer, too, because they can worsen the consumer’s financial outlook in the long-term (liu2018delayed). In this section, we explore the possibility that consumers and firms might have different preferences over outcomes. In certain cases where the utilities of consumers and firms differ, we show that there exist alternative classifiers that jointly serve business needs and lower selection rate disparities but that leave consumers strictly worse off. In other words, there exist classifiers satisfying our prior definitions of LDA that harm the consumers, including those belonging to the disadvantaged group.

However, we show that just because someone can identify the existence of a consumer-harming LDA, this does not necessarily mean that consumer-benefiting LDAs do not exist. Additionally, we find that requiring that consumers should not be harmed does not impose significant computational burden or effort on the LDA search. For any number of additional utility considerations beyond 2, or in settings where the set of utility considerations is unknown, the optimization is easily reduced to the case where $|\vec{\lambda}|=2$.

Consumer-harming LDAs exist. Here, we show that if firm and consumer welfare differ (as specified further in Appendix LABEL:app:firm-and-consumer-utility-differ-supplement), it is possible to identify an LDA that strictly harms consumers.

The above finding (proven in Appendix LABEL:app:consumer-harming-proof) suggests that there are certain instances where it is only possible to achieve consumer-benefiting or firm-benefiting alternatives, but not both simultaneously. An LDA that serves the firm’s interest will not, necessarily, benefit consumers, and vice versa.

The existence of consumer-harming LDAs points to the fact that simplistic definitions of this concept can lead firms to arrive at classifiers that do not meaningfully improve conditions for consumers. It also suggests that an LDA might reasonably be refuted, if it fails to meet the condition that consumers (especially, those from the disadvantaged group) should be better off as the result of a proposed LDA. Thankfully, as we will see, adding stipulations and considerations for consumer welfare does not pose a significant computational challenge as it has nice convexity properties.

Utility behaves nicely. In practice, how should a firm account for consumer utility, particularly when consumers don’t necessarily know their utility functions and firms don’t have the ability to ask at scale? Here we show that as long as an LDA is able to satisfy two utility requirements, defined by two values $\lambda_{1},\lambda_{2}$, it satisfies all utility values for lambda in the interval between them.

A formal proof is provided in Appendix LABEL:app:convex-utility-proof. Another way of thinking about the above result is that the utility as we’ve defined it is convex, so it isn’t too burdensome to add constraints that require additional players or utility functions are satisfied in the LDA search. Further, in a world where firms do not know, exactly, what consumer welfare is, they should still be able to search for LDAs that satisfy a range of (likely) utility formulations. Broadly, even though it is possible that naïvely-defined LDAs leave consumers worse off, it is easy to stipulate that an LDA should satisfy additional utility considerations, and this is unlikely to considerably increase the firm’s computational burden.

Here we describe a set of empirical experiments. The aim of these tests is to better understand the effectiveness and characteristics of certain simple heuristic search methods for finding an alternative classifier with lower disparity and higher utility performance on new data. We do not expect these methods to identify a Pareto-optimal, fair-and-accurate classifier on unseen data — an algorithm designer would need to be unfathomably lucky to arrive at a classifier of that sort, even on relatively small datasets. Instead, the methods we test search for alternative classifiers that are similar to the starting classifier, by changing the random seed or randomly sampling and re-training. After producing, say, 100 similar models, the methods we test evaluate the level of disparity using available data (i.e., an evaluation set) and select the minimally-disparate alternative.

Although these methods only search a narrow slice of possible classifiers, they have some desirable properties that make them easy to work with and analyze. First of all, they do not explicitly model disparity and they produce a selection policy that does not, explicitly, use the protected attribute. In regulated industries like lending, discrimination based on these features is illegal. Second, the methods produce a set of alternative models that are in the same model class as the original classifier. This provides a convincing argument for meeting the business need for generalizable performance: if a model falls within the same class of models as the starting classifier, it does not introduce new complexity or expressiveness that could exhibit good performance on training data that does not translate, in reality, to new data. Third and finally, because the methods we use produce a set of similar models from the same model class, their disparity and utility performance on held-out evaluation data will represent identical and independent draws from a single distribution. This gives the algorithm designer good reason to select the minimum disparity classifier on evaluation data as a best-guess for the best-performing model in general. So-called disparate learning processes — attempts to produce group-independent classifiers using a group-aware learning process — have been analyzed at length, and there is reason to believe other methods may more effectively find less discriminatory models (lipton2018does).

Data and models. For this test, we use two datasets, Adult and German Credit. Both datasets are collected in financial settings. We use the Adult dataset to perform a classification where the task is to predict which individuals make over $50,000 in income per year. We use the German Credit dataset to perform a classification where the task is to predict credit-worthiness (as defined in the dataset’s meta-data). We test three starting classifiers: a Logistic Regression, a Random Forest, and a Decision Tree classifier. We implement these classifiers in Python using sklearn, typically with pre-set default hyper-parameters (though we do set max_depth=5 for the random forest classifier). Though the datasets do not have balanced class weights, we train our models using balanced weights. A more detailed description of the datasets and models is provided in Appendix 9.

Search processes. We conduct two search types to identify proximate models from the same model class. The first is sampling and re-training — we take a random sample, with replacement, the size of the training data and re-train the same model on this new sample of data. The second method is testing different random seeds. We only use this second method for the Random Forest model because it is an ensemble model that explicitly uses pseudorandomness and the model changes significantly when we perturb the random_seed parameter.

Experiment procedure. First, we split the data into train, evaluation, and test sets. Using the training data, for each search process and model type, we train 10,000 models (generated at random) and record their performance and qualities in a dataset. The utility, disparity, and selection rate is measured on training, evaluation and testing data for every model, and recorded in a dataset. To test the procedure of searching over $n$ alternative models, we draw from our dataset $n$ times for $n\in\{1,...,100\}$. Equipped with a subset of $n$ models, we select the model with lowest disparity on the evaluation data, and record its utility and disparity performance on test data. The average ‘lift’ in utility or reduction in disparity is attained by comparing this selected model to the average performance over the $n$ models. For each value of $n$, we perform this sub-sampling procedure 2000 times, and record the mean, 2.5th and 97.5th percentiles to produce point estimates, lower-bounds, and upper-bounds, respectively.

Finally, we also track the rate at which the procedure tested produces a perfect guess of the out-of-sample disparity-minimizing model, over the set of models tested. That is, if we conduct our procedure with $n=100$, we measure the frequency that the lowest-disparity model according to evaluation data is also the lowest-disparity model on the test dataset.

We note that we do not claim to have the best or optimal procedure for searching, nor do we claim that the method we put forward is reasonable in the legal interpretation as advocated by black2023less. Instead, we aim to explore whether, in certain instances, simple methods can attain generalizable reductions in discrimination at no cost to accuracy (utility). We also wish to test whether these methods consistently arrive at the least discriminatory classifiers out-of-sample, or whether they open up the possibility that firms test and reject alternatives that end up with lower disparity in hindsight.

Results. The main results are reported in Table 1. The tests provide evidence that certain search methods can reveal the existence of lower-disparity alternative classifiers whose performance generalizes out-of-sample. The asterisk * signifies that the results are statistically significant according to the boostrapped 95% confidence intervals, attained by repeating the search procedure 2000 times. In other words, the asterisk tests whether the directional change in disparity or utility was observed in at least 95% of the 2000 times the procedure was tested. Disparity reductions are statistically significant according to this procedure on the Adult dataset for all models and search methods tested. The disparity effects on the German Credit dataset are not significant, which is explained both by the much smaller sample size and the minuscule starting disparity level.

The Random Forest model has the highest utility measure on both datasets compared to the other models tested. It also had the highest absolute disparity on both datasets. These results are depicted in Figure 3. Performing an LDA search procedure on the RF increases utility in our Adult test, meaning in this case, utility increases and disparity decreases statistically— no trade-off is observed. The observed differences in these values is visualized in Figure 2. In other cases, with other models, however, the utility decreases. This makes sense, given nothing about our procedure guarantees or tries to maximize directly the utility.

One feature of the procedure we test is that it checks, and rejects, 99 models in favor of the model that has lowest disparity on an evaluation dataset. We find this method, even when it consistently reduces disparity out-of-sample, can increase the likelihood of passing over the actually disparity-optimal model out-of-sample. The frequency that the selected model is disparity-optimal of those considered is displayed in the rightmost plot in Figure 2.

The methods tested are not the only way to systematically search for less discriminatory algorithms. We could imagine altering the loss function of an algorithm directly so that the algorithm optimizes some weighted combination of disparity reduction and utility. We could similarly imagine encoding knowledge about the structure of disparity — if certain attributes are likely proxies for the protected group belonging, using more bespoke modeling assumptions could better target de-biasing interventions. Some may find the methods we test desirable, however, because they do not use pre-existing knowledge about groups or disparity, as they simply draw from the set of plausible good models given a pre-existing model class.

This paper is concerned with a legal concept that predates the era of pervasive machine learning. The less discriminatory alternative has emerged as an enticing notion because it could offer a way for old rules to apply to new tools. We find, however, that simple and elegant operationalizations of this concept run up against fundamental limits, trade-offs, and impossibilities that circumscribe the attainable properties and attributes of an LDA search. Mathematically, a classifier can only exhibit certain combinations of accuracy and disparity – a near-perfect-accuracy model cannot have 0 disparity unless a dataset already exhibits equal base rates. Computationally, a search for the least-discriminatory-possible model at some baseline level of utility is generally intractable in polynomial time. Statistically, although LDAs are almost always identifiable in retrospect on fixed populations, making conclusions about how alternative classifiers perform on an unobserved distribution is much more difficult. Finally, from a modeling and consumer welfare perspective, defining an LDA only in terms of ‘business needs’ can lead to LDAs that leave consumers strictly worse off. Each of these results seems to offer ammunition to firms defending their (potentially unfair) practices against accusations of discrimination. However, they only tell part of the story. While each of these results do fundamentally limit the search, they do not preclude firms and plaintiffs from adopting available, low-cost, and effective methods for identifying LDAs.

Here we provide supplementary matrials and proofs for claims made in Section 2.

Here we provide supplementary materials and proofs for claims made in Section 2.3.

Data and Models (further information). Every row in the Adult dataset represents features of an individual, and the outcome variable is an indicator representing whether they make over $50,000 in annual income. The data is on American adults from census information in 1994. We use a total of four variables – maritalstatus (a categorical variable representing whether the individual is single/divorced/married/etc), hoursperweek (a numerical variable representing the number of hours the individual works per week), education (a categorical variable specifying the level of education achieved, e.g. college degree), and workclass (a categorical variable representing the type of work). The protected attribute is the gender (given as a binary M/F). The dataset contains a total of 32,561 rows.

The German Credit dataset contains loan decisions in Germany, and was accessed via the UCI machine learning database. The dataset contains a total of 1,000 rows with categorical and numerical features related to individual’s credit, financial status, employment, and loan application. The following five features were used to train the models: credit_history_category (categorical variable representing information about credit history), credit_amount (numerical variable representing amount of credit requested by loan applicant), unemployment_category (categorical variable with information about whether the individual is unemployed), installment_rate_percentage_income (numerical feature representing the ratio between loan amount and income), and present_residence_duration (a numerical variable representing the amount of time the applicant has resided in their current residence). The protected attribute is the gender (given as a binary M/F).