Skip to main content

Residency Matching Problem

I have always found the residency matching problem very interesting. In this market there are hospitals and medical students, and both sides of the market have strict preferences. There is no currency in this market, rather our goal is to maximize utility. We want to give the hospitals their top choice residents so that the hospital can continue to be successful. At the same time we want to give residents their top choice hospital because forcing them to live somewhere they do not want to may lead to poor work performance since they will likely be unhappy living there. A good matching pairs residents to hospitals in areas they want to work while still giving the hospitals quality medical students.

The algorithm used to solve this problem is Gale-Shapley’s stable matching algorithm. A very nice property of this algorithm is that, for any matching $M$ of hospitals $h_1,…,h_n$ and residents $r_1,…,r_n$ there does not exist and $h_i$,$r_j$ such that they prefer each other to the agent they were assigned in $M$. This property is what it means for the matching to be stable. This is desirable because if the matching $M$ was unstable, that is if there did exist $h_i$,$r_j$ such that they prefer each other to the agent they were assigned in $M$, then hospital $h_i$ might ditch the resident they were assigned in $M$ and take resident $r_j$ who they prefer and also prefers them to the hospital they were assigned in $M$.

A less fortunate property of the algorithm is that one side is guaranteed to get there best feasible preference while the other side is guaranteed to get there worst feasible preference. This is dependent upon  how the algorithm is implemented. The current algorithm favors hospital preferences, which means the residents will be match with there lowest preference that still results in a stable matching.  Obviously we want the hospitals to get the residents they prefer so they can better serve there community, though it seems unfortunate for the residents. There are no initial endowments, however, there is added complexity at points in the market. For example, two medical students might have gotten engaged or married and therefore want to do their residencies near each other.  This requires special attention during allocation in order to place the two residents near one another.

Kleinberg, Jon, and Eva Tardos. Algorithm design. Harlow: Pearson, 2014.


Leave a Reply

You must be logged in to post a comment.