Notes
Stable matching problem
Given two sets X and Y a matching M is a set of pairs (xi, yi) so that each x and y occurs in exactly one matching.
Bipartite graph
A bipartite graph consists of two distinct sets of nodes U and V with only edges (u, v) where u is from U and v from V.
Thus the matchings created from the stable matching problem are a bipartite graph. Assume each node in U has a ranking of its prefered nodes in V and each node in V has a ranking of the nodes in U. Then we can create a stable matching by; starting with a node u in U pair u with its most preffered node in v, this makes a temporary matching (u, v). If later in the algorithm another node u which is better ranked in v's list matches the old match is broken and the new one is created.
A matching is unstable if it has to pairs (u_a, v_a), (u_b, v_b) and
- u_a prefers v_b and v_b prefers u_a or if,
- v_a prefers u_b and u_b prefers v_a.
A stable matching is a perfect matching which contains no unstable pairs.
An algorithm for solving this problem is the Gale-shapley algorithm.
Gale-Shapley algorithm
Proving the Gale-Shapley algorithm can be done by reasoning.