  The theory of two-sided matching has been extensively developed and applied
to many real-life application domains. As the theory has been applied to
increasingly diverse types of environments, researchers and practitioners have
encountered various forms of distributional constraints. As a mechanism can
handle a more general class of constraints, we can assign students more
flexibly to colleges to increase students' welfare. However, it turns out that
there exists a trade-off between students' welfare (efficiency) and fairness
(which means no student has justified envy). Furthermore, this trade-off
becomes sharper as the class of constraints becomes more general. The first
contribution of this paper is to clarify the boundary on whether a
strategyproof and fair mechanism can satisfy certain efficiency properties for
each class of constraints. Our second contribution is to establish a weaker
fairness requirement called envy-freeness up to $k$ peers (EF-$k$), which is
inspired by a similar concept used in the fair division of indivisible items.
EF-$k$ guarantees that each student has justified envy towards at most $k$
students. By varying $k$, EF-$k$ can represent different levels of fairness. We
investigate theoretical properties associated with EF-$k$. Furthermore, we
develop two contrasting strategyproof mechanisms that work for general
hereditary constraints, i.e., one mechanism can guarantee a strong efficiency
requirement, while the other can guarantee EF-$k$ for any fixed $k$. We
evaluate the performance of these mechanisms through computer simulation.
