The exchange-stable marriage problem

Article English OPEN
Cechlarova, K. ; Manlove, D.F. (2005)
  • Publisher: Elsevier
  • Journal: Discrete Applied Mathematics (issn: 0166-218X, vol: 152, pp: 109-122)
  • Related identifiers: doi: 10.1016/j.dam.2005.06.003
  • Subject: QA | Applied Mathematics | Discrete Mathematics and Combinatorics

In this paper we consider instances of stable matching problems, namely the classical stable marriage (SM) and stable roommates (SR) problems and their variants. In such instances we consider a stability criterion that has recently been proposed, that of <i>exchange-stability</i>. In particular, we prove that ESM — the problem of deciding, given an SM instance, whether an exchange-stable matching exists — is NP-complete. This result is in marked contrast with Gale and Shapley's classical linear-time algorithm for finding a stable matching in an instance of SM. We also extend the result for ESM to the SR case. Finally, we study some variants of ESM under weaker forms of exchange-stability, presenting both polynomial-time solvability and NP-completeness results for the corresponding existence questions.
  • References (21)
    21 references, page 1 of 3

    [2] D.J. Abraham, K. Cechl´arov´a, D.F. Manlove, and K. Mehlhorn. Pareto optimality in house allocation problems. In Proceedings of ISAAC 2004: the 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 3-15. Springer-Verlag, 2004.

    [3] J. Alcalde. Exchance-proofness or divorce-proofness? Stability in one-sided matching markets. Economic Design, 1:275-287, 1995.

    [4] K. Cechl´arov´a. On the complexity of exchange-stable roommates. Discrete Applied Mathematics, 116(3):279-287, 2002.

    [5] D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.

    [6] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, CA., 1979.

    [7] D. Gusfield and R.W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.

    [8] J.E. Hopcroft and R.M. Karp. A n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2:225-231, 1973.

    [9] A. Hylland and R. Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293-314, 1979.

    [10] R.W. Irving. An efficient algorithm for the “stable roommates” problem. Journal of Algorithms, 6:577-595, 1985.

    [11] R.W. Irving. Matching medical students to pairs of hospitals: a new variation on a well-known theme. In Proceedings of ESA '98: the Sixth European Symposium on Algorithms, volume 1461 of Lecture Notes in Computer Science, pages 381-392.

  • Similar Research Results (1)
  • Metrics
    No metrics available
Share - Bookmark