Stable Matching
Consider the problem of pairing jobs and candidates, each with a complete preference list, so that no pair (candidate, job) would prefer each other over their current partners. Such a pairing is called a stable matching, and requires that no rogue couples (i.e., job-candidate pairs where both parties prefer other agents).
The process of finding it is often done using the Gale–Shapley Propose-and-Reject algorithm, where in each iteration:
- Each job proposes to the most preferred candidate who hasn’t rejected it yet.
- Each candidate keeps the best offer so far (on a string) and rejects all others.
- Rejected jobs cross off those candidates and prepare to propose to the next in line.
The propose-and-reject algorithm always halts once no rejections occur in an iteration.
Properties
If a matching is employer/job optimal, then it is also candidate pessimal.
Examples
Stable Matching Intro