Gale-Shapley Stable Matching

Gale-Shapley Stable Matching

Overview

Gale-Shapley (deferred acceptance) finds a stable matching between two equally-sized sets where no unmatched pair prefers each other over their current match. Runs in O(n²) worst case. Proposer-optimal: the proposing side gets their best stable partner.

When to Use

Trigger conditions:

• Matching candidates to job positions based on mutual preferences
• Assigning students to schools or residents to hospitals
• Any two-sided matching where stability (no blocking pairs) is required

When NOT to use:

• For one-sided assignment (use Hungarian algorithm)
• When preferences are based on scores, not rankings (use optimization)

Algorithm

IRON LAW: The Proposing Side Gets Their BEST Stable Partner
Gale-Shapley is proposer-optimal and reviewer-pessimal. If employers
propose, they get their best stable match; candidates get their worst.
The CHOICE of who proposes determines which stable matching is found.

Phase 1: Input Validation

Collect: preference rankings from both sides. Each participant ranks all members of the other side. Gate: Complete preference lists, equal-sized groups (or handle unequal with dummy entries).

Phase 2: Core Algorithm

1. All proposers are "free" (unmatched)
2. While any proposer is free and hasn't proposed to everyone:
   • Free proposer proposes to their highest-ranked unproposed-to reviewer
   • Reviewer accepts if unmatched, or replaces current match if new proposer is preferred
   • Replaced proposer becomes free again
3. Terminate when all proposers are matched

Phase 3: Verification

Check stability: for every unmatched pair (a,b), verify that at least one of them prefers their current match over the other. No blocking pairs = stable.