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.
84,346 characters · 19 sections · 88 citation commands
Fair Policy Targeting
\spacingset{1.5}
{\it Keywords:} Fairness, Causal Inference, Welfare Programs, Pareto Optimal, Treatment Rules.
Heterogeneity in treatment effects, widely documented in social sciences, motivates treatment allocation rules that assign treatments to individuals differently, based on observable characteristics murphy2003optimal, manski2004. However, targeting individuals may induce disparities across sensitive attributes, such as age, gender, or race. Motivated by evidence for policymakers' preferences towards non-discriminatory actions cowgill2019economics, this paper designs fair and efficient targeting rules for applications in welfare and health programs. We construct treatment allocation rules using data from experiments or quasi-experiments, and we develop policies that trade-off efficiency and fairness.
Fair targeting is a controversial task due to the lack of consensus on the formulation of the decision problem. Conventional approaches mostly developed in computer science consist in designing algorithmic decisions that maximize the expected utility across all individuals by imposing fairness constraints on the decision space of the policymaker nabi2019learning.\footnote{For a review, the reader may refer to corbett2018measure. Further discussion on the related literature is contained in Section (ref).} In contrast, the economic literature has outlined the importance of taking into account the welfare-effects of such policies kleinberg2018algorithmic. Fairness constraints on the policymaker's decision space may ultimately lead to sub-optimal welfare for both sensitive groups. This is a significant limitation when the policymakers are concerned with the effects of their decisions on each individual's utilities: absent of legal constraints, we may not want to impose unnecessary constraints on the policy if such constraints are harmful for some or all individuals.
This paper advocates for fair and Pareto optimal treatment rules. We discuss targeting in a setting where decision-makers prefer allocations for which we cannot find any other policy that strictly improves welfare for one of the two sensitive groups without decreasing welfare on the opposite group. Within such a set, she then chooses the fairest allocation. The decision problem is conceived for applications in social welfare and health programs and motivated by the Hippocratic notion of “first do no harm” ( “primum non nocere") rotblat1999hippocratic: instead of imposing possibly harmful fairness constraints on the decision space, we restrict the set of admissible solutions to the Pareto optimal set, and among such, we choose the fairest one. For example, during a health-program campaign, the policy-makers may not be willing to decrease all individuals' health status to gain fairness. Instead, they may be willing to trade-off health-status of different groups (e.g., young and old individuals) when considering fairness. Our framework has three desirable properties: (i) it applies to general notions of fairness which may reflect different decision makers' preferences; (ii) it guarantees Pareto efficiency of the policy-function, with the relative importance of each group solely chosen based on the notion of fairness adopted by the decision-maker; (iii) it also allows for arbitrary legal or ethical constraints, incorporating as a special case the presence of fairness constraints whenever such constraints are binding due to ethical or legal considerations.\footnote{For binding fairness constraints, our proposed policy achieves a lower unfairness compared to the policy that maximizes welfare under fairness constraints while being Pareto optimal. See Section (ref) for details. } We name our method Fair Policy Targeting.
This paper contributes to the statistical treatment choice literature by introducing the notion, estimation procedures, and studying properties of Pareto optimal and fair treatment allocation rules. We allow for general notions of fairness, and as a contribution of independent interest, we define envy-freeness fairness varian1976two for policy targeting.
The decision problem consists of lexicographic preferences of the policymaker of the following form: (i) Pareto dominant allocations are preferred over dominated ones; (ii) Pareto optimal allocations are ranked based on fairness considerations. We identify the Pareto frontier as the set of maximizers over any weighted average of each group's welfares. Therefore, such an approach embeds as a special case maximizing a weighted combination of welfares of each sensitive group such as in athey2017efficient, KitagawaTetenov_EMCA2018\footnote{Under the utilitarian perspective considered in KitagawaTetenov_EMCA2018, athey2017efficient, the welfare maximization problem is equivalent to maximizing a weighted combination of the welfare of different groups with weights equal to corresponding probabilities. See Section (ref) for more discussion.}, and in rambachan2020economic. The above references take a specific weighted combination of welfares with weights as given, while in our case, weights are part of the decision problem and directly selected to maximize fairness. This has important practical implications: our procedure is solely based on the notion of fairness adopted by the social planner, and it does not require specific importance weights assigned to each sensitive group, which would be hard to justify to the general public.
Estimating the set of Pareto optimal allocations represents a fundamental challenge since (i) the set consists of maximizers over a continuum of weights between zero and one; (ii) each maximizer of the welfare (or a weighted combination of welfares) is often not unique elliott2013predicting. To overcome these issues, we show that the Pareto frontier can be approximated using simple linear constraints. We use a discretization argument, and we evaluate weighted combinations of the objective functions separately to construct a polyhedron that contains Pareto allocations. Our approach drastically simplifies the optimization algorithm: instead of estimating the entire set of Pareto allocations, we maximize fairness under easy-to-implement linear constraints. Our theorems show that the distance between the Pareto frontier obtained via linear constraints and its population counterpart converges uniformly to zero at rate $1/\sqrt{n}$.
We study regret guarantees, i.e., the difference between the estimated policy function's expected unfairness against the minimal possible unfairness achieved by Pareto optimal allocations. We characterize the rate under high-level conditions for general notions of unfairness and derive upper bounds that scale at rate $1/\sqrt{n}$, in several examples, and a lower bound that matches the same rate. An application and a calibrated numerical study on targeting student awards illustrate the advantages of the proposed method compared to alternatives that ignore Pareto optimality.
The remainder of this paper is organized as follows: we provide a brief overview of the literature in the following section; we introduce the decision problem in Section (ref); Section (ref) discusses estimation; Section (ref) contains the theoretical analysis; Section (ref) discusses counterfactual notions of fairness; Section (ref) discusses an empirical application and numerical studies, and Section (ref) concludes. Derivations and extensions are in the Appendix.
This paper relates to a growing literature on statistical treatment rules sun2020empirical, manski2004, athey2017efficient, armstrong2015inference, bhattacharya2012inferring, hirano2009asymptotics, KitagawaTetenov_EMCA2018, kitagawa2017equality, mbakop2016model, stoye2012minimax, tetenov2012statistical, viviano2019policy, zhou2018offline. Further connections are also related to the literature on classification elliott2013predicting. However, none of these discuss the design of fair and Pareto optimal decisions.
Fairness is a rising concern in economics, see cowgill2019economics, kleinberg2018algorithmic, rambachan2020economic. The authors provide economic insights on the characteristics of optimal decision rules when discrimination bias occurs. Here, we answer the different questions of the design and estimation of the optimal targeting rule within a statistical framework and derive the method's properties. A further difference is the decision problem with a multi-objective, instead of a single-objective utility function, as in previous references. Additional references include kasy2020 that provide comparative statics on the impact of fairness on the individuals' welfare, focusing on the analysis of algorithms, and narita2021incorporating who motivates fairness based on incentive compatibility in the different context of the design of experiments.
In computer science, Pareto optimality has been considered in the context of binary predictions by balashankar2019fair and martinez2019fairness. The authors propose semi-heuristic and computationally intensive procedures for estimating Pareto efficient classifiers. xiao2017fairness discuss the different problem of estimation of a Pareto allocation that trade-offs fairness and individual utilities for recommender systems, where the relative importance weights of the different objectives are selected a-priori. These references do not address the treatment choice problem discussed in the current paper.
References in computer science include chouldechova2017fair, dwork2012fairness, hardt2016equality among others. corbett2018measure contain a review. Additional work also includes liu2017calibrated who discuss fair bandits, and ustun2019fairness who propose decoupled estimation of tree classifiers without allowing for exogenous (legal or economic) constraints on the policy space. While the above references address the decision problem as a prediction problem, several papers discuss algorithmic fairness within a causal framework coston2020counterfactual, kilbertus2017avoiding, nabi2019learning, kusner2019making. All such papers estimate decision rules under fairness constraints without discussing Pareto optimality. The different decision problem considered here is motivated by applications in social welfare and health programs. When not binding on policy-makers decisions, fairness constraints may lead to Pareto-dominated allocations and possibly harmful policies for advantaged and disadvantaged individuals. When fairness constraints are binding, instead, the decision problem proposed in this paper leads to fairer allocations compared to a constrained welfare maximization problem while not being Pareto dominated.
We start by introducing some notation. For each unit, we denote with $S \in \mathcal{S}$ a sensitive or protected attribute. For expositional convenience, we let $\mathcal{S} = \{0,1\}$, with $S = 1$ denoting the disadvantaged group, and $X \in \mathcal{X} \subseteq \mathbb{R}^p$ individual characteristics. We define the post-treatment outcome with $Y \in \mathcal{Y} \subseteq \mathbb{R}$ realized only once the sensitive attribute, covariates, and the treatment assignment are realized. We define $Y(d)$, $d \in \{ 0,1\}$ the potential outcomes under treatment $d$. The observed $Y$ satisfies the Single Unit Treatment Value Assumption (SUTVA) rubin1990formal. Let
be the propensity score and the probability of being assigned to the disadvantaged group. Here, treatments are independent of potential outcomes.
Given observables, $(Y_i,X_i,D_i,S_i)$ we seek to design a treatment assignment rule (i.e. policy function) $ \pi: \mathcal{X} \times \mathcal{S} \mapsto \mathcal{T} \subseteq [0,1], \pi \in \Pi $ that depends on the individual characteristics and protected attributes, and which can be either probabilistic or deterministic.\footnote{It is deterministic if $\mathcal{T} = \{0,1\}$ and probabilistic if $\mathcal{T} = [0,1]$.} Here, $\Pi$ incorporates given and binding legal or economic constraints that restrict the decision space. The welfare generated by a policy $\pi$ on those individuals with sensitive attribute $S = s$ is defined as\footnote{Welfare is interpreted from an intention-to-treat perspective similarly to KitagawaTetenov_EMCA2018, athey2017efficient.}
Under the utilitarian perspective manski2004, the welfare maximization problem, i.e., the population counterpart of the empirical welfare maximization (EWM) KitagawaTetenov_EMCA2018, solves \[ \max _{\pi \in \Pi} \Big\{ p_1 W_1(\pi) + (1-p_1) W_0(\pi)\Big \} \] where $p_1$ is defined as in Equation (ref). However, whenever the sensitive group is a minority group, welfare maximization assigns a small weight to the welfare of the minority, disproportionally favoring the majority group. An alternative approach is to maximize the welfare separately for each possible sensitive group designing different policies for different groups ustun2019fairness. This approach may violate discriminatory laws, i.e., the resulting policy function violates the constraint in $\Pi$. A simple example is when, due to legal reasons, the policy $\pi(x,s)$ must be constant in the sensitive attribute $s$. Instead, we consider a framework where the policymaker simultaneously maximizes each group's welfare, imposing Pareto efficiency on the estimated policy, under arbitrary legal or economic constraints encoded in $\Pi$. Given the set of efficient policies, the planner then selects the least unfair one. Our approach is designed for social and welfare programs where legal constraints naturally occur and where, given such constraints, the policymaker’s preferences align with classical notions of “first do no harm".
The set of Pareto optimal choices is defined as $\Pi_{\textrm{\tiny o}}$, and it contains all such allocations $\pi \in \Pi$ for which the welfare for one of the two groups cannot be improved without reducing the welfare for the opposite group. We characterize $\Pi_{\textrm{\tiny o}}$ in the following lemma.
The lemma follows from negishi1960welfare, whose proof is in Appendix (ref). It will be convenient to define
the largest value of the objective in Equation (ref) for a fixed $\alpha$. In the following examples, we show that Pareto allocations generalize notions of treatment rules from previous literature.
Pareto optimal allocations are often non-unique, allowing for flexibility in the choice of efficient policies. The policy-maker must appeal to some preferential ranking principle based on her preferences. We discuss those in the following lines.
We start by defining $\mathcal{C}(\Pi)$ the choice set of the policy maker mas1995microeconomic, where $\mathcal{C}$ is a choice function with $\mathcal{C}(\{\pi_1, \pi_2\}) = \pi_1$ if $\pi_1$ is strictly preferred to $\pi_2$. We let
an operator which quantifies the unfairness of a policy. We leave unspecified UnFairness and provide examples in Section (ref) and Section (ref). We now state the planner's preferences.
Assumption (ref) postulates lexicographic preferences of the following form: (i) an allocation is strictly preferred to another if it weakly improves welfare for both groups and strictly improves welfare for at least one group; (ii) given two allocations where none of the two Pareto dominates the other, allocations are ranked based on fairness.
While different applications reflect different planner's preferences, Assumption (ref) is motivated by the applications for social welfare and health programs, where welfare depends on outcomes such as health-status finkelstein2012oregon, future earnings, or school achievements. Sacrificing welfare (e.g., health-status) of each group for fairness is undesirable in such applications. Conditional on achieving a Pareto efficient allocation, the planner minimizes UnFairness. Whenever, however, fairness constraints are binding (e.g., because of legal considerations), these can be directly incorporated in the function class $\Pi$. We can now characterize the decision problem.
The proof is contained in Appendix (ref). Proposition (ref) formally characterizes the policy-makers decision problem, which consists of minimizing the policy's unfairness criterion, under the condition that the policy is Pareto optimal. The policy-maker does not maximize a weighted combination of welfares, with some pre-specified and hard-to-justify weights. Instead, each group's importance (i.e., $\alpha$) is implicitly chosen within the optimization problem to maximize fairness. This approach allows for a transparent choice of the policy based on the policy-makers definition of fairness.
We conclude by comparing the properties of the policy in Proposition (ref) with existing alternatives, stated as a corollary of Proposition (ref). In particular, we compare our method with the policy that maximizes welfare with importance weights for different groups rambachan2020economic in Equation (ref) and the one with fairness constraints. For the latter, define $ \Pi(\kappa) = \Big\{\pi \in \Pi: \mathrm{UnFairness}(\pi) \le \kappa\Big\} \subseteq \Pi, $ the set of policies with constraint, and
the policy that maximizes the welfare imposing fairness constraints nabi2019learning.
Corollary (ref) shows that UnFairness of $\pi^\star$ is Pareto optimal and uniformly smaller than UnFairness of the policy $\pi_\omega$ that maximizes a weighted combination of the welfares. It also shows that if $\widetilde{\pi}$ is Pareto optimal, then its UnFairness is larger than UnFairness of $\pi^\star$. When instead $\widetilde{\pi}$ is not Pareto optimal, its Pareto dominant allocations have larger UnFairness than $\pi^\star$. Further intuition can be gained under strong duality, which we discuss in Appendix (ref). Intuitively, the constraint in Proposition (ref) holding for some weighted combinations of welfares (instead of a particular choice of the weights) is key to achieve lower unfairness of $\pi^\star$ relative to $\widetilde{\pi}$, when $\widetilde{\pi}$ is Pareto efficient.\footnote{Under strong duality, the dual of $\widetilde{\pi}$ corresponds to minimize UnFairness for one particular weighted combination of welfare exceeding a certain threshold. In contrast, our decision problem imposes the constraint that some weighted combination of welfares exceeding a certain threshold. This difference reflects the difference between the lexicographic preferences that we propose as opposed to an additive social planner's utility.} Finally, when fairness constraints are binding, the proposed procedure always leads to smaller UnFairness.
We now construct an estimator of $\pi^\star$. We introduce some notation, and we define
the conditional mean of the group $s$ under treatment $d$, and the doubly robust score robins1995semiparametric, respectively. We let $\hat{\Gamma}_{d,s,i}$ the estimated counterpart of $\Gamma_{d,s,i}$. Define
the estimated welfare built upon semi-parametric literature newey1990semiparametric, robins1995semiparametric, with $ \hat{m}_{d,s}(.),\hat{e}(.), \hat{p}_s, $ constructed via cross-fitting chernozhukov2018double. Details of the cross-fitting procedure are contained in Appendix (ref). We consider first general notions of fairness, and introduce the corresponding estimator below.
We defer to Section (ref) and Section (ref) explicit examples of $\widehat{\mathcal{V}}_n(\pi)$.
Next, we characterize the Pareto frontier using linear inequalities. To construct the Pareto frontier we use the constraint in Equation (ref) after discretizing the set of weights $\alpha$. Namely, in the first step, we discretize the Pareto frontier, and construct a grid of equally spaced values $\alpha_j \in (0,1)$, $j \in \{1, ..., N\}$, with $N = \sqrt{n}$. We approximate the Pareto frontier using the set ($\hat{W}_0, \hat{W}_1$ are defined in Equation (ref))
The grid's choice is arbitrary, as long as values are equally spaced.
The set $\widehat{\Pi}_{\mbox{\tiny o}}$ may be hard, if not impossible, to directly estimate, since we may have uncountably many solutions manski1989estimation, elliott2013predicting. In particular, the solution to each optimization problem in Equation (ref) may not be unique. Instead of directly estimating $\widehat{\Pi}_{\mbox{\tiny o}}$, we characterize it through linear constraints. First, we find the largest empirical welfare achieved on the discretized Pareto Frontier defined as
which can be obtained through standard optimization routines KitagawaTetenov_EMCA2018, zhou2018offline. Second, we observe that any $\pi \in \widehat{\Pi}_{\mbox{\tiny o}}$, must satisfy $\alpha_j \hat{W}_0(\pi) + (1 - \alpha_j) \hat{W}_1(\pi) \ge \bar{W}_{j,n}, \text{ for some } j \in \{1, ..., N\}$, since $\bar{W}_{j,n}$ defines the largest objective for a given $\alpha_j$. We impose such constraint up to a small slackness parameters $\lambda/\sqrt{n}$ and construct an approximate Pareto frontier as follows:
where $\widehat{\Pi}_{\mbox{\tiny o}}(0) = \widehat{\Pi}_{\mbox{\tiny o}}$, and $\widehat{\Pi}_{\mbox{\tiny o}} \subseteq \widehat{\Pi}_{\mbox{\tiny o}}(\lambda)$ for any $\lambda \ge 0$.
Here, we introduced $-\frac{\lambda}{\sqrt{n}}$ which imposes that the resulting policy is “approximately” Pareto optimal. As shown in Section (ref), $\lambda/\sqrt{n}$ guarantees that $\widehat{\Pi}_{\mbox{\tiny o}}(\lambda)$ contains all Pareto optimal policies with high-probability, for $\lambda = \mathcal{O}(1)$. The estimated policy is defined as
We provide a mixed-integer quadratic program (MIQP) for optimization. We define $ \mathbf{z}_s =(z_{s,1},\cdots, z_{s,n}), z_{s,i} = \pi(X_i, s), \pi \in \Pi. $ Here, $z_{s,n}$ defines the treatment assignment under policy $\pi$ and sensititive attribute $s$ (see the example below); $\mathbf{z}_s$ have simple representation for general classes of policy functions, such as either probabilistic rules which we derive in Appendix (ref) or deterministic linear decision rules florios2008exact.
We now need to impose the constraint of Pareto optimality. To do so, we introduce an additional set of decision variables that guarantee the constraints in Equation (ref) hold. The vector $\mathbf{u}=(u_1, ..., u_N) \in \{0,1\}^N$ encodes the locations on the grid of $\alpha$ for which the supremum in (ref) is reached at; here, $u_j=1$ whenever the constraint in Equation (ref) holds for $\alpha_j$. The chosen policy must be Pareto optimal, i.e., $u_j$ must be equal to one for at least one $j$. To ensure this, we impose the constraint $ \sum_{j=1}^N u_j \ge 1$.
Combining such constraints, it directly follows that $\hat{\pi}_\lambda$ satisfies Equation (ref) if and only if
Here, $\mathbf{\Gamma}_{d,s}$ is the vector of $\Gamma_{d,s, i}$ defined in Equation (ref). Constraints (B) and (C) state that the resulting policy is (approximately) Pareto optimal, or, equivalently, it maximizes a weighted combination of groups' welfare for some $\alpha_j$. Constraints (A), (C), (E) are (mixed-integer) linear constraints, while Constraint (B) is quadratic. Notice that we can further simplify (B) as a linear constraint at the expense of introducing additional $N n$ binary variables and $2 N n$ additional constraints (e.g., see wolsey1999integer, viviano2019policy). Finally, (D) is either linear or quadratic for deterministic assignments and linear probability models. Hence the objective admits a MIQP representation whenever $\widehat{\mathcal{V}}_n(\pi)$ admits linear representation in $\pi$, as discussed in the following section. Note that the solution to the optimization problem might not be unique, depending on the function class. However, non-uniqueness does not affect theoretical properties in Section (ref).
Below we impose that Condition (A), which restricts the function class of interest of the policy function, which holds for linear scores manski1975maximum, and decision trees zhou2018offline. Condition (B) ensures the measurability rai2018statistical, kosorok2008introduction.
Condition (i) imposes the standard overlap assumption; Condition (ii) assumes uniformly bounded outcomes mbakop2016model. The following assumptions are imposed on the estimators.
Assumption (ref) states that the product of the mean-squared error of the estimated propensity score and conditional mean converges to zero at the parametric rate. This condition is standard in the doubly-robust literature chernozhukov2018double, farrell2015robust. Assumption (ref) also states that the conditional mean and the propensity score functions are uniformly bounded. The conditions can be stated asymptotically, in which case the uniform bound on estimated nuisance functions is not required and results should be interpreted in the asymptotic sense only athey2017efficient.
It is interesting to study the behavior of the estimated frontier relative to its population counterpart. We do so in the following theorems.
Theorem (ref) shows that the distance between the estimated Pareto frontier and its population counterpart converges to zero at rate $1/\sqrt{n}$ for a choice of $\lambda = \mathcal{O}(1)$ where $\lambda$ is defined in Equation (ref). The derivation uses properties of the double-robust estimator farrell2015robust, and connects to the literature on empirical welfare maximization KitagawaTetenov_EMCA2018, zhou2018offline, athey2017efficient, while differently here we control the maximum deviation uniformly over a set of weights $\alpha$.
A natural question is whether the estimated Pareto frontier also contains all Pareto optimal allocations for a finite $\lambda$. We complement Theorem (ref) by showing that with high probability the set of estimated allocations $\widehat{\Pi}_{\textrm{\mbox{\tiny o}}}(\lambda)$ contains the Pareto frontier for finite $\lambda$.
Theorem (ref) complements Theorem (ref) showing that it suffices $\lambda = \mathcal{O}(1)$ (and hence a slackness of order $\mathcal{O}(1/\sqrt{n})$) for the set of estimated allocations to contain the Pareto frontier. The proofs of Theorems (ref), (ref) are contained in Appendix (ref). Theorem (ref) uses finite sample properties of the estimated (discretized) frontier showing uniform concentration. The choice of $\lambda/\sqrt{n}$ matches the upper-bound on the maximal deviations, and the choice $N = \sqrt{n}$ guarantees that the grid is coarse enough to control the estimation error.
Given the guarantees on the frontier, we next analyze guarantees on fairness. We start our discussion by introducing regret bounds for generic notions of unfairness under high-level assumptions and then provide examples of upper and lower bounds.
Assumption (ref) states that the estimated unfairness converges with probability $1 - \gamma$ to population unfairness uniformly over $\Pi$ at rate $n^{-\eta}$ for some arbitrary $\eta$. The constant $\mathcal{K}(\Pi, \gamma)$ depends on the function class' complexity and the probability $\gamma$. We characterize the constant and the rate $\eta$ in examples in Section (ref) and Appendix (ref).
The proof is contained in Appendix (ref) and leverages Theorem (ref) to show that the set of Pareto allocations is contained with high-probability within the estimated allocations. Theorem (ref) characterizes the convergence rate of the UnFairness of the estimated policy relative to the lowest unfairness within the class of Pareto allocations. To our knowledge, this is the first result of this type of fair policy. The rate depends on the convergence rate of the estimated UnFairness. In the following paragraphs, we discuss examples and sufficient conditions for Assumption (ref) to hold and formally characterize the rate of convergence $\eta$ and the constant $\mathcal{K}(\cdot)$.
Here we discuss three examples, one based on policy predictions, a second based on the welfare-effect, and a third based on incentive compatibility.
Prediction disparity captures disparity in the treatment probability between groups. The second notion of UnFairness measures welfare disparities between the two groups.
Between-groups disparity captures the difference in welfare between the advantaged group $(S = 0)$ and the disadvantaged group $(S = 1)$, relative to the baseline.\footnote{Recall the definition of welfare in Equation (ref) where we only consider the effect under treatment the effect under control.}
The policymaker may also consider $|D(\pi)|$ or $|C(\pi)|$ as measures of UnFairness, in which case the policymaker treats the two groups symmetrically, whose regret bounds are discussed in Appendix (ref). One last example is based on the notion of incentive-compatibility, motivated by discussion in narita2021incorporating.
Here $I_s(\pi)$ captures fairness based on the incentive of an individual in revealing her sensitive attribute: $I_s(\pi)$ is positive if the welfare of an individual generated from reporting her sensitive attribute incorrectly is larger than the welfare obtained if she reported it correctly. Additional notions, such as predictive parity, can also be considered and omitted for the sake of brevity, see Appendix (ref) for details. For each of the three definitions above, UnFairness linear in $\pi$, and hence optimization can be performed via MIQP.
In the following theorem, we discuss the rate of the regret-bound.
The proof is included in Appendix (ref). Theorem (ref) characterizes the regret bound for three different notions of UnFairness. The bound scales at rate $1/\sqrt{n}$. Here $\mathcal{K}(\Pi, \gamma) = \sqrt{v} + \sqrt{\log(2/\gamma)}, \eta = 1/2$ in Theorem (ref). The lower bound depends, however, on the notion of unfairness. Below, we derive a lower bound for any data-dependent policy which achieves the same rate for the predictive disparity.
The proof is contained in Appendix (ref), and, to our knowledge, it is the first result of this type for fair and Pareto optimal policies. The lower bound states that we can find a distribution and some positive (non-vanishing) probability $\gamma$ such that any data-dependent policy $\pi_n$ achieves a regret which scales to zero at a rate no faster than $1/\sqrt{n}$. Observe that a direct corollary of such result is that the rate of the lower bound is also achieved in expectation. The condition imposes a restriction on the set of policies $\Pi$: $\Pi$ does not contain policies that use the sensitive attribute as a covariate. This class of policies occurs if anti-discriminatory laws are enforced and incorporated over the set $\Pi$. The lower bound applies to prediction disparity, and we leave to future research a more comprehensive study of lower bounds under generic notions of fairness. The derivation modifies arguments in the empirical risk minimization literature devroye2013probabilistic, due to the dependence of the objective function with the conditional probability of treatment.
Throughout this section, we have considered distributional notions of fairness, i.e., they depend on distributional statements relative to the sensitive attribute, often used in the literature kasy2020, donini2018empirical, narita2021incorporating. Counterfactual notions depend instead on counterfactual statements relative to the sensitive attribute kilbertus2017avoiding. We discuss one counterfactual notion in Section (ref).
We conclude this section with a discussion on the computational complexity of the procedure. First, consider the case where $|\mathcal{X}| < \infty$, defines a finite number of strata, as often assumed in economic applications manski2004. Since $|\mathcal{X}| < \infty$, let $X$ be a set of dummies $X \in \{0,1\}^p, \sum_j X^{(j)} = 1$, and $\pi(X, S) = X\beta_S, \beta_0, \beta_1 \in [0,1]^p$, where $\beta$ defines the treatment probability for a given individual type. Note that the result continues to hold if we require that $\pi$ assigns treatments on a finite number of strata but $X$ is continuous.
The proof is contained in Appendix (ref). Proposition (ref) states that there exists an exact algorithm with a running time that is polynomial in the number of types and which scales at a rate $\sqrt{n}$ in the number of observations. The exponent $\omega$ depends on the algorithm.\footnote{Classic examples include Vaidya's and Karmarkar's algorithm vaidya1990algorithm, karmarkar1984new.} The intuition is that we can represent the optimization problem in Equation (ref) as a sequence of $\sqrt{n}$ many linear programs (see Appendix (ref)).
For generic function classes, the sequence of linear programs described above is not possible. Two examples are the maximum score with continuous variables and the optimal classification trees. These methods, however, admit a mixed-integer linear program (MILP), which can be solved exactly with, e.g., Branch and Bound (BB) algorithms wolsey1999integer. In generic settings, MILP is known to be NP-hard in the worst-case scenario, hence infeasible for large samples. Here, we characterize properties when an early termination is imposed. Namely, with an early termination, the BB algorithm reports an upper bound on the distance from the best objective (gap), informative for the regret.
The proof is in Appendix (ref). Proposition (ref) shows that the effect of early termination with gap $\delta$ is informative (and can be chosen appropriately) for the policy regret.
This section is of independent interest, and it discusses a novel notion of UnFairness which connects the literature on causal fairness kilbertus2017avoiding and the economic literature on envy-freeness varian1976two. The notion is based on counterfactual statements relative to the sensitive attribute. We sketch the main intuition here and defer details to Appendix (ref). This section defines $Y(d,s), X(s)$ the potential outcome and covariates as functions of the sensitive attribute $s$. The following causal model is considered.
Assumption (ref) is required for estimation with a counterfactual fairness and not for notions of fairness discussed in the previous sections. Condition (A) and (B) in Assumption (ref) state that the sensitive attribute is independent of potential outcomes and covariates, while it allows for the dependence of observed covariates and outcomes with the sensitive attribute. Indexing potential outcomes and covariates captures this dependence by the sensitive attribute. Dependence can also occur through unobserved characteristics, which are dependent on both outcomes and sensitive attributes as long as observables do not causally affect the sensitive attribute. See Figure (ref) for an illustration. Assumption (ref) holds when sensitive attributes do not have causal parents kilbertus2017avoiding.\footnote{Whenever $S_i$ has not causal parents, such as, for instance, age and gender in the application of interest, Assumption (ref) trivially holds. The case of race represents instead an exception under which Assumption (ref) may fail since an individual's race depends on parents' characteristics. Assumption (ref) can be stated after conditioning on baseline characteristics such as parents' observable characteristics to accommodate this latter case.}
Let the conditional welfare, for the policy function being assigned to the opposite attribute, i.e., the effect of $\pi(x, s_1)$, on the group $s_2$, conditional on covariates, be
\definecolor{aero}{rgb}{0.49,0.73,0.91} \definecolor{airsuperiorityblue}{rgb}{0.45,0.63,0.76} \definecolor{babyblueeyes}{rgb}{0.63,0.79,0.95} \definecolor{beaublue}{rgb}{0.74,0.83,0.9} \definecolor{glaucous}{rgb}{0.38,0.51,0.71}
Envy refers to the concept that “an allocation is equitable if and only if no agent prefers another agent’s bundle to his own” varian1976two. We say that the agent with attribute $s_2$ envies the agent with attribute $s_1$, if her welfare (on the right-hand side of Equation (ref)) exceeds the welfare she would have received had her covariate and policy been assigned the opposite attribute (left-hand side of Equation (ref)), namely
We then measure the unfairness towards an individual with attribute $s_2$ as
Whenever we aim not to discriminate in either direction, we take the sum of the effects $\mathcal{A}(s_1,s_2; \pi)$ and $\mathcal{A}(s_2,s_1; \pi)$.\footnote{Such an approach builds on the notion of “social envy” discussed in feldman1974fairness.} Equation (ref) connects to previous notions of counterfactual fairness kilbertus2017avoiding, while, differently from previous references, (i) we provide formal justification to fairness using an envy-freeness argument; (ii) we construct the definition of fairness based on distributional impact of the treatment allocation rule on the welfare. It is complementary to kusner2019making, who compare the policy effects over individuals with the opposite sensitive attribute, lacking an envy-based justification. On the other hand, a shortcoming of the above notion are that, similarly to the above references, it does not capture notions of incentive-compatibility differently from Definitions (ref), discussed in the previous section. A second shortcoming is that it requires parametric estimation for minimax rate of convergence. Namely, in Appendix (ref) we show that for a suitable choice of the estimator of $\mathcal{A}(\cdot)$, with probability at least $1 - 2\gamma$ $$ \mathrm{UnFairness}(\hat{\pi}) - \inf_{\pi \in \Pi_{\textrm{\mbox{\tiny o}}}} \mathrm{UnFairness}(\pi) = \mathcal{O}\Big(\sqrt{\frac{1 }{ n^{2\zeta}} } + \sqrt{\frac{\log(2/\gamma)}{n}}\Big). $$ where here $\zeta$ denote the rate of convergence of the conditional mean function (see Appendix (ref)). The convergence rate is of order $n^{-1/2}$ for a parametric estimators and slower for non-parametric estimators compared to the notions of UnFairness discussed in Section (ref). The slower convergence rate is because counterfactual envy-freeness requires extrapolation on a different population. It opens new questions on the trade-offs between counterfactual and predictive notions of fairness.
We now discuss the empirical application. This section designs a policy that assigns students to entrepreneurial programs, while imposing fairness on gender. We use data that originated from lyons2017impact. The paper studies the effect of an entrepreneurship training and incubation program for undergraduate students in North America on subsequent entrepreneurial activity. We have in total $335$ observations, of which $53\%$ treated and the remaining under control, and $26\%$ of applicants are women.\footnote{Data is available at \url{https://www.openicpsr.org/openicpsr/project/113492/version/V1/view}.} The population of interest is the pool of final applicants. We construct a targeting rule that assigns the award to the finalist based on the applicant's observable characteristics. We maximize subsequent entrepreneurial activity, which is captured using a dummy variable, indicating whether the participant worked in the startup once the program ended. The study is a quasi-experiment, and, as noted in lyons2018does the focus on the pool of final applicants mitigates selection on unobservables. Similarly to lyons2018does we control for residual confounding through individual level observable characteristics and an observable quality score of the final applicant. Estimation of the nuisance functions is through penalized regression and discussed in Appendix (ref).
We consider three notions of UnFairness: (i) counterfactual envy; (ii) (ii) predictive disparity, which minimizes the probability of treatment between the two groups as in Definition (ref); (iii) predictive disparity with absolute value (i.e. it denotes the absolute difference between the probability of treatment between the two groups). While (ii) and (iii) do not impose conditions on the distribution of the sensitive attribute, counterfactual envy ((i)) assumes unconfoundedness also of the sensitive attribute. Such a condition is equivalent to assuming that the decision to change gender is exogenous. The reader may refer to Figure (ref) for a graphical illustration. In case of failure of such assumption, the reader should refer to results for (ii) and (iii) only.
We consider linear decision rules, given their large use in economics manski1975maximum\footnote{This is estimated solving Equation (ref) with a small slackness parameter of order $10^{-6}$. The reader may refer to Appendix (ref) for details. }
We allow covariates $x$ to be either (1) the years to graduation, years of entrepreneurship, the region of the start-up, the major, the school rank, or (2) the score assigned to the candidate by the interviewer and the school rank. We refer to these two cases respectively as Case 1 and Case 2. We consider in-sample capacity constraints imposed on the function class with at most 150 individuals selected for the treatment.\footnote{The validity of the in-sample capacity constraints follows from a uniform concentration argument of the capacity constraint around its expectation. }
We compare the proposed methodology to the method that maximizes the empirical welfare with the double robust score athey2017efficient. We consider three nested function classes for the welfare maximization method. The first does not impose any restriction except for the functional form in Equation (ref). The second, imposes that $\beta_1 = 0$. The third class imposes that $\beta_1 = 0$ and that the average effect of the policy on females is at least as large as the one on males. The function classes are $$
$$ where $\mathbb{E}_n[\cdot]$ denote the empirical expectation, estimated using the doubly-robust method.
Figure (ref) reports the Pareto frontier over each function class.\footnote{The value functions over the Pareto frontier can be exactly recovered as follows: we solve $2$ optimization problems for each $\alpha_j$, $j \in \{1, ..., N\}$. For each of these problems, we impose constraints on the welfare of one of the two groups being larger than the other and vice-versa; we then select the subset of solutions that are not Pareto dominated by the other, and we plot the corresponding welfares in the figure.} The figure shows that restricting the function class leads to Pareto-dominated allocations. This outlines the limitations of maximizing welfare under fairness constraints: such constraints can be harmful for both groups. Instead, the proposed method enforces Pareto optimality in the least constrained environment (red line) and selects the policy based on fairness considerations.
In Table (ref) we collect results\footnote{In computations, the competitors (Welfare Maximization) achieves the global optimum (dual gap equal to zero). For the proposed method we impose a maximum time limit on the MIQP.} of the welfare on female and male students, as well as the relative importance weight assigned to each group for methods that maximize different UnFairness measures. In the table, we observe that minimizing Envy and Predictive Disparity leads to (weakly) larger welfare effects on the minority group. Envy leads to comparable results to welfare maximization for $Case 1$ due to the discreteness of the frontier.\footnote{Even if the weight $\alpha$ is larger for FTP Envy and FTP Parity Abs in $Case$ $1$ and $2$ respectively, this does not lead to a different result than Welfare Max. 1 due to the discreteness of the frontier.} We observe an increase in the welfare of female students when minimizing the absolute difference between probabilities of treatments for $Case$ $1$, and comparable results to the welfare maximization method for $Case$ $2$. The table shows that the proposed method finds importance weights assigned to each group solely based on the notion of fairness provided, without requiring any prior specification of relative weights assigned to each group. The method that maximizes the empirical welfare instead assigns to the sensitive group the importance weight equal to its corresponding probability, small for minorities. In two settings only, the results coincide with the proposed method due to the discreteness of the frontier.
Figure (ref) reports the unfairness level for different sets of covariates, with unfairness measured as the difference in the probability of treatments between the two groups. Overall, Figure (ref) shows that the level of the unfairness of the proposed method is uniformly smaller than the unfairness achieved by maximizing welfare, consistently with results in Section (ref).
Finally, we compare also with probabilistic decision rules, which are allowed in our framework. Figure (ref) also collects result also for a probabilistic policy function (in green) which is a super-set of $\Pi$ in Equation (ref) and assigns different probabilities of treatments to groups below and above the hyperplane in Equation (ref) (see Appendix (ref)).\footnote{Formally, the function class is $\Big\{\pi_\beta(X, S) = p_1 1\{X_i^\top \beta + S \beta_0 > 0\} + p_0 1\{X^\top \beta + S \beta_0 \le 0\}, p_1, p_0 \in [0,1], \beta \in \mathcal{B} \Big\}$.} Results are mostly comparable across probabilistic or deterministic decisions. However, we find that a probabilistic decision enlarges the set of Pareto allocations in Appendix (ref).
Next, we conduct a calibrated experiment. We run the simulations calibrated to the same estimated model in the empirical application (using data from lyons2017impact). Covariates and sensitive attributes are drawn with replacement from the empirical distribution. Formally, we draw $ S_i \sim_{i.i.d.} \mathrm{Bern}(\hat{p}_1), $ where $\hat{p}_1$ is the probability of being female. We draw covariates $X | S = 1$ from the females' empirical distribution and similarly $X | S = 0$ for male applicants. We draw $D | X, S \sim \mathrm{Bern}(\hat{e}(X,S))$, and $ Y(d) = \hat{m}_{d,S}(X) + \varepsilon, \varepsilon \sim \mathcal{N}(0,1), $ where $\hat{e}, \hat{m}$ are the estimated conditional mean and propensity score as in the application. We consider unfairness as prediction disparity in Definition (ref).
We consider three classes of policy functions: (i) probabilistic linear rule $x_1^\top \beta$, were $x_1$ is a set of binary variables ; (ii) maximum-score $\pi(x_2) = 1\{x_2^\top \beta > 0\}$; (iii) classification tree with depth equal to two. For each method, we compute results over three variables (minority, whether the student will graduate in more the one year, whether the average score exceeds the median score). We also include the average score as a continuous variable in the tree and the maximum score. We impose that the number of treated individuals does not exceed $150$ individuals across each design and report welfare per share of treated individuals.\footnote{Welfare is scaled by the unconditional treatment probability since the number of treated units is fixed.} We estimate the probabilistic rule with a linear program, the maximum score with a mixed-integer linear program, and the classification tree via exhaustive search. For the classification tree, we fix the number of possible splits to be four at equally spaced quantiles of each covariate distribution.\footnote{The choice of the exhaustive search follows in spirit to the discussion in zhou2018offline, with differences due to the presence of multiple objectives and constraints here. Four splits facilitate computations. } We run one-hundred replications, and over each replication, we correctly estimate the nuisance functions from the sampled observations.
In Figure (ref) we report the running time (in seconds) of different function classes, with the maximum score having two different stopping times (see also Appendix (ref) for more results). Consistently with Section (ref), the complexity of the linear rule scales much slower than the one of the maximum score. Also, the optimal tree is much faster than the maximum score, even for a larger sample size. The maximum score presents a relatively fast growth in terms of running time, which, however, is still feasible to handle for $n = 600$. Figure (ref) also shows that a more stringent stopping time on the maximum score does not affect its performance either in terms of fairness or welfare. This is because by passing as a starting point an “educated guess", most of the remaining optimization time is to discard dominated solutions. We obtain such a guess by taking the best solution estimated in the first step run to estimate the Pareto frontier. Finally, Figure (ref) shows that different function classes mostly lead to non-dominated males and females welfare comparisons.
Table (ref) contrasts the unfairness and welfare of five different alternative approaches. Each competitor uses the same function class and estimation procedure as the proposed method. The first two competitors maximize a weighted average of female and male welfare with weights either $\alpha = 1/2$ rambachan2020economic, or the empirical average $\mathbb{E}_n[S]$ as a welfare maximization problem. The third approach maximizes welfare with constraints of the form $ \mathrm{UnFairness}_n(\pi) \le \kappa/n, $ where we choose $\kappa \in\{10, 1\}$ (Constrained Max and Constrained Max2, respectively).\footnote{This is in the spirit of fairness constraints nabi2019learning, with constraints on statistical parity.} The fourth approach maximizes welfare with constraints on disparate impact as in Definition (ref) donini2018empirical. Interestingly, while the stricter constraint reduces the gap in males' and females' welfare for the competitor Disparate Impact, such a gap is large due to the estimation error of the constraint (Appendix (ref), Figure (ref) presents details). We observe that the proposed method leads to the lowest UnFairness, and it is not Pareto-dominated. Our method favors the minority group, hence leading to larger welfare for female students. Appendix (ref) provides results for a smaller sample size.
In this paper, we have introduced a novel method for estimating fair and optimal treatment allocation rules. We proposed a multi-objective decision problem, where the policymaker aims to select the least unfair policy in the set of Pareto optimal allocations. We discuss a set of theoretical guarantees on the estimated policy and provide an application. From a theoretical perspective, we open new questions on the trade-offs between predictive and causal notions of fairness and its corresponding regret bound. Counterfactual notions require extrapolation, hence possibly leading to a slower convergence rate. We leave to future research a comprehensive study of properties of different notions of fairness in terms of their implied regret. From a practical perspective, an interesting new direction is estimation with non-utilitarian within-group welfare measures. Finally, the decision problem considered aims to balance efficiency and fairness, and a study of such trade-offs in a decision theoretical framework remains an open research question.
\numberwithin{equation}{section} \numberwithin{figure}{section} \numberwithin{algorithm}{section} \numberwithin{table}{section} \makeatletter \makeatother
\spacingset{1.5}