Compatible $k$-Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints
For market designers dealing with diversity requirements or refugee resettlement, this provides a controlled way to relax both fairness and non-wastefulness simultaneously, offering a practical solution to a known tension.
The paper addresses the incompatibility of fairness and non-wastefulness in two-sided matching markets with hereditary constraints, introducing relaxed notions (ER-k and NW-k) that are always compatible for any fixed k. They provide polynomial-time algorithms and show experimentally that small relaxations achieve a good balance.
We study two-sided matching markets under hereditary constraints, which extend beyond simple capacity limits and arise in applications such as diversity requirements and refugee resettlement. In these settings, fairness and non-wastefulness are often incompatible, and existing approaches typically address this tension by prioritizing one property at the expense of the other. We take a different approach by relaxing both properties simultaneously in a controlled and symmetric manner. We introduce two notions indexed by an integer $k$: envy-received up to $k$ peers (ER-$k$) and non-wastefulness up to $k$ objections (NW-$k$). Our main theoretical result shows that ER-$k$ and NW-$k$ are always compatible under hereditary constraints for any fixed $k$. We provide two equivalent polynomial-time algorithms to compute such matchings: a $k$-admissible cutoff algorithm and a $k$-admissible college-proposing deferred acceptance mechanism. Finally, experimental results demonstrate that even small relaxations achieve a favorable balance between fairness and non-wastefulness.