In applicant-proposing matching, applicants submit ordered program preferences and programs rank applicants. The design aims for a stable match—one with no applicant–program pair that would prefer each other to their assignments—and an outcome optimal for applicants. The NRMP uses a modified version of this approach. section 2.2.4
Applicant-proposing Gale-Shapley algorithm
A Gale-Shapley algorithm variant in which applicants are the proposing side of the matching process.
How Algorithms Every Programmer Should Know covers it
- How deep it goes
- Defines ranked preference lists, stability, and applicant-optimality, but does not detail the modified procedure's steps.
- Examples
- Uses residency applicants and programs, each submitting ordered or ranked lists, as the matching example.
- What you can do after
- Understand how applicant-proposing design targets stable matches that are optimal for applicants.
- How it connects
- Connects stable matching with preference rankings and applicant-optimal outcomes.
Related concepts
- algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- Gale-Shapley algorithmkind of · The Gale-Shapley algorithm, also called deferred acceptance, constructs a stable matching through proposals that can be tentatively accepted and later displaced.
- stabilityproduces · Stability in a matching is the property that no proposer-recipient pair outside the matching would prefer one another over their current assignments.
This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.
