The Finch Formerly Known As Gold

17 September 2006

Frozen shiddachery

It's called the Stable Marriage Problem, and it goes like this:

Imagine you are a matchmaker, with one hundred female clients, and one hundred male clients. Each of the women has given you a complete list of the hundred men, ordered by her preference: her first choice, second choice, and so on. Each of the men has given you a list of the women, ranked similarly. It is your job to arrange one hundred happy marriages.

It should be immediately apparent that everyone is not guaranteed to get their first choice: if a particular man is the first choice of more than one woman, only one can be matched with him, and the other women will have to make do with less. Rather than guarantee the purest of hap