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.