Stable matching
Four applicants, four schools, one place at each school. Everyone has a list, favourite first. Press Step to run one round: every applicant without a place asks the best school that has not yet turned them down, and each school keeps the applicant it likes best and turns down the rest. Keep pressing until everyone has a place. Then try to do it yourself: tap squares in the table to build your own matching, and any pair that would rather have each other lights up as unstable. Tap a name in a list to move it one place towards the front.
The matching
Applicants' lists, favourite first
Schools' lists, favourite first
What's going on
A matching gives every applicant one school and every school one applicant. Suppose Ben has been given East, but Ben would rather be at North, and North would rather have Ben than the applicant it was given. Then Ben and North have a reason to walk away from the plan together. A pair like that makes the matching unstable. A matching with no such pair is stable: nobody can find a partner who would agree to swap.
The rounds always end. An applicant never asks the same school twice, and there are only 4 × 4 = 16 possible requests, so the rounds must stop. A school that has been asked once holds on to somebody from then on. So if an applicant ran out of schools, all four schools would be holding four other applicants, and there are only four applicants. That cannot happen, so everyone ends with a place.
The result is always stable. Suppose Ben prefers North to the school he ended up with. Then Ben asked North before he asked his final school, and North turned him down for someone it liked better. A school only ever trades up, so North still likes its final applicant more than Ben. North will not swap. That argument works for every applicant and every school, so there are no unstable pairs.
This method was published by David Gale and Lloyd Shapley in 1962. Versions of it place new doctors in hospitals and students in schools in many cities. There can be more than one stable matching, and the side that does the asking gets its best one: build the other one by hand, if you can find it, and compare who is happier.
Sheet: Matching without regrets.