Scarf's Lemma and Applications I
summary
Scarf’s Lemma is stated as: every feasible polyhedron built from a nonnegative matrix has an dominant extreme point that “dominates every column,” and that yields existence proofs for stable matchings, stable roommates, and housing-core outcomes by modeling matchings as linear programs. Key specifics: non-bipartite extremes are half-integral and half-variables lie on odd preference cycles; computing the dominating point is PPAD-complete. A constructive result shows hospital capacities can be adjusted by ≤4 each (total +9) to guarantee a stable matching; rounding uses Shapley–Folkman ideas.
AI-written summary · about
chapters (10)
- 0:00Introduction to matching
- 3:24Understanding Scarf's lemma
- 9:47Stable matching basics
- 13:56Applying Scarf's lemma
- 17:56Non-bipartite matching
- 24:35Housing and allocation models
- 29:41Computational complexity
- 33:24Matching with couples
- 40:51Stability and capacity
- 52:31Strategic concerns and outlook
related talks
36mThe Intractability of Hylland-Zeckhauser and its Aftermath
50mDiversity in Matching Markets
32mDynamic Matching Models
44mComputational Complexity of Matching in Ride Sharing
29mClearing Matching Markets Efficiently: Informative Signals and Match Recommendations
35mMore Dominantly Truthful Multi-task Peer Prediction with a Finite Number of Tasks
49mAlgorithmic Mechanism Design with Investment
46mJob Matching under Constraints