algo-hr-matchinglisted

# 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 preferr