This country profile is part of a collective effort by the network members to map matching practices across Europe. If you find it useful and want to refer to it in your own work, please refer to it as “Irving, Rob (2011), Matching practices for entry-labor markets – Scotland, MiP Country Profile 3.”
Relevant country background
Medical School graduates seeking to practice medicine in the UK must undertake two-years of a “foundation training programme”. For this purpose they are initially assigned to a “foundation school” by a national matching process overseen by the UK Foundation Programme Office (UKFPO). The country is subdivided, essentially on a regional basis, into 21 foundation schools, of which Scotland is the largest. Details of this national scheme are available here.
Once applicants have been assigned to foundation schools, it is up to each school to decide how to match applicants with available positions. In Scotland, this process is overseen by NHS Education for Scotland (http://www.nes.scot.nhs.uk/), using a matching scheme known as the Scottish Foundation Allocation Scheme (SFAS) – see .
|What is allocated?||Foundation training programme|
|Who are the participants?||Medical School graduates|
|Stated objectives of
|To produce a stable matching; to give neither an advantage nor a disadvantage to linked applicants (couples)|
|Who’s in charge?||NHS Education for Scotland; the matching scheme is run in the School of Computing Science at the University of Glasgow (Rob Irving & David Manlove)|
|In place since||Current scheme since 2009, earlier versions since 1999|
|Available capacity||there are typically around 750 applicants and approximately the same number of posts in about 50 separate programmes|
|Timing of enrolment||The main matching process takes place in January each year, with the second round in February/March|
to applicants prior to enrolment period
|Full details of the scheme are available on the web, including a comprehensive FAQ|
|Restrictions on preference expression||applicants must provide a preference list of a specified length, currently 10|
|Matching procedure||A heuristic to find a stable matching in the presence of couples – see below|
|Priorities and quotas||Applicants are ranked globally by score; quotas are decided by individual units|
|Tie-breaking||random tie-breaking, but with repetition in an attempt to maximize the size of matching|
|Other special features||Couples are accommodated|
Description of current practices
The current arrangements for medical training in Scotland 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 combine 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 by NHS Education for Scotland 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 (i.e. the relative order of candidates is the same as on 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 .) 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 .
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 . The current SFAS program uses a heuristic that attempts to find a stable matching that allocates as many applicants as possible. Simulations reported in  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.
After the first round of the matching scheme is complete, unmatched applicants are asked to submit a second preference list containing all of the programmes with unfilled places. A second application of the matching algorithm then completes the process.
The matching algorithm has always produced a stable matching. Typically around 93% of the applicants are matched in the first round.
Recent policy changes
The current version of the scheme was introduced in 2009. This incorporates a ‘master list’ of applicant scores and the accommodation of couples. Prior to that date, programme directors were required to construct their own individual preference lists, and there was no provision for linked applications (i.e., couples).
There is considerable imbalance in the popularity of programmes, resulting in round 1 of the matching scheme producing a larger of number of unmatched applicants than would otherwise be the case. This is essentially a manifestation of the ‘Rural Hospitals’ theorem.
SFAS data, in general, is not in the public domain. The SFAS website does contain some information, for example on programme popularity.
Other resources and references
 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.
 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.
 R. W. Irving and D. F. Manlove, Finding large stable matchings. ACM Journal of Experimental Algorithmics vol. 14 (2009), section 1 article no. 2.
 P. Biro, R.W. Irving and I. Schlotter, Stable matching with couples: An empirical study. ACM Journal of Experimental Algorithmics vol 16. (2011), section 1 article no. 2.
 Website of the Scottish Foundation School http://www.scotlanddeanery.nhs.scot/trainee-information/scottish-foundation-school/welcome-to-the-scottish-foundation-school/.