Questions: Two-Sided Matching and the Deferred Acceptance Algorithm
4 questions to test your understanding
Score: 0 / 4
Question 1 Multiple Choice
Proposers P1, P2, P3 and receivers R1, R2, R3 have these rankings. P1: R1, R2, R3. P2: R1, R3, R2. P3: R2, R1, R3. R1: P2, P1, P3. R2: P1, P3, P2. R3: P1, P2, P3. What matching does proposer-side deferred acceptance produce?
AP1-R1, P2-R3, P3-R2
BP1-R2, P2-R1, P3-R3
CP1-R3, P2-R1, P3-R2
DP1-R2, P2-R3, P3-R1
Round 1: P1 and P2 propose to R1, P3 to R2. R1 holds P2 and rejects P1; R2 holds P3. Round 2: P1 proposes to R2, which prefers P1 to P3, so it holds P1 and rejects P3. Round 3: P3 proposes to R1, which keeps P2 and rejects P3. Round 4: P3 proposes to R3, which holds P3. No one is rejected, so the result is P1-R2, P2-R1, P3-R3.
Question 2 True / False
A matching is unstable if there is a proposer and a receiver who each prefer the other to their current partner.
TTrue
FFalse
Answer: True
Such a pair is called a blocking pair. They would both gain by leaving their assigned partners and matching with each other, so the assignment would unravel.
Question 3 Multiple Choice
Compared with every other stable matching, the proposer-proposing deferred acceptance outcome is:
ABest for every receiver
BBest for every proposer and worst for every receiver among stable matchings
CThe only stable matching
DBest for exactly half of each side
Gale and Shapley showed the proposing side gets its best stable partner. A later result shows that, among stable matchings, the same outcome is the least preferred for each receiver.
Question 4 Short Answer
Why have school districts and the U.S. medical residency match adopted deferred acceptance or close variants?
Think about your answer, then reveal below.
Model answer: It produces stable assignments, so participants have no incentive to go around the system and make side deals, and it lets the proposing side, typically students or applicants, report their true preferences without fear of being penalized for ranking a popular option first.
Earlier mechanisms, such as ones that gave priority to first-choice rankings, rewarded strategic ranking and left matches unstable. Alvin Roth's work in market design helped bring deferred acceptance into practice.