6.7 ***Gale-Shapley Stable marriage/matching algorithm***

In more real-life scenarios, like college admission, students have preferences for colleges (i.e., a ranking) and so do the colleges. This in graph-theoretic terms, corresponds to a complete bi-partite graph with every vertex ranking every other vertex in the opposite partition. Stability of matching here would refer to the fact that there is no pair of vertices that would prefer each other over their current pairing i.e., if $u\sim v$ and $w\sim x$ in $M$ with $u,w\in V_1,v,x\in V_2$, then it is not possible that $u$ prefers $x$ to $v$ and $x$ prefers $u$ to $w$.

Does such a matching for any possible ? And more importantly, can one construct such a matching ?

Gale-Shapley Algorithm : In 1962, David Gale and Lloyd Shapley ([Gale and Shapley 1962]) proposed an algorithm to achieve stable matching and this probably the best known of such algorithms. Along with Alvin Roth, Lloyd Shapley was awarded the Noble prize in economics in 2012 for "for the theory of stable allocations and the practice of market design."

1. 1.

   Input : $n$ Men, $n$ Women and their preferences.

2. Step 1 :

   Each "unengaged" man "proposes" to the highest women who has not yet rejected him.

3. Step 2 :

   Each woman agrees to get "engaged" to the "highest proposer" in her list. If previously engaged and current proposer is ranked hgiher, she rejects her the previous engagement. The other proposers are also rejected.

4. Step 3 :

   If any "engagement" is nullified, the man becomes "unengaged"

5. Step 4:

   Go to Step 1 if there is an "unengaged" man.

See [West 2001, Theorem 3.2.18] for the formal theorem statement and proof of the algorithm.