Chapter 2: Gale-Shapley Algorithm
The introduction frames Gale-Shapley as a way to match two equal-sized groups by preference without leaving a mutually preferred unmatched pair, and introduces deferred acceptance and proposer bias.
After this chapter you will be able to
- Stable matching problem. Explain the preference-based matching problem Gale-Shapley addresses and what makes a matching unstable.
- Temporary acceptance and rejection. Describe the introductory account of how proposals, temporary acceptances, and rejections work.
- Stable Match Condition. Explain what makes a student–university matching stable: no student prefers another university that would also prefer that student over its current match.
- One Pass Proposal Walkthrough. Trace the example from initially unmatched participants through X, Y, and Z proposing to Alice, Bob, and Carol, respectively, and the students accepting. Explain why this ideal case finishes in one pass without rejections.
- Rejection and rematching rounds. Trace how Carol moves through her preferences after X and Y reject her, while Alice and Bob keep their matches. Explain that a rejected option is not proposed to again.
- Stability of completed matches. Explain why the student-proposing result is stable even though Carol receives her third choice.
- Effect of proposing side. Compare the final matches when students propose with those when universities propose, and describe which side fares better in this example.
- Proposer Advantage in Stable Matching. Explain why the outcome favors whichever side proposes, using students and universities as examples. Distinguish a stable outcome from an equal outcome for both sides.
- Quadratic Worst-Case Runtime. State the algorithm's worst-case time complexity and describe how the number of participants affects the computing effort required.
- Use-case-dependent implementation. Explain why a real-world implementation of the algorithm may differ from the earlier example: that example addressed conflicts and rematching, while actual uses may involve other factors.
- Dating as stable matching. Explain how dating preferences and interactions fit the stable-matching model: preferences can be treated as ranked lists, someone who sends a like or message is a proposer, and the recipient accepts or rejects.
- Platform Participants and Preferences. Describe how drivers and riders or delivery requests form two sets of participants whose preferences can be represented as ranked lists, including preferences computed by the platform.
- Stability and Reassignment Costs. Explain what an unstable driver–rider assignment means here and why minimizing such assignments benefits a ride-sharing or delivery platform.
- Outcome-based customer adaptation. Explain how KPR customers adapt through repeated interactions and payoff values rather than explicit proposals and acceptances, and relate this to rejection and rematching in Gale-Shapley.
- KPR stability and distribution. Explain what stability means in the KPR account and how it relates to avoiding overcrowding and using restaurant capacity efficiently.
- NRMP preferences and stability. Explain what applicants and programs submit to the NRMP and what a stable match means in this setting. Describe why the section says stability matters.
- Stability and proposer advantage. Distinguish a stable match from one that is optimal for everyone, and explain why choosing who proposes matters when designing a matching system.
- Weighted and Dynamic Preferences. Explain how adding weights and costs can change preference-list ordering so matching considers more than stability, using grades and university distance as examples.
What it builds on
- Time and Space Complexity (chapter 1) · Time complexity notation provides the basis for interpreting O(N²).
Section by section
Introduction
The introduction frames Gale-Shapley as a way to match two equal-sized groups by preference without leaving a mutually preferred unmatched pair, and introduces deferred acceptance and proposer bias.
- Stable matching problem: Explain the preference-based matching problem Gale-Shapley addresses and what makes a matching unstable.
Why it matters: This is the criterion that distinguishes a stable match from merely pairing everyone up. - Temporary acceptance and rejection: Describe the introductory account of how proposals, temporary acceptances, and rejections work.
Why it matters: Temporary acceptance explains why an early offer need not determine the final pairing. - Proposer optimality and bias: Explain the stated advantage for proposers and why it raises a concern in real-world use.
Why it matters: A stable result can still favor one side of the matching.
Key terms: stable matching, preferences, proposer, recipient, proposers, recipients, deferred acceptance, offers, rejections, optimal for the proposer
2.1 The Stable Matching Problem
Introduces a forthcoming student–university example of stable matching without explaining the matching process.
2.1.1 One-Pass Matching
This section defines a stable student–university match and walks through an ideal example completed in one round of proposals.
- Stable Match Condition: Explain what makes a student–university matching stable: no student prefers another university that would also prefer that student over its current match.
Why it matters: This condition explains why a completed set of matches counts as stable, rather than merely complete. - One Pass Proposal Walkthrough: Trace the example from initially unmatched participants through X, Y, and Z proposing to Alice, Bob, and Carol, respectively, and the students accepting. Explain why this ideal case finishes in one pass without rejections.
Why it matters: The simple case establishes who proposes and who responds before the chapter considers rejections.
Key terms: stable match, preference, universities (proposers), students (receivers), proposals, one pass
2.1.2 When preferences collide, rejections and rematching
This section walks through rejection and rematching in Gale–Shapley, checks the resulting matchings for stability, and shows how changing the proposing side changes the outcome.
- Rejection and rematching rounds: Trace how Carol moves through her preferences after X and Y reject her, while Alice and Bob keep their matches. Explain that a rejected option is not proposed to again.
Why it matters: Following Carol’s proposals makes the rejection-and-rematching process concrete. - Stability of completed matches: Explain why the student-proposing result is stable even though Carol receives her third choice.
Why it matters: It distinguishes a stable match from one in which every participant gets a top choice. - Effect of proposing side: Compare the final matches when students propose with those when universities propose, and describe which side fares better in this example.
Why it matters: The same preference lists can produce different stable matches depending on who makes proposals.
Key terms: proposers, receivers, preference order, rejected, stable, preference, matching, first choice, second choice
2.1.3 Understanding the bias and complexity analysis
This section explains how the proposing side benefits in Gale–Shapley matching and what its worst-case quadratic runtime means in practice.
- Proposer Advantage in Stable Matching: Explain why the outcome favors whichever side proposes, using students and universities as examples. Distinguish a stable outcome from an equal outcome for both sides.
Why it matters: Choosing who proposes affects whose preferences the stable result favors. - Quadratic Worst-Case Runtime: State the algorithm's worst-case time complexity and describe how the number of participants affects the computing effort required.
Why it matters: The runtime bound helps you judge how the algorithm's computing demands change as the matching problem grows.
Key terms: proposers, stable matching, structurally biased, worst case, O(N^2), N, time complexity
2.2 Real-World applications
This section contrasts the earlier conflict-and-rematching implementation with real-world uses that must account for the needs of each use case.
- Use-case-dependent implementation: Explain why a real-world implementation of the algorithm may differ from the earlier example: that example addressed conflicts and rematching, while actual uses may involve other factors.
Why it matters: The earlier example is a starting point, not a complete specification for every application.
Key terms: use case, conflicts and rematching
2.2.1 Online dating and matchmaking
This section maps online dating to stable matching while noting how modern platforms extend the original model.
- Dating as stable matching: Explain how dating preferences and interactions fit the stable-matching model: preferences can be treated as ranked lists, someone who sends a like or message is a proposer, and the recipient accepts or rejects.
Why it matters: It connects the abstract matching model to familiar dating-app interactions. - Modern dating platform variations: Describe how implicit activity signals and platform-specific rules extend the initial dating analogy beyond the original matching framework.
Why it matters: It prevents treating the simple stable-matching analogy as an exact description of every dating platform.
Key terms: stable matching, ranked order lists, proposer, receivers, unstable pairs, explicitly express their preferences, implicit, swiping, profile views
2.2.2 Ride Sharing and Delivery Matching
The section applies stable matching to ride-sharing and delivery, showing how platform preferences can be modeled and why avoiding unstable assignments matters.
- Platform Participants and Preferences: Describe how drivers and riders or delivery requests form two sets of participants whose preferences can be represented as ranked lists, including preferences computed by the platform.
Why it matters: This connects a familiar platform assignment to the two-sided matching problem. - Stability and Reassignment Costs: Explain what an unstable driver–rider assignment means here and why minimizing such assignments benefits a ride-sharing or delivery platform.
Why it matters: Stability explains why a workable assignment must also resist disruptive changes.
Key terms: two sets of participants, preferences, ranked ordered lists, constraints, stability, unstable matches, rematching, reassigning, cancellations
2.2.3 Kolkata Paise Restaurant Problem (KPR Model)
This section uses customers and restaurants to explain decentralized resource allocation in KPR and contrasts its outcome-based adaptation with Gale-Shapley matching.
- Customers and restaurant capacity: Describe the KPR setup: customers independently choose restaurants according to preferences and previous outcomes, while each restaurant can serve only one customer.
Why it matters: The capacity limit explains why customers may need to change their choices. - Outcome-based customer adaptation: Explain how KPR customers adapt through repeated interactions and payoff values rather than explicit proposals and acceptances, and relate this to rejection and rematching in Gale-Shapley.
Why it matters: This distinction identifies how the section's decentralized model handles unsuccessful choices. - KPR stability and distribution: Explain what stability means in the KPR account and how it relates to avoiding overcrowding and using restaurant capacity efficiently.
Why it matters: It clarifies what counts as a good matching outcome in this restaurant model.
Key terms: decentralized resource allocation, customers, restaurants, preferences, proposals and acceptances, repeated interaction, payoff values, customer switching, stability, payoff
2.2.4 National Resident Matching Program (NRMP)
The section explains how the NRMP uses ranked preferences and an applicant-proposing variation of Gale–Shapley to match applicants with clinical training programs.
- NRMP preferences and stability: Explain what applicants and programs submit to the NRMP and what a stable match means in this setting. Describe why the section says stability matters.
Why it matters: Stability explains why the NRMP seeks more than a set of assignments. - Applicant proposing design choice: Describe the section's stated relationship between the NRMP algorithm and applicant-proposing Gale–Shapley, including the outcome and purpose attributed to that choice.
Why it matters: The design choice connects the matching method to the interests the NRMP says it aims to protect.
Key terms: NRMP, ordered lists, ranked lists, stable outcome, applicant-proposing Gale–Shapley algorithm, stable matching, optimal for applicants, strategic disadvantage
2.3 Key Insights
2.3.1 Everyone gets matched
2.3.2 Stability over optimality
This section explains that stable matches need not be optimal for everyone and that the proposing side tends to fare better.
- Stability and proposer advantage: Distinguish a stable match from one that is optimal for everyone, and explain why choosing who proposes matters when designing a matching system.
Why it matters: The choice of who proposes can affect whose preferences the resulting matches favor.
Key terms: stable, optimal match, proposing side, receiving universities
2.3.3 Deferred acceptance principle
2.3.4 Weighted and dynamic matching
The section explains how adding weights and costs to preferences can make stable matching more adaptive to real-world priorities.
- Weighted and Dynamic Preferences: Explain how adding weights and costs can change preference-list ordering so matching considers more than stability, using grades and university distance as examples.
Why it matters: It shows how matching preferences can reflect practical priorities rather than only a fixed ranking.
Key terms: weights, costs, preferences, preference list ordering, dynamic
2.4 Summary
Concepts explained in this chapter
- receiverA receiver is a participant on the side that evaluates and tentatively accepts or rejects proposals in a two-sided matching procedure.
- proposerA proposer is a participant role that initiates matching proposals in a deferred-acceptance procedure.
- Gale-Shapley algorithmThe Gale-Shapley algorithm, also called deferred acceptance, constructs a stable matching through proposals that can be tentatively accepted and later displaced.
- stabilityA stable matching is an assignment in which no unmatched pair would both prefer each other to their current partners.
- matchingA matching is an assignment pairing participants from two sets under specified rules.
- preference listA preference list records a participant’s possible matches in ranked order.
- proposalA proposal is an offer made by a proposer to a potential matching partner during the matching procedure.
- preferenceA preference indicates which potential match a participant favors over another.
- rejectionA rejection is a receiver's refusal of a proposal because another available proposal is preferred or the receiver has no capacity to accept it.
- stable matching problemThe stable matching problem asks for a pairing between two groups in which no unmatched pair would both prefer each other to their assigned partners.
- quadratic time complexityA time complexity that grows quadratically with input size, or proportionally to n × m for two input lengths in the stated case.
- algorithmAn algorithm is a finite step-by-step procedure that transforms specified inputs into a solution to a problem.
- constraintA constraint is a requirement or limitation that restricts which selections or solutions are permitted.
- applicant-proposing Gale-Shapley algorithmA Gale-Shapley algorithm variant in which applicants are the proposing side of the matching process.
- costA cost is a quantity representing the expense or disadvantage associated with a preference or match.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
