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)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 Q
i (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. POWER LAW SIGNATURE IN INDONESIAN LEGISLATIVE ELECTION 1999-2004
2. The name is absent
3. The name is absent
4. CONSUMER ACCEPTANCE OF GENETICALLY MODIFIED FOODS
5. PROJECTED COSTS FOR SELECTED LOUISIANA VEGETABLE CROPS - 1997 SEASON
6. The resources and strategies that 10-11 year old boys use to construct masculinities in the school setting
7. On the Existence of the Moments of the Asymptotic Trace Statistic
8. Credit Market Competition and Capital Regulation
9. The name is absent
10. The name is absent
11. Neural Network Modelling of Constrained Spatial Interaction Flows
12. Spectral calibration of exponential Lévy Models [1]
13. The name is absent
14. The name is absent
15. The name is absent
16. Dual Track Reforms: With and Without Losers
17. Has Competition in the Japanese Banking Sector Improved?
18. The name is absent
19. ISO 9000 -- A MARKETING TOOL FOR U.S. AGRIBUSINESS
20. A Study of Adult 'Non-Singers' In Newfoundland