Example 3 Consider the following 8-agent problem: latter and the family of Pareto optimal matchings in the following exampl To prove the incompatibility between almost stable matchings and maximum
subdirectory_arrow_right Figure source:
Abstract: In this paper we propose a new family of matchingsas solution for the roommate problem with strict preferences, when stable matchings may not exist. To define these matchings we proceed as follows: We introduce the solution of maximum irreversibility, a strong notion of stability, and consider two other existing solutions that deal with unsolvable roommate problems: the almost stable matchings (Abraham et al. [2]) and the maximum stable matchings (Tan [31] [33]). Although each of these core consistent solutions is a good candidate for solving roommate problems, we find that it is not possible to reconcile almost stability with any of the other two. Hence we select the family of matchings, the Q-stable family, that lie in the intersection of the maximum irreversible matchings and maximum stable matchings. Then we offer an efficient algorithm to compute a member of this family: a Q∗-stable matching. ∗This research is supported by the Spanish Ministry of Science and Innovation (ECO2010...
... Read more Related Papers Abstract: are circulated to promote discussion and provoque comments. Any references to discussion papers should clearly state that the paper is preliminary. Materials published in this series may subject to further publication.
... Read more
Abstract: An instance of the classical Stable Roommates problem (sr) need not admit a stable matching. This motivates the problem of finding a matching that is "as stable as possible", i.e. admits the fewest number of blocking pairs. In this paper we prove that, given an sr instance with n agents, in which all preference lists are complete, the problem of finding a matching with the fewest number of blocking pairs is NP-hard and not approximable within n 1 2 −ε , for any ε > 0, unless P=NP. If the preference lists contain ties, we improve this result to n 1−ε . Also, we show that, given an integer K and an sr instance I in which all preference lists are complete, the problem of deciding whether I admits a matching with exactly K blocking pairs is NP-complete. By contrast, if K is constant, we give a polynomial-time algorithm that finds a matching with at most (or exactly) K blocking pairs, or reports that no such matching exists. Finally, we give upper and lower bounds for the minimum number of blocking pairs over all matchings in terms of some properties of a stable partition, given an sr instance I.
... Read more
Abstract: The lack of stability in some matching problems suggests that alternative solution concepts to the core might be applied to find predictable matchings. We propose the absorbing sets as a solution for the class of roommate problems with strict preferences. This solution, which always exists, either gives the matchings in the core or predicts some other matchings when the core is empty. Furthermore, it satisfies an interesting property of outer stability. We also characterize the absorbing sets, determine their number and, in case of multiplicity, we find that they all share a similar structure.
... Read more
Abstract: We introduce a restriction of the stable roommates problem in which roommate pairs are ranked globally. In contrast to the unrestricted problem, weakly stable matchings are guaranteed to exist, and additionally, can be found in polynomial time. However, it is still the case that strongly stable matchings may not exist, and so we consider the complexity of finding weakly stable matchings with various desirable properties. In particular, we present a polynomial-time algorithm to find a rankmaximal (weakly stable) matching. This is the first generalization of the algorithm due to Irving et al.
... Read more
Abstract: We show that, given two matchings for a room-mates problem of which say the second is stable, and given a non-empty subset of agents S if (a) no agent in S prefers the first matching to the second, and (b) no agent in S and his room-mate in S under the second matching prefer each other to their respective room-mates in the first matching, then no room-mate of an agent in S prefers the second matching to the first. This result is a strengthening of a result originally due to Knuth (1976). In a paper by Sasaki and Toda (1992) it is shown that if a marriage problem has more than one stable matchings, then given any one stable matching, it is possible to add agents and thereby obtain exactly one stable matching, whose restriction over the original set of agents, coincides with the given stable matching. We are able to extend this result here to the domain of room-mates problems. We also extend a result due to Roth and Sotomayor (1990) originally established for two-sided matching problems in the following manner: If in a room-mates problem, the number of agents increases, then given any stable matching for the old problem and any stable matching for the new one, there is at least one agent who is acceptable to this new agent who prefers the new matching to the old one and his room-mate under the new matching prefers the old matching to the new one. Sasaki and Toda (1992) shows that the solution correspondence which selects the set of all stable matchings, satisfies Pareto Optimality, Anonymity, Consistency and Converse Consistency on the domain of marriage problems. We show here that if a solution correspondence satisfying Consistency and Converse Consistency agrees with the solution correspondence comprising stable matchings for all room-mates problems involving four or fewer agents, then it must agree with the solution correspondence comprising stable matchings for all room-mates problems.
... Read more
