zbMATH — the first resource for mathematics

A nonconstructive elementary proof of the existence of stable marriages. (English) Zbl 0853.90003
Summary: D.Gale and L. S. Shapley [Am. Math. Mon. 69, 9-15 (1962; Zbl 0109.24403)] showed that stable matchings always exist for the marriage market. Their proof was constructed by means of an algorithm. Except for the existence of stable matchings, all the results for the marriage market which were proved by making use of the Gale and Shapley algorithm could also be proved without the algorithm. The purpose of this note is to fill out this case. We present here a nonconstructive proof of the existence of a stable matching for the marriage market, which is quite short and simple and applies directly to both cases of preferences: strict and nonstrict.

91B08 Individual preferences
Full Text: DOI