# Fair-by-design matching

arXiv: https://arxiv.org/abs/1802.02562 · HTML: https://mlsanity.com/paper/1802.02562/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2018.

## Built on by (most cited first, 11 of 11)

- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints](https://mlsanity.com/paper/2106.08652/) (2021)
- [A Graph-based Approach for Mitigating Multi-sided Exposure Bias in Recommender Systems](https://mlsanity.com/paper/2107.03415/) (2021)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise](https://mlsanity.com/paper/2209.05170/) (2022)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)
- [Assortment Optimization for Patient-Provider Matching](https://mlsanity.com/paper/2502.10353/) (2025)
- [Fairness-aware kidney exchange and kidney paired donation](https://mlsanity.com/paper/2503.06431/) (2025)
- [Rawlsian many-to-one matching with non-linear utility](https://mlsanity.com/paper/2511.02533/) (2025)

## Abstract (arXiv)

Matching algorithms are used routinely to match donors to recipients for solid organs transplantation, for the assignment of medical residents to hospitals, record linkage in databases, scheduling jobs on machines, network switching, online advertising, and image recognition, among others. Although many optimal solutions may exist to a given matching problem, when the elements that shall or not be included in a solution correspond to individuals, it becomes of paramount importance that the solution be selected fairly. In this paper we study individual fairness in matching problems. Given that many maximum matchings may exist, each one satisfying a different set of individuals, the only way to guarantee fairness is through randomization. Hence we introduce the distributional maxmin fairness framework which provides, for any given input instance, the strongest guarantee possible simultaneously for all individuals in terms of satisfaction probability (the probability of being matched in the solution). Specifically, a probability distribution over feasible solutions is maxmin-fair if it is not possible to improve the satisfaction probability of any individual without decreasing it for some other individual which is no better off. In the special case of matchings in bipartite graphs, our framework is equivalent to the egalitarian mechanism of Bogomolnaia and Mouline. Our main contribution is a polynomial-time algorithm for fair matching building on techniques from minimum cuts, and edge-coloring algorithms for regular bipartite graphs, and transversal theory. For bipartite graphs, our algorithm runs in O((|V|2 + |E||V|2/3) · (log |V|)2) expected time and scales to graphs with tens of millions of vertices and hundreds of millions of edges. To the best of our knowledge, this provides the first large-scale implementation of the egalitarian mechanism.