The Stable Matching Problem is Wes Chao’s favourite algorithm.

Consider two populations, \(A\) and \(B\), who want to form paired relationships between a person \(A\) and \(B\). \(A_i\) has a list of their ranked order matches (I want to be paired with \(B_1\) most, \(B_4\) second, etc.), and so does \(B_i\) (I want to be paired with \(A_4\) most \(A_9\) second, etc.)

We want to discover a stable matching, where pairs are most unwilling to move. We can solve it using the stable matching algorithm.

Nueva Invention Studio speed-dating noises?

applications of the stable matching problem

• Dating
• Applying to college
• Both of these are high-stress situations, especially if you are doing asking
• You can mathematically prove that person doing the asking gets the best result

Hence, it shows us that the best possible outcomes go to the people who are willing to ask and get rejected.

extensions to the stable matching problem

the stable matching problem can be extended to the rural hospitals problem, which is slightly better.