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. Accurate, fast and stable denoising source separation algorithms2. Healthy state, worried workers: North Carolina in the world economy
3. Hemmnisse für die Vernetzungen von Wissenschaft und Wirtschaft abbauen
4. The name is absent
5. Impact of Ethanol Production on U.S. and Regional Gasoline Prices and On the Profitability of U.S. Oil Refinery Industry
6. Neighborhood Effects, Public Housing and Unemployment in France
7. Modelling Transport in an Interregional General Equilibrium Model with Externalities
8. A Rare Presentation of Crohn's Disease
9. Towards a Strategy for Improving Agricultural Inputs Markets in Africa
10. The name is absent