Stable marriage problem


Stable marriage problem

In mathematics, the stable marriage problem (SMP) is the problem of finding a stable matching — a matching in which no element of the first matched set prefers an element of the second matched set that also prefers the first element.

It is commonly stated as:: 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".

olution

In 1962, David Gale and Lloyd 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. [D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", "American Mathematical Monthly" 69, 9-14, 1962.] [Harry Mairson: "The Stable Marriage Problem", "The Brandeis Review" 12, 1992 ( [http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html online] ).]

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. Each woman then considers all her suitors and tells the one she most prefers "Maybe" and all the rest of them "No". She is then provisionally "engaged". In each subsequent round, each unengaged man proposes to one woman to whom he has not yet proposed (the woman may or may not already be engaged), and the women once again reply with one "maybe" and reject the rest. This may mean that already-engaged women can "trade up", and already-engaged men can be "jilted".

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:" Let Alice be a woman and Bob be a man. They are each paired/partnered/married, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. 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, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.

Algorithm

function stableMatching { Initialize all "m" ∈ M and "w" ∈ W to "free" while ∃ "free" man "m" who still has a woman w to propose to { w = m's highest ranked such woman if w is "free" (m, w) become "engaged" else some pair (m', w) already exists if w prefers m to m' (m, w) become "engaged" m' becomes "free" else (m', w) remain "engaged" } }

Gale-Shapley pairing

The pairing generated by the Gale-Shapley algorithm has a number of interesting properties. In particular, one may prove 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.

"Proof that the Gale-Shapley pairing is female-pessimal:" We can show this using the fact a male-optimal pairing must be female-pessimal. Consider any woman W paired to a man M in the male-optimal stable pairing G. Also consider an arbitrary stable pairing S, where M and W are not paired. Because G is male-optimal, M prefers W to his match in S. Because S is stable, W must prefer her match in S to M. Thus women will always prefer another match in any stable pairing over their match in a male-optimal pairing. Thus, the Gale-Shapley pairing is female-pessimal because it is male-optimal (see above).

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. [ [http://www.dcs.gla.ac.uk/research/algorithms/stable/ Stable Matching Algorithms] ]

Similar problems

The weighted matching problem seeks 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.

The stable roommates problem is similar to the stable marriage problem, but differs in that all participants belong to a single pool (instead of being divided into equal numbers of "men" and "women").

The hospitals/residents problem — also known as the college admissions problem — differs from the stable marriage problem in that the "women" can accept "proposals" from more than one "man" (e.g., a hospital can take multiple residents, or a college can take an incoming class of more than one student). Algorithms to solve the hospitals/residents problem can be "hospital-oriented" (female-optimal) or "resident-oriented" (male-optimal).

The hospitals/residents problem with couples allows the set of residents to include couples who must be assigned together, either to the same hospital or to a specific pair of hospitals chosen by the couple (e.g., a married couple want to ensure that they will stay together and not be stuck in programs that are far away from each other). The addition of couples to the hospitals/residents problem renders the problem NP-complete. [D. Gusfield and R. W. Irving, "The Stable Marriage Problem: Structure and Algorithms," p. 54; MIT Press, 1989.]

References

External links

*http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
*http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
* [http://www.sephlietz.com/gale-shapley/ Gale-Shapley JavaScript Demonstration]
* [http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture5.pdf SMP Lecture Notes]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Stable roommates problem — In mathematics, especially in the fields of game theory and combinatorics, the stable roommate problem (SRP) is the problem of finding a stable matching mdash; a matching in which there is no pair of elements, each from a different matched set,… …   Wikipedia

  • Marriage problem — In mathematics, marriage problem can refer to: the assignment problem the secretary problem the stable marriage problem This disambiguation page lists articles associated with the same title. If an …   Wikipedia

  • Marriage in the United States — Chart illustrating marital status in the United States Marriage is the state of being united to a person of the opposite sex as husband or wife in a consensual and contractual relationship recognized by law. [1] However, marriage can also be the… …   Wikipedia

  • Assignment problem — The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph. In its most… …   Wikipedia

  • Mixed-orientation marriage — For the more general concept, see Mixed marriage Relationships …   Wikipedia

  • Cousin marriage — Charles Darwin and his wife Emma were first cousins. Cousin marriage is marriage between two cousins. In various jurisdictions and cultures, such marriages range from being considered ideal and actively encouraged, to being uncommon but still… …   Wikipedia

  • Open marriage relationship — Relationships Types …   Wikipedia

  • MIXED MARRIAGE, INTERMARRIAGE — The terms intermarriage and mixed marriage are used interchangeably. Intermarriage in the present context is defined as a marriage where one partner professes a religion different from that of his spouse. Marriages in which a partner has… …   Encyclopedia of Judaism

  • Members of the 39th Canadian Parliament and same-sex marriage —   Same sex marriage in Canada Legal Civil Marriage Act Reference re Same Sex Marriage …   Wikipedia

  • National Resident Matching Program — The National Resident Matching Program (NRMP) (or the Match[1]) is a United States based non profit non governmental organization created in 1952 to help match medical school students with residency programs. The NRMP is sponsored by the American …   Wikipedia