Abstract
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 Shapley, Folkman 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.
The second session of this talk will take place on Tuesday, August 25 from 11:30 am to 12:30 pm.