Computer Science Colloquium
    GUEST LECTURE on Thursday 21/07/2011
Time+Place : Thursday 21/07/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Avinatan Hassidim SPECIAL GUEST LECTURE
Affiliation: Google
Host       : Danny Raz
Title      : Finding a job and the two body problem
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
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
Visit our home page-   <>
Wed Jul 20 08:25:02 IDT 2011
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>