Math Detours · Grade 9 · Around the corner · 14

Matching without regrets

Pair applicants with schools so that no applicant and school would both rather have each other. A simple round of proposals always finds such a matching.

Name ____________________Date ____________

Tonight's idea

Applicants A, B and C want places at schools X, Y and Z. Each school has one place. Everyone ranks the other side, best first.

A: X, Y, Z    B: Z, X, Y    C: Z, X, Y
X: B, C, A    Y: B, C, A    Z: A, B, C

Try A–X, B–Y, C–Z. B would rather have Z, and Z would rather have B than C. Those two will make their own deal, and the plan falls apart. A matching is stable when no applicant and school both prefer each other to what they got.

AX Y Z BZ X Y CZ X Y XB C A YB C A ZA B C not stable AX Y Z BZ X Y CZ X Y XB C A YB C A ZA B C stable
Grey letters are each one's ranking, best first. Left: B and Z (dashed) would both rather have each other. Right: no such pair.

Here is a method that always finds one. In each round, every applicant without a place proposes to the best school that has not rejected them. Each school holds on to the best offer it has seen so far and rejects the rest. Stop when nobody is rejected.

Why is the result stable? Suppose an applicant prefers some school S to the one they ended with. They proposed to S earlier, and S turned them down for someone it likes more. A school only ever trades up. So S does not want them back.

Watch one: three rounds

Round 1. A proposes to X. B and C both propose to Z. Z prefers B, so it holds B and rejects C.

Round 2. C proposes to its next choice, X. X is holding A but prefers C, so it holds C and rejects A.

Round 3. A proposes to Y, which has no other offer. Nobody is rejected. Stop: A–Y, B–Z, C–X.

Check. B has its first choice. A prefers only X, but X prefers C. C prefers only Z, but Z prefers B. Stable.

Step through the rounds, or build a matching and see its unstable pairs: mathdetours.com/demos/matching.html. The method is due to David Gale and Lloyd Shapley. Versions of it place new doctors in hospitals.

Your turn

  1. (a) The matching A–X, B–Y, C–Z has a second pair who both prefer each other. Find it. (b) Find such a pair in A–X, B–Z, C–Y.
  2. Now let the schools propose, and let each applicant hold the best offer so far. Run the rounds. Which matching do you get?
  3. Compare the matching from the example with your answer to question 2. Both are stable. (a) Which one does each applicant prefer? (b) Which does each school prefer? (c) Which side would you rather be on: proposing, or receiving?
  4. (a) Why does no applicant ever propose to the same school twice? (b) With 3 applicants and 3 schools, why can there never be more than 9 proposals? What is the limit with \(n\) of each? (c) Why does that prove the method always stops?

Stretch: when there are no two sides

Four students must pair up to share two rooms. A ranks the others B, C, D. B ranks them C, A, D. C ranks them A, B, D. There are only three ways to split four people into two pairs. Show that each one contains two students who would both rather share with each other.

Answers

  1. (a) B and X. B prefers X to Y, and X prefers B to A. (b) C and X. C prefers X to Y, and X prefers C to A.
  2. Round 1: X and Y both propose to B, and Z proposes to A. B prefers X, so B holds X and rejects Y. Round 2: Y proposes to C. Nobody is rejected. Result: A–Z, B–X, C–Y.
  3. (a) A gets Y or Z and prefers Y. B gets Z or X and prefers Z. C gets X or Y and prefers X. Every applicant prefers the matching where applicants proposed. (b) X gets C or B and prefers B. Y gets A or C and prefers C. Z gets B or A and prefers A. Every school prefers the matching where schools proposed. (c) Proposing. The side that proposes starts at the top of its own lists and works down only when forced.
  4. (a) An applicant proposes again only after a rejection, and then moves to the next school down the list, never back up. (b) Each applicant can propose to each school at most once: at most \(3 \times 3 = 9\) proposals, and \(n^2\) in general. (c) Every round except the last contains a rejection, and each rejection is followed by a new proposal. The supply of proposals is limited, so the rounds must run out. (Here it took 5 proposals.)

Stretch. A–B with C–D: B and C. B ranks C first, and C prefers B to D. A–C with B–D: A and B. A ranks B first, and B prefers A to D. A–D with B–C: A and C. C ranks A first, and A prefers C to D. So no stable pairing exists, whatever D thinks. Whoever is left with D is always wanted by somebody else. Having two sides is what makes the proposal method work.

← PreviousNext: How many ways up the stairs? →