We introduce the 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.
Fleiner @cite_18 studied the many-many stable matching in a much more general context. Using a fixed-point approach, he proved that stable matchings always exist provided that the preference of each entity is a . Roughly speaking, such a function can be realized by imposing a matroid over a linear order of elements. In , supposing that there is no lower bound on the classes, then each laminar family is equivalent to a partition matroid. We prove that stable matchings always exist in this situation. Hence, our algorithm in Section 2 can be seen as a constructive proof of a special case of Fleiner's existence theorem.
@cite_18
1978696336
We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope. Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem ( ), to study the mechanism design questions without payment. The possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of , and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in DG10 . Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model. The stable roommates problem is a well-known problem of matching n people into n2 disjoint pairs so that no two unmatched persons both prefer each other to their partners under the matching. We call such a matching “a complete stable matching.” It is known that a complete stable matching may not exist. Irving described an O(n2) algorithm that would find one complete stable matching if there is one, or would report that none exists. In this paper, we give a necessary and sufficient condition for the existence of a complete stable matching; namely, the non-existence of any odd party, which will be defined subsequently. We define a new structure called a “stable partition,” which generalizes the notion of a complete stable matching, and prove that every instance of the stable roommates problem has at least one such structure. We also show that a stable partition contains all the odd parties, if there are any. Finally we have an O(n2) algorithm that finds one stable partition which in turn gives all the odd parties. The stable marriage problem is that of matching n men and n women, each of whom has ranked the members of the opposite sex in order of preference, so that no unmatched couple both prefer each other to their partners under the matching. At least one stable matching exists for every stable marriage instance, and efficient algorithms for finding such a matching are well known. The stable roommates problem involves a single set of even cardinality n, each member of which ranks all the others in order of preference. A stable matching is now a partition of this single set into n2 pairs so that no two unmatched members both prefer each other to their partners under the matching. In this case, there are problem instances for which no stable matching exists. However, the present paper describes an O(n2) algorithm that will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching.