2009/07/10 by Chien‐Chung Huang, Chien-Chung Huang, Huang, Chien-Chung · 2 citations
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Statistical Methods and Inference #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0907.1779
openalex publication_date 2009/07/10 · arxiv created 2009/10/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the \sc classified stable matching problem, 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. A further 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.