Optimal Transport under Group Fairness Constraints

Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:8470-8495, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-bleistein26a, title = {Optimal Transport under Group Fairness Constraints}, author = {Bleistein, Linus and Dagr\'{e}ou, Mathieu and Andrade, Francisco and Boudou, Thomas and Bellet, Aur\'{e}lien}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {8470--8495}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/bleistein26a/bleistein26a.pdf}, url = {https://proceedings.mlr.press/v306/bleistein26a.html}, 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.} }
Endnote
%0 Conference Paper %T Optimal Transport under Group Fairness Constraints %A Linus Bleistein %A Mathieu Dagréou %A Francisco Andrade %A Thomas Boudou %A Aurélien Bellet %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-bleistein26a %I PMLR %P 8470--8495 %U https://proceedings.mlr.press/v306/bleistein26a.html %V 306 %X 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.
APA
Bleistein, L., Dagréou, M., Andrade, F., Boudou, T. & Bellet, A.. (2026). Optimal Transport under Group Fairness Constraints. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:8470-8495 Available from https://proceedings.mlr.press/v306/bleistein26a.html.

Related Material