SPA ¾ The Scottish PRHO Allocations Scheme
Technical Report on the First Year of Operation 1999-2000
Computing Science Department
University of Glasgow
The Scottish PRHO Allocations Scheme (SPA) was introduced under the auspices of the Scottish Council for Postgraduate Medical and Dental Education (SCPMDE) in 1999-2000 as a centrally administered national matching scheme to allocate graduating medical students to their Pre-registration House Officer (PRHO) posts in Scotland.
Prior to 1999, PRHO allocations in Scotland were organised on a regional basis, with the South-eastern region operating an automated system known as PRAMS (PRHO Appointments Matching Scheme) [Mac94] and other regions essentially operating a free market. It was the high degree of dissatisfaction with the free market scheme in the West of Scotland, among all the parties involved, that originally motivated the plan for an automated scheme in that region, a plan that quickly grew to encompass all regions even before its first year of implementation.
The design of the original system, planned for the West, was overseen by a working group comprising the Postgraduate Dean and representatives of consultants and students, with administrative support. Technical expertise was provided by Rob Irving and Gordan Low of the Computing Science Department at the University of Glasgow.
Centralised automated schemes for matching graduating medical students to hospital posts have been well established in some countries for many years. For example, The National Resident Matching Program (NRMP) in the US is responsible for allocating posts to some twenty thousand residents each year, and the Canadian Resident Matching Scheme (CARMS) performs a similar task in Canada.
Extensive research on matching schemes [Rot84, Rot90] has produced strong evidence to suggest that a key requirement for such a scheme to be accepted, and to stand the test of time, is that the matchings it produces should be stable, in a precise technical sense. In this context, a matching is an allocation of each student to at most one post, so that the number of students assigned to each hospital unit does not exceed the number of posts available in that unit. A matching is stable provided there is no student S and hospital unit H with the properties that
If there were such a student S and hospital H, it would clearly be to their mutual benefit to come to a private arrangement, and thereby to undermine the overall matching.
In order for the stability concept to apply, students must supply an ordered preference list of hospital posts, and hospitals must rank in order of preference the relevant students. It turns out that, no matter what the form of these preference lists may be, at least one stable matching is guaranteed to exist, and there may be many. Of course, regardless of the relative numbers of students and available posts, not all students need be matched, and not all posts need be filled, in a stable matching. But one key property is that, no matter which stable matching may be chosen, exactly the same set of students will be matched and each hospital will have the same number of posts filled .
In any particular case, one of the stable matchings, the so-called student-optimal, is uniquely favourable to the students, in the sense that every student simultaneously obtains the best post that he or she can have in any stable matching. Another stable matching, the hospital-optimal, gives each hospital the best set of students that it can have in any stable matching. It is a curious fact, that has been a cause of some controversy, that the student-optimal matching is the worst possible stable matching for the hospitals, while the hospital-optimal is the worst-possible for the students. In a sense, therefore, the objectives of students and hospitals may be seen as conflicting.
Schemes such as NRMP and CARMS use variants of an established algorithm, the so-called Gale-Shapley algorithm [GS62, GI89], to determine a stable matching. This algorithm can be applied from either side ¾ if it is applied from the students’ side it generates the student-optimal matching, whereas if applied from the hospitals’ side, it gives the hospital-optimal. From its inception in 1952 right through until 1997, the NRMP used the hospital-optimal as the basis of its allocation. However, increasing pressure from student bodies and others, prompted by the fact that hospital-optimal is student-‘pessimal’, led to a change of policy, and from 1998 the NRMP adopted the student-optimal solution [RP97].
3. The Scottish context
The situation in Scotland differs in one key respect from that in North America, namely that, traditionally, a student undertakes two six-month posts, a medical post and a surgical post, in his/her PRHO year. Hence from the outset it was clear that the Scottish scheme would have to determine a medical matching and a surgical matching, and somehow combine these in such a way that no student was allocated two posts in the same half-year, and each hospital unit had allocated to it, in each half year, a number of students not exceeding the number of available posts. Furthermore, some students seek just one post, usually for a particular half-year (typically because they have already arranged one of their posts elsewhere, perhaps in England). All of this leads to an algorithmic problem somewhat more complex than in the single-post context.
Indeed, a further complicating factor emerged during the development of the system, namely the introduction of so-called rotational posts. From the point of view of the matching scheme, such a post is effectively a single year-long post (though in practice it is broken into three 4-month sub-posts).
4. The design of SPA
A number of key design decisions were made by the original working group, namely
The working group also established a detailed timetable and mechanism for the submission and administration of the preference lists. This involved each student submitting an initial ‘expression of interest’ in 5 medical units, 5 surgical units, and, if they wished, 2 rotational units. Each hospital/rotational unit would be sent a list of the students who had included it in their appropriate list. Subsequently, after a period of visits, interviews, etc., students would rank their chosen units (with the option of omitting one or more, but not of adding any new ones, at this stage). Consultants would have to provide their ranked lists without knowing how any of the students had ranked their units.
5. The implementation of SPA
The SPA software was designed by Rob Irving and implemented by Gordan Low, first in prototype form as part of the latter’s dissertation for the M.Sc. degree in Information Technology at Glasgow University, and subsequently in production form with Gordan employed on a consultancy basis by SCPMDE.
The SPA program’s allocation process takes place in a number of stages, as follows:
Irving [Irv98] gives further details, particularly of the network flow and graph theory techniques, that are used in the SPA program.
6. Summary of the 1999-2000 SPA outcomes
In the first round of the SPA scheme, run in January 2000, the student optimal stable matchings in medicine and surgery were successfully combined to form a seasonal allocation, without any need to break any individual matches. The numerical outcomes are summarised as follows:
1 2 3 4 5
354 82 23 11 11
1 2 3 4 5
312 82 47 21 11
In the second round:
1 2 3 4
10 1 3 2
1 2 3 4
10 4 0 2
The reason that as many as 17 surgical candidates remained unallocated was that all of these required a surgical post in the second half-year, but all such posts were filled.
7. Conclusion and possible improvements
The outcome of the first year of the SPA scheme was generally viewed as satisfactory by the participants and by those administering the scheme. Some consultants were sceptical, finding it hard to accept that the scheme had allocated to them, for example, their 40th choice student out of 45. Of course, this could only have happened because those of the preferred 39 who were not allocated to the unit in question must have been matched to units that they preferred.
A number of hospital units included ties at the end of their preference list, as allowed for by the scheme, and, as indicated above, these ties were resolved in an arbitrary way by the matching program. Subsequent hand analysis of the medical match revealed that, had these ties been resolved in a different way, an additional 3 students could have been matched, i.e., 484 rather than 481. Although the (laborious) hand analysis has not been carried out on the surgical match, a similar outcome would be likely. Although the difference is small, it would have potentially crucial career implications for the individuals concerned.
No reasonable algorithm is known that will enable the ‘best’ way of breaking the ties to be found effectively in all cases, and it is unlikely that any such algorithm can be found. (In technical terms, this has been shown to be an NP-hard optimisation problem [MIIMM99].) However, a ‘heuristic’ is known, which would be likely to work well in practice ¾ indeed it was this heuristic that was used in the above-mentioned hand-analysis. If and when resources permit, this heuristic ought to be incorporated into the SPA program.
[GI89] D. Gusfield & R.W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989.
[GS62] D. Gale & L.S. Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69 (1962), 9 - 15.
[Irv98] R.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, vol. 1461 of Lecture Notes in Computer Science, pp. 381-392.
[Mac94] V.L. MacKinlay, Pre-registration appointments matching scheme - PRAMS, Unpublished manuscript, 1994.
[MIIMM99] D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki & Y. Morita, Hard variants of stable marriage, Technical Report no. TR-1999-43 of the Computing Science Department of Glasgow University, September 1999. Submitted for publication. Abstract.
[Rot84] A.E. Roth, The evolution of the labor market for medical interns and residents: A Case Study in Game Theory, Journal of Political Economy, 92:991-1016, 1984. Abstract and Introduction.
[Rot90] A.E. Roth, A natural experiment in the organization of entry level labor markets: regional markets for new physicians and surgeons in the U.K., American Economic Review, 81:415-440, June 1991.
[RP97] A.E. Roth & E. Peranson, The effects of the change in the NRMP matching algorithm, Journal of the American Medical Association, 278, 9, September 3, 1997, 729-732.