I learned about this on my own and got excited about it for no particular reason, so here’s a primer on it.
In 1965, two professors – one a mathematician, both economists – published a paper outlining an algorithm to allocate students to colleges.1 For the next 50 years, others would apply its central theory to design markets with great success, streamlining medical residency matching, NYC high school admissions, and kidney donations.2 In 2012 they would share the Nobel prize in economics.
Today, the problem’s most basic version – stable marriage matching – is widely taught in college-level discrete math and algorithms courses. As variations continue to be researched, it remains a useful tool to both teach mathematics and showcase its usefulness.
There are three essential points to walk through: 1) the problem statement, 2) the solution, and 3) interesting properties of the solution. Interesting variants of the problem and solution come last.
Shapley begins his paper by describing the issue of college admissions. At the time, the process was quite fraught. If a college admitted too many people, they would overfill capacity and dilute the quality of their student body; admitting too few, though, would fail to compensate for students who decided not to attend after being accepted and would underfill capacity and quality. Students, on the other hand, felt the need to lie about what schools they actually like best to up their chances of acceptance.
To lessen uncertainty and dissatisfaction on both sides, he proposes a way to match students to colleges that guarantees stability. If a student is matched to a college, then there is no other college that the student prefers and would accept the student. (In other words, no one will be compelled to transfer.) At its core, the scheme matches proposers to receivers, a concept that Shapley models with the language of dating and matchmaking:
Suppose we have men, and women that we want to pair up; . Everyone is straight, heterosexual, monogamous and wants to marry. (Unrealistic, I know, but crucial for later proofs.)
Each person ranks the members of the opposite sex in their preference list. We’d like to match people based on who they like. However, we don’t ever want two people who aren’t married to each other to prefer each other over their spouses – any incentive to cheat or divorce is unacceptable. What do we do?
Let’s introduce some (gender neutral) notation for clarity. We will denote set of people labeled arbitrarily to . Similarly, we’ll have another set . Every has a preference list of length including all people in . Likewise, everyone in also has their own ranking list of the people in . A person “preferring to ” means that is higher on their pref list than is.
What Shapley suggests is a “sequence of proposals” from people in to those in .3 On the first iteration, proposes to their most desired person, who we’ll call . Because is free, they accept. Next, through in turn propose to their favorite partners; again, if the receiver is free, they accept. If not, they choose whoever they like better between their current fiance and the suitor. If the suitor is accepted, the fiance is rejected and becomes free. Once all askers have asked, the process repeats – only, the askers who are engaged do not propose, and the ones who are free propose to their next favorite person.
I recommend drawing out all possible examples of , and maybe one of and checking for stableness by hand if you’re new to this. Many of the sources at the end of this post have such examples too.
Another helpful step in understanding how this works is thinking about implied properties not explicitly stated in the algorithm explanation.
- It’s possible for all askers to have the same favorite receiver, or the exact same preference list; same for receivers. There are possible preference lists for each side.
- Once a proposer is accepted, they are engaged, but could become free at a later point if a suitor that their partner likes better comes along. However, once a receiver engaged, they are never free again – either they end up with their fiance, or trade up for someone they like better.
- Every time a proposer is rejected, their next partner is less preferable than the last. They started from their favorite, and work their way down the pref list while free.
- The first receiver proposed to always accepts, because they are never engaged.
- If an asker likes receiver most, and likes most too, then they’re guaranteed to end up together. will reject any other suitor, since is their favorite.
First to prove is that it terminates.3 A proposer can only propose once to any given reciever, so they can’t propose more than times. Because there can’t be more than proposals, the courting always ends. From the other side, can a receiver reject all askers? Suppose they have rejected all but one asker . For to reject , must be engaged already. That requires askers to have been rejected, one to be engaged to , and an to be rejected next. That is askers, which is impossible given only askers total. Thus, receivers can’t reject more than times.
Next, we will prove stableness.
- Assume for the sake of contradiction that there is a rogue pair in matching so that in pairs and , parties and prefer each other over their assigned partners.
- Because prefers over , our algorithm dictates that would propose to first.
- Because ended up with , however, at some point rejected for .
- This implies that prefers over , a contradiction to our assumption that prefers over their own partner.
Here’s an alternate way to say it.
- Consider any pair is produced by the matchmaking.
- If prefers another partner over , then would have proposed to before .
- The only reason was free to propose to is that was rejected by all such , because each liked some suitor better.
- Thus all the partners likes better than his assigned partner don’t like back more than their own partners, so the matching is stable.
By proving the correctness of this algorithm, we’ve also proved that for any proposers and proposees, there exists a stable matching. If it can be applied, it will succeed.
With this framework, Shapley presents a matching scheme that works for colleges with a quota of students. (Or, rather, he says the proof is analagous and leaves it to the reader.) Colleges can’t possibly rank students who don’t apply to them, but they can rank their applicant pool and select from those like receivers. Each student acts like an asker, and applies to their first choice college, then second, and so on if they are rejected. Schools, then, keep a waitlist of people, with more desirable applicants replacing those on the waitlist at each round. At the end, all students are either rejected by everyone or on a waitlist, and we will have a stable matching.
- Original paper u.arizona.edu/~mwalker/501BReadings/Gale&Shapley_AMM1962.pdf
- Overview of impact, why they won a nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/advanced-economicsciences2012.pdf
- Detailed proofs for teaching cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf
- Overview of application by Roth himself nber.org/papers/w13225.pdf
- Alternative proofs of the same things in 3 web.stanford.edu/~dntse/classes/cs70_fall09/n4.pdf
- More educational material going over core proofs ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/readings/MIT6_042JS15_Session22.pdf