On Fairness and Stability in Two-Sided Matchings

on YouTube ↗33m

" summary

Shows that sampling fair hospital orders and running Gale Shapley fails via a 3x3 counterexample where two doctors in one cluster get systematically worse outcomes. Proves that under a proto-metric and hospitals indifferent inside clusters there always exists a randomized matching and gives the rising tide algorithm (fair propose-and-reject) that produces an N×N probability matrix, converges and yields approximate fairness and stability by stopping when free mass is below a threshold. Also proves GS-style local algorithms cannot guarantee both properties without those assumptions.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 0:13Allocation Problems and Fairness
3. 0:49Two-Sided Matching • Matching doctors to hospitals.
4. 3:15Probabilistic Allocation
5. 5:03Individual Fairness
6. 12:18The Gale-Shapley Algorithm for Stable Matchings
7. 14:41Naive application of Gale-Shapley fails • Use probabilistic representation for each hospital preferences.
8. 27:13Proof Sketch for Fair Propose-and-Reject - Doctor-First Stability: Induction over the rounds.
9. 30:38Barriers for General Metrics and for Unfair Preferences • Define local-proposing algorithms with doctors proposing.
10. 32:02Summary and Open Questions