Top Trading Cycles

Imagine a hallway of neighbors. Each one owns a house, but each secretly prefers one of the other houses. Could they shuffle around so everyone ends up better off — and so that no group of them could splinter off and trade among themselves to do even better?

That last condition is the hard part. It is easy to make a few people happy; it is much harder to reach an allocation that is stable against every possible coalition at once. An allocation with that property is said to be in the core, and on top of that we would like it to be Pareto-efficient (nobody can improve without someone else getting worse).

In 1974, Lloyd Shapley and Herbert Scarf introduced an astonishingly simple rule — credited to David Gale — that always finds such an allocation, and finds it fast: Top Trading Cycles.

Five agents each own one item but have ranked everyone's items by preference. Press Point and each remaining agent points at the owner of its most-preferred available item. Follow the arrows and you always find at least one cycle. Everyone in a cycle gets the item they point at, then leaves.

<p class="hint">{{hint}}</p>
<div id="agents" class="agents"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.agents { display: grid; grid-template-columns: repeat(5, 1fr); gap: 8px; margin: .4rem 0; }
.agent { border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem; background: #f3f7fa; text-align: center; }
.agent .who { font: 700 16px ui-monospace, monospace; color: #1d3557; }
.agent .owns { font-size: .78rem; color: #555; margin: .15rem 0; }
.agent .pts { font-size: .8rem; color: #1d3557; min-height: 1.2em; font-weight: 600; }
.agent.done { background: #e3f5e9; border-color: #9bd9b3; }
.agent.done .got { font: 700 15px ui-monospace, monospace; color: #0a7d33; }
.agent.incycle { background: #fff3d6; border-color: #e6c24d; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Repeat until everyone is matched. Notice the guarantee: once an agent gets its first choice and leaves, nothing later can take it away — so no coalition can ever profitably regroup. Checking that an allocation is core-stable could mean inspecting every subset of agents, yet TTC builds a core allocation directly, in a handful of rounds. Compare this with the cooperative tug-of-war in Nash equilibrium.

How hard is it to reach a core-stable, efficient allocation? Remarkably, not hard at all — this is one of the happy corners of computation, fully solved.

• Each round every remaining agent points at one owner. In a functional graph where every node has out-degree one, a cycle must exist — just follow the arrows until you repeat a node.
• Cycles are disjoint and at least one is found per round, so after at most n rounds everyone is assigned. The whole thing runs in polynomial time, roughly $O(n^{2})$ with a naive implementation.
• The outcome is unique. With strict preferences the core of this housing market contains exactly one allocation, and TTC outputs it.
• It is strategy-proof. Alvin Roth (1982) proved no agent can ever gain by lying about its preferences — and TTC is essentially the only rule that is simultaneously Pareto-efficient, individually rational and strategy-proof.

So unlike the intractable members of the P vs NP family, "find the fair, unbeatable swap" is provably easy. The difficulty was never computational — it was discovering that one cycle-chasing rule does everything at once.

"Reassign indivisible things so the result is fair and nobody wants to undo it" is everywhere, and TTC is the workhorse:

• Kidney exchange: incompatible donor–patient pairs are matched along trading cycles (and chains) so each patient receives a compatible organ — a direct descendant of TTC that has enabled thousands of transplants.
• School choice: TTC is one of the two mechanisms cities studied for assigning students to schools while respecting priorities and preferences.
• House and dorm allocation: reassigning offices, dormitory rooms or on-campus housing where occupants already hold a unit.
• Course and shift allocation: swapping seats in oversubscribed courses or shifts among employees.

Understand TTC and you understand matching markets — the same theory behind stable matching and the assignment problems explored across KipuHub.

Top Trading Cycles is a small miracle: let everyone point at what they want most, find the loops, swap around them, repeat. The result is Pareto-efficient, sits in the core so no coalition can do better, is the unique such allocation, and cannot be gamed — all delivered in polynomial time.

It is a reminder that not every important problem is hard. Sometimes the right idea collapses a question that looks like it needs to inspect every coalition into a few rounds of following arrows. When the swaps stop, you are holding an allocation that the whole of game theory agrees is the right one — quite unlike the open frontier of P vs NP.