Matching with Compatibility Constraints: The Case of the Canadian Medical Residency Match

The Canadian medical residency match has received considerable attention in the Canadian medical community as several students go unmatched every year. Simultaneously, several residency positions go unfilled, largely in Quebec, the Francophone province of Canada. The Canadian match is unique in that positions are designated with a language restriction, a phenomenon that has not been studied or described priorly in the matching literature. To study this phenomenon, we develop the model of matching with compatibility constraints, where based on a dual characteristic, a subset of students is incompatible with a subset of hospitals. We show that while the deferred acceptance algorithm still yields a stable matching, some desirable properties from standard two-sided matching are lost. For instance, we show that if the number of residencies exceeds the number of students, some students can yet go unmatched. We derive a lower bound for the number of English and Francophone residency positions such that every student is matched for all instances of (a form of) preferences. Our analysis suggests that to guarantee a stable match for every student, a number of positions at least equal to the population of bilingual students must be left unfilled. The model can be generalized to other instances of the stable marriage problem.