Formal derivation of a stable marriage algorithm.

Abstract

In this paper the well-known Stable Marriage Problem is considered once again. The name of this programming problem comes from the terms in which it was first described [2]: A certain community consists of n men and n women. Each person ranks those of the opposite sex in accordance with his or her preferences for a marriage partner. We seek a satisfactory way of marrying off all members of the community. (. . . ) We call a set of marriages unstable (. . . ) if under it there are a man and a woman who are not married to each other but prefer each other to their actual mates. Question: For any pattern of preferences is it possible to find a stable set of marriages?