up to qs1 seats to its proposers one at a time following the priority order fs . Remaining
students are rejected. Let qs2 denote the number of available seats at school s. If qs2 = 0
then school s is removed.
Step l, l ≥ 2: Each student i that is rejected in Step l - 1 proposes to the next school
in the ordered list Qi (if there is no such school then i remains unassigned). School s
assigns up to qsl seats to its (new) proposers one at a time following the priority order fs.
Remaining students are rejected. Let qsl+1 denote the number of available seats at school
s. If qsl+1 = 0 then school s is removed.
The algorithm stops when no student is rejected or all schools have been removed. Any
remaining student remains unassigned. Let β(Q) denote the matching. The mechanism
β is the Boston mechanism, or BOS for short. It is well known that BOS is individually
rational, non wasteful, and Pareto-efficient. It is, however, neither stable nor strategy-
proof.
3.2 The Gale-Shapley Deferred Acceptance Algorithm
The deferred acceptance (DA) algorithm was introduced by Gale and Shapley (1962).
Let Q be a profile of ordered lists submitted by the students. The DA algorithm finds a
matching through the following steps.
Step 1: Each student i proposes to the school that is ranked first in Qi (if there is no
such school then i remains unassigned). Each school s tentatively assigns up to qs seats
to its proposers one at a time following the priority order fs . Remaining students are
rejected.
Step l, l ≥ 2: Each student i that is rejected in Step l - 1 proposes to the next school
in the ordered list Qi (if there is no such school then i remains unassigned). Each school
s considers the new proposers and the students that have a (tentative) seat at s. School
s tentatively assigns up to qs seats to these students one at a time following the priority
order fs . Remaining students are rejected.
The algorithm stops when no student is rejected. Each student is assigned to his final
tentative school. Let γ(Q) denote the matching. The mechanism γ is the Student-Optimal
Stable mechanism, or SOSM for short. SOSM is a stable mechanism that is Pareto
superior to any other stable matching mechanism (Gale and Shapley, 1962). An additional
important property of SOSM is that it is strategy-proof (Dubins and Freedman, 1981;
Roth, 1982b). However, it is not Pareto-efficient.
10