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
More intriguing information
1. The Triangular Relationship between the Commission, NRAs and National Courts Revisited2. An Estimated DSGE Model of the Indian Economy.
3. Why unwinding preferences is not the same as liberalisation: the case of sugar
4. The name is absent
5. The name is absent
6. Giant intra-abdominal hydatid cysts with multivisceral locations
7. The English Examining Boards: Their route from independence to government outsourcing agencies
8. Skill and work experience in the European knowledge economy
9. The name is absent
10. Luce Irigaray and divine matter