Constrained School Choice

up to q_s¹ seats to its proposers one at a time following the priority order fs . Remaining
students are rejected. Let q_s² denote the number of available seats at school s. If q_s² = 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 q_s^l seats to its (new) proposers one at a time following the priority order f_s.
Remaining students are rejected. Let q_s^l+1 denote the number of available seats at school
s. If q_s^l+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 f_s . 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 Q_i (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

<<   7   8   9   10   11   12   13   >>

More intriguing information