RAGUEL: Recourse-Aware Group Unfairness Elimination

We define a database $D$, with $D$ records, in which each record is represented as a vector $x\in R^m$ with $m$ attributes such that $x=\{x_1,x_2,\dots ,x_m\}$. A fundamental part of our setting is the notion of recourse cost, which is the difficulty of changing a prediction by taking feasible actions to alter attribute values (Ustun et al., 2019). When we extend this to ranked lists, recourse cost is the difficulty of the actions to reach some ideal point or hyperplane (e.g., the top of the ranking). This chosen target is the counterfactual point $x^{\prime }$, calculated as: $x^{\prime }={argmin}_{x^{\ast }\in X^{\ast }}d(x,x^{\ast })$. Here, $d(x,x^{\ast })$ denotes the distance function that quantifies the cost of the actions required to transfer from $x$ to $x^{\ast }$. That is, given a set of candidate counterfactual points $X^{\ast }$, the counterfactual point to $x$ is the point $x^{\prime }\in X^{\ast }$ that has the minimum distance to $x$.

For settings involving a classifier, we generate counterfactuals by considering the minimal actions to reach the decision boundary (e.g., negatively classified points trying to change their outcome). We use $f:R^m\to \{-1,1\}$ to denote the decision-making model that classifies records into two classes. This assumption is without loss of generality since any multi-class classifier can be considered as a stack of several binary classifiers. In this setting, $X^{\ast }$ is the set of all candidate counterfactual points lying on the classifier boundary. For general ranking problems, we assume a single counterfactual point – the point at the top of the ranking – therefore we have $X^{\ast }=\left\{x^{\prime }\right\}$. This can be generalized in future work by determining recourse with respect to multiple possible counterfactual points.

The recourse cost $c\left(x\right)$ is defined as the cost to reach $x^{\prime }$ from $x$. That is, $c\left(x\right)=d(x,x^{\prime })$. In Example 1 (Section 3.4), the ‘Cost’ column of Table 2 reflects these recourse values based on the weighted Euclidean distance to the corresponding counterfactual on the boundary line, as seen in Figure 1. In our method for increasing fairness in representation and recourse, a chosen point, $x$, is modified towards its counterfactual point, $x^{\prime }$, and $\tilde{x}$ denotes this modified point.

The database (or any subset thereof) can be divided into sub-groups, denoted as $S_j$, according to some protected attribute (e.g., gender, race, marital status) for which we are interested in evaluating fairness of representation and recourse. Without loss of generality and as is common practice in literature (Pitoura et al., 2021; Huan et al., 2020), we illustrate our approach for two sub-groups, $S_1$ and $S_2$, and they are composed such that $|S_1\cup S_2|=D$ and $|S_1\cap S_2|=0$. In any pair of sub-groups, where one sub-group contains records with a protected attribute, $p$ denotes the proportion of the global database with this protected characteristic. That is, $p=|S_2|/D$, assuming $S_2$ contains the records associated with the protected characteristic. This represents the ideal proportion of protected records in any subset of the database.

$X_k$ denotes some ordered subset of $D$ containing $k\le D$ points and the proportion of $X_k$ that consists of records with the protected attribute is $p_k$. Finally, in our block-based approach, we segment the database into $B$ blocks, with each block $b$ as part of the set $B$.

We first introduce the simplest definition of fairness given two sub-groups, which ensures that their proportional representation in any subset correctly reflects that in the database.

Given an ordered subset $X_k$, we can extend this definition to recursively hold for ordered subsets of the database.

Definition 3.2 is a reformulation of the sufficient condition for ranked group fairness in FA*IR (Zehlike et al., 2017). However, while this definition aims to achieve balanced representation for every subset $X_i$, it does not take the cost of recourse into account. Therefore, we propose ‘ranked group-level recourse fairness’ as a constraint in the ranking.

To measure ranked fairness with respect to recourse, we first formalize the notion of recourse fairness between two sub-groups. The ‘group-level recourse fairness ratio’, $r$, assesses how balanced two sub-groups are in terms of the average cost of recovery actions:

where $M_1$ and $M_2$ are the mean recourse costs for $S_1$ and $S_2$ respectively, defined as: $M_j=\frac{1}{|S_j|}{\sum }_{x_i\in S_j}c\left(x_i\right)$. Near-ideal fairness is represented by $r$-values close to 1, as the mean recourse costs for both sub-groups are similar, whereas $r$-values close to zero show that one sub-group is severely disadvantaged when trying to recover from an unwanted outcome.

Recourse fairness therefore ensures that the two sub-groups maintain a ratio of their mean recourse costs that is within some tolerance $\varphi$ (distinct from $ϵ$). This may be extended to an ordered subset $X_k$ in a manner similar to Definition 3.2, as described below.

Given a dataset $D$, we first obtain the ordered set $X_D$ by ranking records according to their recourse costs to reach the chosen counterfactual points. The goal is to identify the actions needed to construct an ordered set of modified points ${\tilde{X}}_D$ such that ${\tilde{X}}_D$ satisfies Definitions 3.2 and 3.4, whilst ensuring that we minimize the extent of the modification, i.e., $min\frac{1}{D}{\sum }_{i}d(x_i,{\tilde{x}}_i)$.

We illustrate our solution in the context of loan applications. We also discuss how RAGUEL can be applied to ranking-based problems such as fair webpage ranking.

1. Recourse-aware Loan Evaluations. Consider four loan applicants who have been rejected and placed onto a ranked waiting list. Abdul (rank #1) and Bogdan (#2) identify as male whereas Chiara (#3) and Diana (#4) identify differently. Table 2 and Figure 1 show this ranked list and the subsequent recourse-fair re-ranking after applying RAGUEL. In this example, the recourse cost is the cost for negatively classified points to reach their counterfactual points on the classifier boundary (i.e., the loan being granted) considering only the loan amount (LA) and loan duration (LD). Each applicant (user) is capable of specific actionable changes, such as changing the requested loan amount in $50 increments, or changing the duration of the requested loan in one year increments. Initially, despite fair representation, the average cost of recourse is higher for non-male customers, which may be due to them facing greater barriers towards gaining credit (as previously claimed in the real world (e.g., Garrison, 1976; Ladd, 1982; Alesina et al., 2013)). As a result, the bank (platform) may be interested in making conditional loan offers to lessen the extent of this disparity, subject to regulations. The platform’s goal here would be to re-rank the list to achieve recourse fairness via minimal interventions (e.g., for widening participation of disadvantaged customers, or for inclusive representation due to policies and regulations). Since the top of the ranking shows disproportionate under-representation of female customers, RAGUEL identifies potential actions for Chiara (e.g., providing proof of her ability to cover $550 from other sources) that would move her up in the ranked list (e.g., a better chance of acceptance with a slightly smaller loan amount offered). In doing so, the bank improves ranked recourse fairness by enabling the disadvantaged group to perform actions to meet their conditional acceptance criteria. An alternative outcome is that the bank chooses to offer loans to applicants from the list (e.g., due to an availability of more funds), where candidates higher up in the list (now including Chiara) would secure their requested loans. RAGUEL provides a mechanism for both fair representation and fair recourse for all sub-groups with minimal re-ranking.

To utilize the block-based solution, the bank can generate equally-sized ‘blocks’ containing two individuals each, with individuals from the first block (Abdul and Bogdan) being offered a lower interest rate. Chiara might be offered conditional acceptance at the lower rate, provided she requests a shorter loan amount, moving her into the first block. If the bank has blocks containing four individuals, the block would already appear balanced with respect to gender, and no recourse would need to be offered.

2. Recourse-Aware Webpage Rankings. RAGUEL can be applied to any ranked list, such as top-$k$ query results. Consider a set of web-pages (users), all of which would like to be listed on the first page of the search engine (platform) results (i.e., the top-10 web-pages). Unlike the case of loan applications, there is no classifier boundary, and the counterfactual is the query itself. Webpages are ranked by their recourse costs, derived simply based on the difficulty of reaching the counterfactual. It is in the search engine’s best interests to strive for “fair” ranking across all categories of web-pages (e.g., business, education, entertainment), while the organizations running the web-pages would like to know what recourse options they have to move up in the ranking (e.g., to help guide their search engine optimization). Considering recourse costs helps to identify the interventions (e.g., mobile-friendly formatting, faster page loading, adding hyperlinks) that can enable re-ordering with minimal cost. If the search engine were only concerned with achieving recourse fairness on each page of results, the less granular block-based solution can be applied, with each block representing a page of search engine results.

RAGUEL produces a ‘recourse-aware ranking’ that corrects group-level imbalances in terms of recourse and representation. The first step computes the recourse cost for each record to reach the relevant counterfactual point. Second, the records are ranked, in ascending order, according to their recourse costs. RAGUEL then identifies the minimal interventions applied to points such that the re-ranked list mitigates (or eliminates) any (group-level) unfairness. RAGUEL can also be extended to a block-based approach in which the ranking is subdivided into a finite number of blocks.

RAGUEL can be extended in a number of directions, which we briefly discuss here. First, as alluded to in Section 3.1, to cater for multi-class classifiers, one can stack several binary classifiers. That is, fairness can be ensured across all outcomes by considering all possible one-versus-rest binary classifiers.

Second, our fairness definitions (and mechanism) can be generalized for more than two sub-groups. For example, a company may want to consider fairness between under-18s, adults, and over-65s. In this case, Definition 3.1 can be formalized such that $X$ only offers fair representation if $|p_X-p_i|\le ϵ$ for all protected sub-groups. A revised Definition 3.2 follows naturally. For Definition 3.4, the redefined $r$ must consider fairness between multiple sub-groups. For $n$ sub-groups, the group-level recourse fairness ratio is:

Finally, RAGUEL can also be applied to non-linear models (e.g., neural networks) when recourse-unaware methods are used to compute counterfactuals and initial rankings. Although methods are yet to be defined that can declare unfairness of recourse in non-linear settings (Ustun et al., 2019), doing so, and incorporating recourse weights to determine these rankings, are interesting research challenges.

We apply RAGUEL to the challenge of automated customer credit and liability decision-making using the ‘German Credit’ (Dua and Graff, 2017), ‘Default of Credit Card Clients’ (DC3) (Dua and Graff, 2017), and HMDA ((FFIEC), 2021) datasets. The German Credit dataset contains 1,000 records and has 20 features relating to individuals’ financial and personal details, such as purpose of loan, missed payments, and marital status. A binary class label indicates individuals who are (un)successful in their loan application. The DC3 dataset has 30,000 records and 24 features, and class labels indicating individuals who default on their payments. For both datasets, we convert categorical attributes into actionable numerical attributes (e.g., length of employment) or binarize them (e.g., has guarantor), and aggregate some columns (e.g., months with zero balance) to construct more relevant features that can easily reflect infeasible recourse weights. After these modifications, the German Credit and DC3 datasets have 18 and 10 features, respectively. The HMDA dataset is based on the Home Mortgage Disclosure Act by the US government, and reports public loan data that can be filtered by year, geography, financial institution, and features such as the type/purpose/duration of loan, gender/race of applicants, or property type. The original data comprises over 25M records, with 5M of these loans being clearly labeled as accepted/rejected. The 93 feature columns are filtered down to 26 where only the columns that reflect aggregated data are preserved. This large HMDA dataset is only used for scalability experiments on RAGUEL, since none of the baselines can operate on this many records. We assume that all attributes are independent of each other in these datasets. We consider marital status as the protected attribute from literature for German Credit and DC3 (Kang et al., 2021; Bhargava et al., 2020) and use gender for HMDA (as the marital status attribute is unavailable). As the classifier boundary (i.e., threshold) is defined based on the accept/reject labels in the real data, we only consider this boundary. Alternative thresholds are possible (as are other types of classifiers).

We first examine the effect of existing post-processing techniques, which are designed to improve fairness by re-classifying data points. ‘Demographic parity’ ensures that the acceptance rate is equal across sub-groups. ‘Equalized odds’ (and its relaxed version, ‘equal opportunity’) instead enforces fairness only among individuals who reach similar outcomes, by equalizing false positive/negative error rates or both (‘weighted’) (Hardt et al., 2016; Pleiss et al., 2017). While these methods do have different objectives, we include them to indicate how existing fairness definitions do not subsume the recourse-based definition and, as shown in Table 3, when these methods fail to improve recourse fairness, they actually exacerbate the problem significantly. The ‘Recourse Cost’ column demonstrates how RAGUEL’s aggregate weighted distance measure across sub-groups is lowered compared to the initial ranking, whereas measures that shift the classifier boundary worsen this distance. This means that disadvantaged individuals under the post-processed classifier model would face even greater difficulty in improving their classification outcome. RAGUEL, however, increases recourse fairness by 15% compared to the initial data, and up to 200% compared to the alternatives, whilst also needing fewer points to be modified. RAGUEL-Block reduces the cost of interventions (difference in recourse cost) by 130% compared to RAGUEL. This guarantees that the re-ranked list remains closer in accuracy to the original ranked list, due to looser, less granular fairness constraints.

Table 3 also includes results for two fair-ranking methods – FA*IR (Zehlike et al., 2017) and FoEiR (Singh and Joachims, 2018). FA*IR hurts recourse fairness and can only select up to 400 points, with RAGUEL attaining a ratio that is 37% better. FoEiR can only re-rank up to 50 points due to inefficiency, but uses an exposure utility measure that can slightly improve recourse, although not as well as RAGUEL. Average results over 50 trials are presented for both. The smaller German Credit data exhibited similar characteristics and is therefore omitted.

Table 4 compares our explainable and efficient approach against two alternatives for generating counterfactuals. MACE (Karimi et al., 2020a) uses formal verification techniques and satisfiability solvers to generate counterfactuals, whereas AR (Ustun et al., 2019) enumerates feasible “flipsets” (counterfactuals) for recommending and auditing recourse. We present a qualitative comparison in terms of average closeness to the training data (Euclidean distance of counterfactual to nearest neighbor), average sparsity (number of attributes modified), and average runtime (per counterfactual generated) (Verma et al., 2020). RAGUEL sometimes shows higher sparsity as different recourse weights may mean that smaller modifications are made to a higher number of attributes. However, our resulting counterfactuals are much closer to the original distribution of points, which is ultimately more important. The efficiency of RAGUEL is comparable with that of AR, and both outperform MACE. Note that MACE and AR merely identify counterfactual points but do not modify the data, classification, or ranking. Hence, their influence on ranking fairness can only be measured in tandem with other methods for fair ranking.

We now consider RAGUEL’s effectiveness at re-ranking $D$ to achieve improved recourse fairness. Before doing so, we introduce the user-specified ‘tolerance’ parameter, $\tau$, which is used to determine the value for $ϵ$, where $ϵ=\tau \times p$. Our default setting is $\tau =\frac{1}{3}$. For example, if 30% of the database belongs to a protected sub-group and $\tau =\frac{1}{3}$, then $ϵ=30\times \frac{1}{3}=10\%$. This means that the proportion of protected individuals in each block should be in the range 30$\pm$10%.

We compare RAGUEL with state-of-the-art fair ranking baselines, where points are originally ranked according to their distance to counterfactuals, as computed by each of the counterfactual generation methods from Section 4.3. FA*IR (Zehlike et al., 2017) selects the top-$k$ points ranked by relevance scores, to satisfy demographic parity without compromising on selection utility. FoEiR (Singh and Joachims, 2018) balances exposure allocation in terms of three different fairness definitions (demographic parity, DP; disparate treatment, DT; and disparate impact, DI). Since FA*IR was infeasible on larger datasets, we report the average values over 50 trials, sampling 400 points each time. Empirically, we find that setting $\alpha$, which is a FA*IR-specific parameter, to 0.15 offers the best results and we use this setting throughout. Similarly, FoEiR could only handle 50 points, and so we similarly obtain average results after 50 trials. In comparison, RAGUEL runs efficiently (¡2.5 seconds) on both full datasets, and it is 4x faster than FoEiR on its smaller sample.

We evaluate these results with respect to different ranking quality metrics (normalized discounted KL-divergence, rKL; normalized discounted difference, rND; normalized discounted ratio, rRD) (Yang and Stoyanovich, 2017). rND indicates the difference between the protected sub-group’s proportion among top-$k$ records and overall, while rKL uses Kullback-Leibler divergence for the expectation of this difference. rRD computes a similar difference to rND but between the ratios of the (minority) protected sub-group to the majority.

Table 5 shows that RAGUEL generally outperforms the alternatives on both datasets, consistently maintaining or improving these ranking metrics compared to the initial ranked list. FoEiR generally achieves better scores with the recourse-unaware MACE, while FA*IR performs comparatively well with AR. RAGUEL allows any combination of techniques to be applied for re-ranking.

We now examine the effectiveness of performing block-based re-ranking by considering different granularities and strictness. We assume all blocks are equal in size with block size being governed by the number of blocks into which the ranked list is sub-divided.

Figure 2 shows how group-level recourse fairness changes with the number of blocks and the tolerance. Recourse fairness decreases as the number of blocks increases as there is a more restricted range of values into which attributes can be perturbed for re-ranking. RAGUEL-Block is relatively stable to an increase in $B$, although there is an expected decrease in $r$ as it becomes harder to satisfy the fairness constraints for small blocks. Similarly, while low $\tau$-values lead to recourse fairness being more strictly enforced within each block, a very low $\tau$-value results in increased unfairness by forcing corrections to more blocks (especially those encountered early).

We also study the effectiveness of our re-ranking approach by considering the number of unfair blocks that are transformed into fair blocks through re-ranking (Table 6). As expected, with high tolerance and very few (large) blocks, the dataset is often already deemed to be fair or it is easily made fair. As the number of blocks is increased and each block thereby becomes smaller, re-ranking has a greater impact. Notably, it is more effective to reduce the size of blocks than to reduce the tolerance, as a lower tolerance leads RAGUEL-Block to be less likely to create fair blocks.

Figure 3 shows the proportion of the two sub-groups in each block before and after re-ranking ($B=20,\tau =\frac{1}{8}$, DC3). The allowable tolerance margin around the ideal proportion, based on the overall dataset, is also indicated. Given the tolerance bound, the original dataset shows that nine of the 20 blocks are unfair initially with only five blocks remaining unfair after re-ranking. This highlights the impact of using a stricter tolerance as more unfair blocks remain, compared to that at lower $\tau$ values. However, these blocks become concentrated at the bottom of the ranking, with the last block in particular becoming more unfair as there is no opportunity for its fairness to be corrected. With a looser tolerance, earlier blocks containing slightly unfair representations can be ignored during re-ranking, which prevents later blocks from accumulating highly imbalanced outliers.

In terms of runtime, when $B$ is low and/or $\tau$ is large, RAGUEL-Block runs in less than two seconds on the larger DC3 dataset. As $B$ increases and/or $\tau$ decreases, runtime increases by up to nine times – 14.3s ($B=35,\tau =\frac{1}{5}$) vs. 1.7s ($B=5,\tau =\frac{1}{2}$). This is to be expected as the mechanism needs to make more satisfiability checks due to the tighter constraints and the larger number of blocks. Moreover, RAGUEL-Block is nearly 30x faster, while changing the fairness ratio by no more than 10% (up to $B=25$ and $\tau =\frac{1}{3}$ on DC3).

Finally, we demonstrate that RAGUEL-Block runs efficiently on large-scale data such as the HMDA dataset, with performance results that remain stable even as the number of records increases. None of the re-ranking alternatives (e.g., FA*IR and FoEiR) could handle large datasets, so they are excluded here. We sample between 2,500 and 1M records HMDA dataset to maintain an initial fairness ratio of 0.83. We run RAGUEL-Block using a fixed block size of 100 records (i.e., the total number of blocks is variable) on these samples, presenting results averaged over 10 trials. Figure 3(a) shows that the final fairness ratio attained is at least 0.95 and does not exhibit much variability as dataset size increases. The ranking quality metrics (Figure 3(b)), which are high when the number of records is small, quickly decrease and remain low for larger datasets.

These results show that our solution can easily handle any arbitrarily large dataset that is sub-divided into smaller blocks within which group-level recourse fairness is being enforced. Our method essentially uses sliding window processing, as a block only requires the next adjoining block of candidate records for RAGUEL-Block to improve its fairness (see Algorithm 2 and Section 3.5.3).