Archive | January, 2017

“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)

Take a Hike – In Canada’s National Parks

Posted on 12 January 2017 by Vanessa DeMelo (meds2017)

Hello everyone! I hope that the holiday season had been restful and delicious for everyone. Today I’m going to write about something fun, outdoorsy, and provide information that may be more applicable for warmer weather. However, it’s fun and temperatures that I for one am looking forward to.

For now, we celebrate a brand new year. As a member of the class of 2017, one thing I had not anticipated is how much I identify with the date every time I see it written. After three and a half years of calling myself a 2017, it’s extra exciting that “The” year is finally here! First and second years, prepare yourselves for an onslaught of humans in MSB whom you have never seen before, as we walk around the VERC and lounge with an eerie poise of familiarity. I am really looking forward to being back and all the socialness that it entails, so feel free to say hello (we’re not that scary).

Now for my topic au jour – Canada’s National Parks! What are these national parks, specifically? Webster’s Dictionary (just kidding, the Canadian government website) describes them as “a country-wide system of representative natural areas of Canadian significance”, or in other language, bits of land that together represent the various natural regions of Canada. These regions include boreal forests, temperate rainforests, prairie grasslands, and more words that I bet you didn’t think that you would hear post-Grade 9 Geography. These parks are protected for public understanding, appreciation and enjoyment, and are maintained for future generations to likewise enjoy.

The park system’s origins date back to November 1885 (the year that the first appendectomy was thought to be performed), when the Canadian government designated 26 km2 of Alberta’s Sulfur Mountain to be preserved for the benefit of all Canadians. This area today is part of Banff National Park and is the Cave and Basin Hot Springs.

Pictured: A postcard by Harmon Byron showing the Government Pool at Cave and Basin, Banff National Park (produced before 1942).

The pool shown in the postcard closed in 1992 and the location has since received a multimillion dollar renovation. Interestingly, these hot springs were regarded as having healing properties and were used for thousands of years by the First Nations peoples. In 1883, they were “re-discovered” by three railway employees who were working on the construction of the first transcontinental railway through the Rocky Mountains. I highly doubt that spelunking was part of that original job description.

Picture2

Pictured: Interior pool post-renovation

Following the government’s designation in 1885, it was found that the area surrounding the original reservation was even more admirable and this led to The Rocky Mountains Park Act being passed in the House of Commons in June 1887 to establish what is now the Banff National Park, the first national park in Canada.

The history of the following development of the park system is (in my opinion) very interesting, detailed, and less fitting for a short, nothing-to-do-with-medicine blog. I found a lot of information on The Canadian Encyclopedia website and would direct you there if you are looking for more procrastination-worthy fodder!

Now, I’ve chosen (with difficulty) three National Parks to give as examples of places that you can and should visit. Many of Canada’s National Parks are also UNESCO world heritage site, which are locations listed by the United Nations Educational, Scientific and Cultural Organization as something of special cultural or physical significance. If the UN thinks they’re important, you should too!

  1. Bruce Peninsula National Park, located between Lion’s Head and Tobermory, Ontario: phenomenal camping and hiking, and only three hours away. Easily weekend-able!

Picture3

(Disclaimer: I did not take this picture)

  1. Cape Breton Highlands National Park on Cape Breton Island, Nova Scotia: it contains one-third of the world famous Cabot Trail. I was lucky enough to take a short trip here during my emergency medicine elective this fall in Sydney, Nova Scotia. Even though it was a wet day and the weather changed between drizzle, rain and snow every 500 m, the vistas were incredible and I will definitely be visiting again.

Picture4

(Disclaimer: I did take this picture)

On a less rainy day, courtesy of the internet:

Picture5

  1. Elk Island National Park, 35 km west of Edmonton, Alberta: this park hosts the densest population of ungulates (hoofed mammals) in Canada, and it is high on my list to visit this summer with my handy national park pass (what is this? Keep reading, my friends).

Picture6

I will hike, canoe and make friends with bison (interestingly, both the singular and plural form of the word. How many bison will I make friends with? It’s a mystery).

Now for the final, exciting news that you hopefully already know: To celebrate Canada’s sesquicentennial (your twenty-five cent word of the day, meaning 150th anniversary) in 2017, admission will be free to all of Canada’s National Parks, Historic Sites and Marine Conservation Areas. I feel this is all the more reason to pick somewhere where you haven’t been before, or even somewhere where you have been and would love to revisit, and make a trip of it. I’ve conveniently included a link below so that you can order your free season’s park pass!

Picture7

Picture8

Happy exploring!!

http://www.commandesparcs-parksorders.ca/webapp/wcs/stores/servlet/en/parksb2c

Comments (0)