Sotomayor, M. (1996), A non constructive elementary proof of the existence of stable marriages, Games and Economic Behavior, 13: 135–7. Link
Abstract Gale and Shapley showed in their well known paper of 1962 (Amer. Math. Monthly 69, 9–14) 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.
In this short note, the author establishes the existence of stable matchings for the marriage market, i.e., one-to-one matching market, without employing any algorithms. Her key idea is a new concept that she calls a simple matching, which is defined as follows:
A matching is simple if, in the case a blocking pair (m, w) exists, w is single.
Since the set of simple matchings is nonempty and finite, there must exist a specific matching that I call here (for notational convenience) an M-simple matching:
A simple matching is M-simple if it cannot be (weakly) Pareto dominated for men by any other simple matching.
Then, she shows that such M-simple matching is stable. The basic logic is that the existence of blocking pair necessarily induces Pareto improvement for men (since w is single), which contradicts to the Pareto efficiency of M-simple matching for men.
As the author claims, the proof is very shout and simple, yet quite novel I think. To explain her proof strategy in a different way, she
- focuses on the subset of stable matchings,
- characterize it by "M-simple matching," and
- shows that the set is non-empty.
It is immediate that M-simple matching is unique and coincides with M-optimal stable matching when all the preferences are strict. In this way, we can see that her idea is somewhat related to the existence of one-sided optimal stable matchings, a widely known result in the literature.
A minor remark: The definition of matching in the paper incorporates individual rationality, and consequently that of of stable matchings pays attention only on blocking pairs. This looks a bit non-standard while nothing is lost in her analysis.
A final remark: I like this paper very much :)