Miyazaki, Shuichi ;
Okamoto, Kazuya
Jointly Stable Matchings
Abstract
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 NPcomplete 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.
BibTeX  Entry
@InProceedings{miyazaki_et_al:LIPIcs:2017:8224,
author = {Shuichi Miyazaki and Kazuya Okamoto},
title = {{Jointly Stable Matchings}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {56:156:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8224},
URN = {urn:nbn:de:0030drops82244},
doi = {10.4230/LIPIcs.ISAAC.2017.56},
annote = {Keywords: stable marriage problem, stable matching, NPcompleteness, linear time algorithm}
}
2017
Keywords: 

stable marriage problem, stable matching, NPcompleteness, linear time algorithm 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

2017 