Matching Under Preferences

Abstract

The Stable Marriage Problem is a classic problem of matching under preferences. It involves two sets of agents, classically refered to as men and women each having a preference list over the other set. A matching is a disjoint collection of man woman pairs. We define a blocking edge with respect to a matching to be a (man,woman) pair, say (m,w), such that both m and w prefer each other over their matched partners in the matching. A Stable Matching is a matching with no blocking pairs. In the 1960s Gale and Shapley gave an algorithm, now known as the Gale-Shapley algorithm, that solves the stable marriage problem in polynomial time. Various extentions of the Stable Marriage problem have been studied. The simplest and most natural extension is to incomplete lists, called a the Stable Marriage problem with incomplete lists, or SMI. As the name suggests an instance of this problem would involve the preference lists to be incomplete. The GS algorithm can be easily extended to this problem and again it has been shown that a stable matching always exists and can be found in polynomial time. If indifference is introduced in the problem instance, that is the preference lists may involve ties and are incomplete as well, the problem is referred to as The Stable Marriage problem with Ties and Incomplete Lists or SMTI in short. With ties there are three different notions of stablity - super stability, strong stability and weak stability. We are only interested in weakly stable matchings. A matching in an SMTI instance is weakly stable if there is no pair (m,w) such that m and w both strictly prefer each other over their respective matched partners. It has been shown that arbitrarily breaking the ties in an SMTI problem instance I we get a corresponding SMI instance I� such that a stable matching in I� is a weakly stable matching in I. Depending on how we break the ties the size of the stable matching obtained may vary. The problem of finding a maximum sized or a minimum sized weakly stable matching is shown to be NP-hard. When the underlying graph is not a bipartite graph, the problem is commonly known as the Stable Roommates problem. We can define versions of SMI and SMTI for the Stable Roommates setting as well and we call them SRI and SRTI respectively. Ronn showed that in an SRTI instance the problem of deciding whether a weakly stable matching exists or not is NP-complete. In this dissertation we study the problem of finding a maximum (minimum) sized weakly stable matching in SMTI and SRTI instances in the realm of parameterized xi xii complexity. We show that these problems are fixed parameter tractable by giving polynomial kernels. Also when the underlying graph is planar we show that we can improve the kernel further to a linear kernel thus giving us better algorithms. Another extension of the Stable Marriage problem gives us the well known Hospital/ Residents Problem (HR Problem). This problem is a many-one stable matching problem. An instance of Hospital/Residents Problem is again a bipartite graph, H ∪ R, where H is the set of hospitals and R the set of residents. Each hospital has a strict preference over a subset of residents and each resident has a strict preference over a subset of hospitals. With every hospital we have an associated number called its upper quota. Our goal is to assign residents to hospitals such that for every hospital not more than its upper quota residents are assigned to it, and the assignment is ‘stable’. Again a stable assignment is an assignment with no blocking pairs, but the definition of a blocking pair is slightly different than the one defined for a stable marraige instance. The GS algorithm can be used in this setting as well to find a stable matching and again a stable matching always exists. When we associate a lower quota with every hospital and add an additional constraint to the problem of assigning at least lower capacity number of residents to each hospital. Now we want to find such a feasible matching which is as stable as possible. A stable matching found by GS may not be feasible and by the Rural Hospital Theorem which states that all stable matchings match the same set of vertices, we are assured that no stable matching would be feasible. So we look for a feasible matching as ‘stable’ as possible. In other words we look for a matching with either fewest number of blocking edges or fewest number of blocking residents. Both these problems of finding a feasible matching minimizing the number of blocking edges or blocking residents are shown to be NP-hard. We study the Hospital/Residents problem with lower quotas in the realm of parameterized complexity. We give an XP Algorithm with parameter blocking residents. For other parameters sum of lower quotas and colleges with positive lower quota we show that the problem is W[1] hard.