Achieved Rank in Stable Matching

Abstract

The concept of stable matching is used in a wide variety of applications. This paper studies the stable matching problem, applied to the NRMP (National Residency Matching Program) that matches medical students and hospitals with residency positions. In stable matching, there is a concept of well an agent performs in the matching, which is represented by the position their match takes on the preference list (an agent who receives their first choice performed "better" than an agent that received their tenth choice.) This paper names this value "achieved rank". In particular, it introduces a model where hospitals have objective "qualities" that affect its probabilisitic placement on students' preference lists. It is proven that expected achieved rank is monotonic to quality, and the claim that higher quality hospitals have higher expected achieved rank is proven for some special cases. However, when trying to prove this claim in the general case, there are several intuitive claims that are proven false by counterexamples. Although these counterexamples show how proving the claim in the general case would be difficult, they provide insight into proof strategies that could be successful.