Definition
Stable Matching Problem
Given two sets
and with elements, where each element in both sets have preferences in the other set to match with. Find a matching without unstable pairs. Example:
Unstable Pair
Unstable Pair
A pair
is called unstable if there exist a pair that prefers above , or there exists a pair that prefers above . In other words, a pair
if there exists a more preferable solution for either or .
Algorithms
Brute-Force
The problem can be solved in using a brute-force approach, however, it is highly inefficient since
Gale-Shapely
Definition
Link to originalGale-Shapely Algorithm
The Gale-Shapely algorithm is an algorithm for finding a solution to the stable matching problem.
