Top Trading Cycles

Top Trading Cycles (TTC) is the algorithm for the one-sided allocation problem that Stable Matching is for the two-sided one. In the Shapley–Scarf housing market (Shapley & Scarf 1974, “On Cores and Indivisibility”, J. Math. Econ.), n agents each own one indivisible good — a house, a dorm room, a kidney donor — and each has a strict ranking over all n goods. There is no money. TTC, which Shapley and Scarf attribute to David Gale, is one paragraph long: every agent points at the owner of its favourite house, every house points at its owner, the resulting out-degree-one graph must contain a cycle, and every cycle is a swap that can be executed immediately and removed. Repeat until the market is empty. What that paragraph buys is three theorems that rarely coexist: the outcome is the unique allocation in the core (Algorithmic Game Theory ch. 10, Theorem 10.6), it is Pareto efficient, and the mechanism is strategyproof — truth-telling is a dominant strategy (Roth 1982, Economics Letters 9:127–132). TTC is why kidney exchange exists as an organized market, and it is one of the two candidate mechanisms every school-choice reform has to choose between. That choice is a genuine policy trade-off: TTC is efficient but not stable, deferred acceptance is stable but not efficient, and no mechanism is both.

---

Mental Model — a market with no money is a graph with no sinks

The trick that makes TTC work is a graph-theoretic triviality with an economic payload. Give every agent exactly one outgoing edge — pointing at the thing it most wants — and every good exactly one outgoing edge, pointing back at its owner. A finite directed graph in which every node has out-degree exactly one must contain a cycle: start anywhere, keep walking, and since the node set is finite you must eventually revisit a node, and everything from that revisit onward is a cycle. There are no dead ends because nobody can point at nothing: every agent owns something, so its own house is always an available fallback.

A cycle is a feasible round of barter. Everybody in the cycle hands their house to the previous member and receives the house they were pointing at — which is, by construction, the best house still on the market as far as they are concerned. Nobody outside the cycle is touched. So the trade can be executed and the participants removed, and the argument repeats on the smaller market.

flowchart LR
    subgraph R1["Round 1 — two cycles fire at once"]
        a0(("a0")) -->|"wants h1"| h1["h1"]
        h1 -->|"owned by"| a1(("a1"))
        a1 -->|"wants h0"| h0["h0"]
        h0 -->|"owned by"| a0
        a5(("a5")) -->|"wants h5<br/>(its own)"| h5["h5"]
        h5 -->|"owned by"| a5
    end
    subgraph R2["Round 2 — after a0,a1,a5 leave"]
        a2(("a2")) -->|"h1 gone,<br/>wants h3"| h3["h3"]
        h3 --> a3(("a3"))
        a3 -->|"wants h2"| h2["h2"]
        h2 --> a2
    end
    subgraph R3["Round 3 — a4 alone"]
        a4(("a4")) -->|"all better<br/>houses gone"| h4["h4"]
        h4 --> a4
    end
    R1 --> R2 --> R3

What it shows: three rounds of TTC on the six-agent market used throughout this note. Circles are agents, boxes are houses; each agent’s edge points at the best house still available, each house’s edge points at its current owner. The insight to take: the two structures in Round 1 are both cycles — a two-cycle (a0 ⇄ a1, a genuine swap) and a self-loop (a5 most prefers the house it already owns, so it trades with itself and leaves). Self-loops are why nobody can be made worse off than their endowment: an agent whose own house is the best thing left simply keeps it, which is exactly what happens to a4 in Round 3. This is individual rationality falling out of the algorithm’s structure rather than being imposed on it.

The three vocabulary items, defined

Because this note has to stand alone, here are the three terms that carry the theorems, defined in plain language before they are used.

The core. An allocation a (a permutation: a[i] is the house agent i ends up with) is blocked by a coalition S if the members of S, using only the houses they themselves brought to the market, could redistribute among themselves so that every member of S is weakly better off and at least one is strictly better off. The core is the set of allocations no coalition can block. It is the natural stability notion when agents own the resources: an allocation outside the core is one that some group would walk away from and implement privately. (This is the non-transferable-utility version of the core defined in Coalitional Games; the same idea, no money.)

Pareto efficiency. a is Pareto efficient if there is no other feasible allocation making everybody weakly better off and somebody strictly better off. The core is a stronger requirement — it demands this against every sub-coalition, and the grand coalition S = N is one of them — so core ⇒ Pareto efficient, and the efficiency theorem is a corollary of the core theorem, not an independent result.

Strategyproofness. The mechanism asks each agent to report a preference ordering. It is strategyproof (dominant-strategy incentive compatible, see Incentive Compatibility) if, whatever everyone else reports, no agent can obtain a house it genuinely ranks higher by reporting anything other than its true ordering.

Why Gibbard–Satterthwaite does not kill this

Impossibility Results contains the Gibbard–Satterthwaite theorem: any non-dictatorial, onto social choice function over three or more alternatives with unrestricted preferences is manipulable. TTC is strategyproof anyway, and the reason is a domain restriction. As the Algorithmic Game Theory treatment puts it: “While any possible (strict) preference ordering over the homes is permitted, the set of preferences over allocations is restricted. In particular, an agent is indifferent between all allocations that give her the same house. Therefore the Gibbard–Satterthwaite Theorem does not apply in this setting.” I care which house I get and nothing else. That single externality-free assumption is what buys strategyproofness, and it is exactly what fails when agents care about who else is admitted.

---

The Algorithm, in Real C

/* Every remaining agent points at its favourite remaining house; every house
 * points back at its owner.  Out-degree 1 on a finite graph guarantees a cycle.
 * Clear every cycle, remove those agents and houses, repeat. */
static void ttc(const Mkt *m, int *alloc)
{
    int gone[N] = {0};
    int point[N];                                        /* point[i] = house i wants */
    for (int i = 0; i < N; i++) alloc[i] = -1;
 
    int remaining = N;
    while (remaining > 0) {
        for (int i = 0; i < N; i++) {
            if (gone[i]) continue;
            for (int k = 0; k < N; k++) {
                int h = m->pref[i][k];
                if (!gone[h]) { point[i] = h; break; }    /* house h == owner h */
            }
        }
        /* find one cycle by walking from any live agent until a node repeats */
        int start = -1;
        for (int i = 0; i < N; i++) if (!gone[i]) { start = i; break; }
        int seen[N]; memset(seen, -1, sizeof seen);
        int cur = start, step = 0;
        while (seen[cur] < 0) { seen[cur] = step++; cur = point[cur]; }
        /* everything from seen[cur] onward is the cycle */
        int cyc_start = seen[cur];
        for (int i = 0; i < N; i++)
            if (seen[i] >= cyc_start) { alloc[i] = point[i]; gone[i] = 1; remaining--; }
    }
}

Reading it line by line:

• point[i] is the only state the algorithm needs. Because houses are indexed by their owner (house i is endowed to agent i), “the house i wants” and “the agent i is pointing at” are the same integer, and the graph collapses to a single successor array. This identification is the reason the code is fifteen lines rather than fifty.
• The inner for (k…) scan is the pointing rule — walk down i’s preference list until you find a house still on the market. Because i’s own house is on the market as long as i is, this loop cannot fall off the end. That is the individual-rationality guarantee, encoded as a loop bound.
• while (seen[cur] < 0) is the cycle finder, and it is a ρ-shaped walk: follow successors, stamping each node with the step at which it was first seen, until you hit a stamped node. Everything stamped ≥ seen[cur] is on the cycle; everything stamped lower is on the tail leading into it and stays for the next round. This is the same shape as Floyd’s cycle detection, without needing two pointers because the successor array is materialized.
• Complexity. Each round removes at least one agent, so there are at most n rounds; each round costs O(n²) for the pointing scan plus O(n) for the walk. The naive bound is O(n³). Clearing all cycles per round rather than one (a strongly-connected-components pass) gets you O(n²), and with adjacency lists the whole thing is linear in the input size. For the sizes at which TTC is actually deployed — a school district, a kidney registry — none of this matters, and readability is worth more than the constant factor.

A worked trace

Six agents, preferences chosen so that the algorithm takes three rounds and produces four different outcomes-by-rank:

Agent	Owns	Preference order (best first)
a0	h0	h1 h2 h0 h3 h4 h5
a1	h1	h0 h3 h1 h2 h4 h5
a2	h2	h1 h3 h4 h2 h0 h5
a3	h3	h2 h0 h3 h1 h4 h5
a4	h4	h0 h2 h5 h4 h1 h3
a5	h5	h5 h4 h0 h1 h2 h3

=== worked Shapley-Scarf housing market, 6 agents ===
agent : endowment -> TTC assignment (rank on own list)
  a0  :    h0      ->    h1   (choice #1)
  a1  :    h1      ->    h0   (choice #1)
  a2  :    h2      ->    h3   (choice #2)
  a3  :    h3      ->    h2   (choice #1)
  a4  :    h4      ->    h4   (choice #4)
  a5  :    h5      ->    h5   (choice #1)
TTC allocation is in the core : YES
number of core allocations over all 6! = 720 allocations : 1

a4 is the instructive one. Its first three choices (h0, h2, h5) are all gone by Round 3 — taken in earlier cycles by agents who wanted them and could pay for them with something those owners wanted. So a4 keeps its own house, its fourth choice. That is not a failure of the mechanism; it is the mechanism working. a4 had nothing anyone in the first two cycles wanted enough to trade for, so there was no trade to be had. Nobody made a4 worse off than it started, which is all a barter market can promise.

---

The Three Theorems, and Verifying Them Exhaustively

1. The core is exactly one allocation, and TTC finds it

The proof is short enough to give in full, and it is by induction on the rounds. Let N₁ be the set of agents removed in Round 1, N₂ those removed in Round 2, and so on. Following Algorithmic Game Theory, Theorem 10.6:

Under the TTCA, each agent in N₁ receives his favorite house, i.e., the house ranked first in his preference ordering. Therefore, N₁ would form a blocking coalition to any allocation that does not assign to all of those agents the houses they would receive under the TTCA… Given this fact, the same argument applies to N₂: Under the TTCA, each agent in N₂ receives his favorite house not including those houses originally endowed by agents in N₁… Continuing the argument for each N_k proves that if an allocation is in the core, then it is the one determined by the TTCA.

Walk through why each step is forced. Every agent in N₁ is getting its globally favourite house — so if any candidate allocation gives even one of them something else, that whole set can walk out and re-execute their Round-1 cycles among themselves, and everyone in the coalition is weakly better off with at least one strictly better. That is a block. So the core, if non-empty, agrees with TTC on N₁. Now the houses owned by N₁ are spoken for; N₂’s members are getting their favourites among what remains, and the identical argument applies. Induction finishes it.

flowchart TB
    N1["N₁ — removed in round 1<br/>each gets its GLOBALLY<br/>favourite house"]
    Q1{"Does a candidate core allocation<br/>give N₁ anything else?"}
    B1["N₁ walks out and re-runs its own<br/>round-1 cycles among themselves.<br/>BLOCKED."]
    N2["N₂ — removed in round 2<br/>each gets its favourite house<br/>among what N₁ did not own"]
    Q2{"Does it give N₂<br/>anything else?"}
    B2["N₂ walks out. BLOCKED."]
    NK["…induct on N₃, N₄, …, N_k"]
    U["Any core allocation agrees<br/>with TTC on every round<br/>⇒ AT MOST ONE core allocation"]

    N1 --> Q1
    Q1 -->|yes| B1
    Q1 -->|no| N2
    N2 --> Q2
    Q2 -->|yes| B2
    Q2 -->|no| NK
    NK --> U

What it shows: the induction behind Theorem 10.6 — each round’s departing set N_k is a ready-made blocking coalition against any allocation that disagrees with TTC about them. The insight to take: the proof never searches for a blocking coalition; the algorithm hands you one, round by round. That is why “TTC finds the core” and “the core has one element” are the same theorem rather than two.

That establishes at most one core allocation. That the TTC allocation is in the core requires showing no other coalition blocks it — the textbook leaves that to the reader, and it is the half the computer checks below.

2. Strategyproofness

Again short, and worth understanding rather than memorizing. Suppose agent j is removed in round k under truthful reporting and tries some misreport. The rounds 1 … k−1 did not involve j at all, so the misreport cannot change who left in them — the set of houses still on the market when round k begins is unchanged. But TTC gave j its favourite house among exactly that remaining set. Any misreport can only make j leave in some round with the same or a smaller pool of available houses. There is nothing better to get. In the source’s compressed form:

the TTCA chooses a_i to be agent i’s top ranked choice from N \ {∪ N_r} contradicting the fact that a'_i > _i a_i.

Note what the proof does not rely on: it never mentions other agents’ incentives, and it never assumes anything about the distribution of preferences. This is dominant-strategy truthfulness, the strong kind.

3. Verified by exhaustive search

Proofs on paper are exactly the thing that gets mistyped into code. So both theorems were checked by brute force on random six-agent markets:

• Core membership is tested by enumerating all 2⁶ = 64 coalitions and, for each, every permutation of that coalition’s own endowments — the full definition of a block, no shortcuts.
• Core uniqueness is tested by running that core test on all 6! = 720 possible allocations and counting the survivors.
• Strategyproofness is tested by, for each agent in turn, replacing its report with each of the 720 possible preference orders, re-running TTC, and scoring the result against the agent’s true preferences. If any misreport ever yields a strictly better house, the mechanism is manipulable on that instance.

=== random sweep: 6 agents, 20000 markets ===
markets tested                           : 20000
TTC allocation was in the core           : 20000
markets with EXACTLY ONE core allocation : 20000
agent-instances where a misreport helped : 0 (out of 120000)
total misreports exhaustively evaluated  : 86400000

Twenty thousand markets, twenty thousand core memberships, twenty thousand unique cores, and 86.4 million individual misreports evaluated without a single profitable one. That is not a proof, but as The Gale-Shapley Algorithm argues about its own strategyproofness checks, a claim you have genuinely tried and failed to break is worth more than one you proved on paper and then mistyped into an implementation.

Uncertain

Verify: (a) the precise statement and attribution of the characterization result — TTC is often said to be the unique mechanism that is simultaneously individually rational, Pareto efficient, and strategyproof, usually attributed to Ma (1994, International Journal of Game Theory 23:75–83); (b) the exact page/volume of Shapley & Scarf (1974). Reason: neither primary paper could be retrieved — and the failure is retrieval, not extraction. Twelve candidate URLs were tried for Shapley & Scarf (1974) and Roth (1982), including the ScienceDirect article PDF and eight course-page mirrors of the */courses/*/papers/*.pdf shape. Not one returned a PDF: every response was HTML — HTTP 404, HTTP 403, or a JavaScript “Session Verification” interstitial (Harvard’s eecs.harvard.edu/cs286r/courses/fall09/papers/ archive, which indexes both papers, is behind exactly that challenge and answers HTTP 200 with a 4.4 KB challenge page rather than the file). Because nothing was downloaded, the render-and-read route for image-only scans (pdftoppm -png -r 120, which recovers text from a PDF with no font layer) has nothing to operate on; it is worth retrying only if a mirror later serves an actual PDF. Shapley & Scarf is cited as “Journal of Mathematical Economics (1974), 23–28” in the reference list of Roth, Sönmez & Ünver (2004), which was read, so the bibliographic fact is second-hand but from a primary source; Ma (1994) is not cited in anything fetched here and is stated from background knowledge only. To resolve: fetch Shapley & Scarf (1974) and Ma (1994) directly. The three theorems that this note does assert — core uniqueness, Pareto efficiency, strategyproofness — are each quoted from a fetched source and verified computationally above.

Where the guarantees stop: indifference

Everything above assumes strict preferences. Relax that and the picture changes in a way worth knowing, because real applications (kidney compatibility in particular) are riddled with indifference. With ties, “blocking” splits into two notions: a weakly blocking coalition (everyone weakly better, someone strictly) and a blocking coalition (everyone strictly better). The set of allocations immune to weak blocking is the strict core; the set immune to strict blocking is the core. Under strict preferences these coincide — the argument, from the same source, is that in a weakly blocking set any member not made strictly better off must have kept their own house, and can be deleted from the coalition; iterate, and what remains blocks strictly. With indifference they come apart: “there are examples where the strict core is empty and others where it is not unique. Deciding emptiness of the strict core is polynomial in |N|.”

The other relaxation that kills everything is multiple endowments: give agents a house and a car, and “even under very severe restrictions the core can still be empty. For example, when preferences are separable.” That is the same complementarity disease that couples give the Hospital-Residents and the NRMP problem, arriving from a different direction.

---

School Choice: TTC versus Deferred Acceptance

This is the section where TTC stops being an elegant algorithm and becomes a policy argument.

Abdulkadiroğlu and Sönmez (2003) made the observation that turned school assignment into a matching problem: school priorities have the same mathematical form as school preferences, so two-sided matching machinery applies — but with a crucial difference in interpretation. In Boston, as the Roth–Abdulkadiroğlu–Pathak account puts it, “only the students and their families were active players, the schools were passive, with priorities set by the central administration.” Schools do not want anything. Their priority orders — sibling attending, walk-zone, lottery number — are administrative devices, not preferences.

That reframing forces a question. If priorities are just a rationing device, why should they be inviolable? Abdulkadiroğlu and Sönmez observed that the counterpart of stability here is the elimination of justified envy: there should be no student who prefers some school to their assignment where that school either has an empty seat or admitted a student with lower priority. Student-proposing deferred acceptance eliminates justified envy and is strategyproof for students, but it is not Pareto efficient. TTC, adapted so that students point at their favourite school with seats left and each school points at its highest-priority remaining student, is Pareto efficient and strategyproof, but it creates justified envy — because that is precisely what trading priorities means.

flowchart TB
    Q{"What are school priorities FOR?"}
    Q -->|"They are earned entitlements<br/>(exam scores, sibling ties)<br/>and must be enforced"| DA["Student-proposing<br/>Deferred Acceptance"]
    Q -->|"They are just a rationing<br/>device for scarce seats"| TTC["Top Trading Cycles"]
    DA --> DAP["✓ No justified envy<br/>✓ Strategyproof for students<br/>✗ NOT Pareto efficient"]
    TTC --> TTCP["✓ Pareto efficient<br/>✓ Strategyproof<br/>✗ Creates justified envy"]
    DAP --> IMP["No mechanism has all four.<br/>The choice is a value judgement,<br/>not a technical one."]
    TTCP --> IMP

What it shows: the school-choice decision tree, with the property each branch buys and the property it gives up. The insight to take: the question at the top is not answerable by an algorithm. It is a question about what a priority means in that district, and different districts have answered it differently.

Measured on the same instances

The trade-off is usually described qualitatively. Here it is numerically, on 200,000 random instances with six students, three schools, two seats each, complete strict preferences and random priority orders. Both mechanisms run on identical inputs; blocking_pairs and the Pareto-domination test are independent code paths from either algorithm.

=== TTC vs student-proposing DA, 6 students / 3 schools / 2 seats each ===
instances                                    : 200000
mean rank of assigned school  DA             : 1.3435
mean rank of assigned school  TTC            : 1.3271
students getting first choice DA             : 71.67%
students getting first choice TTC            : 74.99%
student-instances strictly better under TTC  : 98832 (8.24%)
student-instances strictly better under DA   : 67477 (5.62%)
--
instances where TTC == DA                    : 131124 (65.56%)
instances where TTC Pareto-dominates DA      : 8380 (4.19%)
instances where neither dominates            : 60496 (30.25%)
--
blocking pairs under DA  (total / instance)  : 0 / 0.0000
blocking pairs under TTC (total / instance)  : 97048 / 0.4852
instances where TTC has >=1 blocking pair    : 68876 (34.44%)
instances where the DA  outcome is Pareto-inefficient : 14459 (7.23%)
instances where the TTC outcome is Pareto-inefficient : 0  <- must be 0

Six things fall out of that table, and several of them are not obvious:

1. The two sanity checks pass. DA produces zero blocking pairs across 1.2 million student-instances (it is stable by construction), and TTC’s outcome is never Pareto-dominated (it is efficient by construction). Getting either number wrong would mean the harness, not the theory, was broken.
2. TTC really is more efficient, and the margin is modest. 75.0% of students get their first choice under TTC versus 71.7% under DA — a gain of about 3.3 percentage points. Mean assigned rank improves from 1.344 to 1.327.
3. The price is not modest. TTC generates 0.485 blocking pairs per instance, and 34.4% of instances contain at least one student with justified envy. Roughly one district-year in three, under these preferences, would contain a family able to point at a specific child with lower priority who got the seat.
4. TTC does not Pareto-dominate DA. This is the subtlety the Boston paper flags explicitly — “the former does not Pareto dominate the latter” — and here it is quantified: TTC dominates DA in only 4.19% of instances, while in 30.25% neither dominates the other, because 5.62% of student-instances are made strictly worse by TTC. Being efficient does not mean being better for everyone; it means no further Pareto improvement exists from where you land.
5. DA’s inefficiency is real but not ubiquitous. Only 7.23% of DA outcomes are Pareto-dominated by some feasible assignment. Two thirds of the time (65.56%) the two mechanisms return literally the same matching, and the argument is moot.
6. The two “costs” are not commensurable. 4,296 students improved versus 34,899 students with justified envy — as the New York numbers below show at real scale — is not a comparison a mean rank can adjudicate.

The same trade-off on real New York City data

Abdulkadiroğlu, Pathak and Roth (2009) ran exactly this exercise on the New York City high school match. Starting from a student-optimal stable matching for grade 8 applicants in 2006–2007, they used “Gale’s top trading cycles algorithm” to find all welfare-enhancing swaps and produce an efficient matching that dominates it. Their Table 2:

Quantity (2006–07 NYC, grade 8, mean over 250 draws)	Value
Students getting first choice, student-optimal stable matching	32,105.2
Students getting first choice, efficient (TTC) matching	34,707.8
Improvement in first-choice assignments	+2,602.6
Students strictly better off in the efficient matching	4,296.6
…of whom moved up exactly one rank	1,819.7 (42.4%)
Students involved in ≥1 blocking pair in the efficient matching	34,898.8
Total blocking pairs created	~57,046
Students in a blocking pair at exactly one school	22,287.5 (63.9%)
Students in a blocking pair at two schools	6,707.8 (19.2%)
Students in a blocking pair at twelve schools	3.2

Read the third and seventh rows together: buying an improvement for 4,297 students costs justified envy for 34,899 students. The authors’ warning about who those blocking pairs involve is the operational punchline: “If the blocking pair involves a student and a school that actively ranks applicants, then both the student and school will prefer to be matched with each other, and have incentives to circumvent the match.” More than 90% of the created blocking pairs involve an “educational option” programme and about 7% a “screened” programme — both of which submit real rank order lists. These are not passive schools whose priorities are administrative fictions. They are counterparties who will go around the clearinghouse, which is the failure mode that killed the unstable British regional matches described in Hospital-Residents and the NRMP.

What Boston actually decided, and why

Boston chose deferred acceptance. The reasoning is documented, and it is not a mathematical argument. TTC “was initially recommended by a taskforce of community members focused on student assignment in 2003 after over a year of community meetings with parents and families.” The Superintendent’s recommendation against it reads:

Another algorithm we have considered, Top Trading Cycles Mechanism, presents the opportunity for the priority for one student at a given school to be “traded” for the priority of a student at another school… There may be advantages to this approach, particularly if two lesser choices can be “traded” for two higher choices. It may be argued, however, that certain priorities – e.g., sibling priority – apply only to students for particular schools and should not be traded away.

The economists’ own framing of the question they put to the School Committee in June 2005 is the cleanest statement of the trade-off anyone has produced:

“In case your child wants to go to the school for which my child has high priority, and my child wants to go to the school for which your child has a high priority, would anyone mind if they traded priorities?”

They add the honest caveat that such a trade “might result in a third family being excluded from a school even though a child with lower priority was admitted,” and record what happened: “Initially it appeared that the answer was going to be that no one minded, but as the discussion was broadened over the following weeks and months, the choice was made to go with the deferred acceptance algorithm.” A year of consultation flipped the answer. That is what a value judgement looks like when a market designer has to ship one.

TTC did not vanish from school choice, though: Roth notes that it “forms the basis of a new appeals process in the NYC high school match.”

---

Kidney Exchange: the Application That Made TTC Famous

Kidney exchange is the reason most people outside economics have heard of TTC, and it is the clearest case of an algorithm needing surgery — literally — before it could ship.

Why the housing market model fits

A patient with end-stage renal disease may have a willing living donor who cannot donate to them because of ABO blood-type incompatibility or a positive crossmatch. That patient–donor pair is exactly an agent endowed with an indivisible good they do not want and cannot sell — the National Organ Transplant Act of 1984 makes buying or selling a kidney illegal in the United States, which is why this is a barter market with no money and therefore a Shapley–Scarf housing market. Roth, Sönmez and Ünver (2004) make the mapping explicit and note the immediate consequence: “if we consider exchange only among patients with donors, the properties of the housing market model essentially carry over unchanged, if we assume that donors’ preferences are aligned with those of their intended recipient.”

The economics is Jevons’s double coincidence of wants, quoted at length in Roth, Sönmez and Ünver (2007): “to allow of an act of barter, there must be a double coincidence, which will rarely happen.” A two-pair swap requires exactly such a coincidence. TTC’s whole contribution is that it finds cycles, not just pairs, and a cycle of length three or more is a coincidence of wants that no pair of patients could have discovered on their own.

The scale of the problem in the mid-2000s, from the same paper: just over 9,900 deceased-donor kidney transplants in 2005 against more than 60,000 patients waiting, a median wait over three years, over 4,000 deaths on the list that year and another 1,000 removed as “too sick to transplant.” Against that, 6,563 living-donor transplants. Roth, Sönmez and Ünver’s earlier estimate was that organized exchange could raise live donations among unrelated donors “from about 54% to as much as 91% if multiple-pair exchanges are feasible, and to as much as 75% even if only pairwise exchanges are feasible.” On a real database of incompatible pairs assembled by Dr Susan Saidman at Massachusetts General, “18% of them could participate in live donor exchanges involving only paired exchanges among patient–donor pairs in the database, and 27% could receive transplants if larger exchanges among them were feasible.”

Why pure TTC could not be deployed: the simultaneity constraint

Here is the modification that theory did not anticipate. The pairwise-exchange paper states the binding constraint plainly:

all transplantations in an exchange need to be carried out simultaneously, for incentive reasons, since otherwise a donor may withdraw her consent after her intended recipient receives a transplanted kidney. So even a pairwise exchange involves four simultaneous surgical teams, operating rooms, etc.

That is the whole problem in two sentences. A cycle in TTC is a promise to trade, executed atomically on paper. In kidney exchange the trade cannot be atomic unless every surgery in the cycle happens at once, because there is no contract that can compel a donor to give up a kidney after their own loved one has already been transplanted. Two pairs means four simultaneous surgeries; three pairs means six. Roth, Sönmez and Ünver note the counts explicitly and add, with masterful understatement, “Larger exchanges pose more logistical difficulties.”

So a mechanism whose entire power comes from finding arbitrarily long cycles must be run with a hard cap on cycle length. That is not a tuning parameter; it is a structural amputation, and it costs the guarantees. Once cycles are length-bounded, the outcome is no longer the core allocation, and the problem becomes a constrained matching problem solved with integer programming rather than a graph walk.

The empirical rescue, and the reason the compromise is tolerable, is Roth, Sönmez and Ünver (2007): “Developing infrastructure to perform three-way as well as two-way exchanges will have a substantial effect on the number of transplants that can be arranged. Larger than three-way exchanges have less impact on efficiency. In a general model of type-compatible exchanges, the size of the largest exchanges required to achieve efficiency equals the number of types.” Because compatibility is driven mostly by a small number of blood types, most of the achievable gain is captured by allowing cycles of length ≤ 3 — so a cap of three buys nearly all the efficiency at six simultaneous surgeries rather than an unbounded number.

Two further deviations from the textbook model are worth naming. First, preferences are essentially 0–1, not strict: “transplants of compatible live kidneys have about equal graft survival probabilities, regardless of the closeness of tissue types between patient and donor.” That is mass indifference, which — per the strict-core discussion above — is exactly where TTC’s uniqueness guarantee dissolves. Second, patients without donors and unpredictable deceased-donor kidneys have to be folded in, which the 2004 paper handles with a TTCC (Top Trading Cycles and Chains) generalization: alongside cycles, a w-chain ends with a donation to the deceased-donor waiting list, and the patient at the head of the chain is upgraded on that list.

flowchart LR
    subgraph CY["A CYCLE — must be simultaneous"]
        P1["pair 1<br/>donor D1"] --> P2["pair 2<br/>donor D2"]
        P2 --> P3["pair 3<br/>donor D3"]
        P3 --> P1
    end
    subgraph CH["A NEAD CHAIN — need NOT be simultaneous"]
        AD["altruistic<br/>(non-directed)<br/>donor"] --> C1["pair 1"]
        C1 --> C2["pair 2"]
        C2 --> C3["pair 3"]
        C3 --> BD["bridge donor<br/>waits, then<br/>starts the next<br/>segment"]
    end

What it shows: the structural difference between the two ways a kidney exchange can be organized. The insight to take: a cycle has no beginning, so every donor in it is at risk of being the one who reneges after their own patient is transplanted — which forces simultaneity and caps the length. A chain has a beginning — an altruistic donor who is owed nothing — so each donation is made only after the donor’s own recipient has already been transplanted. Reneging is still bad but no longer catastrophic, which removes the simultaneity constraint and with it the length cap.

Chains: the innovation that broke the cycle-length ceiling

Rees et al., New England Journal of Medicine 2009 — Roth and Tuomas Sandholm are among the authors — reported the first nonsimultaneous, extended, altruistic-donor (NEAD) chain:

We report a chain of 10 kidney transplantations, initiated in July 2007 by a single altruistic donor (i.e., a donor without a designated recipient) and coordinated over a period of 8 months by two large paired-donation registries. These transplantations involved six transplantation centers in five states. In the case of five of the transplantations, the donors and their coregistered recipients underwent surgery simultaneously. In the other five cases, “bridge donors” continued the chain as many as 5 months after the coregistered recipients in their own pairs had received transplants.

The incentive logic is what makes this work, and the paper states it directly: “when an altruistic donation… initiates a chain of transplantations, each subsequent donor makes the donation only after the coregistered recipient in his or her pair has already received a transplant. Thus, although reneging in the middle of a chain would still be problematic, it would not irreparably harm the remaining pairs in the chain.” In a cycle, a defection strands somebody who has already given up their kidney. In a chain, a defection merely ends the chain early; nobody who has donated is left without a transplant for their patient. That asymmetry is the entire argument, and it converts a hard atomicity constraint into a soft one. As of that report, “none of the bridge donors have reneged.”

Ten transplants from one altruistic donor over eight months is a result the original TTC could not have produced under any parameter setting, because it is not a cycle at all.

---

Failure Modes and Gotchas

Assuming TTC’s guarantees survive indifference. They do not, and kidney exchange is the case where this bites hardest, since compatible kidneys are close to interchangeable. With ties, the strict core can be empty or non-unique. If your domain has genuine indifference, you must decide whether you are computing a core allocation or merely a Pareto-efficient one, and say which.

Assuming TTC’s guarantees survive multiple endowments. Give agents two goods and the core can be empty even under separable preferences. This is the same complementarity failure that couples inflict on hospital-residents.

Believing “Pareto efficient” implies “everyone does at least as well as under DA.” Measured above: TTC makes 5.62% of student-instances strictly worse than DA, and Pareto-dominates DA in only 4.19% of instances. Efficiency is a statement about the absence of further improvements from the point you land, not a comparison with any other mechanism.

Deploying TTC where the other side has real preferences. The strategyproofness proof rests on agents being indifferent between all allocations that give them the same object. A school that genuinely ranks applicants is a counterparty with an incentive to circumvent an assignment it dislikes — which is exactly what the NYC numbers show: 90%+ of the blocking pairs created by an efficient matching involve programmes that submit real rank order lists.

Ignoring the atomicity of the cycle. In software a cycle is executed by permuting an array. In the physical world every edge of the cycle is a separate irreversible act by a person who can change their mind. If your domain has no way to execute the whole cycle atomically, the cycle length must be capped, and the theorems go with it. Ask this question before writing any code.

Writing a cycle finder that misses the tail. The ρ-shaped walk stamps every node it visits, but only the nodes stamped at or after the first revisited node are on the cycle; the tail must stay for the next round. Off-by-one here silently removes agents who have not traded, and the resulting allocation will fail the core test in a confusing way. This is the single most common TTC implementation bug and it is why the core check above is exhaustive rather than spot-checked.

Assuming self-loops are a degenerate case to special-case away. They are not: they are how the algorithm expresses “this agent keeps its endowment,” and they are load-bearing for individual rationality. A cycle finder that only looks for cycles of length ≥ 2 will loop forever on a market where somebody’s favourite remaining house is their own.

---

Alternatives and When to Choose Them

Mechanism	Efficient?	Stable / no justified envy?	Strategyproof?	Needs two-sided preferences?
Top Trading Cycles	Yes (and the unique core allocation)	No	Yes	No — one side only
Student-proposing deferred acceptance	No	Yes	Yes (for students)	Yes
Hospital/school-proposing DA	No	Yes	No (for the receiving side)	Yes
Boston mechanism (immediate acceptance)	No	No	No — famously manipulable	Yes
Random serial dictatorship	Yes	No	Yes	No — and ignores endowments
Bipartite Matching (max cardinality)	Maximizes count, not welfare	No	n/a — no reports	No preferences at all
Integer programming with cycle caps	Optimal subject to the cap	n/a	Not in general	No

TTC versus deferred acceptance is the decision covered above: it turns on whether priorities are entitlements or rationing devices. Boston and New York both chose DA for the main assignment; NYC uses TTC in an appeals process.

TTC versus random serial dictatorship (order the agents at random; each takes their favourite remaining object) is the choice when there are no endowments — a fresh set of dorm rooms, say. RSD is efficient and strategyproof too, but it has no notion of ownership, so it cannot guarantee anybody keeps what they already have. The bridge between the two settings is the “you request my house — I get your turn” (YRMH-IGYT) mechanism of Abdulkadiroğlu and Sönmez (1999), described in the kidney QJE paper: run a serial dictatorship, but whenever someone requests the room of an existing tenant who has not yet been served, move that tenant to the front of the queue. That upgrade is what makes existing tenants willing to enter the market at all. Roth’s aside is worth quoting because it is the best example in the literature of practitioners independently rediscovering a mechanism: “the idea of upgrading an existing tenant whose current room is requested to the top of the line was also invented by the transplantation community in the form of an indirect exchange program: when a potential donor donates his kidney to the highest priority patient on the waiting list, his intended recipient is upgraded to the top of the waiting list.”

TTC versus integer programming is the kidney-exchange choice in practice. Once cycles are capped at length 2 or 3 and chains are in play, the problem is a constrained maximum-weight packing, and the graph-walk elegance of TTC is not what you want. TTC’s contribution there is conceptual — it established that the problem was a housing market, and that a mechanism could be strategyproof — rather than being the code that ships.

---

Production Notes

Kidney exchange is a real, running clearinghouse. The New England Program for Kidney Exchange was proposed by Delmonico, Saidman, Roth, Sönmez and Ünver, and approved by the Renal Transplant Oversight Committee of New England in September 2004; it is administered through the New England Organ Bank. Databases for identifying exchanges were also initiated in Ohio and in Baltimore (Johns Hopkins). Before organized exchange, the volume was negligible: in UNOS Region 1 (fourteen New England transplant centres and two Organ Procurement Organizations), four paired exchanges and seventeen indirect exchanges were conducted across 2001–2003; five two-way exchanges as of December 2004. The pre-clearinghouse bottleneck was not medical, it was informational — “until recently there have been no databases of incompatible patient-donor pairs: incompatible donors were simply not further considered.”

The market’s structure, not just its size, determines what the algorithm can achieve. Because compatibility is driven by a small number of blood types, exchanges of size three capture most of the efficiency, and the theoretical statement — “the size of the largest exchanges required to achieve efficiency equals the number of types” — is what licenses the practical cycle cap. That is a good example of theory earning its keep by justifying a restriction rather than by producing an algorithm.

Logistics dominate. Four to six simultaneous operating rooms and surgical teams, coordinated across institutions, is the actual cost of a cycle. The NEAD chain that produced ten transplants spanned six transplantation centres in five states over eight months, with bridge donors waiting up to five months. Chains trade a hard scheduling constraint for an ongoing coordination burden and a residual reneging risk that has, so far, not materialized.

Repugnance is a design constraint. The reason this is a barter market at all is that organ sales are illegal under NOTA 1984. Roth’s own footnote in the Boston paper connects the two applications directly: “There is sometimes a gap in intuitions between economists and non-economists about what kinds of things should and should not be traded. As with the reservations about the trading of sibling preferences, these perceptions can play a big role in what kinds of market designs are possible.” The Boston decision against TTC and the existence of kidney exchange have the same root cause — a social judgement about what may be traded.

Deployment lag is measured in years, and consultation changes answers. Boston’s TTC recommendation came from a community taskforce after “over a year of community meetings”; the reversal to DA came after months of further discussion. A market designer’s output is not a matching, it is a decision a school committee can defend in public.

Verification discipline. Every claim in this note that is not a quotation came from code with independent checkers: TTC’s core membership was tested against the full definition (all 2ⁿ coalitions × all permutations within each), core uniqueness against all n! allocations, strategyproofness against all n! misreports per agent, and the school-choice comparison used blocking-pair and Pareto-domination routines that neither algorithm’s implementation shares. The two “must be zero / must be n” sanity rows — DA’s blocking-pair count and TTC’s Pareto-domination count — exist specifically so that a harness bug shows up as an impossible number rather than as a plausible one.

---

See Also

• Stable Matching — the two-sided problem, blocking pairs, and why stability is a different criterion from efficiency
• The Gale-Shapley Algorithm — deferred acceptance, the mechanism TTC competes with in school choice
• Hospital-Residents and the NRMP — many-to-one matching with quotas, the Rural Hospitals Theorem, and the same complementarity failure arriving via couples
• Proposer-Optimality and Strategic Truncation — why the proposing side wins in DA, and where its strategyproofness stops
• Coalitional Games — the core in general, of which the housing-market core here is the non-transferable-utility case
• Incentive Compatibility — dominant-strategy versus Bayes–Nash truthfulness; TTC achieves the strong kind
• Impossibility Results — Gibbard–Satterthwaite, and the domain restriction that lets TTC escape it
• Mechanism Design — the general inverse problem
• Envy-Free Division — the divisible-goods counterpart to “who gets which indivisible thing”
• Bipartite Matching — maximum matching: same picture, no preferences, different problem
• Games and Strategic Systems in C MOC — the parent MOC; this note is part of stage P5