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
