One Two
You are here: Home Seminars 10.05. Micro Theory Seminar: Rakesh Vohra

10.05. Micro Theory Seminar: Rakesh Vohra

Micro Theory Seminar with Rakesh Vohra (University of Pennsylvania)

Event details
  • Micro Theory Seminar
When May 10, 2017
from 16:30 to 17:45
Where Faculty Room
Contact Name Stephan Lauermann
Contact Email
Add event to calendar vCal


Stable Matchings and Scarf’s Lemma



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

filed under:
Document Actions