Optimal Cost-Based Allocations Under Two-Sided Preferences

The Hospital Residents setting models important problems like school choice, assignment of undergraduate students to degree programs, among many others. In this setting, fixed quotas are associated with programs that limit the number of agents that can be assigned to them. Motivated by scenarios where all agents must be matched, we propose and study the cost-based allocation setting, which allows controlled flexibility with respect to quotas. In our model, we seek to compute a matching that matches all agents and is optimal with respect to preferences, and minimizes either a local or a global objective on costs. We show that there is a sharp contrast – minimizing the local objective is polynomial-time solvable, whereas minimizing the global objective is hard to approximate within a specific constant factor unless P= NP. On the positive side, we present approximation algorithms for the global objective in the general case and a particular hard case. We achieve the approximation guarantee for the particular case via a linear programming based algorithm.