Introduction

    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 n amount of men and n amount of women, where each person has ranked all members of the opposite sex with a number between 1 and n in order of preference, suppose you “marry” the men and women off in such a way that there are no two people of opposite sex who would both rather have each other than their current partners. If there is no such case in a couple, then all the marriages are "stable". 

    Proof that the Gale-Shapley pairing is male-optimal: 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 n amount of women and men I will prove that each person will eventually be sufficiently happy with their partners.