Document Open Access Logo

Jointly Stable Matchings

Authors Shuichi Miyazaki, Kazuya Okamoto

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2017.56.pdf
  • Filesize: 488 kB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • stable marriage problem
  • stable matching
  • NP-completeness
  • linear time algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 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.

Cite As Get BibTex

Shuichi Miyazaki and Kazuya Okamoto. Jointly Stable Matchings. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 56:1-56:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.56

Author Details

Shuichi Miyazaki
Kazuya Okamoto

References

  1. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121-123, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90002-4.
  2. Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976. URL: http://dx.doi.org/10.1137/0205048.
  3. David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. URL: http://www.jstor.org/stable/2312726.
  4. David Gale and Marilda Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11(3):223-232, 1985. URL: http://dx.doi.org/10.1016/0166-218X(85)90074-5.
  5. Dan Gusfield and Robert W. Irving. The Stable marriage problem - structure and algorithms. Foundations of computing series. MIT Press, 1989. Google Scholar
  6. Robert W. Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261-272, 1994. URL: http://dx.doi.org/10.1016/0166-218X(92)00179-P.
  7. Robert W. Irving and Paul Leather. The complexity of counting stable marriages. SIAM J. Comput., 15(3):655-667, 1986. URL: http://dx.doi.org/10.1137/0215048.
  8. David F. Manlove. Stable marriage with ties and unacceptable partners. Technical Report TR-1999-29, University of Glasgow, Department of Computing Science, 1999. Google Scholar
  9. David F. Manlove. The structure of stable marriage with indifference. Discrete Applied Mathematics, 122(1-3):167-181, 2002. URL: http://dx.doi.org/10.1016/S0166-218X(01)00322-5.
  10. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013. URL: http://dx.doi.org/10.1142/8591.
  11. Jay Sethuraman and Chung-Piaw Teo. A polynomial-time algorithm for the bistable roommates problem. J. Comput. Syst. Sci., 63(3):486-497, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1791.
  12. Boris Spieker. The set of super-stable marriages forms a distributive lattice. Discrete Applied Mathematics, 58(1):79-84, 1995. URL: http://dx.doi.org/10.1016/0166-218X(94)00080-W.
  13. Edward G. Thurber. Concerning the maximum number of stable matchings in the stable marriage problem. Discrete Mathematics, 248(1-3):195-219, 2002. URL: http://dx.doi.org/10.1016/S0012-365X(01)00194-7.
  14. Bob P. Weems. Bistable versions of the marriages and roommates problems. J. Comput. Syst. Sci., 59(3):504-520, 1999. URL: http://dx.doi.org/10.1006/jcss.1999.1657.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact