Constrained School Choice

3.3 The Top Trading Cycles Algorithm

The Top Trading Cycles mechanism in the context of school choice was introduced by
Abdulkadiroglu and Sonmez (2003).¹² Let Q be a profile of ordered lists submitted by
the students. The Top Trading Cycles algorithm finds a matching through the following
steps.

Step 1: Set q_s¹ := qs for all s ∈ S. Each student i points to the school that is ranked
first in Q_i (if there is no such school then i points to himself, i.e., he forms a self-cycle).
Each school s points to the student that has the highest priority in f_s . There is at least
one cycle. If a student is in a cycle he is assigned a seat at the school he points to (or to
himself if he is in a self-cycle). Students that are assigned are removed. If a school s is
in a cycle and q_s¹ = 1, then the school is removed. If a school s is in a cycle and q_s¹ > 1,
then the school is not removed and its capacity becomes q_s² := q_s¹ - 1.

Step l, l ≥ 2: Each student i that is rejected in Step l - 1 points to the next school in
the ordered list Q_i that has not been removed at some step r, r < l, or points to himself
if there is no such school. Each school s points to the student with the highest priority
in fs among the students that have not been removed at a step r, r < l. There is at least
one cycle. If a student is in a cycle he is assigned a seat at the school he points to (or to
himself if he is in a self-cycle). Students that are assigned are removed. If a school s is
in a cycle and q_s^l = 1, then the school is removed. If a school s is in a cycle and q_s^l > 1,
then the school is not removed and its capacity becomes q_s^l+1 := q_s^l - 1.

The algorithm stops when all students or all schools have been removed. Any remaining
student is assigned to himself. Let τ (Q) denote the matching. The mechanism τ is the
Top Trading Cycles mechanism, or TTC for short. TTC is Pareto-efficient and strategy-
proof (see Roth, 1982a, for a proof in the context of housing markets and Abdulkadiroglu
and Sonmez, 2003, for a proof in the context of school choice). The mechanism is also
individually rational and non wasteful. However, it is not stable.

¹²The Top Trading Cycles mechanism was inspired by Gale’s Top Trading Cycles algorithm which was
used by Roth and Postlewaite (1977) to obtain the unique core allocation for housing markets (Shapley
and Scarf, 1974). A variant of the Top Trading Cycles mechanism was introduced by Abdulkadiroglu
and Sonmez (1999) for a model of house allocation with existing tenants.

11

<<   8   9   10   11   12   13   14   >>

More intriguing information