Mapping the Tradeoffs and Limitations of Algorithmic Fairness

As mentioned above, it is known that separation and sufficiency are often incompatible (although, as we show in Appendix A, they are sometimes compatible in non-trivial scenarios). A common consequence of this impossibility is that researchers and practitioners have been told that they must choose one or the other – separation or sufficiency – but not both. In this work, we propose a relaxation of these statistical criteria of fairness (Section 3.2), study the combinations of these relaxed criteria that are achievable (Lemma 10 and Theorem 12), and show that, in certain scenarios, there exists a continuous, meaningful tradeoff between the relaxed notions, forming a Pareto frontier (Theorem 14). We explore the relationships between the relaxed criteria, see that full sufficiency is not always achievable (Theorem 15), and draw conclusions regarding the post-processing of fair representations – post-processing cannot degrade our notion of approximate separation, but there are conditions on representations under which full sufficiency cannot be recovered by any post-processing (Theorem 17). These results enrich our understanding of the possible fairness tradeoffs that can be achieved, giving policymakers and domain experts a richer design space from which to select.

There has been substantial work on relaxations of the statistical criteria of group fairness. Some approaches weaken the criteria in some non-continuous fashion. This includes, for example, relaxed equalized odds [12] (weakening separation) and equal precision [3] (weakening sufficiency), both of which are motivated by the incompatibility results, in an attempt to find weaker fairness notions that are compatible with each other. A major motivation for equal opportunity [8] (a relaxation of separation) in contrast, is compatibility with higher prediction accuracy than the stronger notion of equalized odds.

More continuous relaxations have primarily appeared in the contexts of learning and optimization. They typically involve the definition of some approximation or error term that quantifies how much a predictor violates the desired criterion, and then use this term either as an objective or as a penalty or regularization term in the learning objective of the predictor; such work has not focused on the compatibilities that such relaxations enable. Examples include Zafar et al. [16] and Woodworth et al. [15], who propose moment-based approximations in order to solve the intractability of the optimization problem, as well as Zemel et al. [17] and Bechavod and Ligett [2], who define a regularization term in order to achieve independence and separation, respectively. Of particular relevance to our work are Kashima et al. [10], who use mutual information as a regularization term for learning classifiers that satisfy independence, and Gopalan et al. [6], who define the objective of multicalibration [9] in terms of average conditional covariance (as discussed in Section 3.3).

Perhaps most closely related to our work is the analysis of Hamman and Dutta [7], who adopt an information-theoretic perspective with very similar definitions to ours. However, their analysis – based on partial information decomposition – focuses only on scenarios where at least one of the fairness criteria is fully met.

As mentioned above, the main statistical criteria for fair classification are defined in terms of statistical independence of the three variables $Y$, $A$ and $R$:

In this work we focus on separation and sufficiency, as independence is usually too restrictive.

Throughout this paper, we use capital letters for random variables, their respective lower case letters for their realizations, and script for the alphabet, as in $X=x\in 𝒳$. The notation $P(X|y)$ is short for $P(X|Y=y)$. For simplicity, we assume that all variables are finite; if, for example, $R$ naturally takes values in $[0,1]$, we consider a suitable quantization.

The next section provides the essential background on $f$-divergences and $f$-information, including definitions and key properties.

Some important examples of $f$-divergences are the Kullback-Leibler (KL) divergence, taking $f(t)=t\log t$ to obtain $D_{\mathrm{KL}}[P\parallel Q]={𝔼}_P\log \frac{P}{Q}$ (note that the expectation is over $P$); the total variation (TV), with $f(t)=\frac{1}{2}|t-1|$ yielding $\mathrm{TV}(P,Q)=\frac{1}{2}{\Vert P-Q\Vert }_1$; and the ${\chi }^2$-divergence, with $f(t)={(x-1)}^2$. The Rényi divergences, although not $f$-divergences, are closely related and share many of their properties.

The following is a useful property of $f$-divergences.

In all the examples above, $f$ is indeed strictly convex at 1.

Inspired by the definition of mutual information, a similar measure of association between random variables can be defined using $f$-divergences:

For KL divergence, $f$-information is exactly Shannon’s mutual information. For TV, $I_{\mathrm{TV}}$ is closely related to the covariance (see Proposition 8).

The following property of $f$-information is an immediate consequence of Proposition 3 and the definition of statistical independence.

(If $f$ is not strictly convex at 1, then independence still implies zero information, but not vice versa.)

We highlight another important property of $f$-information – the data processing inequality (DPI):

In light of Proposition 5, the statistical criteria for fair classification, which are defined in terms of conditional independence, can be relaxed using the notion of $f$-information.

Each of these quantities measures to what extent the joint distribution of $Y$, $A$ and $R$ diverges from the statistical independence that defines the respective criterion, where a value of zero means that the criterion is fully satisfied. When the specific $f$-information is of relevance, we may write ${\mathrm{\Delta }}_{\mathrm{sep}}^f$ for clarity. We sometimes refer to the original statistical criteria as, e.g., “full separation” and “full sufficiency” to distinguish them from these relaxed notions.

An additional relevant quantity that is closely related to the deviations above is $I_f(R;Y)$, which expresses the amount of “information” that the predictor $R$ conveys about the true label $Y$. This can be seen as a measure of the predictor’s overall performance, similar to its accuracy. It can be shown that maximizing $I(R;Y)$ (using KL divergence) is equivalent to minimizing the expected cross-entropy loss, $-{𝔼}_{Y,R}\log P(Y|R)$, which is a common practice in the optimization of classifiers.¹¹1Note that $I(R;Y)=H(Y)-H(Y|R)=-{𝔼}_Y\log P(Y)+{𝔼}_R{𝔼}_{Y|R}\log P(Y|R)$, where the first term, $H(Y)$, is the entropy of $Y$ and does not depend on $R$, and the second term is the negative of the expected cross-entropy loss (see, e.g., [4]).

The definition of the relaxed criteria in terms of $f$-information (Definition 7) may not seem intuitive at first. However, applying Bayes’ rule and some algebra transforms these expressions into a form that more closely resembles the original definitions of the fairness criteria. Consider, for example, the deviation from separation:

This expression represents the expected divergence between the conditional distribution of $R$ given both $A$ and $Y$, and its conditional distribution given only $Y$. In other words, it quantifies how much, on average (over the values of $A$ and $Y$), the predictor’s outcome distribution within the subgroups differs from the average in the population, among individuals that share the same true label.

Similarly, for the deviation from sufficiency we have

that is, the average difference between the the true label distribution within the subgroups and its average in the population, among individuals that share the same predicted value.

One potential drawback of using $f$-information to define relaxed fairness criteria is its average-case nature. In particular, smaller subgroups – especially those where certain labels or prediction values are rare – contribute less to the deviation. One could argue that this is an unfair approach to fairness. In any case, some of our results treat scenarios where one or more of the deviations is zero, in which case taking the average or the maximum yields the same result.

To address this drawback, some works instead use a maximum-based approach to defining relaxed group fairness criteria (see, for example, [15]). However, placing excessive weight on rare examples can introduce statistical biases and negatively impact the learning process of fair predictors and representations. This very concern has led the multicalibration literature [9, 6] to adopt a relaxed objective that is essentially equivalent to TV-information, as we demonstrate next.

Following the definition in [6], a predictor $R$ is said to be $\alpha$-approximate subgroup calibrated with respect to $A$ if it satisfies ${𝔼}_R|\mathrm{Cov}[A,Y\mid R]|\le \alpha$.

The proof, provided in Appendix B, relies on the fact that in the binary case, ${𝔼}_R|\mathrm{Cov}[A,Y\mid R]|=\frac{1}{2}{\mathrm{\Delta }}_{\mathrm{suff}}^{\mathrm{TV}}(R)$. More generally, for $A$ and $Y$ that take on numeric values, denote the ranges ${ℛ}_Y=\max Y-\min Y$ and ${ℛ}_A=\max A-\min A$. Then we have ${𝔼}_R|\mathrm{Cov}[A,Y\mid R]|\le \frac{1}{2}{ℛ}_A{ℛ}_Y{\mathrm{\Delta }}_{\mathrm{suff}}^{\mathrm{TV}}(R)$.

Finally, Pinsker’s inequality [13, Theorem 7.10] states that $\mathrm{TV}(P,Q)\le \sqrt{\frac{1}{2}{D}_{\mathrm{KL}}[P\parallel Q]}$ (when KL divergence is taken with the natural logarithm), meaning that using KL divergence for the deviation dominates the use of total variation. In particular, this gives ${𝔼}_R|\mathrm{Cov}[A,Y\mid R]|\le {ℛ}_A{ℛ}_Y\sqrt{\frac{1}{8}{\mathrm{\Delta }}_{\mathrm{suff}}^{\mathrm{KL}}(R)}$.

Consider any joint distribution $P(X,Y,A)$. Any choice of a predictor $R$ – that is, a choice of a conditional distribution $P(R|X)$ – corresponds to a point in the nonnegative octant representing the triplet $({\mathrm{\Delta }}_{\mathrm{sep}}(R),{\mathrm{\Delta }}_{\mathrm{suff}}(R),I_f(R;Y))$. We refer to the set of all such possible points as the achievable region. We first show that the achievable region (as illustrated in Figure 2) is convex and compact.

If both $A$ and $Y$ are determined by (possibly stochastic) functions of $X$, then all the information about the true label that is encoded in the protected attribute is also encoded in the data $X$. This assumption is common in the multicalibration literature, where $A$ denotes either a subset of $𝒳$ [9], or more generally a real valued function of $X$ [6]. It is equivalent to saying that $Y\to X\to A$ form a Markov chain, that $A⟂Y|X$, or – most importantly for our analysis – that $I_f(A;Y|X)=0$. In this case, we say that the data itself satisfies sufficiency.

In this specific setting, as we prove in the following theorem, the separation-sufficiency curve is monotonically nonincreasing, and thus represents a Pareto frontier of fairness, reflecting the fundamental tradeoff between separation and sufficiency (see Figure 2(b) for a schematic, and the left panel of Figure 3 for a simulation).

The previous result relies heavily on the assumption that the data itself satisfies sufficiency. When this is not the case, that is, when $I_f(A;Y|X)>0$, it means that the data $X$ is not expressive enough to convey all the information about the relationship between the protected attribute $A$ and the true label $Y$. This can occur if the protected attribute is not an inherent part of the data, yet it bears information about the true label. In particular, this can happen when the protected attribute is deliberately stripped from the data, as in the practice of “fairness through unawareness.”

In this case, there is no guarantee that the separation-sufficiency curve is monotonic (see an example of such a situation in the middle panel of Figure 3), nor that it attains the value zero (see Figure 3, right panel). In other words, there is no guarantee that there exist predictors that satisfy perfect sufficiency. In fact, we show that in certain scenarios such predictors do not exist.

In the following analysis, we rely exclusively on Shannon’s mutual information, as it allows us to apply its chain rule (see, for example, [4]), which does not necessarily have a counterpart in other forms of $f$-information.

Our analysis of the achievable region, along with the tradeoffs and limitations of separation and sufficiency, has some straightforward implications for the downstream use of fair representations. Specifically, note that when $R$ is regarded as a representation, upon which a further prediction $R^{\prime }$ will be made, then $R$ takes the place of $X$ in our model (Figure 1(c)). This is formalized in the next result.