SPA ¾
The __S__cottish __P__RHO __A__llocations Scheme

Technical Report on the First Year of Operation 1999-2000

Rob Irving

Computing Science Department

University of Glasgow

1. Introduction

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.

2. Background

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

- S is unallocated, or would prefer a post in H to the post he or she has been given,

and simultaneously

- H has a vacant post, or would prefer S to at least one of the students assigned to it.

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

- Matchings should respect the stability criterion
- Student-optimal, rather than hospital-optimal matchings should be used
- Students should be allowed to express an optional
*seasonal preference*, in other words a preference that they should undertake their posts in the order medical-surgical or surgical-medical - A match of rotational posts should be carried out first; any student seeking a rotational post would take part in this match; students unallocated at this stage would then join the medical/surgical match
- Students would be asked to rank their top 5 medical units, their top 5 surgical units, and, if they wished, their top 2 rotational choices
- Hospital units would be asked to rank as many as possible of the students who had ranked them, and the remainder would be randomly ranked (at the ‘tail’ of the unit’s list) by the computer program
- The allocations would be binding on all participants
- Students not completely allocated in the first round of the SPA scheme, together with unfilled posts, would enter a second round; new preference data would be collected, with students allowed to rank as many of the available units as they wished, and a further allocation carried out using the same methods as in the first round. Some ad hoc allocations might be necessary for the last few participants incompletely matched after the second round.

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:

- Any ties in hospitals preference lists are resolved randomly, and student and hospital lists are made consistent, so that hospital H is in the list of student S if and only if S is in H’s list (bearing in mind possible vetos, and a student’s possible withdrawal of interest in a particular hospital)

- The student-optimal stable matching of students to rotational posts is determined using the classical Gale-Shapley algorithm; all matched students are then removed from the pool for the medical and surgical matches
- The student-optimal stable matchings for medical posts and surgical posts are then found separately and independently, using a version of the Gale-Shapley algorithm extended and adapted to allow for seasonally restricted applicants
- Using techniques of network flow, the medical and surgical matches are integrated so that each student’s allocation to a post is scheduled for a particular half-year; this is done in such a way that no student has two posts in the same half year, and no hospital unit is assigned more students than it needs in a particular half year
- Using techniques of graph theory, the combination of the two matchings is adjusted to maximise the number of students who have their seasonal preference satisfied.

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:

- A total of 676 students took part in the scheme

- 127 students were allocated to a rotational post
- 103 to their first choice, and 24 to their second choice
- 7 rotational posts remained unfilled

- 503 students took part in the medical match
- 481 were matched, to their various choices as follows:

1 2 3 4 5

354 82 23 11 11

- 511 students took part in the surgical match
- 473 were matched, to their various choices as follows:

1 2 3 4 5

312 82 47 21 11

- 38 students sought only a medical post, of whom 34 were matched

- 46 students sought only a surgical post, of whom 37 were matched

- 465 students sought both a medical post and a surgical post, of whom 420 achieved both, 27 achieved only a medical post, 16 achieved only a surgical post, and 2 achieved neither

- Of these 465 candidates, 122 expressed a seasonal preference, and only 2 of these were allocated posts that failed to satisfy that preference.

In the second round:

- There was a total of 50 applicants, 2 for rotational appointments, 15 for a medical posts only, 32 for a surgical post only, and 1 for both a medical and surgical post
- Both rotational candidates were allocated, one to his first and one to his second choice
- All medical candidates were allocated to their various choices as follows:

1 2 3 4

10 1 3 2

- Only 16 of the surgical candidates were allocated, as follows:

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.

References

[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.