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,
1. The Stability
Property
At the heart of the program
is a matching algorithm known as the "GaleShapley 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 shortlived. 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 "applicantoptimal," which
means that no applicant could have a more preferred assignment in any other
stable matching. Other options would have included the "programmeoptimal"
matching, the basis of the Preregistration Appointments Matching Scheme (in
use in the Lothians,
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 GaleShapley algorithm has been made fundamental to the
Scottish scheme.
2. An Example
The following smallscale
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
applicantoptimal on the left, the programmeoptimal 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 applicantoptimal matching,
and to Z and X respectively in the programmeoptimal matching. In
particular, as predicted in Section 1, the same applicant (e) is
unmatched and the same unit (W) is undersubscribed in both cases.