2026-07-23T06:52:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8224 2024-03-06T10:41:52Z ddc:004 open_access

Jointly Stable Matchings Miyazaki, Shuichi Okamoto, Kazuya stable marriage problem stable matching NP-completeness linear time algorithm In the stable marriage problem, we are given a set of men, a set of women, and each person's preference list. Our task is to find a stable matching, that is, a matching admitting no unmatched (man, woman)-pair each of which improves the situation by being matched together. It is known that any instance admits at least one stable matching. In this paper, we consider a natural extension where k (>= 2) sets of preference lists L_i (1 <= i <= k) over the same set of people are given, and the aim is to find a jointly stable matching, a matching that is stable with respect to all L_i. We show that the decision problem is NP-complete already for k=2, even if each person's preference list is of length at most four, while it is solvable in linear time for any k if each man's preference list is of length at most two (women's lists can be of unbounded length). We also show that if each woman's preference lists are same in all L_i, then the problem can be solved in linear time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Miyazaki and Kazuya Okamoto 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.56 urn:nbn:de:0030-drops-82244 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.56 eng https://creativecommons.org/licenses/by/3.0/legalcode