Thursday, March 26, 2015

Redesigning the Israeli Medical Internship Match

Israel has a new system for allocating medical intern positions. It's quite different from the system in the U.S., in large part because hospitals are passive. Assaf Romm and Avinatan Hassidim are playing a big role in the design of several markets in Israel, and some papers just appeared on this one in the Israel Journal of Health Policy Research:

Original research article   Open Access
Slava Bronfman, Avinatan Hassidim, Arnon Afek, Assaf Romm, Rony Sherberk, Ayal Hassidim, Anda MasslerIsrael Journal of Health Policy Research 2015, 4:6 (20 March 2015)

Commentary   Open Access
Alvin E Roth, Ran I ShorrerIsrael Journal of Health Policy Research 2015, 4:11 (25 March 2015)

Assaf Romm writes:

"Every year about 500 medical students in Israel are assigned to 23 different hospitals in Israel for an internship (in Hebrew this phase is called סטאז') that lasts one year. Unlike the American market, in which both interns have preferences over being hired by different hospitals, and hospitals have preferences over hiring different resident, in Israel the market is one-sided, and hospitals (which are owned by the government) are not allowed to express their preferences. The reason for that is that the Ministry of Health (MoH) does not want the better medical students to do their internships in the big cities (Tel Aviv and Jerusalem) only, but instead prefers to scatter across the country. Then again, students do have diverse preferences because of family issues or other issues, and we would like to accommodate those preferences if possible. There is also the option of being matched as a couple, and in 2014 there were 24 couples in the market.

In the past the MoH employed the random serial dictatorship mechanism (RSD). Ex-post trades (with no monetary transfers) were allowed, which created a black market (with monetary transfers) for internships in Tel-Aviv and other highly demanded places. This led to MoH banning trading positions if one of the positions traded was ranked in the first to fourth places by the intern that received it through RSD.

Last year our team helped in redesigning the mechanism. The change was meant to improve the efficiency of the results, by moving from RSD which is ex-post efficient, to a mechanism which is rank-efficient (see Featherstone C., 2014, working paper). Using surveys we tried to assess interns' "utilities" from being assigned to differently ranked hospitals, and then we were able to maximize a linear program given those weights (while making sure, per the student body's demands, that no student's "utility" goes below her RSD allocation).

The interesting thing from a theory standpoint is that most of the algorithms that we know of and that provide an ordinally-efficient result require Birkhoff-von Neumann (BvN) decomposition. However, when there are couples in the market it can be shown that some matrices cannot be decomposed to a convex combination of valid "permutation" matrices. Furthermore, the problem of determining whether a matrix can be decomposed is NP-complete. We decided to consider algorithms that approximately decompose matrices, i.e., they result in a convex combination of valid matrices, but the sum of the combination is only very similar to the original matrix, and not exactly equal to the original matrix.

We were able to prove a lower bound on the distance between the approximation and the original matrix, and then came up with an approximation algorithm that manages to almost exactly hit this lower-bound. We tested the algorithm on actual data (and bootstrapped data) from recent years and showed it performs very well.

The new algorithm was deployed last year and was since used three times. The responses were very good, and we've also seen (as expected) a major improvement in rank distribution. MoH has agreed to continue running the new mechanism in the coming years. The student body related to the 2015 lottery also voted for continuing with the new mechanism. (We also ran a survey on medical interns that took part in the match, but unfortunately participation was very low.)

This project is summarized in two papers: the first one above in the IJHPR, and this one:

Redesigning the Israeli Medical Internship Match (Noga Alon, Slava Bronfman, Avinatan Hassidim and Assaf Romm) - Intended for Economics and CS audience. Includes detailed introduction about the market, analysis of interns' preferences, the NPC result, the approximation algorithm, and simulations that show performance on preference data."

No comments: