Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Envy-free Matchings with Lower Quotas   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.

35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
21
The categories of this paper are: adap-org
2
The categories of this paper are: math
28
The categories of this paper are: alg-geom
14
The categories of this paper are: math-ph
6
The categories of this paper are: astro-ph
24
The categories of this paper are: dg-ga
4
The categories of this paper are: cond-mat
10
The categories of this paper are: q-bio
16
The categories of this paper are: stat
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg
7
The categories of this paper are: hep-th
17
The categories of this paper are: q-fin
32
The categories of this paper are: atom-ph