Abstract:

Every year, over 16,000 American medical students graduate from 130 medical
schools, and look for a residency position. Since 1952, doctors are matched
to residency programs by a central authority - the National Resident
Matching Program (NMRP). With the increased participation of women in the
medical labor market, a growing number of doctors join the residency market
as couples. In 2010 the number of couples taking part in the Match exceeded
800.
One of the greatest future challenges the Match will face is handling the
growing number of couples, in which both doctors wish to get a residency in
the same geographical area. A stable matching in a market with couples need
not exist, and determining if such a matching exists is NP complete.
We introduce a new matching algorithm for such markets - the Sorted Deferred
Acceptance Algorithm - and show that for a general class of large random
markets the algorithm will find a stable matching with high probability.
Furthermore, truth-telling is an approximated equilibrium in the game
induced by the new matching algorithm.

Joint work with Itai Ashlagi and Mark Braverman