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).12 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 qs1 := qs for all s ∈ S. Each student i points to the school that is ranked
first in Qi (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 fs . 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 qs1 = 1, then the school is removed. If a school s is in a cycle and qs1 > 1,
then the school is not removed and its capacity becomes qs2 := qs1 - 1.
Step l, l ≥ 2: Each student i that is rejected in Step l - 1 points to the next school in
the ordered list Qi 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 qsl = 1, then the school is removed. If a school s is in a cycle and qsl > 1,
then the school is not removed and its capacity becomes qsl+1 := qsl - 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.
12The 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