Fair and large stable matchings in the stable marriage and student-project allocation problems

In this thesis, we present new algorithmic and complexity results for specific matching problems involving preferences. In particular we study the Stable Marriage problem (SM) and the Student-Project Allocation problem (SPA) and their variants. A matching in these scenarios is an allocation of men to women (SM) or students to projects (SPA). Primarily we are interested in finding matchings that are stable. A stable matching is a matching that admits no blocking pair, which is a pair of agents (not already allocated together) who would rather deviate from the given matching and become assigned to each other. In addition to stability, other objectives may be applied. We focus on finding either fair or large stable matchings in SM and SPA. In the Stable Marriage problem with Incomplete lists (SMI), the rank of a matched man or woman, with respect to a matching, is the position of their assigned partner on their preference list. The degree of the set of men in a matching is the rank of a worst-off man, over all matched men. A similar definition exists for the set of women. The cost of the set of men in a matching is sum of ranks of all matched men. Again a similar definition exists for the set of women. We introduce the following degree-based definitions of fairness in SMI. A stable matching is regret-equal if it minimises the difference in degree between the set of men and the set of women, over all stable matchings. Additionally, a stable matching is min-regret sum if it minimises the sum of the degree of men and the degree of women, over all stable matchings. We present polynomial-time algorithms to find these types of fair stable matchings, given an instance of SMI, and perform experiments to both test the performance of two algorithms to find a regret-equal stable matching, and to compare properties of several other types of fair stable matchings over both degree- and cost-based measures. Also in SMI, we investigate fairness in the form of profile-based stable matchings. The profile of a matching is a vector of integers, where the ith vector element indicates the number of agents assigned to their ith-choice partner. A stable matching is rank-maximal if its profile is lexicographically maximum taken over all stable matchings. A stable matching is generous if its reverse profile is lexicographically minimum taken over all stable matchings. A polynomial-time algorithm exists to find a rank-maximal stable matching, using weights that are exponential in the number of men or women [32]. We adapt this algorithm to work with polynomially-bounded weight vectors, and show using randomly-generated instances that our approach is significantly less costly in terms of space. Further experiments are carried out to compare these profile-based optimal matchings over several cost- and profile-based fairness properties. We additionally show that in the Stable Roommates problem, each of the problems of finding a rank-maximal stable matching or a generous stable matching is NP-hard. In the Student-Project Allocation problem with lecturer preferences over Students including Ties (SPA-ST) we study the problem of finding large stable matchings. A 3/2-approximation algorithm exists to find a maximum-sized stable matching in HRT, and we extend this to the SPA-ST case, developing a linear-time 3/2-approximation algorithm for the problem of finding a maximum-sized stable matching in SPA-ST. We test the performance of our approximation algorithm using the implementation of a new Integer Programming (IP) model that finds a maximum-sized stable matching, and show that in practice, our approximation algorithm produces stable matchings of size far closer to optimal than the 3/2 bound. Additionally, we give an example to show that this bound is tight. Finally, we look at fairness in the context of the Student-Project Allocation problem with lecturer preferences over Students including Ties and Lecturer targets (SPA-STL), an extension to SPA-ST in which each lecturer has an associated target, indicating their preferred number of allocations (or the number of allocations preferred by the matching scheme administrator). We first investigate load balancing without the presence of stability. A load-max-balanced matching is a matching in which the maximum difference between a lecturer’s target and their number of allocations is minimised. A load-sum-balanced matching is a matching in which the sum of differences between all lecturers’ targets and their number of allocations is minimised. Finally, a load-balanced matching is a matching that is both load-max-balanced and load-sum-balanced. We provide new polynomial-time algorithms to find matchings of these types. Additionally we show that in the presence of stability, each of the problems of finding a stable matching that is load-max-balanced, load-sum-balanced or load-balanced is NP-hard. Finally, we present new IP models for finding such types of optimal stable matching