liveBook · Manning

Matching

As explained in Algorithms Every Programmer Should Know

A matching is an assignment pairing participants from two sets under specified rules.

A matching pairs participants from two sets under specified rules. In preference-based matching, each side ranks possible partners, and the assignment aims to satisfy those preferences. section 2.0 section 2.1.1

For a stable matching:

  • No unmatched pair should both prefer each other to their assigned partners; such a pair would make the matching unstable. section 2.0
  • Gale–Shapley uses proposals, temporary acceptance, and rejection: a participant who is rejected can propose to their next choice. section 2.0 section 2.1.2

Students and universities

Students and universities rank one another. If two students propose to the same university, it keeps the one it prefers and rejects the other, who can then try another choice. section 2.1.1 section 2.1.2

Figure 2.3 Round 1 where students are proposers. Alice, Bob, and Carol propose to their first choices from the list. A conflict is seen between Bob and Carol, where both students opt for university X. X prefers Bob over Carol and rejects Carol.

This figure traces a collision: two students propose to one university, which keeps its preferred student and rejects the other. section 2.1.2

The same pairing idea applies to drivers and riders or delivery requests, where preferences and constraints can affect assignments. section 2.2.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through ranked preferences, proposals, rejections, and rematching, with pseudocode and a Python implementation.
Examples
Uses student-university preference lists and driver-rider or delivery assignments as examples.
What you can do after
Apply it via Gale–Shapley to match preference-ranked participants through proposals and rejections.
How it connects
Connects stable matching with Gale–Shapley, deferred acceptance, the Hungarian algorithm, and bipartite graphs.

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.