Can we always pair two groups of people together in such a way that there is no mutual incentive for change in any of the pairings? This problem shows the elegance of mathematics and also gives insight as to why I decided to study pure mathematics.
There comes a time in a budding mathematician’s life where we must make the jump from being an undergraduate to some kind of research student. A key part of this process is finding an academic who is willing to supervise you. There’s just one problem: you’re not the only student looking for a supervisor!
Let’s set the scene a little bit. You’ve just been hired by a university to help them assign academics to students. You have an equal number of students and academics willing to supervise them. There’s one catch though – each academic is so busy and they can only supervise a single student. You also need to pair students and supervisors in a stable way. To illustrate what we mean by stable let’s do an example. Suppose we have two students, Kate and Ben, and we have two supervisors, Joan and Peter. You decide to make the following pairs:
(Kate, Peter) and (Ben, Joan).
This pairing is unstable if, for example, Peter would prefer to have Ben as a student over Kate and Ben would prefer to have Peter as a supervisor over Joan. If we don’t have the mutual incentive to change then we call the pairings stable.
Let’s return to your role. You have to pair off the students and supervisors so that all the pairings are stable. We don’t want the above scenario! The question is this – can you always do this? No matter how many students and possible supervisors, provided there is an equal number of each, can you always do this?
I first encountered this problem just after graduating high school in 2013. The traditional setting (and hence the name) is creating stable marriages in a village with an equal number of men and women, but I’ve picked a more relevant scenario to me here. It almost seems like, in this problem, that you can’t guarantee this. You don’t really have a way to know if pairings will be stable. The best part is – the answer is yes. You can always do this!
We’re going to sketch the proof for this. Why? For a number of reasons:
- It’s a proof by construction and involves no numbers!
- The idea of the proof is incredibly easy to grasp.
- This proof is one reason that I decided to study pure mathematics at university.
- I think it highlights the elegance of mathematics quite nicely.
First things first, we’re going to need to know preferences. We get every student to submit a list of their preferences for supervisors. Likewise, we get the supervisors to submit a list of their preferences for students. Now we’re going to construct an algorithm.
On the first day we get each student to submit a request for their first choice of supervisor. This means that some supervisors may get multiple requests, some get only one, and some get none. Next, for each supervisor that received a request you pair them with whichever student ranks highest on their preference list. What you have done is made some tentative pairings.
On the second day we get each student who is not in a tentative pairing to submit a request for their second choice of supervisor, even if the supervisor is already in a tentative pairing. Once again, you match each supervisor to the student that ranks highest on their preference list. What can happen here is if a supervisor is in a tentative pairing but receives a request for a student who they prefer more, they can switch.
That’s it. We just repeat this process until every student is paired with a supervisor. Gale and Shapely [1] derived this algorithm and showed that it always works. If you don’t believe me, try an example! The beauty of this problem is that it seems impossible – you can probably figure it out for a small group but what if there were a hundred, or even a million students and supervisors that needed to be paired. This is what mathematics can feel like – seemingly impossible problems that you have no idea how to tackle – but so often we end up with a solution which is so elegant you can’t help but stand back and be impressed.
[1] Gale, D., and L. S. Shapley. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly 69, no. 1 (1962): 9-15. Accessed February 27, 2020. doi:10.2307/2312726.
James Morgan
The Australian National University
