===== Chapter 1: Introduction =====

==== 1.1 - Stable Matching ====

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
	

=== The Problem ===

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


=== Designing the Algorithm ===

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:
<code>
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
</code>

=== Analyzing the Algorithm ===

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.