Optimal Transport under Group Fairness Constraints
This work addresses fairness in resource allocation for applications like job matching, but it is incremental as it builds on existing optimal transport methods with new constraints and relaxations.
The paper tackles the problem of ensuring group fairness in optimal transport matching algorithms by introducing a novel fairness constraint and proposing FairSinkhorn for exact fairness, along with two relaxation strategies to balance fairness and matching quality, with empirical results illustrating trade-offs.
Ensuring fairness in matching algorithms is a key challenge in allocating scarce resources and positions. Focusing on Optimal Transport (OT), we introduce a novel notion of group fairness requiring that the probability of matching two individuals from any two given groups in the OT plan satisfies a predefined target. We first propose \texttt{FairSinkhorn}, a modified Sinkhorn algorithm to compute perfectly fair transport plans efficiently. Since exact fairness can significantly degrade matching quality in practice, we then develop two relaxation strategies. The first one involves solving a penalised OT problem, for which we derive novel finite-sample complexity guarantees. This result is of independent interest as it can be generalized to arbitrary convex penalties. Our second strategy leverages bilevel optimization to learn a ground cost that induces a fair OT solution, and we establish a bound guaranteeing that the learned cost yields fair matchings on unseen data. Finally, we present empirical results that illustrate the trade-offs between fairness and performance.