Marriage Problem

WHAT IS IT?

There are 64 single men and 64 single women, all heterosexual its is presumed, who want to get married. Each one ranks all possible mates. The problem is how to find the set of marriages so that no two people (one man one woman) that are not married to each other do, in fact, prefer each other over their assigned partners.

The solution we implement is the deferred acceptance algorithm from

• D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9--15, Mathematical Association of America. 1962.

In this model the woman are the pink circles and the men are blue (well, cyan). When a man connects to a woman (edge) it means he proposes to her. The numbers in the nodes represent the preference of that node for its partner. The algorithm works as follows

1. while there are women without a proposal
2. every man proposes to the his most preferred woman who has not rejected him
3. every woman with multiple proposals rejects all but the one she prefers the most

When done, all women have one proposal which they accept and live happily ever after. The resulting marriages are stable.

The scatter plot shows the marriages that we find, where the x coordinate is the man's preference for the woman and the y coordinate is the woman's preference for the man (1 means her most preferred). Notice that even though women turn down men, the men do much better.

CREDITS

Jose M Vidal

CHANGES

20100623