Stable Matching Problem

algorithms

Definition

Stable Matching Problem

Given two sets $A$ and $B$ with $n=|A|=|B|$ elements, where each element in both sets have preferences in the other set to match with. Find a matching $f:A\to B$ without unstable pairs.

Example:

Unstable Pair

Unstable Pair

A pair $(a,b)\in A\times B$ is called unstable if there exist a pair $(a,c)\in A\times B$ that $a$ prefers above $(a,b)$, or there exists a pair $(c,b)\in A\times B$ that $b$ prefers above $(a,b)$.

In other words, a pair $(a,b)\in A\times B$ if there exists a more preferable solution for either $a$ or $b$.

Algorithms

Brute-Force

The problem can be solved in using a brute-force approach, however, it is highly inefficient since $n!$ solutions must be considered.

Gale-Shapely

Gale–Shapley Algorithm

algorithms

Definition

Gale-Shapely Algorithm

The Gale-Shapely algorithm is an algorithm for finding a solution to the stable matching problem.

Proofs

Proof of Termination

Proof of Conclusion

Proof of Stability

Link to original