SPA and SFAS - stable matching of medical graduates to posts in Scotland Description

Webpage: Scottish Foundation Allocation Scheme

Short description of the program:
The four main medical schools in Scotland (Glasgow, Edinburgh, Aberdeen and Dundee) produce around 800 graduates per year. The allocation of these graduates to their first positions has been carried out by a centralized matching scheme since 2000. Initially, when the allocation was to Pre-Registration House Officer posts, or PRHOs, the scheme was known as SPA (Scottish PRHO Allocations). SPA ran for six years, but since 2006 the allocation has been to so-called Foundation Programmes, and the scheme has been changed and renamed SFAS (Scottish Foundation Allocation Scheme).
SPA (2000 -- 2005)
In the SPA scheme, the requirement was that each applicant be allocated to two six-month positions, a medical post and a surgical post (except for a small number of applicants who required only one of these.) Applicants were required to rank their preferred n medical posts and preferred n surgical posts separately, in strict order of preference, and these rankings were submitted to the central body. (The value of n varied from year to year, in the range from 3 to 6.) Applicants were also invited to indicate whether they wished their medical post or their surgical post to come first chronologically (their so-called seasonal preference). Consultants in charge of each medical and each surgical unit were then sent the names of those applicants who had listed them, and were in turn required to submit strictly ranked preferences over their applicants, together with the number of posts on offer. The matching program was based primarily on the classical Gale-Shapley applicant-oriented algorithm. This was used to find the applicant-optimal stable matchings to medical and surgical posts separately. Following this, the two matchings were combined , using a network-flow based approach, to ensure that each candidate's allocation was to two different six-month periods, and that no unit's capacity was exceeded during any six-month period, at the same time maximizing the number of applicants whose seasonal preference was satisfied. Technical details of the algorithm appear in the webpage. Typically some 90-95% of positions were allocated by this first round of matching. Subsequently, details of unfilled positions were circulated to unmatched or partially matched applicants, and these applicants were matched in a second, somewhat ad hoc, round.
SFAS (2006 -- )
The current arrangements for medical training involve the allocation of each graduate to an integrated two-year Foundation Programme, which involves a range of medical disciplines. From the point of view of the matching algorithm, all that is required is an allocation of each applicant to (at most) one programme, respecting the capacities of the programmes. So, on the surface this appears to be an instance of the classical Hospitals-Residents problem. However, two factors combined to add extra interest to this process.
Firstly, as a matter of policy, programme directors are no longer asked to rank their applicants in order of preference. Instead, applicants are ranked in a so-called master list, in order of score – each applicant has a numerical score allocated partly on the basis of academic performance and partly as a result of the assessment of their application form. (Application forms are complex, and require detailed responses to challenging questions.) The range of possible scores (approximately 40 – 100) is much smaller than the number of applicants (around 750 each year), so there are inevitably ties of substantial length in the master list. The individual programme preference lists are constructed from the master list, so these also typically contain ties. It turns out that, even in the presence of a master list, random or arbitrary tie-breaking can lead to variations in the size of the stable matching produced by the Gale-Shapley algorithm. Finding a maximum size stable matching in these circumstances is known to be an NP-hard problem [2].) Discussion of a range of heuristics that are applicable in this context, together with an empirical evaluation of their performance relative to random tie-breaking, appears in [3].
Secondly, pairs of applicants to SFAS may declare themselves to be a couple, with a view to being assigned to geographically compatible positions. Such applicants are required to submit individual preference lists, just like single applicants. These are then combined in a pre-specified way to form a joint preference list for the couple, omitting any incompatible allocations. (A complete compatibility matrix for all pairs of programmes is available to applicants.) Under a natural extension of the stability concept, it is well known that a stable matching may not exist in the presence of couples, and that it is an NP-complete problem to determine whether such a matching exists. These results continue to hold in the presence of a master list [4]. The current SFAS program uses a heuristic that attempts to find a stable matching that allocates as many applicants as possible. Simulations reported in [4] suggest that, as long as the proportion of couples is relatively low, it is highly likely that a stable matching can be found, and this has so far been borne out in practice.

Description was given by Robert W. Irving.

References

[1] Robert W. Irving. Matching medical students to pairs of hospitals: a new variation on a well-known theme, in Proceedings of ESA'98, the Sixth Annual European Symposium on Algorithms, Venice Italy, 1998, Lecture Notes in Computer Science, vol. 1461 (Springer 1998), pp. 381-392.

[2] 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. Postprint.

[3] R. W. Irving and D. F. Manlove, Finding large stable matchings. ACM Journal of Experimental Algorithmics vol. 14 (2009), section 1 article no. 2, 30 pages. Postprint.

P. Biro and R.W. Irving, Stable matching with couples – an empirical study, forthcoming.