Archive | Medonomics

“Gaming” CaRMS: the game theory and history of resident matching

Posted on 20 January 2017 by Tina Zhou (meds2020)

Let’s face it: the sight and sound of this term is a stress-inducer for many. This charming acronym stands for Canadian Resident Matching Service and match medical students with residency programs across Canada. Each year, the participating students wait anxiously for their results, and the non-participants wait anxiously for the match statistics.

The main concern usually relates to building a competitive application. However, lurking in the back of people’s mind is the mysterious CaRMS match algorithm. To address people’s curiosity (read: stress), CaRMS has a special webpage titled “De-mystifying the Match Algorithm” that contains key words such as “Roth-Peranson algorithm”, “rank order lists” and “applicant-proposing”. But how does it really work? For a better understanding of the mechanism and history of this “globally-recognized and award-winning” algorithm, let’s take a look across the border where the algorithm was first developed.

Medical internship in the United States was introduced in the 1900s as a form of post-graduate training. The idea gained popularity quickly for obvious reasons, but the implementation had a more troublesome history. Initially, medical students and hospitals made internship arrangements privately. An overabundance of internship positions relative to the size of graduating class each year resulted in a race among hospitals to recruit medical students as early as possible; some students received binding offers by the end of second year. Such a pre-emptive decision on the hospital’s side was risky and costly. Hospitals could potentially make a more well-informed choice if they withheld their offers until later, but they would then risk losing the brightest students to the early-acting hospitals. Consequently, everyone acts early –a classical case of Prisoner’s Dilemma.

The cost of this recruitment race was even higher for students. Many were still uncertain about their specialties of interest by the time they received an offer; signing a binding contract meant they might lose out on better options or make the wrong career decisions.

To mitigate the problem, medical schools established policies that prevented student information from being released to hospitals until a set date, forcing hospitals to make offers at the same time. This created a phenomenon of “exploding offers”. As hospitals scrambled to secure their preferred candidates, they shortened the response time for students to decide from 10 days to as short as 12 hours. Imagine if you were on a trans-Atlantic flight, you might miss your offer!

By the 1950s, it became clear that a central clearing house was urgently needed to facilitate the matching process. At first, a “priority matching” algorithm was proposed. Students and hospitals submit their preference lists for each other. In the first round of matching, those who put each other as first choices are matched and eliminated from the matching (1-1). Then, hospitals will be matched with their 2nd preferred candidates who rank the respective hospitals as first choices (2-1). In the third round, remaining students will match to their 2nd preferred hospitals who reciprocate by ranking the students as their first choice (1-2). The process goes on (2-2, 3-1, 3-2, 1-3, 2-3…). This proposal was rejected, as students would essentially be “penalized” for ranking hospitals they preferred but unlikely to secure.

Ultimately, a “deferred acceptance” algorithm was put forth. In brief, the proposing side makes offer to their most preferred candidates of the other party, who then temporarily accept the offer until they get a better deal in subsequent rounds – hence the “deferred” acceptance. Let’s demonstrate this in an example.

Assume there are four students who are trying to match to four hospitals. The students have a preference list, or “rank order list” (ROL), for the hospitals as shown:

 

Adam: Chrawna>Hammie>Vancity>Purple land

Beth: Chrawna>Purple land>Hammie>Vancity

Charlie: Vancity>Hammie>Purple land>Chrawna

Doug: Purple land>Hammie>Chrawna>Vancity

 

Similarly, hospitals rank the candidates as:

Chrawna: A>C>B>D

Hammie: B>C>D>A

Purple land: C>A>B>D

Vancity: D>B>A>C

Let’s start with the students as the proposing side. Adam and Beth both like Chrawna the best, so they both apply there. Charlie and Doug apply to Vancity and Purple land respectively. Now, since Chrawna receives two offers, it will be matched to its more preferred student Adam. Purple land and Vancity only receive one offer each and will be matched automatically. In this first stage of matching, Beth is unmatched. In stage two, she will apply to her second favourite place – Purple land. Even though Purple land is currently matched to Doug, it can still change its mind. After comparing its current match Doug to the new applicant Beth, the hospital selects Beth. At a result, Doug is now unmatched. Adam and Charlie remain matched to the hospitals from the previous stage. In the third stage, Doug will apply to the next location on his ROL, which is Hammie. Since Hammie still has not received any offer, it will happily take on Doug. Now everyone is matched and the matching process is complete.

 

Adam Beth Charlie Doug
Proposes to

Match

Chrawna

Chrawna

Chrawna

unmatched

Vancity

Vancity

Purple land

Purple land

Proposes to

Match

 

Chrawna

Purple land

Purple land

 

Vancity

 

unmatched

Proposes to

Match

 

Chrawna

 

Purple land

 

Vancity

Hammie

Hammie

Final result Chrawna Purple land Vancity Hammie

 

As a result, Adam is matched to Chrawna, Beth to Purple land, Charlie to Vancity, and Doug to Hammie.

On a cautionary note, in practice, students do not actually have to propose to hospitals repeatedly. Instead, these “stages” of matching are simulated – presumably with powerful computers at National Matching Services Inc. – with only one round of ROL submission to the central clearing house. In the context of CaRMS, each submission of ROL is equivalent to one round of iteration.

One may then wonder: does it matter which side starts the process? In the example above, the students make the “proposal” first. If one starts the process with the hospital side, there will be only one round of matching. The results are: Chrawna with Adam, Hammie with Beth, Purple land with Charlie, and Vancity with Doug. Every hospital will get their first choice, but the students will be worse off with their less preferred hospitals (just compare the results according to the students’ preferences). In general, student-proposing will lead to better or at least equally good results for students, since they essentially get their picks before the hospitals.

Is there a way to “game” the system? The simple answer is, not really. There is no incentive to put your “safer” options higher on your list just so that you are matched to at least somewhere, because you may potentially miss out on better matches. There is also technically no penalty for putting your “dream” hospital as your first choice. Even if you are rejected during the first “stage” within a submission, you can still “propose” to your other options and be accepted in later stages. As a result, the Deferred Acceptance algorithm elicits “true” preferences: students have no incentive to submit a rank order list that does not reflect their wishes.

In addition to solving the recruitment race, exploding offers, and too-risky-to-dream-big problems, this algorithm also produces so-called “stable” matches. Going back to our example, there is no pair of hospital-student such that they prefer each other to their assigned partners. Even though Hammie prefers Beth to its current match, Beth is not willing to give up Purple land for Hammie.

There have been modifications over the years to incorporate match variations such as couples matching. Nevertheless, “deferred acceptance” concept remains central to the currently used Roth-Peranson algorithm. It is used for resident matching in both US and Canada. If this post has not been re-assuring enough, the algorithm was also pivotal to Roth winning a Nobel Prize for Economics in 2012 – a truly “globally recognized and award winning” match program. Indeed, not many matchmaking solutions can be quite a match for this one and its making.

 

Resources:

De-mystifying the Match Algorithm http://www.carms.ca/en/about/blog/de-mystifying-match-algorithm/

The Match Algorithm http://www.carms.ca/en/residency/match-algorithm/

Alvin Roth “The Origins, History, and Design of the Resident Match”

Alvin Roth and Elliot Peranson “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design.”

 

Comments (0)