Another desirable property for a matching is Pareto-efficiency. In the context of school
choice, to determine whether a matching is Pareto-efficient we only take into account
students’ welfare. A matching μ' Pareto dominates a matching μ if all students prefer μ'
to μ and there is at least one student that strictly prefers μ' to μ. Formally, μ' Pareto
dominates μ if μ'(i)Riμ(i) for all i ∈ I, and μ'(i')Pi'μ(i') for some i' ∈ I. A matching is
Pareto-efficient if it is not Pareto dominated by any other matching. We denote the set
of Pareto-efficient matchings by PE(P).
A (student assignment) mechanism systematically selects a matching for each school
choice problem. A mechanism is individually rational if it always selects an individually
rational matching. Similarly, one can speak of non wasteful, stable, or Pareto-efficient
mechanisms. Finally, a mechanism is strategy-proof if no student can ever benefit by
unilaterally misrepresenting his preferences.11
3 Three Competing Mechanisms
In this section we describe the mechanisms that we study in the context of constrained
school choice: the Boston, Student-Optimal Stable, and the Top Trading Cycles mecha-
nisms. The three mechanisms are direct mechanisms, i.e., students only need to report an
ordered list of their acceptable schools. For a profile of revealed preferences the matching
that is selected by a mechanism is computed via an algorithm. Below we give a description
of the three algorithms, thereby introducing some additional notation. Let (I, S, q, P, f)
be a school choice problem.
3.1 The Boston Algorithm
The Boston mechanism was first described in the literature by Alcalde (1996) who called
it the “Now-or-never” mechanism. The term “Boston mechanism” was coined by Ab-
dulkadiroglu and Sonmez (2003) because the mechanism was used in the Boston school
district until recently. Consider a profile of ordered lists Q submitted by the students.
The Boston algorithm finds a matching through the following steps.
Step 1: Set qs1 := qs for all s ∈ S. 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 assigns
11In game theoretic terms, a mechanism is strategy-proof if truthful preference revelation is a weakly
dominant strategy.
More intriguing information
1. An Incentive System for Salmonella Control in the Pork Supply Chain2. Group cooperation, inclusion and disaffected pupils: some responses to informal learning in the music classroom
3. Mergers under endogenous minimum quality standard: a note
4. Ability grouping in the secondary school: attitudes of teachers of practically based subjects
5. Outsourcing, Complementary Innovations and Growth
6. The name is absent
7. The name is absent
8. Migration and Technological Change in Rural Households: Complements or Substitutes?
9. fMRI Investigation of Cortical and Subcortical Networks in the Learning of Abstract and Effector-Specific Representations of Motor Sequences
10. EU enlargement and environmental policy