The stable marriage problem is a matching with preferences. Both the men and women rank their preference of the mates.
Does the example have more applications then finding a set of stable marriages?
Suppose the new Algorithm course has a list of groups and projects. The groups could rank their preference for projects and the ranking for the groups could be instructors preference for assigning the projects.
The stable marriage problem is performed on two sets, one set Y of vertices represent men, m, and the other set of vertices, X, represent women, w. Each man and woman has ranking for the other gender with respect to marrying.
Illustrate rankings
The ranking can expressed in a single nxn matrix, where n = |Y| = |X|.
Illustrate the matrix
A set of marriages is a marriage matching, M, is a set of n (m, w) pairs.
If we represent Y and X as a complete bipartite then M is a perfect matching.
A pair (m, w) is called a blocking pair for a marriage matching, M, if both m and w prefer each other more than there mate in the marriage, M.
M is stable if there is no blocking pair. If there is a blocking pair then it is unstable.
Step 0: Start with all men and woman free
Step 1: While there are free men, select one, m, and do
Proposal: the man, m, proposes to w, the next woman on his preference list.
Response: if w is free, she accepts. If she is not free and prefer m to whom she is matched then she accepts m, which makes her previous match free.
Step 2: return the set of n matches
Illustrate the algorithm
The stable marriage algorithm terminates after no more then n2 iterations with a stable marriage.
Proof
The algorithm starts with n men and a total of n2 women on their preference list. Each preference is examine at most once. Therefore the algorithm has at most n2 iteration.
We prove the marriage matching is stable by contradiction.
Suppose that M is unstable. Therefore there exist a blocking par of m and w. They are unmatched in M. Since m proposes to each woman by the ranking on his preference list and m is mated to a woman with lower ranking then w, m must have proposed to w. Weather w refused m's proposal or accepted and then replacing it, she must be mated with some man she prefers more. This is a contradiction that m and w are a blocking pair.
The stable marriage has a shortcoming that it is not gender neutral. It is man-optimal.
Illustrate