TY - JOUR
T1 - Many-to-many stable matchings with ties in trees
AU - Nakamura, Keita
AU - Kamiyama, Naoyuki
N1 - Funding Information:
Naoyuki Kamiyama was supported by JST, PRESTO. The authors would like to thank anonymous referees for helpful comments on an earlier version of this paper.
PY - 2016
Y1 - 2016
N2 - In the stable matching problem introduced by Gale and Shapley, it is known that in the case where the preference lists may involve ties, a stable matching always exists, but the sizes of stable matchings may be different. In this paper, we consider the problem of finding a maximum-size stable matching in a many-to-many matching market with ties. It is known that this problem is NP-hard even if the capacity of every agent is one. In this paper, we prove that this problem in trees can be solved in polynomial time by extending the algorithm proposed by Tayu and Ueno for the one-to-one setting.
AB - In the stable matching problem introduced by Gale and Shapley, it is known that in the case where the preference lists may involve ties, a stable matching always exists, but the sizes of stable matchings may be different. In this paper, we consider the problem of finding a maximum-size stable matching in a many-to-many matching market with ties. It is known that this problem is NP-hard even if the capacity of every agent is one. In this paper, we prove that this problem in trees can be solved in polynomial time by extending the algorithm proposed by Tayu and Ueno for the one-to-one setting.
UR - http://www.scopus.com/inward/record.url?scp=84982994477&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84982994477&partnerID=8YFLogxK
U2 - 10.15807/jorsj.59.225
DO - 10.15807/jorsj.59.225
M3 - Article
AN - SCOPUS:84982994477
SN - 0453-4514
VL - 59
SP - 225
EP - 240
JO - Journal of the Operations Research Society of Japan
JF - Journal of the Operations Research Society of Japan
IS - 3
ER -