PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 49-55
DOI: https://doi.org/10.7151/dmgt.1667

Dedicated to Mietek Borowiecki on the occasion of his 70th birthday and to his wife Wanda who together with Mietek create a necassary pair in each stable marriage matching.

A note on the uniqueness of stable
marriage matching

Ewa Drgas-Burchardt Faculty of Mathematics, Computer Science and Econometrics University of Zielona Góra ul. prof. Z.Szafrana 4a, 65-516 Zielona Góra, Poland

Abstract

In this note we present some sufficient conditions for the uniqueness of a stable matching in the Gale-Shapley marriage classical model of even size. We also state the result on the existence of exactly two stable matchings in the marriage problem of odd size with the same conditions.

Keywords: stable matching, Gale-Shapley model, stable perfect matching

2010 Mathematics Subject Classification: 05C70, 05C90.

References

[1]	E. Drgas-Burchardt and Z. Świtalski, A number of stable matchings in models of the Gale-Shapley type, manuscript.
[2]	J. Eeckhout, On the uniqueness of stable marriage matchings , Econom. Lett. 69 (2000) 1--8, doi: 10.1016/S0165-1765(00)00263-9.
[3]	D. Gale, The two-sided matching problem: origin, development and current issues, Int. Game Theory Rev. 3 (2001) 237--252, doi: 10.1142/S0219198901000373.
[4]	D. Gale and L.S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly 69 (1962) 9--15, doi: 10.2307/2312726.
[5]	R.W. Irving and P. Leather, The complexity of counting stable marriages, SIAM J. Comput. 15 (1986) 655--667, doi: 10.1137/0215048.
[6]	D.E. Knuth, Mariages Stables (Less Presses de l'Universite de Montreal, Montreal, 1976).
[7]	D.E. Knuth, Stable Marriage and Its Relation to other Combinatorial Problems. An Introduction to the Mathematical Analysis of Algorithms (American Mathematical Society, Providence, Rhode Island, 1997).
[8]	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) (1984) 991--1016, doi: 10.1086/261272.

Received 30 March 2012
Revised 11 November 2012
Accepted 11 November 2012