Cooper, Frances (2020) Fair and large stable matchings in the stable marriage and studentproject allocation problems. PhD thesis, University of Glasgow.
Full text available as:

PDF
Download (1MB)  Preview 
Abstract
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 StudentProject 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 worstoff 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 degreebased definitions of fairness in SMI. A stable matching is regretequal 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 minregret sum if it minimises the sum of the degree of men and the degree of women, over all stable matchings. We present polynomialtime 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 regretequal stable matching, and to compare properties of several other types of fair stable matchings over both degree and costbased measures.
Also in SMI, we investigate fairness in the form of profilebased 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 ithchoice partner. A stable matching is rankmaximal 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 polynomialtime algorithm exists to find a rankmaximal stable matching, using weights that are exponential in the number of men or women [32]. We adapt this algorithm to work with polynomiallybounded weight vectors, and show using randomlygenerated instances that our approach is significantly less costly in terms of space. Further experiments are carried out to compare these profilebased optimal matchings over several cost and profilebased fairness properties. We additionally show that in the Stable Roommates problem, each of the problems of finding a rankmaximal stable matching or a generous stable matching is NPhard.
In the StudentProject Allocation problem with lecturer preferences over Students including Ties (SPAST) we study the problem of finding large stable matchings. A 3/2approximation algorithm exists to find a maximumsized stable matching in HRT, and we extend this to the SPAST case, developing a lineartime 3/2approximation algorithm for the problem of finding a maximumsized stable matching in SPAST. We test the performance of our approximation algorithm using the implementation of a new Integer Programming (IP) model that finds a maximumsized 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 StudentProject Allocation problem with lecturer preferences over Students including Ties and Lecturer targets (SPASTL), an extension to SPAST 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 loadmaxbalanced matching is a matching in which the maximum difference between a lecturer’s target and their number of allocations is minimised. A loadsumbalanced matching is a matching in which the sum of differences between all lecturers’ targets and their number of allocations is minimised. Finally, a loadbalanced matching is a matching that is both loadmaxbalanced and loadsumbalanced. We provide new polynomialtime 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 loadmaxbalanced, loadsumbalanced or loadbalanced is NPhard. Finally, we present new IP models for finding such types of optimal stable matching.
Item Type:  Thesis (PhD) 

Qualification Level:  Doctoral 
Keywords:  Stable matchings, Stability, Matching problems, Optimality, Fairness, Algorithms, Complexity, Maximality, IP models. 
Subjects:  Q Science > Q Science (General) Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software 
Colleges/Schools:  College of Science and Engineering > School of Computing Science 
Funder's Name:  Engineering and Physical Sciences Research Council (EPSRC) 
Supervisor's Name:  Manlove, Prof. David and Meeks, Dr. Kitty 
Date of Award:  2020 
Depositing User:  Dr Frances Cooper 
Unique ID:  glathesis:202081622 
Copyright:  Copyright of this thesis is held by the author. 
Date Deposited:  04 Sep 2020 15:03 
Last Modified:  04 Sep 2020 16:04 
URI:  http://theses.gla.ac.uk/id/eprint/81622 
Related URLs: 
Actions (login required)
View Item 