Market Design & Operations Research
Gale-Shapley Matching Blocking-Pair Audit Formula
Audit proposed hospital-resident, school-choice, or project-team assignments for David Gale and Lloyd Shapley’s (1962) stability condition by counting Blocking Pairs.
Test whether a proposed matching will unravel via mutual side-deals (Blocking Pairs)!
David Gale and Lloyd Shapley (1962) proved that a two-sided 1-to-1 matching mu is Stable iff NO unmatched pair (Applicant i, Program j) forms a Blocking Pair — defined as Applicant i strictly preferring Program j over Applicant i’s current assignment mu(i) (Rank_i(j) < Rank_i(mu(i)), where 1 = top choice!) AND Program j strictly preferring Applicant i over Program j’s current assignee mu(j) (Rank_j(i) < Rank_j(mu(j)))! Even a single Blocking Pair causes centralized clearinghouses (medical residency NRMP, school choice, internal rotation rosters) to unravel via off-market side deals!
Build a 4-pair candidate audit table (Rows 2..5) for a 2x2 matching between Applicants {A1, A2} and Programs {P1, P2} to see instability immediately! Suppose A1 ranks (P1=1, P2=2), A2 ranks (P1=1, P2=2), P1 ranks (A2=1, A1=2), and P2 ranks (A1=1, A2=2). If an administrator naively assigns A1->P1 and A2->P2, check all 4 pairs (A_i, P_j): for unmatched pair (A2, P1), Applicant A2 got rank 2 (P2) but ranks P1 as #1 (1 < 2 -> Applicant Prefers = TRUE!), AND Program P1 got rank 2 (A1) but ranks A2 as #1 (1 < 2 -> Program Prefers = TRUE!) -> Blocking Pair = 1 ("Unstable Matching: Side-Deal Unraveling")! Swapping to Deferred-Acceptance assignment A1->P2 and A2->P1 drops Blocking_Pair_Count to 0 ("Gale-Shapley Stable Matching")!
| Candidate Pair Audit (Naive A1->P1, A2->P2) | Rank vs Current Match | Blocking Pair? |
|---|---|---|
| Pair (A1, P1) — Matched | A1: 1 vs 1 | P1: 2 vs 2 | 0 (Already Matched) |
| Pair (A1, P2) — Unmatched | A1: 2 vs 1 (False) | P2: 1 vs 2 (True) | 0 (A1 Happy at P1) |
| Pair (A2, P1) — Unmatched | A2: 1 < 2 (True!) & P1: 1 < 2 (True!) | 1 (BLOCKING PAIR!) |
| Swap to A2->P1, A1->P2 | SUM(Blocking_Pairs) | 0 (Gale-Shapley Stable!) |
Row-Level Pairwise Blocking-Pair Detector Formula
Lower rank integer means strictly higher preference (1 = 1st choice < 2 = 2nd choice): both sides must strictly beat their current match!
=IF(AND(B2 < C2, D2 < E2), 1, 0)Clearinghouse Matching Stability Verdict Formula
Sum F2:F5 across all candidate pairs: stability requires zero blocking pairs everywhere.
=IF(OR(MIN(B2:E5) < 1), "Invalid Preference Rank", IF(SUM(F2:F5) = 0, "Gale-Shapley Stable Matching", "Unstable: Blocking Pair Detected"))Try the example
Use the original values or change them to test your understanding.