The Stable Matching Problem was created by David Gale and Lloyd Shapley in 1962 based on the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing?

Concerns with the process: Better offers come along and change the matching of applicants, causing a domino effect

Both applicants and employers must be happy to maintain a stable state. One of the two must hold true:

• E prefers every one of its accepted applicants to A; or
• A prefers her current situation over working for employer E

Consider matching men and women where set M = {m(1),m(2),…,m(n)} represents n men and set W = {w(1),w(2),…w(n)} represents n women.

M X W denotes the set of all ordered pairs of the form (m, w).

A matching S is a set of ordered pairs with the property that each member of M and W appears in at most one pair in S. A perfect matching S’ is a matching with the property that each member of M and W appears in exactly one pair in S’.

Preferences must also be accounted for - in this problem, men rank all women. For example: m of (m,w) and w’ of (m’,w’) may prefer each other to their matching in S. In this case, the matching is unstable.

Matching S is stable if:

• It is perfect
• There is no instability with respect to S

Basic ideas:

• Initially, every person is free. During the matching process, pairs may enter a state of engagement.
• If an engaged women w of pair (m,w) receives a more preferred offer from m’, she becomes engaged to m’ and m becomes free.
• The algorithm terminates when no one is free.

Concrete description of Gale-Shapley algorithm:

Initially all m (in M) and w (in W) are free
While there is a man m who is free and hasn’t proposed to every woman
        Choose such a man m
        Let w be the highest-ranked woman in m’s preference list to whom m has not yet proposed
	If w is free then
		(m,w) become engaged
	Else w is currently engaged to m’
		If w prefers m’ to m then
			m remains free
		Else w prefers m to m’
			(m,w) become engaged
			m’ becomes free
		Endif
	Endif
Endwhile
Return the set S of engaged pairs

w remains engaged from first proposal, and her partners increase in terms of preference.

The sequence of women to whom m proposes gets worse in terms of preference.

The G-S algorithm terminates after at most n^2 iterations of the while loop.

• Proof: Each iteration is a man proposing to a new woman. There are only n^2 possible pairs of men and women and so only n^2 iterations at most.

If m is free at some point, then there remains a free w

The set S returned at termination is a perfect matching

• Proof: At termination, m must have proposed to every woman, otherwise the while loop would not have exited. This contradicts the statement that there can’t be a free man who has proposed to every woman.

Consider and execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.

• Proof: Because S is a perfect matching, an instability is assumed to create a contradiction. We must prove that (i) m prefers w’ to w or (ii) w’ prefers m to m’. Following the proven statements above, it concludes that S is a stable matching.

All executions yield the same matching, set S*.

• Proof: Suppose that an execution resulted in a match with a woman who is not his valid partner. Since men propose in descending order of preference, this means the man is rejected because the woman has a preferred partner or he was left for a preferred partner. Either way, w continues an engagement to a man. Because the matching must adhere to the code of descending preference, this statement becomes a contradiction.

In the stable matching S*, each woman is paired with her worst valid partner.

• Proof: Suppose there were a pair (m, w) in S* where m is not the worst valid partner. Then there is a stable matching with a man m’ who she likes less than m. In this situation, m is paired with a woman w’; since w is the best valid partner of m, and w’ is a valid partner of m, we see that m prefers w to w’. This shows an instability in the stable matching, leading to a contradiction.

From this we can conclude that the gender doing the proposing ends up with a more desirable stable matching.