Classified Stable Matching

a problem motivated by academic hiring. Suppose that a number of institutes are hiring faculty members from a pool of applicants. Both
institutes and applicants have preferences over the other side.
An institute classifies the applicants based on their research
areas (or any other criterion), and, for each class, it sets a lower bound and an upper bound on the number of applicants it would hire in that class. The objective is to find a stable matching from which
no group of participants has reason to deviate. Moreover, the matching
should respect the upper/lower bounds of the classes.

In the first part of the paper, we study classified stable matching problems whose classifications belong to a fixed set of ``order types.'' We show that if the set consists entirely of downward forests, there is a polynomial-time algorithm; otherwise, it is NP-complete to decide the existence of a stable matching.

In the second part, we investigate the problem using a polyhedral approach. Suppose that all classifications are laminar families and there is no lower bound. We propose a set of linear inequalities to describe stable matching polytope and prove that it is integral.
This integrality allows us to find various optimal stable matchings using Ellipsoid algorithm. By studying the geometric structure of fractional stable matchings, we are able to generalize a theorem of Teo and Sethuraman in the context of classified stable matching: given any number of stable matchings, if every applicant is assigned to his median choice among all stable matchings, the outcome is still a stable matching. Finally, a ramification of our result is the description of the stable matching polytope for the many-to-many (unclassified) stable matching problem. This answers an open question posed by Sethuraman, Teo and Qian.