New clearinghouse for new doctors in Scotland

There have been some changes in the SCOTTISH FOUNDATION ALLOCATION SCHEME, the program that matches new medical graduates to their first positions (which would be called residencies in the US) in Scotland.

Two features stand out in comparison to the American system (the NRMP).

First, employers may not submit preferences, but rather are all constrained to rank potential employees by their exam scores.

Second, couples cannot submit preferences over pairs of positions. Instead, each member of the couple submits a rank ordering of individual positions, and the algorithm combines these into a joint preference over pairs that is a function of the submitted rank order list and a table of compatibilities of positions.

"To accommodate linked applicants, a joint preference list is formed for each such pair, using their individual preference lists and the programme compatibility information. If such a pair, a and b, have individual preferences p1, p2, . . . , p10 and q1, q2, . . . , q10 respectively (with a the higher scoring applicant), then the joint preference list of the pair (a,b) is (p1,q1), (p1,q2), (p2,q1), (p2,q2), (p1,q3), (p3,q1), (p2,q3), (p3,q2), . . ., (p9,q10), (p10,q9), (p10,q10) (except that incompatible pairs of programmes are omitted)
In the main body of the algorithm, the members of a linked pair are handled together, so the match of the pair (a,b) to the programmes (p,q) will be accepted only if each of these programmes either has an unfilled place or a lower scoring applicant who can be displaced. A complication arises when one member x of a linked pair has to be withdrawn from a programme p because his/her partner was displaced from their current assigned programme. In this case, some other applicants may have been rejected by p because of the presence of x, and any such applicant a must be withdrawn from their current programme, if any, and have their best achievable preference reset to p. (A corresponding, but more complex reset operation is needed if a is a member of a linked pair). This reset operation thereby allows a further opportunity for applicant a to be matched to programme p.
The algorithm terminates when every single applicant and linked pair is either matched or has been rejected by, or displaced from, every entry in their preference list with no possibility of reconsideration by a programme that has had a withdrawal.
The final matching is stable for single applicants, as before, but also for linked pairs, in the sense that:
there can be no linked pair (a,b) of applicants who would prefer to be matched to compatible programmes (p,q), and at the same time, each of p and q has an unfilled place or an assigned applicant with a lower score than a and b respectively."

HT: Rob Irving, who has designed and implemented the algorithm.

Here are some related papers by members of the Scottish matching group.

Keeping partners together: algorithmic results for the hospitals/residents problem with couples by Eric J. McDermid and David F. Manlove in
Journal of Combinatorial Optimization, (2009)

R.W. Irving, D.F. Manlove and S. Scott, The stable marriage problem with master preference lists, Discrete Applied Mathematics vol. 156 (2008), pp. 2959-2977.