  We analyze the (parameterized) computational complexity of "fair" variants of
bipartite many-to-one matching, where each vertex from the "left" side is
matched to exactly one vertex and each vertex from the "right" side may be
matched to multiple vertices. We want to find a "fair" matching, in which each
vertex from the right side is matched to a "fair" set of vertices. Assuming
that each vertex from the left side has one color modeling its attribute, we
study two fairness criteria. In one of them, we deem a vertex set fair if for
any two colors, the difference between the numbers of their occurrences does
not exceed a given threshold. Fairness is relevant when finding many-to-one
matchings between students and colleges, voters and constituencies, and
applicants and firms. Here colors may model sociodemographic attributes, party
memberships, and qualifications, respectively. We show that finding a fair
many-to-one matching is NP-hard even for three colors and maximum degree five.
Our main contribution is the design of fixed-parameter tractable algorithms
with respect to the number of vertices on the right side. Our algorithms make
use of a variety of techniques including color coding. At the core lie integer
linear programs encoding Hall like conditions. To establish the correctness of
our integer programs, we prove a new separation result, inspired by Frank's
separation theorem [Frank, Discrete Math. 1982], which may also be of
independent interest. We further obtain complete complexity dichotomies
regarding the number of colors and the maximum degree of each side.
