Through time, the increase of divorces during
the past couple of years has greatly increased. In the U.S, the algorithm
of Gale and Shapley (1962) is sometimes used to match hospitals to medical
interns (Skiena 1990, p. 245). This algorithm has also been used by colleges to match roommates. The stable marriage problem is a matching problem in which no one woman
(in this case) can be matched with two men at the same time. Given : To do this we go by
contradiction. Suppose the pairing formed by the Gale-Shapley
algorithm were not male-optimal. Let X be the first iteration where a
man is rejected by his "partner". Let man M be one man who is
rejected by his "partner", woman(W), during this iteration. Then
woman W must have rejected man M for another man, man Z. Since this is the first iteration where a man is rejected by his
"partner", woman(W) must be one of man Z's top preferences
as his preferred "partner". Also, since woman W is man M's preferred 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. I will be conducting this problem by gathering an even amount of females and males and having them rank each other so that their 1st choice is the person they prefer the most and would rather marry and their last choice is the person they would least want to be with. Using Gale and Shapley algorithm and applying the |