The increasing deployment of algorithmic decision making systems in social, political, and economic domains has brought with it a demand that fairness of decisions be a central part of algorithm design. While the specic notion of fairness appropriate to a domain is often a matter of debate, several have come to be commonly used in prior literature, such as positive (or selection) rate and false positive rate. A common goal in the design of fairness-aware (group-fair) algorithms is to balance predictive ecacy (such as accuracy) with achieving near-equality on a chosen fairness measure among demographic categories, such as race or gender. A question that arises in many domains where such "fair" algorithms could be used is whether they are susceptible to, and create incentives for, manipulation by agents who may misrepresent themselves in order to achieve better outcomes. For example, in selection of individuals to receive assistance from social service programs or selection of individuals for loans, it may be possible for applicants to misreport the number of dependents, income, or other self-reported characteristics, and, in some cases, even the sensitive attribute itself.
We investigate the eects of such strategic manipulation of a binary group-fair classier. In the social services example, the classier may decide whether an applicant receives assistance, and the fairness criterion could be approximate equality of selection rate between male and female applicants. First, we observe that the ability of individuals to manipulate the features a classier uses can lead to fairness reversal, with the conventional (accuracymaximizing) classier exhibiting greater fairness than a group-fair classier. We demonstrate this phenomenon on several standard benchmark datasets commonly used in evaluating group-fair classiers. Next, we theoretically investigate conditions under which fairness reversal occurs. We prove that the key characteristic that leads to fairness reversal is that the group fair classier becomes more selective, excluding some of the individuals in the advantaged group from being selected. Moreover, we show that this condition is sucient for fairness reversal for several classes of functions measuring feature misreporting costs. In contrast, we experimentally demonstrate that when a group-fair classier exhibits inclusiveness instead by selecting additional individuals from the disadvantaged group, fairness reversal does not occur.
Summary of results: We begin by observing empirically the phenomenon of fairness reversal, exhibited on a number of datasets commonly used in benchmarking group-fair classication ecacy.
The key factor that results in fairness reversal is the extent to which group fairness is achieved through increased selectivity (the fair classier 5 positively classies fewer inputs than the conventional classier 5 ⇠ ) as opposed to increased inclusiveness (5 positively classies more inputs than 5 ⇠ ). Next, we examine this issue theoretically, and prove that selectivity is a sucient condition for fairness reversal. Further, we show that, under some additional conditions, selectivity is also a necessary condition. These results obtain for two common classes of functions measuring the cost of misreporting attributes, and explain our empirical observations.
Our work is closely related to two major strands in the literature: algorithmic group-fair learning and adversarial, or strategic, learning.
The algorithmic fairness literature aims to study the extent to which algorithmic decisions are perceived as unfair, for example, by being inequitable to historically disadvantaged groups [2,4,5,10].
Many approaches have been introduced, particularly in machine learning, that investigate how to balance fairness and task-related ecacy, such as accuracy [1,8,16,20,24,27,[43][44][45]. Many of these impose hard constraints to ensure that pre-dened groups are nearequitable on some exogenously specied metric, e.g., selection (positive) rate [1,24,44], although alternative means, such as modifying the data to eliminate disparities, have also been proposed [9,16].
Within the domain of algorithmic fairness, our work is related to recent investigations into the eects of distribution shift, or data mismeasurement, on fair learning [17,33,37,38]. These works asses the ecacy of fair learning in settings in which data is noisy, or settings in which training data and testing data are sourced from separate distributions. This line of research considers worstcase, or random, distribution shifts, which is distinct from our setting in which we explicitly consider shifts caused by strategic agent behavior. Moreover, these works compare model fairness and performance under distribution shifts or noise with model fairness and performance under no distribution shifts or noise. This is contrast to our work which examines fairness and performance or a particular (fair) model, against an alternate choice of (fairnessagnostic) model.
The adversarial learning literature, initially motivated by security considerations, such as malware detection [22,30,41], has come to have a far broader scope, including social applications [3,6,12,19]. In the latter context, this is known as strategic classication, to indicate the concern that individuals impacted by algorithmic decisions change their features. In most cases, the strategic aspect here is actual misreporting of features, which is our concern. However, a related but distinct, line of work considers individuals who actually change their features (rather than misreport these) to achieve a better outcome [7,25]. A broader related area of performative prediction considers more general changes in behavior induced by algorithmic systems [33,34]. The intersection between strategic classication and fairness is particularly salient to our work, and has featured studies that highlight the inequity that results from strategic behavior by individuals [21], as well as social cost disparities resulting from making classiers robust to strategic behavior [32,43]. Our goal, however, is quite distinct: we investigate the extent to which group-fair learning itself leads to greater inequity than non-groupfair baselines due to strategic manipulation of features. Finally, Liu et al. [29] consider a closely related issue of fairness reversal that may result from a population adapting to a classier. However, their analysis is at the population level, assuming known prediction scores; in contrast, we delve into individual-level manipulation of features, and build results using popular agency models.
We consider a setting with a population of agents, each characterized by a feature vector x 2 X, a group 6 2 ⌧ ⌘ {0, 1} to which they belong (as is common in much prior literature, we treat groups as binary), and a (true) binary label ~2 Y ⌘ {0, 1}, denoting, for example, the agent's qualication (for a service, employment, bail, etc). Let D be the joint distribution over ⌧ ⇥ X ⇥ Y. We dene ? (x) as the marginal pdf of x, and assume that ? (x) > 0 for each x 2 X.
Since using the sensitive group membership feature may pose a legal challenge, we assume that neither the conventional nor the group-fair classier do so at prediction time (but may at training time); from a analytical perspective group-aware classiers (those that use group membership at prediction time) are equivalent to group-unaware classiers from the perspective of agent manipulations, so long as group membership can be misreported in a similar fashion to other features. As such we provide a set of empirical results demonstrating that fairness reversals occur for group aware classiers as well, but defer discussion of group-aware results to Section E.3 of the Supplement. We denote the conventional classier by 5 ⇠ , while the group-fair classier is denoted by 5 , and both map from the domain of features X to the set of binary labels Y. Let M(5 ; 6) be a measure of ecacy (e.g., positive rate) of 5 restricted to a group 6, and dene
We shorten this notation to * (5 ) where M is clear from context. We assume that the conventional classier aims to maximize accuracy, i.e., 5 ⇠ = arg max 5 P (x,~) 5 (x) = ~ , while 5 aims to balance accuracy and fairness, solving
where U 2 [0, 1] species the relative weight of accuracy and fairness terms.
In the literature fairness is sometimes dened with hard constraints, rather than the soft constraints of U-fairness, for example
In general these two formulations are not equivalent, however in the cases we study (PR, FPR, and TPR fairness) soft constrained and hard constrained fairness are equivalent, in the sense that for any U there exists a V such that the classiers produced under either formulation are equivalent, and viceversa. This is given more precisely as Lemma A.4 in the Supplement. As such our results hold for either case; we elect to study the problem through the lens of U-fairness simply for ease of presentation.
We consider the impact of strategic behavior of agents when they face a classier 5 (whether conventional or group-fair). Specifically, we suppose that each agent with features x can modify these, transforming them into another feature vector x 0 that is reported to the classier. In doing so, the agent incurs a cost, captured by a manipulation cost function 2 (x, x 0 ) 0 [18,19,30]. Cost functions are assumed to be bounded 1 over the domain X ⇥ X.
We study two common families of manipulation cost functions:
Feature-monotonic costs: Manipulation cost 2 (x, x 0 ) is monotonic in ||x x 0 || (larger manipulations are more costly).
Outcome-monotonic costs: Manipulation cost 2 (x, x 0 ) is monotonic in P(~= 1|x 0 ) P(~= 1|x) where 2 (x, x 0 ) = 0 for any x 0 such that P(~= 1|x) > P(~= 1|x 0 ) (manipulations leading to better outcomes are more costly).
1 Boundedness of 2 is a rather mild assumption and holds for any continuous function when X is a closed and bounded set, e.g. [0, 1] 3 . This assumption is used primarily to avoid degenerated settings such as those in which no agents can manipulate, e.g., 2 (x, x 0 ) = 1 for all x < x 0 .
For example, if the problem domain involves lending, feature-monotonic costs can correspond to the mental and physiological burden of dishonesty [39], or to the likelihood of failing an authenticity check [14], while outcome-monotonic costs can correspond to the required time investment to identify a productive manipulation, or the likelihood of being audited [15] (applications more likely to succeed are also more likely to be audited) and incurring associated penalties.
We dene the agent's utility as
where ⌫ is a parameter trading o costs and benets of manipulation. Following the standard setting in strategic classication or adversarial machine learning, we assume any misreporting behavior would not change the true label ~associated with x. We assume that all agents are rational utility maximizers. Thus, since 5 (x 0 ) 5 (x) 1, the agent will misreport its features only when 2 (x, x 0 ) ⌫. Additionally, the agent will not misreport if 5 (x) = 1 (they are selected even when truthfully reporting x). Consequently, we can equivalently view ⌫ as an upper bound on the costs that agents are willing to incur from misreporting their features, that is, the manipulation budget.
We next formalize the notion of a fairness reversal in the presence of strategic agents (i.e., what it means for strategic agent behavior to lead to 5 becoming less fair than 5 ⇠ ). Denition 3.1. (Fairness Reversal) Let M be a measure of ecacy, 5 be a classier which is group-fair with respect to * (5 ; M) and 5 ⇠ be a conventional accuracy-maximizing classier. Suppose that * (5 ; M) < * (5 ⇠ ; M). Let 5
(2,⌫) ⇠ , 5
(2,⌫) be the induced classiers when agents best respond to 5 ⇠ and 5 respectively with manipulation cost 2 (x, x 0 ) and budget ⌫. We say that a budget ⌫ leads to fairness reversal between 5 ⇠ and 5 if * (5 (2,⌫) ; M) * (5
(2,⌫) ⇠
; M).
We will then say that fairness reversal between 5 and 5 ⇠ occurs if there is some strategic manipulation budget ⌫ which leads to fairness reversal, that is, for this budget, 5 ⇠ becomes more fair than 5 after manipulation. Note that if the budget ⌫ is 0, 5 will be more fair than 5 ⇠ by construction, whereas if the budget is innite, as long as any input is classied as the positive class, all individuals can misreport their features to be this class, and consequently both classiers are fair in the sense that every input is predicted as 1. As a result, our analysis is focused solely on the intermediate cases between these extremes.
Our central goal is to understand the conditions under which fairness reversal occurs in strategic settings, that is, when a fair classier 5 becomes less fair than its conventional counterpart 5 ⇠ if agents act strategically. Fairness reversal occurs when there is a range of strategic manipulation budgets ⌫ for which the conventional classier 5 ⇠ exhibits greater fairness than the group-fair model 5 . In this section, we study this phenomenon empirically, demonstrating that it is commonly observed for several benchmark datasets.
Datasets and Algorithms. For our empirical study, we use ve datasets commonly used as benchmarks for group-fair classication: Adult: Dataset of working professionals where the goal is to predict high or low income (protected feature: gender) [13,26]. Community Crime: Dataset of communities where the objective is to predict if the community has high crime (protected feature: race) [13,36]. Law School: Dataset of law students where the objective is to predict bar-exam passage (protected feature: race) [42]. Student: Dataset of students where the objective is to predict a student receiving high math grades (protected feature: race) [11,13]. Credit: Dataset of people applying for credit where the objective is to predict creditworthiness (protected feature: age) [13].
All ve datasets have binary outcomes, and we label the more desirable outcome for the individuals by ~= 1 (e.g., having a high income in the Adult dataset), with the less desirable outcome labeled by ~= 0. Consequently, higher positive rate (PR), true positive rate (TPR), or false positive rate (FPR) is more desirable for individuals. Group membership in each dataset is determined by race, gender, or age which in these datasets corresponds to a binary feature (as in [23] the age feature is made binary by considering those older than 25 as Old, and those 25 or younger as Young). A detailed breakdown of the datasets can be found in Section E.7 of the Supplement. In all cases, we refer to the "advantaged" group (e.g. the group with higher PR for PR based fairness) as group 1, or ⌧ 1 , while the disadvantaged group is referred to as 0 or ⌧ 0 . In our experiments, we only consider features that can potentially be manipulated (see Section E.7 of the Supplement for further details). We use four types of conventional classiers for 5 ⇠ , namely logistic regression (LGR), support vector machines with an RBF kernel (SVM), neural networks (NN), and gradient boosting trees (GB), and three group-fair approaches to obtain 5 , Reductions [1], Gerry-Fair [24], and EqOdds [35]. The rst two are inprocessing methods which learn a fair model direction on a given dataset, while the third remedies unfairness through postprocessing the predictions of a conventional classier. To study strategic manipulation, we use a mix of local search for categorical features [28,40] and projected gradient descent (PGD) for continuous features [31]; further details are provided in Section E.6 of the Supplement.
Fairness reversals under strategic agent behavior. In Figure 1 we investigate fairness reversals on three datasets with both Reductions and EqOdds fairness methods; additional experiments in Section E of the Supplement show that this illustration is representative in the sense that although fairness reversals do not occur in all cases, they are quite common. Consider rst Figure 1 (top), which examines settings where predictions do not take the sensitive features as an input (we call these group-agnostic classiers). In these three plots, the dashed line corresponds to 5 ⇠ , and the rest are group-fair classiers 5 for dierent values of U (recall that higher U entails greater importance of group fairness). What we observe is that in many cases, particularly when U is not very high, there is a range of budget values ⌫ for which 5 becomes less fair than 5 ⇠ . Moreover, in many cases, this range is considerable. In Figure 1 (bottom plots), where group-fair classiers are group-aware, including the sensitive feature as an input, the fairness reversal phenomenon is even more dramatic (not that EqOdds attempts to achieve 0 unfairness between groups, i.e., V = 0 is used in all experiments instead of U) Figure 1: Dierence in unfairness between groups on several datasets as a function of the manipulation budget ⌫ when manipulation cost is 2 (x, x 0 ) = kx x 0 k 2 . The dashed black lines correspond to 5 ⇠ and colored lines correspond to 5 . Fairness reversal occurs when one of the colored lines is above the black line. The top row displays results when 5 is learned via the Reductions algorithm, with fairness dened in terms of PR, TPR, or FPR, for several dierent values of U. The bottom row displays results when 5 is learned via the EqOdds algorithm, with fairness dened in terms of generalized false positive rate GFPR (i.e. expected FPR: Denition 1 of [35]). Reductions is group-agnostic, and EqOdds is group-aware.
. In this experiment, when best responding agents are capable of misreporting their group as if it where a feature in x (fairness is still computed with true group membership). Due to the particular nature of EqOdds, specically its handling of agents from dierent groups, we observe a sharp change in fairness at ⌫ = 1, the precise budget for which misreporting group membership is feasible.
Figure 1 exhibits several additional phenomena. Note, in particular, that in many cases the unfairness (i.e., FPR dierence between the groups) initially increases as the budget increases, but in all cases as budgets ⌫ keep increasing, eventually unfairness vanishes as a result of strategic behavior by agents. Furthermore, much as we observe this initial unfairness increase for both 5 ⇠ and 5 , it appears amplied for some of the group fair classiers 5 .
What causes fairness reversal? As we formally prove below, the essential condition is selectivity of fair classier 5 compared to 5 ⇠ . Specically, in binary classication, there are, roughly, two ways one can improve fairness on a given dataset (that is, without any consideration of strategic behavior); either through inclusiveness (positively classifying additional agents from the disadvantaged group by changing their predicted class to 1), or through selectivity (negative classifying some of the members of the advantaged group by changing their predicted class 1 to 0).
Our key observation is that selectivity leads to fairness reversals, while inclusiveness does not. Specically, we observe that as the number of agents positively classied under 5 ⇠ , but negatively under 5 , is larger than the number of agents negatively classied by 5 ⇠ , but positively under 5 , fairness reversals are more commons.
We illustrate this in Figure 2, which shows the decision boundaries of 5 and 5 ⇠ (top row), as well as associated fairness as a function of budget (bottom row) for several combinations of dataset, classier, and fairness denition. On the Adult and Crime datasets (rst two columns), fairness is achieved predominantly through selectivity, as the orange region (5 ⇠ ) includes few additional green points (disadvantaged group) compared to the blue region (5 ⇠ ), but excludes many blue points (advantaged group). This is given more precisely in terms of the respective group-wise positive rates for 5 ⇠ and 5 ; in the rst two examples the positive rates on both groups drops when switching from 5 ⇠ to 5 , while in the third case the positive rate for both groups increases. This, in turn, leads to instances of fairness reversal (bottom row rst column). In the Law School dataset (third column), in contrast, fairness is achieved primarily through inclusiveness, and 5 remains more fair than 5 ⇠ over a broad range of strategic manipulation budgets ⌫. The Figure 2: Fairness reversals and selectivity of classiers on two ordinal features. The top row shows regions with positive predictions (blue for 5 ⇠ and light orange for 5 ) using two features (corresponding to the axes), and dot colors correspond to the sensitive demographics. The darker orange region corresponds to an overlap between the positive predictions of 5 ⇠ and 5 . The bottom row shows the relative unfairness between demographic groups (for the classiers shown in the top row) as a function of strategic manipulation budget ⌫ (lower means more fair). In the top row, the fraction of each group being positively classied under 5 ⇠ is, Adult: (Male: .63, Female: .45), Crime: (White: .84, None-White: .26), Law: (White: .64: None-White: .35) alternatively under 5 is, Adult: (Male: .42, Female: .39), Crime: (White: .62, None-White: .23), Law: (White: .62: None-White: .51) reason that selectivity leads to fairness reversal is that those from the advantaged group who are excluded tend as a result to be closer to the decision boundary than those from the disadvantaged group. In Section E.1 of the Supplement we provide further results linking selectivity of the fair classier to fairness reversals. In this section we also observe that when strategic agent behavior (for some manipulation budget) results in a fairness reversal between 5 and 5 ⇠ , the relative accuracy of the classiers is also reversed (for some potentially dierent manipulation budget), implying a fundamental relationship between fairness and accuracy when agents are strategic.
Unfairness of 5 . Lastly we remark on the relationship of the between the manipulation budge ⌫ and the unfairness of the fair classier 5 . As seen in Figures 2 and1, the unfairness of 5 is frequently increasing in ⌫ (for small values of ⌫). To provide insight into this phenomenon we look to the case of single variable prediction as showing in Figure 3. This gure shows the error and unfairness of a single variable classier (i.e., a threshold classier with threshold \ ) when using a student's LSAT score to predict whether they will pass the bar exam. Since manipulations change model decisions only in a single direction (negative predictions become positive), predicting on strategically altered data amounts to predicting on unaltered data with a lower threshold . As the manipulation budget ⌫ grows, the corresponding threshold becomes increasingly smaller. Thus, when 5 is more selective than 5 ⇠ , i.e. \ > \ ⇠ = 0.57, the unfairness of 5 will initially increase as ⌫ increases. In the case of multivariate prediction, the increased unfairness of 5 stems from a similar Next, we study fairness and accuracy reversals in strategic classication settings theoretically, demonstrating that selectivity is indeed a sucient (and, under some additional qualications, necessary) condition for fairness reversal.
In this section we provide theoretical explanations of the empirical observations made in the previous section. We start with singlevariable classiers and then proceed to generalize our observations to multi-feature classiers. Our key nding is that selectivity (dened next) is in fact a sucient condition for fairness reversal, providing a theoretical underpinning for the empirical observations above. Additionally, we investigate the underlying causes of fair classiers becoming more selective, and provide conditions on the underlying distribution for this to be the case. In the cases of single variable classiers with feature-monotonic costs and multivariable classiers with outcome-monotonic costs, we further demonstrate that selectivity also leads to accuracy reversals (strategic behavior causes the fair classier to become more accurate than the conventional model), and outline conditions on the underlying distribution such that selectivity is not just sucient, but also necessary for both of these phenomena. When strategic agent behavior results in both a fairness and accuracy reversal, the functionality of both classiers has fundamentally swapped; the accuracy driven (conventional) model 5 ⇠ is no longer the most accurate model and the fairness driven (fair) model 5 is no longer the most fair model. Prior to our results, we rst formalize the notion of classier selectivity. Denition 5.1. Let X 5 ⇠ = {x 2 X : 5 ⇠ (x) = 1} and X 5 = {x 2 X : 5 (x) = 1}. We say that 5 is more selective than
That is, 5 is more selective than 5 ⇠ if the set of positively classied examples under 5 is a subset of those positively classied under 5 ⇠ . While this denition of selectivity is slightly more restrictive than the type of selectivity found in our empirical results, the subset propriety is a driving force behind the fairness reversals observed in practice. Selectivity can be interpreted as the fair model 5 , achieving fairness by "excluding" additional agents from positive classication, compared to 5 ⇠ . As an example, under PR-based fairness let ⌧ 0 be the group with lower PR and ⌧ 1 be the group with higher PR under 5 ⇠ (TPR and FPR hold similarly). A model designer could improve the fairness of 5 ⇠ by positively classifying more agents in ⌧ 0 or negatively classifying more agents in ⌧ 1 (or a combination of both). In the latter case, members of ⌧ 0 are "excluded" from positive classication, and the resulting model is considered to be more selective. Note that this type of exclusion is precisely the means through which fairness is achieved in Figure 2 (center).
We begin our theoretical exploration of fairness reversals with an exemplar case: a single variable threshold classier. In this setting agents possess a single ordinal feature G. For simplicity we demonstrate our results for a continuous feature G 2 [0, 1], but the results hold for any ordinal feature (discrete or continuous) . Both the conventional classier (selected for maximal accuracy) and fair classier (selected for a weighted combination of accuracy and fairness with respect to a fairness metric ") can be expressed as a single parameter \ ⇠ , \ 2 [0, 1] respectively where
Our rst result is that in single-feature classication, higher selectivity of the group-fair classier (i.e. \ ⇠ < \ ) is sucient for fairness reversal. Theorem 5.2. Suppose fairness is dened by PR, TPR, or FPR, 2 (G, G 0 ) is monotone in |G 0 G |, \ ⇠ is the most accurate, and \ the optimal U-fair, threshold. If \ ⇠ < \ , then there exists a budget ⌫ that leads to fairness reversal between 5 and 5 ⇠ . P S. The full proof is provided in Section B of the Supplement. Here we provide a proof sketch for continuous 2, a similar line of reasoning, with a few additional edge cases, holds for discontinuous 2. The unfairness of threshold \ w.r.t. to the distribution D and fairness metric M 2 {PR, TPR, FPR} is expressed as,
For a given threshold \ and manipulation budget ⌫ the best response of an agent with true feature G is
When agents from D play this optimal response, let the resulting distribution be D
(2,⌫) \
. The dierence in unfairness between classiers when agents are strategic is * D (2,⌫)
Since both 5 ⇠ and 5 are thresholds, and 2 is feature-monotonic, the decisions of \ ⇠ , \ on the modied distribution D (2,⌫) on the original distribution D, i.e.,
where
Given these modied threshold, we see that strategic agent behavior results in a lowering of each threshold as more agents are now able to achieve positive classication; this is due to the fact that only negatively classied agents will behavior strategically, their goal being to achieve positive classication. Moreover, when considering
⌫) as functions of ⌫, both are monotonically decreasing in ⌫ (due to the the monotonicity of 2), and
Since fairness is dened in terms of PR, FPR, or TPR the constant function 5 (G) = 1 has unfairness 0 for any distribution. Thus,
0 and the boundedness of 2 (G, G 0 ). Since * D 0 and 2 is continuous, there must exist some Y > 0 such that over the interval
then a fairness reversal has already occurred for budget ⌫ 0 Y, so assume otherwise. Combining the dierence in relative fairness for budget ⌫ 0 Y with the fact that \
(2,⌫) ⇠ \ (2,⌫) for all ⌫, we get
Since 2 is monotonic and continuous there must exist some budget
Since ⌫ ⌫ 0 Y, and * D (\ (2,⌫) ⇠
) is decreasing for ⌫ ⌫ 0 Y, it must be the case that
and a fairness reversal occurs for budget ⌫ . ⇤
We now turn our attention to a complementary observation: fairness reversal is accompanied by accuracy reversal, that is, strategic behavior leads to 5 having higher accuracy than 5 ⇠ . This is primarily due to the fact that 5 becomes more selective and therefore more resilient to manipulation. Note that the fairness reversal and accuracy reversal need not occur for the same budget ⌫. Theorem 5.3. Suppose fairness is dened by PR, TPR, or FPR, 2 (G, G 0 ) is monotone in |G 0 G |, \ ⇠ is the most accurate threshold, and \ the optimal U-fair threshold. If \ ⇠ < \ , then there exists a budget ⌫ s.t. 5 is more accurate than 5 ⇠ . P S. We defer the full proof to Section B of the Supplement and again give a proof sketch for continuous 2. The error of threshold \ on distribution D is given by
By the denition of \ ⇠ , we have
and therefore L D (\ ⇠ ) L D (\ ). Similar to the proof of Theorem 5.2, agents strategically responding to threshold classiers \ ⇠ , \ can be viewed as modied thresholds \ ) < P(~= 0)}, i.e. ⌫ 0 is the "largest" manipulation budget such that the conventional threshold is not a trivial classier (i.e., not making constant predictions) in the presence of strategic agent behavior. In a similar line of reasoning to the case of fairness reversals, there must exist some interval [⌫ 0 Y, ⌫ 0 ] over which L D (\ (2,⌫) ) is strictly increasing. Again, by the fact that \ ⇠ < \ , there must exist some
implying that an accuracy reversal occurs for budget ⌫ . ⇤
We have showed thus far that selectivity is sucient for fairness and accuracy reversals, but under what conditions is it also necessary? Loosely speaking, when a feature G is a good predictor of both ~and 6, the error and unfairness of 5 ⇠ and 5 are unimodal (dened next) with respect to the manipulation budget ⌫. Unimodality is relevant to fairness and accuracy reversals as we will see that when error is negatively unimodal and unfairness is positively unimodal, both fairness and accuracy reversals occur. We empirically demonstrate that unimodality of both functions holds frequently on real data. The condition of unimodal error and unfairness can be interpreted as both functions possessing a "sweet spot" which yields best case accuracy (or worst case unfairness). In the former, G is good predictor of true label ~and in the latter G is a good predictor of 6.
As an example, in Figure 3 we see this phenomenon occur on the Law School dataset when using a student's LSAT score as the predictive feature x. Both error and unfairness (in terms of positive rate dierence between groups) are both unimodal in the threshold \ . In this, we observe that LSAT score is a good predictor of both the target variable (bar passage) and the sensitive feature (race); this is a well established source of bias within this particular dataset.
We further document this relationship in Section E.4 of the Supplement and nd that most ordinal features produce threshold classiers which have (approximately) unimodal error and unfairness. In this section we also theoretically outline the precise conditions under which error and unfairness would be unimodal; these conditions essentially boil down to a correlation between ~|G and 6|G, (which we observe to be the case for most ordinal features across the datasets we study). When this occurs, the selectivity of 5 is not only sucient for fairness and accuracy reversals, but also necessary. We next formalize this in the following theorem; further details on the necessary and sucient conditions required for fairness and accuracy reversals are provided in Section B of the Supplement.
Theorem 5.5. Let \ ⇠ and \ be the most accurate and optimal fair classiers respectively. Suppose fairness is dened by PR, FPR, or TPR, and 2 (x, x 0 ) is outcome monotonic, and that error (and unfairness) are negatively (positively) unimodal in \ . Then there exists a budget ⌫ such that strategic agent behavior leads to a fairness reversal if an only if 5 is more selective than ⇠ .
. When error L D (\ ) and unfairness * D (\ ) are both unimodal in \ , the optimal conventional threshold \ ⇠ and optimal U-fair threshold \ can be expressed in terms of the inection points G L and G * of error and unfairness respectively. The most accurate threshold is then \ ⇠ = G L , and the most unfair threshold (2,⌫) be the modied thresholds induced by agents best responding to either threshold with cost function 2 and budget ⌫. Then, since \ ⌫) are monotonically decreasing in ⌫ and \ ⇠ < \ , there must exist a ⌫ 0 such that \
and
implying that a fairness and accuracy reversal occurs for budget ⌫ 0 . The reverse direction, follows from the relationship between \ and the two inection points \ ⇠ , \ * . Given the assumption that \ < \ ⇠ , there are only three possible cases for the relationship between these points
the strict inequalities being due to the fact that \ < \ ⇠ and \ < \ * by denition. In cases ( 1) and ( 2), no fairness or accuracy reversal can occur. Only in case (3) can a fairness or accuracy reversal occur, however we will show by contradiction that such a case is impossible.
Beginning with case (1), both error and unfairness are unimodal in \
(2,⌫) , \
, each of which is monotonically increasing in ⌫. Since unfairness in unimodal, any \ \ * and any ⌫ 0 unfairness * (\ (2,⌫) ) is monotonically decreasing in ⌫. Similarly, since error is unimodal, for any \ \ ⇠ , error L(\ (2,⌫) is monotonically decreasing. Thus if \ < \ ⇠ , then no accuracy reversal can occur. Similarly if \ < \ ⇠ \ * , no fairness reversal can occur, i.e. in case (1), neither reversal can occur.
In case (2) since * D (\ ) < * D (\ ⇠ ), and * D (\ (2,⌫) ⇠
) is monotonically increasing until \
(2,⌫) ⇠ = \ * , no fairness reversal will occur. Similar to case (1), \ < \ ⇠ , implies that no accuracy reversal occurs either.
Thus it remains only to show that case (3) can never occur. To see this, note that for any 0 < Y < \ ⇠ \ , it must be the case that both
Which implies that \ is in-fact not the optimal fair threshold. ⇤ Now that we have established the critical role of selectivity in fairness reversal, we next analyze why that is. As mentioned previously, there are roughly two ways to achieve fairness: inclusiveness (classifying more examples as positive) or selectivity (classifying fewer examples as positive). Which of these will be the predominant outcome of training 5 depends intimately on the data distribution. We outline these conditions, as well as conditions for error and unfairness to be unimodal, via Lemmas B.4, B.5, and Theorem B in the Supplement. In particular, Theorem B provides conditions on the underlying distribution such that the optimal fair classier will achieve fairness via selectivity. The condition in this theorem can be intuitively interpreted as follows. Suppose that ( is the set of individuals selected (i.e., classied as 1) by 5 ⇠ , who are also near the decision boundary of 5 ⇠ . If the advantaged group (i.e., group with better average outcomes) is overrepresented in (, there is a range of parameters U such that the optimal U-fair classier is more selective than 5 ⇠ (recall that higher U places greater importance on group-fairness in learning).
Next we discuss general multi-variate classiers, generalizing several of the results from Section 5.1. First we show that when 5 is more selective than 5 ⇠ , fairness reversal occurs for both featuremonotonic and outcome-monotonic cost functions. Second, we give conditions which lead to 5 being more selective than 5 ⇠ . For outcome-monotonic costs, we provide two additional results: 1) greater selectivity of 5 also leads to accuracy reversal, and 2) unimodality of each classier's error and unfairness causes selectivity to be both necessary and sucient for fairness and accuracy reversal.
Outcome-Monotonic Costs. We begin with the case of outcomemonotonic costs. As shown by Milli et al. [32], outcome-monotonic manipulation costs result in the following best response for classier 5 . Let
If 2 (x, x ⇤ ) ⌫ then the best response is x 0 = x ⇤ otherwise x 0 = x. With this best response in hand we show that 5 having greater selectivity than 5 ⇠ leads to fairness reversal. Theorem 5.6. Let 5 ⇠ and 5 be the most accurate and optimal fair classiers respectively. Suppose fairness is dened by PR, FPR, or TPR, and 2 (x, x 0 ) is outcome monotonic. Then if 5 is more selective than 5 ⇠ , there exists a budget ⌫ such that strategic agent behavior leads to a fairness reversal.
Here we provide a proof sketch of this and other results; complete proofs are deferred to the Supplement (Section C). P . For a given classier 5 , let
and let x min be the feature associated with ? min (x min,⇠ , ? min,⇠ and x min, , ? min, correspond to 5 ⇠ and 5 respectively). When agents best respond to 5 the resulting manipulated classier can be expressed as a threshold on the underlying probabilities P(~= 1|x). More specically, let
Then when agents best resound to 5 (inducing classier 5 (2,⌫) ) any agent x with P(~= 1|x) P(~= 1|x ⇤ ) will be positively classied under 5 (2,⌫) , i.e. 5 (2,⌫)
Thus 5 (2,⌫) can expressed as the threshold P(~= 1|x ⇤ ) operating on the conditional distribution P(~= 1|x).
Since 5 is more selective than 5 ⇠ , (i.e., for any x 2 X, if 5 (x) = 1 then 5 ⇠ (x) = 1), and x min, is positively classied under 5 , we have, 5 (x min, ) = 1 = 5 ⇠ (x min, ) and therefore ? min,⇠ ? min, Therefore the induced conventional and fair thresholds P(~= 1|x ⇤ ⇠ ) and P(~= 1|x ⇤ ) acting on P(~= 1|x) have the relationship that P(~= 1|x ⇤ ⇠ ) P(~= 1|x ⇤ ⇠ ). Thus, we see that selectivity of the fair classier in the case of outcome-monotonic costs yields a fair threshold (on a modied distribution) which is larger than the induced conventional threshold (operating on the same distribution as the fair threshold).
While this setting is not entirely equivalent to the single variable case, the remainder of the proof follows in similar fashion to that of Theorem 5.2. In particular, the monotonicity of P(~= 1|x ⇤ ), as a function of ⌫, implies P(~= 1|x ⇤ ⇠ ) P(~= 1|x ⇤ ) for any ⌫, which in turn implies the existence of a budget interval over which the unfairness of 5
(2,⌫) ⇠ decreases below 5 (2,⌫) , thus resulting in a fairness reversal. ⇤
Similar to the single-variable case, selectivity also result in accuracy reversal.
Theorem 5.7. Let 5 ⇠ and 5 be the most accurate and optimal fair classiers respectively. Suppose fairness is dened by PR, FPR, or TPR, and 2 (x, x 0 ) is outcome-monotonic. Then if 5 is more selective than 5 ⇠ , then there exists a budget ⌫ under which 5 becomes more accurate than 5 ⇠ .
P. The full proof (which follows from a similarly Theorem 5.3, 5.6) is deferred to Section C of the Supplement. ⇤ Before outlining settings in which selectivity is not only sucient but also necessary for fairness and accuracy reversals to occur, we rst remark on the connection between selectivity, accuracy, and fairness. As previously noted, errors caused by strategic agent behavior are single-directional in the sense that manipulation can only induce false positive errors. As such, classiers which are more selective are thus more robust to manipulation than their less selective counterparts. Generally speaking, this implies that for some range of manipulation budgets, a model that is more selective than the accuracy-maximizing model 5 ⇠ will increase in its performative ability compared to 5 ⇠ . As the performative ability of most classiers on biased datasets is naturally tied with unfairness, the unfairness of the more robust model (more selective model) will likewise increase. Thus, we see a fundamental, albeit not necessarily universal, connection between selectivity (which in turn increases robustness) and model unfairness (which is increasing in model performance).
We next discuss unimodality in the context of outcome-monotonic costs. Empirically we observe that when costs are outcome-monotonic, the majority of classiers tend to have error and unfairness which is (approximately) unimodal with respect to the manipulation budget ⌫. When this occurs, selectivity of 5 becomes both necessary and sucient.
Theorem 5.8. Let 5 ⇠ and 5 the optimal conventional and fair classiers respectively. Suppose fairness is dened in terms of PR, TPR, or FPR fairness, and 2 (G, G 0 ) is outcome-monotonic. When error (and unfairness) are negatively (positively) unimodal with respect to the manipulation budget ⌫, a fairness and accuracy reversal will occur between 5 and 5 ⇠ if and only if 5 is more selective than 5 ⇠ (each reversal may occur at dierent budgets ⌫) . P S. We deer the full proof to Section C of the Supplement. The intuition for this proof follows similarly to that of Theorem 5.5. As shown in the proof of Theorem 5.6 when agents best respond to classier 5 , the decisions of 5 can be expressed as threshold classier acting on the conditional probability P(~= 1|x) of the original distribution D, namely
where x ⇤ is determined by the cost function 2 and budget ⌫. Since P(~= 1|x⇤) is monotonically decreasing in ⌫, we recover a setting similar to 5.5, in which the forward direction of the claim holds from the fact that, P(~= 1|x ⇤ ⇠ ) P(~= 1|x ⇤ ), for all ⌫. While the reverse direction holds due to the fact that when x ⇤ x ⇤ ⇠ , unfairness is monotonically decreasing for both classiers. ⇤ Remark 5.9. To better contextualize unimodality of error and unfairness with respect to the manipulation budget ⌫, we can view this condition in terms of the calibration of the score function ⌘ of the classier 5 . As is typical, classiers are dened via thresholds on their underlying score functions, i.e. 5 (x) = I[⌘(x) \ ]. Suppose that ⌘ is reasonably well calibrated, then for every ? 2 [0, 1], P(~= 1|⌘(x) = ?) ⇡ ?, i.e. ⌘(x) is a good approximation of the conditional distribution given by P(~= 1|x). When ⌘ is reasonably well calibrated, the condition that error and unfairness are unimodal w.r.t. to the manipulation budget ⌫ is equivalent to the error and unfairness of 5 being unimodal w.r.t. to the choice of threshold \ . Through this lens, one can see that the assumption of unimodality is likely to hold (at least approximately so) in practice as it is typically the case there is one "good" choice of threshold \ and any deviation (increasing or decreasing \ ) results in strictly worse performance of 5 .
Feature-Monotonic Costs. Finally, we demonstrate that selectivity remains sucient for fairness reversal in general when costs are feature-monotonic.
Theorem 5.10. Let 5 ⇠ and 5 be the most accurate and the optimal U-fair classier, respectively. Suppose fairness is dened by PR, FPR, or TPR and 2 (x, x 0 ) is feature-monotonic. If 5 is more selective than 5 ⇠ , then there exists a budget ⌫ that leads to fairness reversal between 5 and 5 ⇠ . P S. The full proof is deferred to Section D of the Supplement. The intuition behind this results is that trivial classiers (i.e., those that predict 5 (x) = 1 for all x) have 0 unfairness for PR, FPR, and TPR based fairness. As ⌫ increases, both 5
(2,⌫) ⇠ and 5
(2,⌫) (the classiers resulting from agents best responding to either classier with budget ⌫ and cost function 2) will approach 0 unfairness, not necessarily monotonically, as they become more like trivial classiers. At some point prior to reaching trivial classication, the conventional classier 5 ⇠ will be at least as fair as 5 . This can be seen through a combination of the fact that 5 is more selective than 5 ⇠ and the way in which manipulations alter the positively predicted region of a classier when costs are featuremonotonic. In particular, 5 being more selective than 5 ⇠ implies that, {x 2 X :
Feature-monotonic cost functions preserve this subset propriety under manipulation, i.e., for any ⌫,
Thus 5 is always more selective than 5 ⇠ , regardless of the manipulation budget ⌫. As such, the positive rate of 5 will never exceed the positive rate of 5 ⇠ , implying that 5 (2,⌫) approaches a trivial classier more "slowly" than 5
(2,⌫) ⇠
, with respect to ⌫. Moreover, prior to approaching triviality 5 (2,⌫) will eectively approach 5 ⇠ , thus partially absorbing some of the original unfairness of 5 ⇠ , resulting in a fairness reversal. ⇤
Next, we provide a condition which leads 5 to be more selective than 5 ⇠ . Here, we provide this condition for the PR fairness metric; analogous results for TPR and FPR are given in Section D of the Supplement. For this result, we dene the following notation % ⌧ I = P(6 = I), 6(x) = % (6 = 1|x) and X 0 = {x 2 X : 6(G) < % ⌧ 1 and P(~= 1|x) < 1 /2}.
The set X 0 represents the set of features which are less likely than chance to correspond to 6 = 0 and ~= 0.
Theorem 5.11. Let 5 ⇠ and 5 be the most accurate and optimal U-fair classiers respectively, and fairness dened by PR. Then 5 is more selective than 5 ⇠ if and only if 0 < U U ⇤ , where
6 (x)+% ⌧ 1 % ⌧ 1 26 (x) 2% ⌧ 1 P(~=1|x)
. P. Both the conventional and fair objectives can be written as follows:
(1 U)2P(~= 1|x) + 1 0 and 5 ⇠ (x) = 1 is optimal if P(~= 1|x) P(~= 1). Thus, the only case in which 5 positively classies an example x, which is negatively classied by 5 ⇠ (i.e., 5 5 (x) = 1 < 5 ⇠ (X) = 0), is when the left-hand side of Inequality 1 is nonnegative and P(~= 1|x) P(~= 1). Simplifying the condition in Equation ?? yields U ⇤ . ⇤
The key observation from Theorem 5.11 is that fairness reversal is a small-U phenomenon. This may seem surprising, since 5 is likely to be most similar to 5 ⇠ for smaller values of U (in particular, the two are identical when U = 0). However, when U is high, the fairness term is suciently dominant that reversals are unlikely. Consequently, it is precisely the intermediate values of U, where we aspire to preserve high accuracy while improving group-fairness that are most susceptible to fairness reversal. This is indeed consistent with our empirical observations in Section 4, which indicate that for intermediate values of U fairness reversals are not only more common, but occur with greater magnitude. Lastly, note that for some distributions, U ⇤ 0, which means that fairness reversals are luckily not guaranteed. Remark 5.12. For some classiers and agent distributions, fairness reversals are straightforward to prevent. We outline several of these cases in Section D.1 of the supplement.
We demonstrate a fairness-reversal phenomenon, where a trainedto-be fair classier exhibits more unfairness than the conventional accuracy-maximizing one if human agents can strategically respond to a classier. We show that a sucient condition for observing fairness reversal is "selectivity", that is, a group-fair classier making fewer positive predictions than its conventional counterpart. Additionally, we demonstrated that this condition of "selectivity" also results in an accuracy reversal. The aggregate of these results indicates that when fairness is achieved through an overall decrease in positive rate (compared to the conventional classier), strategic agent behavior can lead to a reversal of the core functionality of both models (i.e., the performance based model becomes less accurate than the fair model, and the fair model becomes less fair than the fairness-agnostic model).
We view these results not as a critique of fair-learning, but rather as a caution towards the expectation of fairness guarantees when a fair classier sees real-world deployment. The successful deployment of fair-learning models requires the consideration of many nuanced factors, strategic agent response to model choice being on such consideration. While we have outlined several necessary and sucient conditions regarding both classier selectivity as well as fairness reversals, a deeper investigation into when fair classiers may suer from such problems in cases where the classier s designed to anticipate strategic behavior. Mitigating fairness and accuracy reversals is an important direction for future work.