key: cord-0183935-o2fm8vu7 authors: He, Yuzi; Burghardt, Keith; Guo, Siyi; Lerman, Kristina title: Inherent Trade-offs in the Fair Allocation of Treatments date: 2020-10-30 journal: nan DOI: nan sha: 8554e8e105c652214d4d23c53c410dd570b0750c doc_id: 183935 cord_uid: o2fm8vu7 Explicit and implicit bias clouds human judgement, leading to discriminatory treatment of minority groups. A fundamental goal of algorithmic fairness is to avoid the pitfalls in human judgement by learning policies that improve the overall outcomes while providing fair treatment to protected classes. In this paper, we propose a causal framework that learns optimal intervention policies from data subject to fairness constraints. We define two measures of treatment bias and infer best treatment assignment that minimizes the bias while optimizing overall outcome. We demonstrate that there is a dilemma of balancing fairness and overall benefit; however, allowing preferential treatment to protected classes in certain circumstances (affirmative action) can dramatically improve the overall benefit while also preserving fairness. We apply our framework to data containing student outcomes on standardized tests and show how it can be used to design real-world policies that fairly improve student test scores. Our framework provides a principled way to learn fair treatment policies in real-world settings. Equitable assignment of treatments is a fundamental problem of fairness, especially in cases where treatments are not available to all people and some individuals stand to benefit more from them than others. This problem arises in multiple contexts, including allocating costly medical care to sick patients [9, 25] , materials following a disaster [28] , college spots and financial aid in college admissions, extending credit to consumers, and many others. Despite growing interest from the research community [7, 8, 21] and the rise of automated decision support systems in healthcare and college admissions that help make such decisions [23] , fair allocation of scarce resources and treatments remains an important open problem. To motivate the problem, consider an infectious disease, like the COVID-19 pandemic, spreading through the population. The toll of the pandemic varies in different ethnic and racial groups (i.e., protected groups) and also via several comorbidities, such as age, weight, underlying medical conditions, etc. When a vaccine becomes available, who should receive it first? To minimize loss of life, we could reserve the vaccine for high-risk groups with comorbidities, but this does not guarantee protected groups will be treated equitably. Some groups will get preferential treatment, unless-and * Also with University of Southern California, Department of Physics and Astronomy. † Also with University of Southern California, Department of Computer Science. this is highly unlikely-all groups reside in high-risk categories at equal rates. In comparison, adding fairness constraints to provide more vaccines to protected groups may result in more lives lost overall, in cases where protected groups have lower mortality. This demonstrates the difficult trade-offs policy-makers must consider regardless of the policies they choose. Similar trade-offs between unbiased and optimal outcomes often appear in automated decisions. This issue received much attention since an investigation by ProPublica found that software used by judges in sentencing decisions was systematically biased [1] . The software's algorithm deemed Black defendants to be a higher risk for committing a crime in the future than White defendants with similar profiles. Subsequent studies showed the cost in making the algorithm less biased is a decrease in its accuracy [6, 19] . As a result, a fairer algorithm is more likely to incorrectly label violent offenders as low-risk and vice versa. This can jeopardize public safety if high-risk offenders are released, or needlessly keep lowrisk individuals in jail. We will also show that there are multiple ways to define fair policies which do not necessarily overlap. Going back to the vaccine example, selecting individuals from the population at random to receive the limited doses of the vaccine may be considered equitable, but there might be grave differences in mortality rates across protected classes, which this treatment would not overcome. In contrast, preferentially giving vaccines to protected groups may create equitable losses of life between classes, but implies unfair allocation of resources and will not benefit the population the most. Kleinberg et al. made a similar finding for automated decisions [15] . Except for rare trivial cases, a fair algorithm cannot simultaneously be balanced (conditioned on outcome, predictions are similar across groups) [1] and well-calibrated (conditioned on predictions, the outcomes will be similar across groups) [15] . Decreasing one type of bias necessarily increases the other type. Empirical analysis confirmed these trends in benchmark data sets [13] . More worrisome still, there are dozens of definitions of AI fairness [26] , and we suspect there is also no shortage of fair policy definitions, making an unambiguous definition of "fair" a challenge. In the current paper, we combine causal inference with fairness to learn optimal treatment policies from data that increase the overall outcome for the population. First, we define novel metrics for fairness in causal models that account for the heterogeneous effect a treatment may have on different subgroups within population. These metrics measure inequality of treatment opportunity (who is selected for treatment) and inequality of treatment outcomes (who benefits from treatment). This compliments previous research to maximize utilization of resources, i.e., ensuring that they do not sit idle, while also maximizing fairness [8] . We also show a necessary trade-off between fair policies and those that provide the largest benefit of treatment to the most people. We then show how affirmative action policies that preferentially select individuals from protected subgroups for treatment can improve the overall benefit of the treatment to the population, for a given level of fairness. Thus we find a necessary trade-off between policies that are fair overall with policies that would be fair within subgroups. These results demonstrate novel ways to improve fairness of treatments, as well as the important trade-offs due to distinct definitions of fairness. Our methods are tested in synthetic and real-world data. Using high school student test scores and school funding in different regions of the US, we devise fair funding policies that reduce discrimination against counties with a high percentage of Black families. Because the protected subgroup is more sensitive to the treatment (school funding), we create an affirmative action policy in which school funding tends to increase in regions with more Black families. This policy could raise test score more fairly than alternative funding policies. The rest of the paper is organized as follows. We begin by reviewing related work, then we describe the causal inference framework we use to estimate the heterogeneous effect of treatments, define treatment biases, and optimization algorithm that learns fair intervention policies from data. We explore the methods in synthetic data, as well as real-world data. Trade-off between fairness and optimal prediction is intuitively unavoidable. We can regard fairness condition as a constraint to the optimization and the optimal solution which satisfies the constraint will be a sub-optimal. In our case, this means that when designing the intervention policy, we have to sacrifice overall benefit in order to make our policy fair. Fairness is first considered in predictions and representations. Early works include constrained Logistic regressions proposed by Zafar et al. [30] [31] [32] . Menon et al. [19] related two fairness measures, disparate impact (DI) factor and mean difference (MD) score to cost sensitive fairness aware learning. There has also been extensive research on autoencoder based method which produced fair representation (embedding) [18, 20] and generative models which generates data instances which are fair [11, 14, 29] . Recently, there is a growing literature of fairness in causal inference, decision making and resource allocation. There are case studies on social work and health care policy such as [5, 9, 25] . Corbett-Davies et al. [6] formulate the fair decision making as optimization problem under the constraints of fairness. This can be regarded as an easy adaption from fair prediction task such as [32] . Kusner et al. [17] proposed a new perspective of fairness based on causal inference, counterfactual fairness. The counterfactual fairness requires the outcome be independent of the sensitive feature, or in other words, conditional on confounders, which further differs from equal opportunity [12] , or still other metrics, such as the 80% rule, statistical parity, equalized odds, or differential fairness [10] . Donahue and Kleinberg [7] studied the problem of fair resource allocation. The goal was maximizing utility under the constrain of fairness, from which theoretical bound for the gap between fairness and unconstrained optimal utility is derived. Elzayn et al. [8] considered a similar case, with potentially more realistic assumptions that the actual demand is unknown and should be inferred. The problem is formulated as constrained optimization, with the help of censored feedback. Zhang et al. [33] modeled direct and indirect discrimination using path specific effect (PSE) and proposed a constrained optimization algorithm to eliminate both direct and indirect discrimination. Also based on the concept of PSE, Nabi et al. [22] considered performing fair inference of outcome from the joint distribution of outcomes and features. Chiappa [4] also proposed PSE based fair decision making by simply correcting the decision at test time. Our work, however, differs from this previous work because we create (a) policy-based definitions of fairness, (b) optimize on whow to treat while accounting for fairness trade-offs, and (c) address an under-explored trade-off between equal opportunity and affirmative action to improve policy fairness. We briefly review heterogeneous treatment effect estimation, which we use to learn fair treatment policies. We then discuss how we measure biases in treatments, and create optimal intervention strategies. Suppose we are given observations indexed with = 1, ..., , consisting of tuples of data of the form of ( , obs , ). Here denotes features of the observation, obs is the observed outcome, and binary variable indicates whether the observation came from the treated group ( = 1) or the control ( = 0). We assume that each observation has two potential outcomes: the controlled outcome (0) and the treated outcome (1) , but we only observe one outcome obs = ( ) . In addition, we assume that given features , both of the potential outcomes (0) , (1) are independent of the treatment assignment . This condition is called the unconfoundedness assumption. The heterogeneous treatment effect is defined as The task of heterogeneous treatment effect (HTE) estimation is to construct an optimal estimator^( ) from the observations. A standard model of HTE is a causal tree [2] . Causal trees are similar to classification and regression trees (CART), as they both rely on recursive splitting of the feature space X, but causal trees are designed to give the best estimate of the treatment effect, rather than the outcome. To avoid overfitting, we employ an honest splitting scheme [2] , in which half of the data is reserved to estimate the treatment effect on leaf nodes. The objective function to be maximized for honest splitting is the negative expected mean squared error of the treatment effect , defined as below. Here tr is the training set, tr and est are the size of training and estimation set. Π is a given splitting, is a given leaf node, is the ratio of data being treated. Terms Var tr ( | = 0) and Var tr ( | = 1) are the within-leaf variance calculated for controlled and treated data on training set. Note that we only use the size of the estimation data during splitting. In cross validation, we use the same objective function and plug in validation set val instead of tr . After a causal tree is learned from data, observations in each leaf node correspond to groups of similar individuals who experience the same effect, in the same way a CART produces leaf nodes grouping similar individuals with similar predicted outcomes. In many situations of interest, data comes from a heterogeneous population that includes some protected subgroups, for example, racial, gender, age, or income groups. We categorize these subgroups into one of bins, ∈ [1, ]. Even though we do not use as a feature in HTE estimation, the biases present in data may distort learning, and lead to to infer policies that unfairly discriminate against protected subgroups. An additional challenge in causal inference is that a treatment can affect the subgroups differently. To give an intuitive example, consider a hypothetical scenario where a high school is performing a supplemental instruction program (intervention or treatment) to help students who are struggling academically. Student are described by features , such as age, sex, race, historical performance, average time spent on homework and computer games, etc. We want our intervention to be fair with respect to students with different races (in this case, the sensitive feature is race). That means we may want to both reduce the performance gap between different races and we also want to make sure that the minority race gets ample opportunity to participate in the intervention program. However, we assume that the school district has limited resources for supplemental instruction, which means that not every struggling student can be assigned to the intervention program. To best improve the overall performance, it therefore makes sense to leave more spots in the program to students who are more sensitive to intervention (they have a large treatment effect ( )). But if the previous pilot programs show that the effect of the intervention is different amount subgroups (e.g., races), with one subgroup more sensitive to the intervention and also having a better average outcome, we have a dilemma between optimal performance and fairness. If we only care about optimal outcome, the intervention will lead to not only larger performance gap between races but also lack of treatment opportunity for minority race. If we assign the intervention randomly, we will not make full use of the limited resource to benefit the population. Below we discuss our approach to measure bias in treatment or intervention. We learn the effect of the interventions using causal trees. A causal tree learned on some data partitions individual observations among the leaf nodes. A group of observations associated with a leaf node of the causal tree is composed of (1) , = as the estimated outcomes for the control and treated subgroup = in group . Table 1 Table 1 : Definitions used in measuring biases in treatment. To quantify the inequalities of treatment, we first look at the inequality of treatment opportunity, i.e., the disparity of the assignment of individuals from the protected subgroup in leaf node to the treatment condition. To measure the bias, we introduce the treatment ratio , = as the fraction of treated individuals from subgroup among the group in leaf node : We define the inequality of treatment opportunity as the maximum difference of the within-leaf treatment ratios taken over all leaf nodes and pairs of subgroups , ′ , 3.2.2 Measuring Inequality of Treatment Outcomes. The second type of bias we measure is the inequality of treatment outcomes. This bias arises because subgroups may differ in their response to treatment and their controlled outcomes. We quantify this disparity as Figure 1 : The outcome vs feature 0 plot for synthetic data. Note that the other feature 1 is independent from . where the index is for leaf nodes of the causal tree. We define inequality of outcomes as the largest difference of expected outcomes for all pairs of protected subgroups Note that when there are only two protected groups, it is not necessary to take the maximum. A crucial problem in the design of interventions is how to balance between the optimal performance and bias. Below we describe learning optimal interventions that maximize the overall benefit of treatment while properly control the bias of treatment opportunity and the bias of outcome among different subgroups. We can achieve optimality by choosing which individuals to treat. Specifically, given the features , the potential outcomes (0) and (1) are independent of treatment assignment . Therefore, we can vary , = , while keeping (0) , = constant, as part of the optimal policy. 3.3.1 Equal Treatment Opportunity-Constrained Interventions. As a first step, let us consider the case in which Bias = 0, i.e., all subgroups have the same fraction of treated individuals, and the equality of treatment opportunity is strictly satisfied. For every group , we assign the same treatment ratio to all subgroups within defined by . The mean of overall outcome can be written as¯= Our objective is to maximize¯by varying , subject to the following constraints: • First we set an upper bound for the inequality of outcomes, meaning we will not tolerate a disparity in outcomes that is larger than , Bias ≤ Δ¯vs when affirmative action is allowed. Here max = 0.8 and different curves shows different degrees of affirmative action, measured by . Affirmative action greatly improves Δ¯in case where is low, or constrain is "tight." • Practically speaking, the treatment is often bounded by the availability of resources, which usually means that we can treat at most • Finally, treatment ratios have to satisfy a trivial constraint, 3.3.2 Affirmative Action-Constrained Interventions. Alternatively, we can single out subgroups for preferential treatment, assigning different treatment ratios to subgroups within the leaf node , which may improve the overall outcome for the entire population. We refer to this type of intervention as affirmative action policy. For example, in the context of the school intervention program introduced earlier in the paper, affirmative action means that groups that benefit most from the treatment (have largest effect) should be preferentially assigned to the intervention. As another example, affirmative actions for COVID-19 vaccinations means that minorities who are at high risk for COVID-19 complications should get priority access to early vaccines. To learn affirmative action interventions, we vary treatment ratios , = to maximize the overall outcomē under the constraints: • We set an upper bound for the discrepancy of outcomes: Bias ≤ (11) • We set an upper bound for the amount of discrepancy in treatment opportunity we will tolerate as: Bias ≤ (12) • As before, we limit the number of individuals that can be treated ∑︁ ∑︁ , = · , = ≤ (1) max (13) • And finally, all treatment ratios have to satisfy Given the parameter of constrains, ( , max ), we can use linear programming to solve for the optimal¯and corresponding treatment assignment plan or , = . The policies which are optimal under the constraints can be regarded as efficient policies. The causal tree learned from data depends on the random splitting of data into training, validation and estimation sets. Although this may not be a problem when we have sufficiently large dataset, random splits may cause instabilities when used for smaller datasets. To overcome this problem, we carry out multiple random spits of the data and train a causal tree for each data split. When designing an optimal policy, for every constraint parameter ( , max ) we perform optimization for each of the causal tree trained and calculate the optimal outcome as the average for all the causal trees. When boosting is involved, the treatment assignment can not be expressed using treatment probability in each leaf node, since we have multiple causal trees. Instead, we denote the optimal treatment assignment for causal tree with index as ( ) , = , where is the index for the leaf node and is the index for values of . Given the features and sensitive attribute , in the case where affirmative action is allowed, we can define the treatment probability for the individual as Here tree is the number of causal trees trained and ( | ) is the leaf node index corresponds to an individual with feature in causal tree . When affirmative action is not allowed, similarly we have As proof of concept, we demonstrate our approach on synthetic data representing observations from a hypothetical experiment. The individual observations have features, = [ 0 , 1 ], 0 , 1 ∼ (0, 1), drawn independently from a uniform distribution in range [0, 1]. The treatment assignment and sensitive feature are generated independently using Bernoulli distributions: , ∼ (0.5). Finally, the observed outcomes depend on features and treatment as follows: Note that the feature 1 is designed to not correlate with . Figure 1 shows the outcomes for the control ( = 0) and treated ( = 1) individuals. The two subgroups have the same outcome in the control case, but individuals from the protected subgroup ( = 1) benefit more from the treatment ( = 1), since their outcomes are higher than for individuals from the other group ( = 0). Note that the larger the feature 0 , the larger the impact of treatment on the protected subgroup = 1. The disparate response to treatment creates a dilemma for decision makers-if both subgroups receive the same treatment (Bias = 0), then higher population-wide outcome will be associated with a larger discrepancy in the outcomes for the two subgroups, hence, larger bias (Bias ). We train a causal tree to estimate the heterogeneous treatment effect using = [ 0 , 1 ]. Given 6, 000 total observations, we use a third of the data for training the causal tree, a third for validation, and a third for estimation using honest trees [2] . We estimate biases for the sensitive attribute and learn optimal interventions using data reserved in the estimation set. (allowed mean score difference between counties with high/low Black household ratio) when equal treatment opportunity is assumed. Different curves shows different max , the maximum treatment ratio. The leftmost point of each curve shows the edge of the infeasible region. (b) Δ¯vs. when affirmative action is allowed. Here max = 0.4 and different curves show results with different constrains on affirmative action . Equal Treatment Policy. First we consider the equal treatment policy, where individuals from either subgroup are equally likely to be treated. As described in the preceding section, in this case Bias = 0. To model limited resources, such as limited doses of a vaccine or limited number of spots in the academic intervention program, we assume that we can only treat up to (1) max individuals. For simplicity, we introduce max = (1) max / , which is the maximum treatment ratio as a measure of resource limit. Also we use , as a measure of the improvement of the outcome after treatment. We vary treatment ratio max in {0.2, 0.4, 0.6, 0.8, 1.0}, and for each value of max plot the improvement in overall outcome of the intervention (Δ¯) as a function of , the upper limit of the bias in outcomes (Bias ). Figure 2 (a) shows that as we treat more individuals (larger max ), there is greater benefit from the intervention in terms of larger overall outcome (Δ¯). Additionally, as we tolerate more bias ( increases), the overall outcome also increases. However, for large enough , there is no more benefit from the intervention. In this case, we have assigned all the necessary treatment and allowing more bias will not further improve the outcome. In other words, when no more people can be treated under the constraint max , and Bias is maximized. Affirmative Action Policy. To see how affirmative action could improve the average overall outcome, we fix max = 0.8 and vary in {0, 0.05, 0.10, 0.15, 0.20, 0.25}. This allows us to prioritize protected subgroups for treatment. As more individuals from protected subgroups are treated, the treatment ratios become different, increasing Bias . Trade-offs between and . To further illustrate the how and affect the outcome¯, we plot¯against and using heat map and contour line, as shown in Fig. 3 . The heatmap and contour lines demonstrates the trade-offs between the two biases. In order to maintain the same level of benefit from the intervention (moving along the contour lines) while reducing maximum allowed treatment opportunity bias requires us to tolerate larger treatment outcome bias and vice versa. The EdGap data contains education performance of different counties of United States. The data we used contains around 2000 counties and 19 features. The features include funding, normalized mean test score, average school size, number of magnet schools, number of charter schools, percent of students took standardized tests and average number of students in schools receiving discounted or free lunches. Besides these features, we have census features for each county including household mean income, household marriage ratio, Black household ratio, percent of people who finished high school, percent of people with a bachelor's degree, employment ratio, and Gini coefficient. We use z-score normalized mean test score as the outcome. We binarize school funding and the county ratio of Black households to be above and below the median values as treatment indicator and sensitive feature, respectively. In summary, we are interested in the heterogeneous effect of funding increase on different counties and we want to design a fair intervention which reduces the education performance difference between Black and non-Black populations. We use one third of data as training, validation and testing, respectively and train forty boosted causal trees and report the average performance. We first show the result where equal treatment opportunity is assumed. We plot the overall mean score after treatment versus in Fig.4(a) . Unlike the synthetic data ( Fig.2(a) ), we find an infeasible region (note that the left bound of curves are different; beyond the left bound is the infeasible region). The lower the maximum allowed treatment ratio, the larger the infeasible region. This is because, without any treatment, there is a difference in the mean of average test scores for county with more Black population and less Black population. If the constrain , score difference between two groups of county, is set to be too low and the maximum allowed treatment ratio max is also low, the constraints cannot be satisfied. But on the other hand, we also notice that if affirmative action is allowed, we can assign more counties with high Black ratio to treatment and dramatically improve the mean outcome and also reduce the infeasible region (allow greater fairness), as shown in Fig. 4(b) . We also plot Δ¯versus and for different max in heat maps (Fig. 5) . We observe that the size of infeasible region (grey region) is reduced as and max increase. To further understand the bias in the data and the fair intervention we learned, we visualize the geographical distribution of data and the learned treatment assignment in Fig. 6 . We first plot the mean test score of counties and the ratio of Black household in Fig. 6(a)-(b) , respectively. We see that in the southeast states, from Louisiana to North Carolina, there are counties with high ratio of Black households. Correspondingly, we also see that the mean test scores of those counties are lower than national average due to chronic under-funding and racism. To illustrate the effect of affirmative action, we plot the learned optimal treatment assignments of two sets of parameters. First, we consider the case where we assume equal treatment opportunity. We use parameters = 0.25, max = 0.4, = 0. Then for the case where affirmative action is allowed, we use parameters = 0.25, max = 0.4, = 1.0. For both plots, we can see that counties in California, Texas, and Georgia have a high probability of being assigned to treatment. This is because the causal tree model predicts that counties in those state have higher treatment effect ( ). Importantly, comparing Fig.6 (c) and (d), we see when affirmative action is allowed, the counties in Louisiana, Mississippi, Alabama, South Carolina, and North Carolina have a high probability of being assigned to treatment. The treatment will not only improve the overall performance, but will also reduce performance difference between counties with high and low Black households. In this paper, we ask how we can learn intervention policies that both improve desired outcomes and increase equality in treatment across any number of protected classes. To do so, we first create novel metrics to quantify the fairness of any policy, and then create fairer policies based on two complimentary, but distinct, definitions of fairness. These findings demonstrate a trade-off between policies that maximize outcomes and fairness. Increasing the overall outcome can bring unintended unequal treatments between protected classes. That said, the ways to mitigate this unfair treatment has its own trade-off. Policies that provide equal treatment to all classes still provide substantial overall unequal treatment. Affirmative action policies, in contrast, provide greater overall fairness, but imply that subgroups must receive unequal treatment. Finally, we provide an algorithm that offers the best policies, conditional on the trade-offs policy-makers' desire. While this methodology offers substantial benefits to policymakers, our work still has limitations. First, the algorithm and metrics are tailored to causal trees. While trees are highly interpretable, numerous other causal methods exist, and other algorithms need to be tailored to these other methods [3, 16, 27] . Second, there is an open question of how Bayesian networks [24] , which model the pathways of causality, relate to algorithms that model heterogenous treatment effects. Future work must explore how fair policies created via causal models relate to potentially fair policies created by Bayesian networks. Machine bias Recursive partitioning for heterogeneous causal effects Generalized random forests Path-specific counterfactual fairness A case study of algorithm-assisted decision making in child maltreatment hotline screening decisions Algorithmic decision making and the cost of fairness Fairness and utilization in allocating resources with uncertain demand Fair algorithms for learning in allocation problems Fair allocation of scarce medical resources in the time of covid-19 Kamrun Naher Keya, and Shimei Pan. An intersectional definition of fairness Fair generative modeling via weak supervision Equality of opportunity in supervised learning A geometric solution to fair representations Censored and fair universal representations using generative adversarial models Inherent trade-offs in the fair determination of risk scores Metalearners for estimating heterogeneous treatment effects using machine learning Counterfactual fairness The variational fair autoencoder The cost of fairness in binary classification Rob Brekelmans, Aram Galstyan, and Greg Ver Steeg. Invariant representations without adversarial training Learning optimal fair policies Fair inference on outcomes Dissecting racial bias in an algorithm used to manage the health of populations Ensuring fairness in machine learning to advance health equity Fairness definitions explained Estimation and inference of heterogeneous treatment effects using random forests Measuring and achieving equity in multiperiod emergency material allocation Fairgan+: Achieving fair data generation and classification through generative adversarial nets Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment From parity to preference-based notions of fairness in classification Fairness constraints: Mechanisms for fair classification A causal framework for discovering and removing direct and indirect discrimination This project has been funded, in part, by DARPA under contract HR00111990114.