Math317Fa26 Lec21
Watch on YouTube →
Overview
Steven Miller introduces the Gale-Shapley stable matching problem, where a matching is stable if no applicant and institution both prefer each other to their assigned partners. He explains how the deferred acceptance procedure produces a stable matching in at most n² proposals, why the proposing side receives its best possible stable outcome, and how matching ideas apply to college admissions, residency placement, and kidney exchanges.
Key takeaways
- A blocking pair consists of an applicant and an institution who both prefer one another to their assigned partners; applicants wanting to swap alone is not enough to make a matching unstable.
- Deferred acceptance terminates because each proposer approaches each of n options at most once, giving a straightforward upper bound of n² proposals.
- When men propose, deferred acceptance returns the best stable outcome for every man; reversing the proposing side can produce a different stable matching.
- A stable matching can be found without examining all n! possible assignments, which grow much faster than the algorithm's roughly quadratic proposal count.
- The definition of a desirable outcome matters: maximizing combined preference scores can differ from finding stability or prioritizing only applicants or institutions.
Chapters
- Steven Miller frames stable matching as pairing two equally sized groups so that no pair can mutually benefit by switching.
- Applications include assigning students to colleges, doctors to hospitals, and students to public schools, often with capacities or unequal group sizes.
- Kidney exchanges can form chains in which donors from different families are compatible with one another's patients.
- Miller connects the topic to work recognized by the economics Nobel and notes that the foundational exposition appeared in the American Mathematical Monthly.
- A matching can be judged by more than whether everyone is assigned: a scoring system could give n points for a first choice, n−1 for a second, and so on.
- Maximizing total preference scores can favor a different outcome from maximizing the happiness of only applicants, colleges, or another one-sided group.
- College and job decisions illustrate how deadlines and early offers can pressure applicants before they hear from all their options.
- The objective matters: different definitions of success can produce different assignments.
- An assignment is unstable if an applicant prefers another college to their assigned one and that college prefers the applicant to its current assignee.
- Two applicants who want to swap colleges do not by themselves create a blocking pair, because the colleges must also accept the change.
- Miller distinguishes a stable matching from an optimal one and notes that stable outcomes may trade off which people or institutions are better off.
- For the basic model, everyone ranks every option and ties are broken so each preference list is strict.
- A three-men, three-women preference example illustrates distinct stable matchings, including outcomes giving one side its top choices.
- If one side receives its first choice, its members have no incentive to form blocking pairs.
- Miller states that a stable matching always exists and introduces deferred acceptance as a constructive way to find one.
- He also points to other matching criteria, including median matchings, as examples of further results in the field.
- Miller defines binary xᵢⱼ variables, equal to 1 when person i is matched with person j and 0 otherwise.
- The assignment constraints require each i and each j to appear in exactly one match: the corresponding row and column sums equal 1.
- Preference comparisons can be encoded as data, such as whether i prefers j₂ to j₁, rather than as decisions made by the optimization.
- Stability requires ruling out every mutually preferred alternative pair; encoding all such cases adds many pairwise conditions and can make an optimization model expensive.
- In the men-propose version, each unmatched man proposes to his highest-ranked woman he has not already approached.
- Each woman tentatively holds her preferred offer and rejects the others; a later, better offer can replace the person she is holding.
- A rejected proposer moves down his preference list, and a person who has already rejected him never needs to be approached again.
- At most n² proposals are needed because each of n proposers can approach each of n recipients at most once.
- Miller recommends working through the example using Elizabeth, Jane, Lydia, Charlotte, Bingley, Darcy, Collins, and Wickham from Pride and Prejudice.
- The process can be followed round by round as proposals are made, tentatively held, and rejected until no further proposal is possible.
- A crude worst-case bound counts n possible proposals from each of n proposers, giving n² proposals; a slightly tighter bound changes little asymptotically.
- There are n! possible one-to-one matchings, so searching them all grows far faster than running the deferred acceptance algorithm.
- If John and Mary prefer each other to their final partners, John must have proposed to Mary before reaching a lower-ranked choice such as Jane.
- Mary could not have rejected John while later holding someone she likes less: she would have accepted him or replaced her current tentative match.
- That contradiction rules out a blocking pair, establishing that the procedure terminates in a stable matching.
- Under men-propose deferred acceptance, the proposers receive their best outcome among all stable matchings.
- Reversing which side proposes can change the outcome; Miller uses the three-by-three example to show that the two sides can receive different top-choice results.
- He connects sequencing advantages to salary negotiation: naming a number first can anchor an agreement below what the other side might have paid.
- The Gamma function extends factorials beyond integers, with Γ(n+1) = n! and an integral definition that also works for real and complex inputs.
- Miller describes the Gamma integral as an exponential function integrated against a kernel and notes its use for studying factorial growth.
Transcript excerpt
0:00 So, welcome to math 317 operations research. What I want to do today is I want to talk about the Gale-Shapley algorithm. Why it works, why we care, but I do not want to prove it as well as possible. All right, so right now it looks like it is not showing it on the screen even though it said it should be showing on the screen. So, I'm going to do a small Hmm. All right, take two. All right, that looks better. Okay. So, I'm going to give this lecture a
0:48 little bit differently than I have in previous years. In previous years, I actually proved the optimal bound for how long it takes to run. And I've decided that that's not worth doing. And I'll comment as to why it is not worth doing. So, I'm going to use an abusive notation and talk about a Nobel Prize in economics. Is there anybody here who is studying economics? Why is this an abusive notation? >> Why is it Why is it an abusive notation? >> Talking about the Nobel Prize in economics. >> I don't know. >> Anybody know? >> Is there a Nobel Prize in economics? >> There is not a Nobel Prize in economics. It was not one of the original fields, it was added later. So, there's a technical name for it. We
1:35 all just call it the Nobel Prize in economics. All right, so to give you a sense of just how valuable this work is, it led to a Nobel Prize. Um admittedly in economics, but still it's a Nobel Prize. Okay. And so, the paper was published in the American Mathematical Monthly. It's a wonderful journal, beautifully written papers, but this is not one of the top theory journals of mathematics.
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Steven Miller.