The Stable Marriage Problem

How does one go about matching husbands with wives?

Is there a way to do it that will result in stable marriages? 

If we define stable marriages as the situation where no couple would prefer each other to their current partner, then the answer is yes: a stable matching does exist. We can create a situation where no new couple would be created at the cost of a current couple.

Let's say there is a finite number of singles, who all go to a dance together.

We now use something called the deferred acceptance algorithm (Gale & Shapely, 1962):

Step 1. Each man proposes to his preferred woman.

Step 2. Each woman records all the men who propose to her.

Step 3. Each woman then rejects all the men except her most preferred suitor.

Step 4. Each rejected man then proposes to his next most preferred woman.

Step 5. Repeat Step 2 onwards until all men and/or all women are matched.

Ta da! We have a stable matching. There is no new couple that could be created. If a man preferred a different woman to his partner, well, the woman would already have rejected him.

Romance versus efficiency: which will win??