On the (In)Compatibility between Group Fairness and Individual Fairness
Authors: Shizhou Xu, Thomas Strohmer
Organizations: Department of Mathematics, University of California Davis, Davis, CA 95616-5270, USA · Department of Mathematics, Center of Data Science and Artificial Intelligence Research, University of California Davis, Davis, CA 95616-5270, USA
We study the compatibility between utility-optimized statistical parity and individual fairness. While individual fairness seeks to treat similar individuals similarly, optimal statistical parity aims to provide similar treatment to individuals who share relative similarity within their respective sensitive groups. Although both fairness perspectives are desirable, they often conflict in practical applications. Our goal in this work is to analyze the existence of this conflict and its potential solution. In particular, we establish sufficient (sharp) conditions for the compatibility between the optimal (post-processing) statistical parity L2 learning and the (K-Lipschitz or (ε,δ)) individual fairness requirements. When a conflict arises, we first relax the optimal statistical parity solution to the Pareto frontier, representing the optimal trade-off between L2 error and statistical disparity, and then examine its compatibility with individual fairness. Our analysis identifies regions along the Pareto frontier that satisfy individual fairness constraints. Additionally, we provide individual fairness guarantees for the composition of a trained model with the optimal post-processing step, enabling practitioners to assess the compatibility of post-processed models. This provides practitioners with a principled approach to achieving Pareto-optimal statistical parity while maintaining individual fairness constraints.
Figures & tables
Data Set
Methods
Data Size
dim( X )
dim( Y )
LSAC
Linear Regression, ANN
20,454
9
1
CRIME
Linear Regression, ANN
1,994
97
1
CRIME
Linear Regression, ANN
1,994
87
11
Table 1: Summary of benchmark data sets and test configurations.
Figure 1: All the three rows above consist of the L2 loss and Wasserstein disparity of the original prediction (LR or ANN), the prediction using data excluding Z (LR or ANN + Excluding Z), the exact post-processing W2 barycenter via cumulative distribution functions (cdfs) matching approach (LR or ANN + chzhen2020fair), the optimal affine estimation of the post-processing W2 barycenter (LR or ANN + post-proc. Pseudo-barycenter), the Pareto frontier estimated by the optimal affine maps (LR or ANN + post-proc. Pareto Est.), and finally the portion of the estimated Pareto frontier that is compatible with the corresponding (ϵ,δ) -IF constraints. Here, L(f∗)=0.959,1.045,3.396 for linear regression prediction and L(f∗)=1.250,1.385,5.765 for ANN prediction on LSAC, CRIME, and multivariate CRIME respectively. For each (ϵ,δ) -IF constraint, the compatible portion is the first (δ−ϵ)/(2L(f∗)) part of the Pareto frontier. More generally, each percentage increase in (δ−ϵ)/(2L(f∗)) results in one percentage larger portion of the Pareto frontier to be compatible. Also, the portion is guaranteed to satisfy (ϵ,ϵ+(δ−ϵ)) -IF for all ϵ∈[0,∞)
Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.
Individual fairness, the notion that "similar individuals should be treated similarly," provides a strong and flexible fairness guarantee for algorithmic decision makers. However, a barrier to implementing individual fairness in practice is the difficulty of learning the similarity metric over individuals. In this work, we present an algorithm for learning a Mahalanobis similarity metric from triplet queries of the form "is individual i more similar to individual j or k?" We work in the standard Bradley-Terry model for pairwise comparisons. Our algorithm consists of a spectral initialization step followed by gradient descent. We provide extensive theoretical guarantees on our algorithm, showing that it converges quickly to the ground truth metric despite the non-convexity of the loss in our model. Because our focus is on fairness, we also show that individual fairness with respect to an estimated metric is sufficient to achieve similar fairness with respect to the true metric. We also discuss potential applications of our work to AI model tuning. Finally, we present experimental results that demonstrate the convergence of our algorithm and the fairness performance of downstream fair predictors trained on our estimated metric.
Conlan Olson, Linjun Zhang, Zhun Deng +1
Columbia University · Rutgers University · UNC Chapel Hill +1
Designing fair algorithmic decision systems requires balancing model performance with fairness toward affected individuals: More fairness might require sacrificing some performance and vice versa, yet the space of possible trade-offs is still poorly understood. We investigate fairness in binary prediction-based decision problems by conceptualizing decision making as a multi-objective optimization problem that simultaneously considers decision-maker utility and group fairness. We investigate the set of Pareto-optimal decision rules for arbitrary utility functions for decision maker, arbitrary population distributions, and a wide range of group fairness metrics. We find that the Pareto frontier consists of deterministic, group-specific threshold rules applied to individuals' success probability. This complements existing optimality theorems from literature which, for specific fairness constraints, posit lower-bound threshold rules only. However we also show that, depending on the used fairness metric, the Pareto frontier may include upper-bound threshold rules, thus preferring individuals with lower success probabilities. We show that the location of the Pareto frontier depends only on population characteristics, utility functions and fairness score, but not on the technical design of the algorithm - our findings hold for pre-, in-, and post-processing approaches alike. Our results generalize existing optimality theorems for fairness-constrained classification and extend them to generalized fairness metrics and fairness principles, and to partial fairness regimes. This paper connects formal fairness research with legal and ethical requirements to search for less discriminatory alternatives, offering a principled foundation for evaluating and comparing algorithmic decision systems.
Mieke Wilms, Christoph Heitz
Zurich University of Applied Sciences / University of Zurich, Switzerland · Zurich University of Applied Sciences, Switzerland
Demographic parity (DP) is a widely used group fairness criterion requiring predictive distributions to be invariant across sensitive groups. While natural in classification, full distributional DP is often overly restrictive in regression and can lead to substantial accuracy loss. We propose a relaxation of DP tailored to regression, enforcing parity only at a finite set of quantile levels and/or score thresholds. Concretely, we introduce a novel (ℓ, Z)-fair predictor, which imposes groupwise CDF constraints of the form F f |S=s (z m ) = ℓ m for prescribed pairs (ℓ m , z m ). For this setting, we derive closed-form characterizations of the optimal fair discretized predictor via a Lagrangian dual formulation and quantify the discretization cost, showing that the risk gap to the continuous optimum vanishes as the grid is refined. We further develop a model-agnostic post-processing algorithm based on two samples (labeled for learning a base regressor and unlabeled for calibration), and establish finite-sample guarantees on constraint violation and excess penalized risk. In addition, we introduce two alternative frameworks where we match group and marginal CDF values at selected score thresholds. In both settings, we provide closed-form solutions for the optimal fair discretized predictor. Experiments on synthetic and real datasets illustrate an interpretable fairness-accuracy trade-off, enabling targeted corrections at decision-relevant quantiles or thresholds while preserving predictive performance.
Arthur Charpentier, Christophe Denis, Romuald Elie +2
UQAM · Université du Québec à Montréal, UQAM, Canada · Kyoto University, Japan +7