Efficient algorithms for optimal matching problems under preferences

Q Science (General);QA Mathematics;QA76 Computer software

Kwanashie, Augustine ; Manlove, David

University:University of Glasgow

Department:School of Computing Science

关键词: stable matching, student project allocation, hospitals residents problem, algorithms, matching;   

Others  :  http://theses.gla.ac.uk/6706/1/2015kwanashiephd.pdf

来源: University of Glasgow

【 摘 要 】

In this thesis we consider efficient algorithms for matching problems involving preferences,i.e., problems where agents may be required to list other agents that they findacceptable in order of preference. In particular we mainly study the Stable Marriageproblem (SM), the Hospitals / Residents problem (HR) and the Student / Project Allocationproblem (SPA), and some of their variants. In some of these problems the aimis to find a stable matching which is one that admits no blocking pair. A blocking pairwith respect to a matching is a pair of agents that prefer to be matched to each otherthan their assigned partners in the matching if any.We present an Integer Programming (IP) model for the Hospitals / Residents problemwith Ties (HRT) and use it to find a maximum cardinality stable matching. We alsopresent results from an empirical evaluation of our model which show it to be scalablewith respect to real-world HRT instance sizes. Motivated by the observation that not all blocking pairs that exist in theory will leadto a matching being undermined in practice, we investigate a relaxed stability criterioncalled social stability where only pairs of agents with a social relationship have theability to undermine a matching. This stability concept is studied in instances ofthe Stable Marriage problem with Incomplete lists (smi) and in instances of hr. Weshow that, in the smi and hr contexts, socially stable matchings can be of varyingsizes and the problem of finding a maximum socially stable matching (max smiss andmax hrss respectively) is NP-hard though approximable within 3/2. Furthermore wegive polynomial time algorithms for three special cases of the problem arising fromrestrictions on the social network graph and the lengths of agents’ preference lists.We also consider other optimality criteria with respect to social stability and establishinapproximability bounds for the problems of finding an egalitarian, minimum regretand sex equal socially stable matching in the sm context.We extend our study of social stability by considering other variants and restrictionsof max smiss and max hrss. We present NP-hardness results for max smiss evenunder certain restrictions on the degree and structure of the social network graph aswell as the presence of master lists. Other NP-hardness results presented relate to theproblem of determining whether a given man-woman pair belongs to a socially stable matching and the problem of determining whether a given man (or woman) is part ofat least one socially stable matching. We also consider the Stable Roommates problemwith Incomplete lists under Social Stability (a non-bipartite generalisation of smi undersocial stability). We observe that the problem of finding a maximum socially stablematching in this context is also NP-hard. We present efficient algorithms for threespecial cases of the problem arising from restrictions on the social network graph andthe lengths of agents’ preference lists. These are the cases where (i) there exists aconstant number of acquainted pairs (ii) or a constant number of unacquainted pairsor (iii) each preference list is of length at most 2.We also present algorithmic results for finding matchings in the spa context that areoptimal with respect to profile, which is the vector whose ith component is the numberof students assigned to their ith-choice project. We present an efficient algorithm forfinding a greedy maximum matching in the spa context — this is a maximum matchingwhose profile is lexicographically maximum. We then show how to adapt this algorithmto find a generous maximum matching — this is a matching whose reverse profile islexicographically minimum. We demonstrate how this approach can allow additionalconstraints, such as lecturer lower quotas, to be handled flexibly. We also presentresults of empirical evaluations carried out on both real world and randomly generateddatasets. These results demonstrate the scalability of our algorithms as well as someinteresting properties of these profile-based optimality criteria.Practical applications of spa motivate the investigation of certain special cases of theproblem. For instance, it is often desired that the workload on lecturers is evenly distributed(i.e. load balanced). We enforce this by either adding lower quota constraintson the lecturers (which leads to the potential for infeasible problem instances) or addinga load balancing optimisation criterion. We present efficient algorithms in both cases.Another consideration is the fact that certain projects may require a minimum numberof students to become viable. This can be handled by enforcing lower quota constraintson the projects (which also leads to the possibility of infeasible problem instances). Atechnique of handling this infeasibility is the idea of closing projects that do not meettheir lower quotas (i.e. leaving such project completely unassigned). We show that theproblem of finding a maximum matching subject to project lower quotas where projectscan be closed is NP-hard even under severe restrictions on preference lists lengths andproject upper and lower quotas. To offset this hardness, we present polynomial timeheuristics that find large feasible matchings in practice. We also present ip modelsfor the spa variants discussed and show results obtained from an empirical evaluationcarried out on both real and randomly generated datasets. These results show thatour algorithms and heuristics are scalable and provide good matchings with respect toprofile-based optimality