We were very lucky to have ex Lycee student and maths club attendee Sophia Sergeeva come today to run a session on the Gale-Shapley Stable Marriage Problem. It was absolutely fascinating and delivered brilliantly.
The Problem
This problem looks at matchings: one to one correspondences between sets.
Suppose that we are looking at a strictly heterosexual space (e.g. Tinder) with four boys and four girls. A matching between the boys and girls is sought for.
Let each of the girls have a list of preferences for the boys (from best to worst) and vice versa.
Let’s name the boys MA MB MC MD and the girls FA FB FC FD and list their preferences as follows.
The challenge is to match them up to maximise their happiness such that the system is “stable”. Stable in this sense means that no two people will want to run away together. For example if there exists two couples F1M1 and F2M2 then if F1 prefers M2 to M1 and M2 prefers F1 to F2 then this is unstable as they will want to run away. Note that it requires both to be true, if there is a couple for which one is top of the list for the other, but the other is bottom then it doesn’t matter as they can’t run away!
Challenge 1
Find a stable matching for the boys and girls above
The Algorithm
Does a stable matching always exist? Yes, and there is an algorithm to find it.
In each round of the this first very “traditional” algorithm, each unengaged man proposes to his next favourite woman who hasn’t rejected him. Each woman, if she has one or more suitors, becomes engaged to her favourite suitor and rejects all the others. Rounds continue until men have no one to propose to or are engaged. In subsequent rounds, females can break their engagement if someone they prefer proposes.
In the first stage of this algorithm for our list of preferences, the first round would work like this:
MA – FB
MB – FC
MC – FB
MD – FD
FC and FD have only one suitor so would accept them. FB has a choice so would choose MC as he is further up her list of preferences.
Challenge 2
Carry out the algorithm on the original list to find a stable matching.
Challenge 3
Which group are on average happier in this stable matching, the boys or the girls? Does it make a difference if the females propose?
Challenge 4
Is there a way that the girls could “lie” in the algorithm to maximise their happiness even if the boys were proposing?!
Challenge 5
Now think of the general case. Does the algorithm always stop? Does it always produce a stable matching? Can you prove it?
Challenge 6
There doesn’t always exist a stable matching for non-hetrosexual preferences. Can you think of a list of preferences of 4 people such that no stable marriage exists? What about 3?
Applications
The Gale-Shapley algorithm is used in real life to solve problems like assigning university places and assigning doctors to hospitals. Thanks again to Sophia for introducing us to this fascinating problem and algorithm.