Topic

Stable Matchings and Scarf’s Lemma

Abstract

Each year the US National Resident Matching Program matches about 20,000 would be residents to hospitals. To encourage participation in the centralized clearinghouse, the matching is supposed to be stable. This means that no subset of doctors and hospitals should be able to improve upon their match by contracting outside the clearinghouse. The problem of finding such a stable matching was conceived by David Gale and Lloyd Shapley. Not only did they show the existence of stable matchings (in certain circumstances) they did so via a simple and elegant algorithm called the deferred acceptance algorithm (DA). It and its variants have become the algorithm of choice for determining stable matchings in a variety of settings. Each setting has imposed new demands on the algorithm. Among them are to how to handle complementarities and distributional constraints. The simplicity of the DA makes it difficult to accommodate these new considerations except in special cases. In this talk I will outline an alternative approach based on Scarf's lemma for tackling such problems. The lemma arose in the context of co-operative Game Theory, is closely related to Sperner's lemma and has subsequently found applications in combinatorics. 

Paper: Download