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