Stable Matchings and Scarf’s Lemma
Rakesh Vohra, UPenn

Abstract:
Each year the 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. However, 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.  This is based on joint work with Thanh Nguyen. This talk will assume no prior knowledge about either stable matchings or Scarf’s lemma.