Stable Marriage Problem

Stable Marriage Problem

The stable marriage problem is a matching problem between two equally sized groups. Each element of a group has an ordering of preferences for elements of the other group. A solution would match pairs optimally, maximizing preference.

Matching library

The matching library can solve these solutions.

It also contains a concise explanation of the problem.

Stability

The difficulty in finding a solution is achieving stability. A participant would want to change their pairing, if a higher preference is available. By switching, this frees up their former partner, which triggers another set of evaluations (instability). Convergence on stability means that all participants can not find another for whom they would both be better matched together. In this sense, stability is when we arrive at a “deadlock”.

Variation

Stable Roommate Problem

The stable roommate problem is a matching problem but there is only one pool. It’s the idea that a big group splits into smaller groups of roommates.

Another example would be when kids find a partner for a school project.

Hospitals/Residents Problem

The hospitals/residents problem is a variation of the stable marriage problem but there is a 1:N matching. Each hospital has several open positions and each resident wants to work in one of these positions.

This is the ranking system they used at my university for matching co-op students to companies that were participating in the program. It was incorrectly referenced as stack ranking, which has a whole other meaning.