Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Cechlárová, Katarína; Manlove, David F. (2005)
Publisher: Elsevier BV
Journal: Discrete Applied Mathematics
Languages: English
Types: Article
Subjects: 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 exchange-stability. 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • Springer-Verlag, 1998.
    • [12] R.W. Irving. Personal communication, 2002.
    • [13] R.W. Irving. The Man-Exchange Stable Marriage problem. Technical Report TR2004-177, University of Glasgow, Department of Computing Science, 2004.
    • [14] D.E. Knuth. Stable Marriage and its Relation to Other Combinatorial Problems, volume 10 of CRM Proceedings and Lecture Notes. American Mathematical Society, 1997. English translation of Mariages Stables, Les Presses de L'Universit´e de Montr´eal, 1976.
    • [15] C. Ng and D.S. Hirschberg. Three-dimensional stable matching problems. SIAM Journal on Discrete Mathematics, 4:245-252, 1991.
    • [16] E. Ronn. NP-complete stable matching problems. Journal of Algorithms, 11:285-304, 1990.
    • [17] A.E. Roth. Incentive compatibility in a market with indivisible goods. Economics Letters, 9:127-132, 1982.
    • [18] A.E. Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6):991-1016, 1984.
    • [19] A.E. Roth and A. Postlewaite. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4:131-137, 1977.
    • [20] A.E. Roth and M.A.O. Sotomayor. Two-sided matching: a study in game-theoretic modeling and analysis, volume 18 of Econometric Society Monographs. Cambridge University Press, 1990.
    • [21] L. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:23-37, 1974.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article