Stable marriage problem
|
|
In mathematics, the stable marriage problem (hereafter: SMP) is as follows:
- Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".
| Contents |
Solving the problem
In 1962, Gale and Shapley proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an algorithm to do so.
The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed, and she accepts or rejects him based on whether she is already engaged to someone she prefers. If she is unengaged, or engaged to a man lower down her preference list than her new suitor, she accepts the proposal (and in the latter case, the other man becomes unengaged again).
This algorithm guarantees that:
Everyone gets married: Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.
The marriages are stable: At the end, it is not possible for a man and a woman (call them Alice and Bob) to both prefer each other to their current partners. This is easy to show. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more (since women only switch partners to increase their happiness). If Alice rejected his proposal, she was already with someone she liked more than Bob.
Stable Matching Algorithm
function stableMatching {
Initialize all m <math>\in<math> M and w <math>\in<math> W to free
while <math>\exists<math> free man m who still has a woman w to propose to {
w = m's highest ranked such woman
if w is free
engage (m, w)
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become married
m' becomes free
else
(m', w) remain married
}
}
Properties of the Gale-Shapley pairing
The pairing generated by the Gale-Shapley algorithm has a number of interesting properties. In particular, we can show that, in some sense, the Gale-Shapley pairing, in the form presented here, is male-optimal and female-pessimal (it would be the reverse, of course, if the roles of "male" and "female" participants in the algorithm were interchanged). To see this, consider the definition of a feasible marriage. We say that the marriage between man A and woman B is feasible if there exists a stable pairing in which A and B are married. When we say a pairing is male-optimal, we mean that every man is paired with his highest ranked feasible partner. Similarly, a female-pessimal pairing is one in which each female is paired with her lowest ranked feasible partner.
Proof that the Gale-Shapley pairing is male-optimal: We go by contradiction. Suppose the pairing generated by the Gale-Shapley algorithm were not male-optimal. Let T be the first iteration where a man is rejected by his optimal partner. Let man M be one man who is rejected by his optimal partner, woman W, during this iteration. Then woman W must have rejected man M for some other man, man Z. Further, since this is the first iteration where a man is rejected by his optimal partner, woman W must be at least as high on man Z's preference list as his optimal partner. Also note that, since woman W is man M's optimal partner, there exists some stable pairing S where man M is paired with woman W. Then, in pairing S, woman W prefers man Z to man M (since she rejected M for Z in the Gale-Shapley algorithm) and man Z prefers woman W to his partner in S, since he likes woman W at least as much as his optimal partner and, by our definition of optimal, he could not be paired with anyone better than this. But then, by definition, this pairing is unstable, since man Z and woman W prefer each other to their partners in S. We have reached a contradiction, so the Gale-Shapley algorithm must produce a male-optimal pairing. <math>\Box<math>
Proof that the Gale-Shapley pairing is female-pessimal: We can show this using the fact that the Gale-Shapley pairing is male-optimal (see above). Again, we go by contradiction. Suppose there were a stable pairing S where a woman W is paired with a man Z who she likes less than the man she is paired with by the Gale-Shapley algorithm, man M. We know the Gale-Shapley algorithm is male-optimal, and since it pairs man M with woman W, she must be his optimal woman, and therefore, in S, he can only be paired with someone lower on his preference list than woman W. Further, we already know that woman W prefers man M to man Z, with whom she is paired in S. So, S is unstable since W and M would rather be with each other than with their partners. Thus, we have a contradiction and the Gale-Shapley algorithm produces a female-pessimal pairing. <math>\Box<math>
Real world applications
There are a number of real world applications for the Gale-Shapley solution. For example, their algorithm has been used to pair graduating medical students with hospital jobs.
Similar problems
The weighted matching problem is to find a matching in a weighted bipartite graph that has maximum weight. Maximum weighted matchings do not have to be stable, but in some applications a maximum weighted matching is better than a stable one.
Other observations
The SMP can be used to illustrate certain social phenomena, such as the effect of beauty on partner choice. When the preferences of the men and women are purely random, everyone is quite likely to get a partner that is high on their preference list. However, if the preferences tend to aim at certain beautiful individuals, a person's chances of getting a partner they really want is drastically reduced, as their top choices are massively in demand. Hence, it has been said that the SMP proves that beauty just makes everyone unhappy.
Further reading
- D. Gale, and L. S. Shapley: College Admissions and the Stability of Marriage, in American Mathematics Monthly 69, 9-14, 1962.
- Harry Mairson: The Stable Marriage Problem, in The Brandeis Review 12, 1992 (online (http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html)).