liveBook · Manning

Applicant-proposing Gale-Shapley algorithm

As explained in Algorithms Every Programmer Should Know

A Gale-Shapley algorithm variant in which applicants are the proposing side of the matching process.

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

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

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.