Jointly stable matchings

Shuichi Miyazaki () and Kazuya Okamoto ()
Additional contact information
Shuichi Miyazaki: Kyoto University
Kazuya Okamoto: Kyoto University Hospital

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 18, 646-665

Abstract: 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 (\ge 2)$$ k ( ≥ 2 ) sets of preference lists $$L_{i}$$ L i ( $$1 \le i \le k$$ 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}$$ L i . We show that the decision problem is NP-complete for the following two restricted cases; (1) $$k=2$$ k = 2 and each person’s preference list is of length at most four, and (2) $$k=4$$ k = 4 , each man’s preference list is of length at most three, and each woman’s preference list is of length at most four. On the other hand, we show that 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}$$ L i , then the problem can be solved in linear time.

Keywords: Stable marriage problem; Stable matching; NP-completeness; Linear time algorithm (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00402-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00402-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00402-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().