Scarf's Lemma and Applications II
summary
Outlines a constructive use of Scarf’s lemma on an LP for doctor–hospital matching with couples: variables x_dh and x_c,hh′, non‑negative A and positive b, induce an ordering from hospital choice scores to get a dominating extreme point (fractional). Uses Shapley–Folkman intuition plus iterative rounding exploiting column sparsity (each column appears ≤3 times) to round to integers while guaranteeing capacity violation at most three per hospital (aggregate bound can be pushed to nine); proves stability preserved under responsive preferences.
AI-written summary · about
chapters (7)
- 0:00Start
- 4:30Scarf's Lemma (1967)
- 8:00Matching with Couples
- 12:45Shapley-Folkman-Starr (Starr (1969))
- 35:12Shapley-Folkman-Starr: Weakness
- 38:17Iterative Rounding: Updating LP
- 40:49Iterative Rounding & Matching
related talks
50mDiversity in Matching Markets
44mComputational Complexity of Matching in Ride Sharing
36mThe Intractability of Hylland-Zeckhauser and its Aftermath
33mThe Rideshare Dispatch Problem (Aka Online Bipartite Matching with Supply Externalities)
46mJob Matching under Constraints
29mClearing Matching Markets Efficiently: Informative Signals and Match Recommendations
32mDynamic Matching Models
50mQuality Selection in Two-Sided Markets: A Price Discrimination Approach