Introduction

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.

Trade the 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">Five agents (A–E) each own one item and have ranked all items by
    preference. Press <b>Point</b>: every remaining agent points at the owner of its most
    preferred <i>available</i> item. Follow the arrows to find a <b>cycle</b> — everyone in
    it gets what they point at and leaves. Repeat until all are matched.</p>
<div id="agents" class="agents"></div>
<div class="status" id="status">Press Point to begin a round.</div>
<div class="btns">
  <button id="step" type="button">Point &amp; trade one round</button>
  <button id="auto" type="button">Run all</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Top Trading Cycles (Shapley & Scarf, 1974; Gale's rule).
// Each agent owns one item and ranks ALL items. In every round each remaining
// agent points at the OWNER of its most-preferred item that is still available.
// The "points-to" graph has out-degree 1 on a finite set, so a cycle must exist.
// Everyone in a cycle receives the item they point at and is removed. After at
// most n rounds all are matched; the result is the unique core allocation and is
// strategy-proof (Roth, 1982). Runs in polynomial time.
const AGENTS = ['A','B','C','D','E'];
// owner of each item == the agent of the same name (item X is owned by agent X).
// Preference lists (most preferred first) over items:
const PREF = {
  A: ['B','C','A','D','E'],
  B: ['A','D','B','C','E'],
  C: ['D','C','E','A','B'],
  D: ['C','A','D','B','E'],
  E: ['B','A','C','D','E'],
};
let assigned, round;
function reset(){ assigned = {}; round = 0; render(); setStatus('Press Point to begin a round.',''); document.getElementById('step').disabled=false; document.getElementById('auto').disabled=false; }

function remaining(){ return AGENTS.filter(a => !(a in assigned)); }
// top available item for agent a => its current "pointer" target (the owner of that item)
function pointer(a){
  const avail = new Set(remaining()); // available items are owned by remaining agents
  for(const item of PREF[a]) if(avail.has(item)) return item; // item owned by 'item'
  return null;
}
// find one cycle in the functional graph over remaining agents
function findCycle(){
  const rem = remaining(); if(!rem.length) return null;
  const next = {}; rem.forEach(a => next[a] = pointer(a));
  let slow = rem[0], fast = rem[0];
  do { slow = next[slow]; fast = next[next[fast]]; } while(slow !== fast);
  // collect the cycle starting at the meeting point
  const cyc = []; let x = slow;
  do { cyc.push(x); x = next[x]; } while(x !== slow);
  return cyc;
}
function doRound(){
  if(!remaining().length) return false;
  round++;
  const cyc = findCycle();
  const next = {}; remaining().forEach(a => next[a] = pointer(a));
  cyc.forEach(a => { assigned[a] = next[a]; }); // a receives the item it points at
  render(cyc);
  const got = cyc.map(a => a+'→'+assigned[a]).join(', ');
  if(!remaining().length) setStatus(fmt('Round %round%: cycle [%cyc%]. All matched! Core allocation reached.', { round: round, cyc: cyc.join('→') }),'ok');
  else setStatus(fmt('Round %round%: traded cycle [%cyc%] — %got%.', { round: round, cyc: cyc.join('→'), got: got }),'');
  return remaining().length>0;
}
function render(cyc){
  const box = document.getElementById('agents'); box.innerHTML='';
  const cycSet = new Set(cyc||[]);
  AGENTS.forEach(a => {
    const d = document.createElement('div');
    const done = a in assigned;
    d.className = 'agent' + (done?' done':'') + (cycSet.has(a)?' incycle':'');
    let pts = '';
    if(done) pts = fmt('<div class="got">got %v%</div>', { v: assigned[a] });
    else { const p = pointer(a); pts = fmt('<div class="pts">points → %v%</div>', { v: p||'—' }); }
    d.innerHTML = fmt('<div class="who">%a%</div><div class="owns">owns %a%</div>%pts%', { a: a, pts: pts });
    box.appendChild(d);
  });
  const fin = remaining().length===0;
  document.getElementById('step').disabled = fin;
  document.getElementById('auto').disabled = fin;
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
document.getElementById('step').addEventListener('click', ()=>doRound());
document.getElementById('auto').addEventListener('click', ()=>{ while(doRound()){} });
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

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.

The Real Complexity

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(n2)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/top-trading-cycles/Content licensed under CC BY-NC 4.0.