Optimal Matchings with One-Sided Preferences: Fixed and Cost-Based Quotas

We consider the well-studied many-to-one bipartite matching problem of assigning applicants A to posts P where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form “match at least 80% of applicants to one of their top three choices” or “it is unacceptable to leave more than 10% of applicants unassigned”. The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the signature of a matching. We, therefore, propose a novel optimality criterion, which we call as the “cumulative better signature”. We investigate the computational complexity of the new notion of optimality in the setting where posts have associated fixed quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under natural restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a cost-based quota setting and show that min-cost cumulative better matching can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation or school choice where the capacities or quotas need not be rigid.