Scarf's Lemma and Applications

Lecture 1: Scarf's Lemma and Applications I
Lecture 2: Scarf's Lemma and Applications II

This series of talks was part of the Economics and Computation Boot Camp. Videos for each talk area available through the links above.

Speaker: Rakesh Vohra, University of Pennsylvania 

Scarf’s lemma is a tool for establishing the existence of allocations that are immune to coalitional deviations (usually called stable) in a variety of settings. For example, Scarf’s lemma implies the existence of bipartite stable matchings, necessary and sufficient conditions for the stable roommates problem to have solution and non-emptiness of the core in unit demand economies with indivisible goods.
Even when stable allocations may not exist, such as stable matchings with couples, Scarf’s lemma gives us a way to  define `fractional’ allocations that are stable. Combining this with recent methods for rounding fractional solutions of integer programs (developed in CS), gives us methods for obtaining near feasible stable allocations in settings where stable allocations do not exist.
Interestingly, these rounding methods can be seen as sharpenings of an earlier lemma of ShapleyFolkman and Starr (which in turn was a generalization of the Caratheodory theorem). That lemma can be interpreted as a kind of central limit theorem for sets as it asserts that the Minkowski sum of a large number of sets (none of which may be convex) is approximately convex.