Optimal Transport under Group Fairness Constraints

AI summary

Overview

• Research area: Optimal transport (OT), algorithmic fairness, matching theory, and statistical learning theory (stat.ML).
• Technical level: Advanced. The paper works with entropic OT duality, Sinkhorn-type algorithms, generalized conditional gradient methods, bilevel optimization, and finite-sample complexity bounds.
• Scope in one sentence: The paper defines a new notion of group fairness for optimal transport — where a central planner specifies the probability that members of each pair of groups are matched — and develops one exact algorithm plus two relaxed, statistically analyzed methods for computing such plans.

What This Paper Is About

Optimal transport is widely used to model matching between two populations, but when the features used to build the transport cost are correlated with sensitive attributes, the resulting coupling can concentrate mass between similar groups and preserve or amplify segregation. This paper lets a central planner state a fairness target: a matrix specifying the desired probability of matching each group on one side with each group on the other, and then asks how to compute transport plans that realize that target. Because forcing exact fairness can substantially raise transport cost, the paper also studies ways to relax the constraint while keeping the fairness violation controlled.

Key Contributions

1. A new fair OT problem and an exact solver. The authors introduce the notion of an F-fair optimal transport plan, where the mass transported between every group pair equals a prescribed target, and propose FairSinkhorn, a modified Sinkhorn algorithm that computes such plans by adding an extra projection step to the standard iterations.

2. Two relaxation strategies. The first solves a fairness-penalized OT problem by adding a squared fairness violation term to the entropic OT objective with weight λ, yielding a convex (indeed strongly convex) problem whose cost–fairness trade-off is controlled by λ. The second casts fairness as a bilevel optimization problem: it learns a ground cost c_θ so that the induced OT plan is fair, while staying close to a baseline cost via a discrepancy term D(c_θ, c_base).

3. New theoretical guarantees. For the penalized approach, the authors derive a finite-sample complexity bound for penalized entropic OT. For cost learning, they prove a uniform bound on the expected deviation between the fairness of finite-sample transport plans and the population solution, holding for every cost in the parameterized family.

4. Empirical study and open code. Numerical experiments illustrate the performance of the proposed approaches and the fairness–transport-cost trade-off, with code released at https://github.com/LinusBleistein/fair_ot/.

Main Findings

• Fairness can be encoded as inter-group mass constraints. A valid fairness target F is a K_s × K_w matrix that is itself a coupling of the group marginals p and q, satisfying the row constraints ∑_w F_sw = p_s and column constraints ∑_s F_sw = q_w. Under the assumption that μ and η are compactly supported, a unique F-fair OT plan exists for any such target.

• The exact fair plan has a Sinkhorn-like form. The solution to the finite-sample fair OT problem can be written as diag(e^{f/ε}) (K ⊙ H) diag(e^{g/ε}), where K := [e^{-C_ij/ε}] and H := ∑_sw e^{h_sw/ε} B_sw. This motivates FairSinkhorn, which adds a fairness projection step to the usual Sinkhorn updates; the authors report in Section D.5 that FairSinkhorn and regular Sinkhorn have qualitatively similar convergence rates.

• The penalized relaxation preserves statistical efficiency. Under a smoothness assumption on the cost (infinitely differentiable), the fairness-penalized estimator satisfies E|m*(μ_n, η_n) − m*(μ, η)| ≲ 1/√n. This matches the O(n^{-1/2}) scaling of standard entropic OT sample-complexity bounds, showing that the extra fairness penalty does not reduce statistical efficiency. The bound inherits exponential dependence on ε and on λ, and extends to generic convex penalties at the cost of a supplementary log(n) factor.

• Learned costs transfer to unseen data with a quantified deviation. Under a bounded-cost assumption (sup_θ ||c_θ||_∞ < R_Θ), the expected gap between the fairness of a finite-sample plan and the population plan satisfies sup_θ E[|L_F(Π_ε(c_θ)) − L_F(π*_ε(c_θ))|] ≲ exp(5R_Θ/ε)/√n. The proof generalizes a deviation result for bounded test functions, giving a bound that holds with probability 1 − 18e^{-t²}.

• Exact fairness carries a price, motivating relaxation. The authors motivate both relaxed methods by the observation that enforcing exact fairness can substantially increase transport cost — a "price of fairness" analogous to what has been studied in resource allocation and in supervised learning with exact group fairness constraints.

• Deterministic matchings remain nearly fair at scale. Sampling a deterministic matching from a fair entropic plan is reported to exhibit nearly the same level of fairness for sufficiently large samples (Figure 7(b), Section D.4).

• Empirical results are presented but the truncated content does not report specific numbers. The abstract and contributions state that numerical experiments illustrate performance and the fairness–transport-cost trade-off; the provided text does not include the experimental section's figures or values.

Methodology in Plain English

The authors model matching as entropic optimal transport between two distributions, each carrying a sensitive-attribute label that defines its group. Instead of letting the cost function alone determine who matches whom, they let a planner specify a target table of group-to-group matching probabilities.

To enforce the target exactly, they exploit the fact that the fairness constraints are linear in the transport plan. Using the dual of the problem, they show the optimal plan has the same multiplicative form as a Sinkhorn solution, except with an extra matrix built from group indicators. This yields FairSinkhorn: run the usual alternating row-and-column normalizations, then renormalize the mass within each group block so that the block totals hit the target.

Because exact fairness can be costly, they offer two softer alternatives. The first adds the squared difference between the achieved and target group-matching probabilities to the OT objective, weighted by a penalty parameter. The resulting problem is convex, and they solve it with a generalized conditional gradient method that, at each step, linearizes the fairness term and solves an ordinary Sinkhorn problem with a modified cost. They then prove how quickly the value of this penalized problem converges as sample size grows.

The second alternative flips the perspective: rather than constraining the plan, it changes the geometry of the problem by learning the cost itself. The outer problem adjusts cost parameters to reduce fairness violation and to stay near a baseline cost; the inner problem computes the entropic OT plan induced by those parameters. The authors instantiate this with a Mahalanobis cost (a positive semidefinite matrix M scaling squared distances, whose learned entries are interpretable) and with a neural cost (embedding each side through a network and taking squared Euclidean distance in the embedding). Because this produces a reusable cost function, they additionally bound how much fairness deviates when the same recipe is applied to new, unseen samples.

Why This Matters

The work shifts the focus of fairness research in OT: instead of using OT as a tool to make a downstream predictor fair, it studies the fairness of the transport plan itself — the object that actually determines who gets matched with whom. It also gives a flexible, auditable interface: a planner states target matching probabilities, and the machinery computes a plan matching them as closely as the chosen relaxation allows.

Real-world applications the paper points to include:

• School admissions. The running example concerns students with high or low social status and elite or non-elite schools; a city administrator can require, for instance, that 60% of low-status students be matched to elite schools.
• Hiring and corporate governance. The US four-fifths rule requires the selection rate of any demographic group to be at least 80% of that of the highest-selecting group; the EU Directive 2022/2381 targets at least 40% of non-executive director positions, or 33% of all director positions, held by women by 2026.
• Higher education quotas. The paper cites French institutions that are subject to minimum quotas for scholarship holders, a rule that maps directly onto a fairness target.
• Online platforms. Job recommendations, dating apps, and ride-hailing apps are cited as matching mechanisms whose homogeneity has raised concerns about social and racial marital homogamy.

Industry relevance follows from the same list: any organization operating a centralized matching or recommendation system under regulatory diversity goals — employment platforms, admissions offices, and marketplaces — can treat fairness targets as a configurable constraint on top of an existing transport-based matching pipeline, and can choose between exact enforcement and the two relaxations depending on how much cost increase is acceptable.

Future Directions

• Extensions of the fairness target. The authors note that the framework extends to targets imposed only on a subset of group pairs, to cost-weighted targets that balance transport costs across groups, and to range-based constraints solvable with a margin-based loss that penalizes only violations outside an interval.
• Better handling of the exponential dependence on ε and λ. Both the penalized sample-complexity bound and the cost-learning deviation bound grow exponentially in 1/ε (and in R_Θ), leaving open whether tighter control is possible.
• Scaling and solver comparison. FairSinkhorn's convergence relative to standard Sinkhorn is reported to be qualitatively similar, but a fuller characterization of convergence rates, and how the methods behave at large scale, remains open.
• Broader empirical evaluation. The reported experiments are described only at a high level in the provided text; broader benchmarking across matching domains and systematic study of the fairness–cost trade-off would clarify when each of the three approaches is preferable.

Target Audience

This paper is most useful to researchers and graduate students working on optimal transport, algorithmic fairness, or matching markets, and to theoretically inclined practitioners who need sample-complexity guarantees for fairness-constrained estimation. Readers should be comfortable with entropic OT, Sinkhorn iterations, convex duality, and bilevel optimization; the proofs are deferred to the appendix, and the code is publicly available for those who want to reproduce the experiments.

Authors’ abstract

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 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 penalized OT problem, for which we derive novel finite-sample complexity guarantees. Our second strategy leverages bilevel optimization to learn a ground cost that induces a fair OT solution, and we establish a bound on the deviation of fairness when matching unseen data. Finally, we present empirical results illustrating the performance of our approaches and the trade-off between fairness and transport cost.