The Scottish PRHO Allocations Scheme

This document is intended for those who want more information about the algorithm used in the SPA scheme. It should be read in conjunction with the application booklet. (The algorithm used in the SPA scheme was designed, and the computer program which implements them was written, by Rob Irving and Gordan Low, Computing Science Department, University of Glasgow.)

1. The Stability Property

At the heart of the program is a matching algorithm known as the "Gale-Shapley algorithm", which is applied to produce a stable matching. Stability can be defined as follows:

There cannot be an applicant A and a programme P where

• A is either unmatched or prefers P to his or her assigned programme;

and simultaneously

• P either has a vacancy or prefers A to at least one of the applicants actually assigned to it.

Were such an applicant and programme to exist, it would be to their mutual advantage to break their assignments and come to a private arrangement, thereby undermining the integrity of the scheme. Evidence is available from a number of countries that have used different matching schemes at one time or another for various purposes. This evidence suggests that participants soon lose confidence in any scheme that attempts to enforce an unstable matching, and that such schemes are short-lived. By contrast, stable matching schemes are generally accepted as fair and, for that reason, are more successful in the long term.

One consequence of choosing a stable matching is that an applicant A cannot end up unmatched, unless each programme on his or her preference list has managed to fill all its posts with applicants whom it prefers to A. A second consequence is that an applicant is guaranteed to be matched to the top programme on his or her preference list, provided that, if the programme has n posts, the applicant is ranked among the top n applicants on the programme’s preference list.

It should be noted that, for any given set of data, there may be several possible stable matchings. The one that our algorithm finds is known as "applicant-optimal," which means that no applicant could have a more preferred assignment in any other stable matching. Other options would have included the "programme-optimal" matching, the basis of the Pre-registration Appointments Matching Scheme (in use in the Lothians, Fife and Borders until 1998) and of the National Residents Matching Program (the United States scheme, which, however, switched to the applicant-optimal matching in 1998).

However, no matter which stable matching were to be chosen, many applicants and programmes would end up with exactly the same assignments. For instance, any applicant left unmatched in one stable matching would be unmatched in any stable matching, while any programme that was left with vacancies in one stable matching would have the same number of vacancies in any stable matching and would, indeed, be matched to exactly the same set of applicants. (This property is known as the "rural hospitals" theorem, because of evidence from the United States suggesting that it tends to be hospitals in rural areas which end up undersubscribed.)

Because of the importance of stability, the Gale-Shapley algorithm has been made fundamental to the Scottish scheme.

2. An Example

The following small-scale example illustrates the main idea of the SPA scheme. We consider a set of programme and applicant preference lists. Suppose there are ten applicants, a,b,c,...,j, competing for positions on five programmes, V, W, X, Y and Z, each of which has two positions available. Suppose that each applicant ranks four programmes, and that each programme ranks all of its interested applicants. The following might be the preference lists, with the most preferred applicant or programme listed first in each case, and with a possible matching shown by the red characters (thus, V is matched to d and b, and a is matched to W, etc.):

Applicants’ preference lists

a	:	V	W	Z	X
b	:	V	X	Y	W
c	:	X	Z	W	V
d	:	V	X	Z	Y
e	:	Z	V	X	Y
f	:	Y	Z	V	X
g	:	X	Z	V	W
h	:	Z	V	Y	W
i	:	Z	X	W	V
j	:	Z	V	W	X

Programmes' preference lists

V	:	d	g	j	a	b	h	e	c	i	f
W	:	a	j	c	i	h	b	g
X	:	d	g	i	c	b	e	j	f	a
Y	:	f	h	b	e	d
Z	:	d	h	c	i	a	f	j	e	g

Now, it is clear that the matching indicated is unstable. For instance, a would prefer to be matched to V rather than to W, while V would prefer applicant a to applicant b. Thus a and V could mutually improve their positions by coming to a private arrangement. By contrast, two stable matchings are now shown: the applicant-optimal on the left, the programme-optimal on the right.

Applicants’ preference lists

a	:	V	W	Z	X	a	:	V	W	Z	X
b	:	V	X	Y	W	b	:	V	X	Y	W
c	:	X	Z	W	V	c	:	X	Z	W	V
d	:	V	X	Z	Y	d	:	V	X	Z	Y
e	:	Z	V	X	Y	e	:	Z	V	X	Y
f	:	Y	Z	V	X	f	:	Y	Z	V	X
g	:	X	Z	V	W	g	:	X	Z	V	W
h	:	Z	V	Y	W	h	:	Z	V	Y	W
i	:	Z	X	W	V	i	:	Z	X	W	V
j	:	Z	V	W	X	j	:	Z	V	W	X

Programmes' preference lists

V

:

d

g

j

a

b

h

e

c

i

f

V

:

d

g

j

a

b

h

e

c

i

f

W

:

a

j

c

i

h

b

g

W

:

a

j

c

i

h

b

g

X

:

d

g

i

c

b

e

j

f

a

X

:

d

g

i

c

b

e

j

f

a

Y

:

f

h

b

e

d

Y

:

f

h

b

e

d

Z

:

d

h

c

i

a

f

j

e

g

Z

:

d

h

c

i

a

f

j

e

g

In fact, the only difference between these two stable matchings is that c and i are matched to X and Z respectively in the applicant-optimal matching, and to Z and X respectively in the programme-optimal matching. In particular, as predicted in Section 1, the same applicant (e) is unmatched and the same unit (W) is undersubscribed in both cases.

06/05/04