Envy-free matchings with cost-controlled quotas

We consider the problem of assigning agents to programs in the presence of two-sided preferences, commonly known as the Hospital Residents problem. In the standard setting each program has a rigid upper-quota which cannot be violated. Motivated by applications where quotas are governed by resource availability, we propose and study the problem of computing optimal matchings with cost-controlled quotas -- denoted as the CCQ setting. In the CCQ setting we have a cost associated with every program which denotes the cost of matching a single agent to the program and these costs control the quotas. Our goal is to compute a matching that matches all agents, respects the preference lists of agents and programs and is optimal with respect to the cost criteria. We study two optimization problems with respect to the costs -- minimize the total cost (MINSUM) and minimize the maximum cost at a program (MINMAX). We show that there is a sharp contrast in the complexity status of these two problems -- MINMAX is polynomial time solvable whereas MINSUM is NP-hard and hard to approximate within a constant factor unless P = NP even under severe restrictions. On the positive side, we present approximation algorithms for the MINSUM for the general case and a special hard case. The special hard case is theoretically challenging as well as practically motivated and we present a Linear Programming based algorithm for this case. We also establish the connection of our model with the stable extension problem in an apparently different two-round setting of the stable matching problem [Gajulapalli et al. FSTTCS 2020]. We show that our results in the CCQ setting generalize the stable extension problem.