Most foundational frameworks in algorithmic fairness were built for a simple world: one with binary sensitive attributes (e.g., protected group vs. majority group) and binary outcomes (e.g., loan approved vs. denied). Early benchmarks relied heavily on this paradigm, enforcing parity by calculating simple differences or ratios between two groups.
However, real-world applications rarely fit into binary boxes. Demographics involve multi-valued, intersecting identities, and tasks like clinical diagnosis, text generation, and image segmentation require multi-class or high-dimensional outputs. When we try to force traditional fairness constraints into these complex settings, the mathematics break down.
To bridge this gap, a major research direction focuses on scaling algorithmic fairness to multi-class outcomes and multi-group sensitive attributes. By moving away from rigid pairwise constraints and embracing geometric alignment, information projection, and min-max optimization, these modern frameworks allow fairness to scale to complex, real-world decision environments.
The Combinatorial Explosion of Pairwise Parity
To understand why binary fairness fails to scale, consider the standard definition of Demographic Parity. For a binary sensitive attribute $A \in \{0, 1\}$ and a binary prediction $\hat{Y} \in \{0, 1\}$, fairness is achieved when:
$$P(\hat{Y} = 1 \mid A = 0) = P(\hat{Y} = 1 \mid A = 1)$$
This requires satisfying a single, straightforward constraint. But if we expand the sensitive attribute to $K$ distinct demographic groups and the target to $M$ distinct classes, a naive extension requires enforcing parity across every combination of groups and classes. This creates an explosion of $O(K^2 M)$ pairwise constraints.
As Kazuto Fukuchi et al. and Dennis Wei et al. observe, this combinatorial explosion over-constrains the optimization landscape. When a machine learning model attempts to satisfy hundreds of interlocking pairwise constraints simultaneously, the optimization process frequently fails to converge, or it severely degrades the model's predictive utility. Furthermore, ensuring that a model remains well-calibrated across all these sub-groups becomes mathematically intractable using traditional threshold-shifting methods.
Geometric Alignment via Optimal Transport and Barycenters
Instead of forcing every demographic group to match every other group through explicit pairwise penalties, how can we align distributions globally? One powerful solution is to leverage the geometry of probability spaces.
Instead of comparing groups to one another, we can map all groups toward a single, mutually fair reference distribution. Qihang Lin et al. implement this idea in a post-processing framework called TAB (Transporting to Approximate Barycenter).
[Group 1 Distribution] \
[Group 2 Distribution] --> [ Wasserstein Barycenter ] --> [Fair Joint Distribution]
[Group 3 Distribution] /
Using Optimal Transport theory, TAB computes a Wasserstein barycenter—essentially a geometric "center of mass" of the prediction distributions across all demographic groups. By transporting each group's high-dimensional output distribution toward this central barycenter, the framework enforces multi-output fairness globally without ever calculating a pairwise metric. This builds on data-level repair concepts pioneered by Paula Gordaliza, who utilized Wasserstein distances to blur the relationship between multi-class protected attributes and outcomes during pre-processing.
An alternative geometric approach is to project biased model predictions onto a fair subspace. Wael Alghamdi et al. introduce FairProjection, a framework that views multi-class prediction space as a probability simplex. Instead of retraining a model from scratch, FairProjection takes the output probabilities of any pre-trained model and "tilts" them using information-theoretic projections. By minimizing the Kullback-Leibler (KL) divergence between the original and modified distributions, they snap the predictions onto a fair polytope. Because this projection can be computed independently of model training, it scales efficiently to datasets with millions of samples and dozens of intersecting groups.
Reformulating Fairness as a Min-Max Game
When fairness must be enforced during training (in-processing), managing multi-group constraints requires a shift in how optimization problems are framed. Rather than tracking a massive matrix of discrete penalties, researchers reformulate fair learning as a continuous, zero-sum game.
Andrew Lowy et al. introduce FERMI, a stochastic optimization framework that translates multi-class fairness constraints into a non-convex min-max problem. In this formulation, an internal optimization "adversary" dynamically searches for and amplifies the largest fairness violations across all demographic categories, while the model's classifier attempts to minimize both the empirical prediction risk and the adversary's penalties.
This min-max formulation removes the need to explicitly track every group combination during a gradient step. Instead, the model naturally smooths out disparities by defending against the adversary. The authors later demonstrated that this min-max approach can successfully incorporate strict differential privacy guarantees (Andrew Lowy et al.), proving that models can handle non-binary sensitive attributes and multi-class labels simultaneously without leaking sensitive training data or sacrificing convergence stability.
Scaling Fairness to Structured and High-Dimensional Spaces
The mathematical challenge of multi-class fairness intensifies when moving from simple tabular data to structured domains like graphs, clusters, and generative text.
Unsupervised Clustering
In fair clustering, the goal is to ensure that clusters do not disproportionately exclude or contain specific demographic groups. Flavio Chierichetti et al. pioneered the use of "fairlets"—small, perfectly balanced micro-clusters that serve as building blocks for larger clustering algorithms like $k$-means. However, their initial guarantees were strictly limited to binary group ratios (e.g., a 1:1 balance). To scale this to real-world datasets, Melanie Schmidt et al. developed fair coresets and streaming architectures, generalizing these mathematical approximation bounds to accommodate multiple overlapping protected categories and arbitrary group balance ratios.
Graph Neural Networks
On graphs, demographic bias propagates through the network topology itself; a node's representation is influenced by its neighbors. When attributes are multi-class, this structural bias compounds. Yushun Dong et al. address this with EDITS, a framework that uses Wasserstein distance to debias multi-class node attributes and structural connections simultaneously before graph training. In decentralized environments, Nan Cui et al. extend this concept to federated graph neural networks ($F^2GNN$), using local fairness-aware updates and server-side weighted aggregations to prevent multi-class demographic imbalances from propagating across edge clients.
High-Dimensional Risk Control
In generative tasks like language modeling, the output space is a high-dimensional probability distribution over an entire vocabulary. Enforcing fairness across multi-group demographic concepts requires highly flexible post-processing boundaries. Lujing Zhang et al. address this by introducing the $(s, \mathcal{G}, \alpha)$-GMC framework. By treating fairness calibration as a generalized risk control problem, their method successfully bounds multi-group fairness risks across complex, overlapping demographic intersections, making it applicable to high-dimensional outputs like text generation distributions and pixel-wise image segmentation masks.