Algorithmic aspects of stable matching problems

[摘要] The Stable Marriage problem (SM), the Hospitals/Residents problem (HR) and the Stable Roommates problem (SR) are three classical stable matching problems that were first studied by Gale and Shapley in 1962.These problems have widespread practical application in centralised automated matching schemes, which assign applicants to posts based on preference lists and capacity constraints in both the UK and internationally.Within such schemes it is often the case that an agent's preference list may be incomplete, and agents may also be allowed to express indifference in the form of ties. In the presence of ties, three stability criteria can be defined, namely weak stability, strong stability and super-stability.In this thesis we consider stable matching problems from an algorithmic point of view. Some of the problems that we consider are derived from new stable matching models, whilst others are obtained from existing stable matching models involving ties and incomplete lists, with additional natural restrictions on the problem instance.Furthermore, we also explore the use of constraint programming with both SM and HR.We first study a new variant of the Student-Project Allocation problem in which each student ranks a set of acceptable projects in preference order and similarly each lecturer ranks his available projects in preference order. In this context, two stability definitions can be identified, namely weak stability and strong stability.We show that the problem of finding a maximum weakly stable matching is NP-hard.However, we describe two 2-approximation algorithms for this problem.Regarding strong stability, we describe a polynomial-time algorithm for finding such a matching or reporting that none exists.Next we investigate SM with ties and incomplete lists (SMTI), and HR with ties (HRT), where the length of each agent's list is subject to an upper bound. We present both polynomial-time algorithms and NP-hardness results for a range of problems that are derived from imposing upper bounds on the length of the lists on one or both sides.We also consider HRT, and SR with ties and incomplete lists (SRTI), where the preference lists of one or both sets of agents (as applicable) are derived from one or two master lists in which agents are ranked.For super-stability, in the case of each of HRT and SRTI with a master list, we describe a linear-time algorithm that simplifies the algorithm used in the general case.In the case of strong stability, for each of HRT and SRTI with a master list, we describe an algorithm that is faster than that for the general case. We also show that, given an instance I of SRTI with a master list, the problem of finding a weakly stable matching is polynomial-time solvable.However, we show that given such an I, the problem of finding a maximum weakly stable matching is NP-hard.Other new stable matching models that we study are the variants of SMTI and SRTI with symmetric preferences.In this context we consider two models that are derived from alternative ways of interpreting the rank of an agent in the presence of ties. For both models we show that deciding if a complete weakly stable matching exists is NP-complete.Then for one of the models we show that each of the problem of finding a minimum regret and an egalitarian weakly stable matching is NP-hard and that the problem of determining if a (man,woman) pair belongs to a weakly stable matching is NP-complete. We then describe algorithms for each of the problems of finding a super-stable matching and a strongly stable matching, or reporting that none exists, given instances of SRTI and HRT with symmetric preferences (regardless of how the ranks are interpreted).Finally, we use constraint programming techniques to model instances of SM and HR.We describe two encodings of SM in terms of a constraint satisfaction problem.The first model for SM is then extended to the case of HR.This encoding for HR is then extended to create a model for HRT under weak stability.Using this encoding we can obtain, with the aid of search, all the weakly stable matchings, given an instance of HRT.

[发布机构] University:University of Glasgow;Department:School of Computing Science

[关键词] algorithms, matching, stable matching, constraint programming, student project allocation, Hospitals/Residents, stable roommates, stable marriage, master lists, symmetric preferences