Constrained School Choice

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)R_iμ(i) for all i ∈ I, and μ'(i')P_i'μ(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.¹¹

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 q_s¹ := 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

¹¹In game theoretic terms, a mechanism is strategy-proof if truthful preference revelation is a weakly
dominant strategy.

<<   6   7   8   9   10   11   12   >>

More intriguing information