Envy-freeness and relaxed stability: hardness and approximation algorithms

We consider the problem of computing matchings under two-sided preferences in the presence of lower as well as upper-quota requirements for the resources. In the presence of lower-quotas a feasible matching may not exist and hence we focus on critical matchings. Informally, a critical matching achieves the smallest deficiency. We first consider two well-studied notions of optimality with respect to preferences, namely stability and envy-freeness. There exist instances that do not admit a critical stable matching or a critical envy-free matching. When critical matching satisfying the optimality criteria does not exist, we focus on computing a minimum-deficiency matching among all stable or envy-free matchings. To ensure guaranteed existence of an optimal critical matching, we introduce and study a new notion of optimality, namely relaxed stability. We show that every instance admits a critical relaxed stable matching and it can be efficiently computed. We then investigate the computational complexity of computing maximum size optimal matchings with smallest deficiency. Our results show that computing a maximum size minimum-deficiency envy-free matching and a maximum size critical relaxed stable matching are both hard to approximate within $$\frac{21}{19}-\epsilon $$ 21 19 - ϵ , for any $$\epsilon > 0$$ ϵ > 0 unless P = NP. For envy-free matchings, we present an approximation algorithm for general instances and a polynomial time exact algorithm for a special case. For relaxed stable matchings, we present a constant factor approximation algorithm for general instances.