  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}) \cdot (\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.
