🔑

Four people each own a house and each would rather have someone else’s. There is no money, just swaps. Kidney exchange works the same way: patients with willing but incompatible donors trade donors around a cycle so everyone gets a transplant.

Top trading cycles

When goods must be reassigned without money and everyone starts with something, top trading cycles is the answer. Each person points to whoever owns their favourite item; wherever the pointing forms a cycle, that cycle trades and leaves. The result is efficient, in the core, and impossible to game.

From earlier lessons

Two quick ones before we start.

An allocation is in the core if no coalition can...

Deferred acceptance is strategy-proof for...

Predict, then play

Four agents, each owning one house, each with a ranking. Run the cycles and see who ends up where.

Why did that happen?

Take a guess, then reveal the reason

A cycle is a chain of wants that closes on itself: 1 wants 3’s house, 3 wants 2’s, 2 wants 1’s. Everyone in that loop can be satisfied at once by rotating the houses around it. Once a cycle trades and leaves, every remaining agent points again to the owner of their favourite remaining house. An agent keeps their own house only if it is their best option among the houses left, as happens to agent 4 here.

The math

Definition, top trading cycles

Each agent owns one object and has strict preferences. Build a graph in which every remaining agent points to the owner of its favourite remaining object. Because every node has exactly one outgoing edge, at least one cycle exists. Every agent on a cycle receives the object it points to, then leaves with it. Repeat on what remains. The allocation is Pareto efficient, is the unique allocation in the core, and the mechanism is strategy-proof.

With agents $1,2,3,4$ owning $h_1,\dots,h_4$ and the given preferences, round 1 has $1 \to 3$ (owner of $h_3$ ), $2 \to 1$ , $3 \to 2$ , $4 \to 3$ . The cycle $1 \to 3 \to 2 \to 1$ trades: agent 1 gets $h_3$ , agent 3 gets $h_2$ , agent 2 gets $h_1$ . Agent 4 pointed into the cycle but is not on it, so it waits. Round 2 leaves only agent 4 and house $h_4$ , which it takes. Final allocation: $(h_3, h_1, h_2, h_4)$ .

Compare with deferred acceptance: in school choice, TTC is efficient but can violate priorities, whereas DA respects priorities (is stable) but is not always efficient. The two mechanisms optimize different things.

Work it out

Find and execute the cycle

Each agent points to the owner of its top remaining house. Agent 1’s favourite is $h_3$ , owned by agent 3, so $1 \to 3$ . Agent 2’s favourite is $h_1$ (agent 1), so $2 \to 1$ . Agent 3’s favourite is $h_2$ (agent 2), so $3 \to 2$ . Agent 4’s favourite is $h_3$ (agent 3), so $4 \to 3$ .

Follow the arrows: $1 \to 3 \to 2 \to 1$ closes into a cycle; agent 4 points into it but is not part of it. Execute the cycle by giving each member the house it points to: agent 1 takes $h_3$ , agent 3 takes $h_2$ , agent 2 takes $h_1$ . Remove them and their houses. Only agent 4 and $h_4$ remain, so agent 4 keeps $h_4$ . No agent could have done better by misreporting, and no coalition can re-trade to improve, so the outcome is both strategy-proof and in the core.

Key idea

Top trading cycles reassigns owned goods by rotating them around cycles of mutual demand. The result is efficient, the unique core allocation, and strategy-proof, though scarcity means not everyone gets their first choice.

Check yourself

Check yourselfapply

Agent 4 points at agent 3, but agent 3 is in the cycle 1-3-2. What happens to agent 4 in round 1?

Check yourselfanalyse

Why is top trading cycles strategy-proof?

Check yourselfbrings back: the core

How does the TTC outcome relate to the core of the housing market?

Sources

Shapley, L., and Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.
Roth, A. E., Sönmez, T., and Ünver, M. U. (2004). Kidney exchange. Quarterly Journal of Economics, 119(2), 457-488.