An introduction to the stable marriage problem

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.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 n men, and n women that we want to pair up; n > 0. 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 A = \{a_1, a_2, ... , a_n\} of people labeled arbitrarily 1 to n. Similarly, we’ll have another set R = \{r_1, r_2, ... , r_n\}. Every a \in A has a preference list (r^1, r^2, .., r^n) of length n including all people in R. Likewise, everyone in R also has their own ranking list of the people in A. A person “preferring p to q ” means that p is higher on their pref list than q is.

What Shapley suggests is a “sequence of  proposals” from people in A to those in R.3 On the first iteration, a_1 proposes to their most desired person, who we’ll call r_a. Because r_a is free, they accept. Next, a_2 through a_n 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 n = 2, and maybe one of n = 3 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 n askers to have the same favorite receiver, or the exact same preference list; same for receivers. There are n! 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 a likes receiver r most, and r likes a most too, then they’re guaranteed to end up together. r will reject any other suitor, since a 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 n times. Because there can’t be more than n^2 proposals, the courting always ends. From the other side, can a receiver r reject all n askers? Suppose they have rejected all but one asker a_{last}. For r to reject a_{last}, r must be engaged already. That requires n - 1 askers to have been rejected, one to be engaged to r, and an a_{last} to be rejected next. That is n + 1 askers, which is impossible given only n askers total. Thus, receivers can’t reject more than n - 1 times.

Next, we will prove stableness.

  1. Assume for the sake of contradiction that there is a rogue pair in matching M so that in pairs (m_{rogue}, w) and (m, w_{rogue}), parties m_{rogue} and w_{rogue} prefer each other over their assigned partners.
  2. Because m_{rogue} prefers w_{rogue} over w, our algorithm dictates that m_{rogue} would propose to w_{rogue} first.
  3. Because w_{rogue} ended up with m, however, at some point w_{rogue} rejected m_{rogue} for m.
  4. This implies that w_{rogue} prefers m over m_{rogue}, a contradiction to our assumption that w_{rogue} prefers m_{rogue} over their own partner.

Here’s an alternate way to say it.

  1. Consider any pair (m, w) is produced by the matchmaking.
  2. If m prefers another partner w_i over w, then m would have proposed to w_i before w.
  3. The only reason m was free to propose to w is that m was rejected by all such w_i, because each w_i liked some suitor better.
  4. Thus all the partners m likes better than his assigned partner don’t like m 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 n proposers and n 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 q 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 q 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.

  1. Original paper u.arizona.edu/~mwalker/501BReadings/Gale&Shapley_AMM1962.pdf
  2. Overview of impact, why they won a nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/advanced-economicsciences2012.pdf
  3. Detailed proofs for teaching cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf
  4. Overview of application by Roth himself nber.org/papers/w13225.pdf
  5. Alternative proofs of the same things in 3 web.stanford.edu/~dntse/classes/cs70_fall09/n4.pdf
  6. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s