liveBook · Manning

Stable matching problem

As explained in Algorithms Every Programmer Should Know

The stable matching problem asks for a pairing between two groups in which no unmatched pair would both prefer each other to their assigned partners.

A stable matching pairs two groups using their preference rankings so no unmatched pair would both prefer each other to their assigned partners. Gale–Shapley addresses this with proposals and rejections: recipients can accept temporarily, then switch when a more-preferred proposal arrives. section 2.0

In a student–university example, universities propose and students compare each offer with their rankings:

  • X proposes to Alice, Y to Bob, and Z to Carol—their first choices. section 2.1.1
  • The students’ rankings determine whether they keep or reject those proposals; the process continues until the matching is complete. section 2.0 section 2.1.1
Figure 2.1 shows universities proposing their first preferences. X proposes to Alice, Y to Bob, and Z to Carol.

See the initial university proposals to students in the example. section 2.1.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines stability, traces proposals and rejections, and identifies termination, correctness, optimality, and proposer bias.
Examples
Uses ranked student–university preferences and residency-program matching to illustrate stable outcomes.
What you can do after
Apply proposal-and-rejection steps to ranked groups and check whether an unmatched pair would prefer each other.
How it connects
Connects stable matching to Gale–Shapley, deferred acceptance, preference rankings, and proposer-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.