# Envy-free Matchings with Lower Quotas

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2017.

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

- [Two-Sided Matching Meets Fair Division](https://mlsanity.com/paper/2107.07404/) (2021)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Reforming an Envy-Free Matching](https://mlsanity.com/paper/2207.02641/) (2022)

## Abstract (arXiv)

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor-hospital pairs are acceptable. We first show that, for an HR-LQ instance, we can efficiently decide the existence of an envy-free matching. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.