📊 statistics

Optimal Transport under Group Fairness Constraints

This paper introduces a novel group fairness notion for Optimal Transport and proposes efficient computational methods, including a modified Sinkhorn algorithm and two relaxation strategies with theoretical guarantees, to balance fairness constraints with matching quality.

Original authors: Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Core Problem: The "Smart" Matchmaker’s Bias

Imagine you are running a massive matchmaking service (like a dating app, a school admission system, or a job placement agency). Your goal is to pair people up in the most efficient way possible. In mathematics, this is called Optimal Transport (OT). It’s like finding the shortest path to move a pile of sand from one spot to another with the least amount of effort.

However, there’s a catch. If you just let the algorithm pair people based on who is "closest" or "most similar," it often creates unfair outcomes.

The Analogy:
Imagine a city where rich students live near elite schools, and poor students live near regular schools. If you use a standard "efficiency" algorithm to assign students to schools, it will naturally pair rich students with elite schools and poor students with regular schools because that requires the least travel distance. This creates segregation. The algorithm isn’t trying to be racist or classist; it’s just being efficient. But efficiency, in this case, leads to inequality.

The Solution: Setting "Fairness Targets"

The authors of this paper introduce a new rulebook. Instead of just asking, "What is the cheapest way to match these people?" they ask, "What is the cheapest way to match these people while hitting specific fairness goals?"

They call these goals Fairness Targets.

The Analogy:
Think of the Fairness Target as a recipe. The city planner says: "I don’t care if it costs a little more in bus tickets, but I want 60% of the students from low-income neighborhoods to end up in elite schools."

The paper defines this mathematically. They create a matrix (a grid) that specifies exactly how many people from Group A should match with Group B, Group C, etc. This ensures that the final matching isn't just efficient, but also diverse and fair according to the planner's rules.

Three Ways to Solve It

The paper proposes three different methods to achieve this, ranging from "strict" to "flexible."

1. The Strict Rule-Follower (FairSinkhorn)

This is the most direct approach. The authors modified a famous mathematical algorithm called Sinkhorn (which is like a super-fast calculator for matching problems) to force it to obey the fairness targets exactly.

Pros: It guarantees perfect fairness.
Cons: It can be very expensive. To force 60% of poor students into elite schools, you might have to send them on very long bus rides, increasing the total "cost" (time, money, or distance) significantly.

2. The "Good Enough" Compromise (Penalized OT)

The authors realized that perfect fairness is often too costly for real-world use. So, they created a second method that allows for small mistakes.

The Analogy:
Imagine you have a budget for fairness. You tell the algorithm: "Try to hit the fairness target, but if you miss it by a tiny bit, that’s okay. Just don’t miss it by a lot."

They add a "penalty" to the math equation. If the algorithm deviates from the fairness target, it gets "punished" with a higher score. This allows the system to find a sweet spot: it’s mostly fair, but it doesn’t cost an arm and a leg to achieve. The paper proves mathematically that this method is statistically reliable even when you only have a small amount of data.

3. The "Redefining Distance" Trick (Cost Learning)

This is the most clever approach. Instead of forcing the matching to be fair, the algorithm changes how it sees the world.

The Analogy:
In the standard model, "distance" is physical miles. But what if we changed the definition of distance?

Normally, a rich student is "close" to an elite school.
The Cost Learning algorithm learns a new way to measure distance where a rich student is suddenly "far" from an elite school, and a poor student is "close" to it.

It’s like putting on special glasses that distort the map. The algorithm then runs the standard "efficient" matching on this distorted map. The result? The matching looks efficient on the distorted map, but when you look at it in the real world, it happens to be fair.

Why is this cool?
Once the algorithm learns these "special glasses" (the new cost function), you can reuse them forever. If new students apply next year, you don’t need to run the complex fairness calculation again. You just put on the glasses and match them normally. The paper proves that this method works well even for people the algorithm hasn’t seen before.

What Did They Find?

The authors tested these methods on simulated data (students and schools) and a semi-realistic dating app dataset.

Trade-offs: They confirmed that there is always a trade-off. The stricter the fairness, the higher the cost. The "Penalized" method lets you slide along this curve to find the best balance.
Flexibility: The "Penalized" method was generally more flexible and could achieve better fairness at lower costs than the "Cost Learning" method in some complex scenarios.
Reusability: The "Cost Learning" method was much faster for new data. Once trained, it could match new people instantly, whereas the other methods had to recalculate everything from scratch.
Real-World Application: On the dating app data, they showed that you can enforce fairness (e.g., ensuring people from different income brackets match more often) without breaking the system.

Summary

This paper gives us a mathematical toolkit to make matching systems (like jobs, schools, or dates) fairer. It moves beyond just "treating everyone the same" (which can still lead to inequality) to actively ensuring that specific groups are represented in the outcomes. It offers a choice: do you want perfect fairness (expensive), approximate fairness (balanced), or a learned system that makes fairness automatic for future users?

Technical Summary: Optimal Transport under Group Fairness Constraints

Problem Statement
The paper addresses the challenge of ensuring group fairness in algorithmic matching mechanisms, specifically within the framework of Optimal Transport (OT). While OT is widely used for resource allocation and matching (e.g., job recommendations, school admissions, dating apps), standard OT plans often reflect and amplify existing disparities when features are correlated with sensitive attributes (e.g., ethnicity, socioeconomic status). This leads to homogeneous matchings that may violate principles of diversity and equal opportunity. The authors identify a gap in existing literature: while fairness has been studied in supervised and unsupervised learning, and individual fairness has been explored in matching, there is a lack of frameworks for enforcing explicit group-level fairness constraints on the transport plan itself.

Methodology
The authors formalize group fairness in OT by introducing a "fairness target" matrix $F$ , which specifies the desired probability of matching individuals from a specific group in the source distribution $\mu$ (with sensitive attribute $S$ ) to a specific group in the target distribution $\eta$ (with sensitive attribute $W$ ). An $F$ -fair transport plan is defined as a coupling that minimizes the transport cost while satisfying these marginal constraints on the sensitive attributes.

The paper proposes three methodological approaches to solve this problem:

Exact Fairness (FairSinkhorn): The authors derive a modified Sinkhorn algorithm, termed FairSinkhorn, to compute transport plans that satisfy the fairness constraints exactly. By leveraging the dual formulation of the constrained OT problem, they show that the solution retains the scaling structure of standard entropic OT but includes an additional projection step to enforce the group-wise mass constraints. This allows for efficient computation of perfectly fair plans.
Penalized Optimal Transport: Recognizing that exact fairness can significantly degrade matching quality (increase transport cost), the authors propose a relaxed approach. They introduce a convex penalty term $L_F(\Pi)$ into the OT objective, which measures the squared deviation from the fairness targets. This results in a penalized entropic OT problem that is strongly convex and can be solved efficiently using a generalized conditional gradient algorithm. The strength of the fairness constraint is controlled via a hyperparameter $\lambda$ , allowing for a trade-off between cost and fairness.
Cost Learning via Bilevel Optimization: The second relaxation strategy involves learning a ground cost function $c_\theta$ such that the resulting entropic OT solution naturally satisfies the fairness targets. This is formulated as a bilevel optimization problem: the outer level minimizes the fairness violation of the OT plan induced by $c_\theta$ , while the inner level solves the standard entropic OT problem. This approach allows for the reuse of the learned cost function for matching new, unseen samples. The authors consider parameterizations such as Mahalanobis distances and neural networks.

Key Contributions

Novel Fairness Notion: Introduction of a flexible group fairness definition for OT based on explicit inter-group mass constraints (fairness targets), applicable to scenarios like limiting homogamy or enforcing matching quotas.
Algorithmic Solutions: Development of the FairSinkhorn algorithm for exact fairness and two relaxed strategies (penalized OT and cost learning) to manage the cost-fairness trade-off.
Theoretical Guarantees:
- For the penalized OT approach, the authors derive novel finite-sample complexity guarantees, showing that the estimation error of the optimal cost scales as $O(1/\sqrt{n})$ , matching the rate of standard entropic OT.
- For the cost learning approach, they establish a uniform bound on the expected deviation of fairness between finite-sample estimates and the population distribution, ensuring that the learned cost generalizes to unseen data.
Empirical Validation: Comprehensive experiments on synthetic and semi-synthetic datasets demonstrating the performance of the proposed methods.

Results

Synthetic Experiments: On Gaussian and Circle datasets, the FairSinkhorn algorithm achieves perfect fairness but at a higher transport cost. The penalized OT approach smoothly interpolates between the low-cost, low-fairness vanilla OT and the high-cost, perfect-fairness FairSinkhorn, offering fine-grained control. The cost learning approach performs comparably to penalized OT on Gaussian data but struggles with the Mahalanobis parameterization on Circle data due to its linear nature; however, a neural network-based cost function successfully captures the non-linear transformations required.
Reusability: The cost learning approach demonstrates significant advantages in inference time for new samples compared to penalized OT, which requires solving a new optimization problem for each batch. The learned costs maintain fairness levels on test data close to those achieved during training, with a generalization gap that is larger for neural costs than for Mahalanobis costs.
Semi-Synthetic Dating App Experiment: On a high-dimensional dataset with multiple income groups, both penalized OT and cost learning achieve similar convex-shaped cost-fairness trade-off curves, validating the methods in a more complex, multi-group setting.

Significance
The paper claims to provide a principled framework for regulators and market designers to enforce fairness targets in OT-based matching mechanisms. By allowing central planners to specify desired group-wise matching probabilities, the work offers a tool to audit and improve existing matching systems. The authors emphasize that the definition of fairness targets remains a political and ethical decision, but their technical contribution lies in providing efficient algorithms and theoretical guarantees to implement such targets. The work distinguishes itself from prior literature by focusing on the fairness of the transport plan itself rather than using OT as a tool for downstream prediction fairness, and by addressing group-level constraints in a symmetric, mass-splitting matching framework.