How it works, precisely
Everyone starts with an endowment: their current assignment, desk or slot. The number of people and goods must therefore be equal.
Everyone points at the good they prefer. Following the arrows always produces at least one cycle — possibly a self-loop, when someone already holds their favourite.
The cycles are executed: everyone receives what they pointed at. Those served leave with their good, and the process repeats with the rest until nobody is left.
Three proven properties: the outcome is Pareto-efficient, individually rational (nobody leaves with worse than their endowment), and the mechanism is strategy-proof.
A worked example
Three people, each holding a slot, each wanting another.
| Person | Current slot | Wanted slot | Gets |
|---|---|---|---|
| Chloé | Monday | Tuesday | Tuesday |
| Ali | Tuesday | Monday | Monday |
| Bruno | Wednesday | Wednesday | Wednesday |
- Chloé points at Ali's slot, Ali points at Chloé's: a cycle of length 2.
- The cycle executes: the two swap and leave satisfied.
- Bruno points at his own slot: a self-loop, so he keeps it.
Two trades, no losers. That is the method's central guarantee: you can never come out worse off than you went in.
Where it comes from
Lloyd Shapley and Herbert Scarf published the founding paper on the « housing market » in the Journal of Mathematical Economics in 1974. They credit the top trading cycles algorithm to David Gale and prove that it always produces an allocation in the core of the market.
Atila Abdulkadiroğlu and Tayfun Sönmez extended it in 1999 to mixed situations, where some occupants are already in place and others are arriving — the concrete case of American student housing.
Its most spectacular application is medical: kidney exchange programmes between incompatible donor-recipient pairs, formalised by Roth, Sönmez and Ünver in the early 2000s, rest on this cycle mechanism. Alvin Roth and Lloyd Shapley received the 2012 Nobel Prize in Economics for this body of work.
Where it is used
- Swapping on-call slots, duty shifts or days off.
- Reallocating desks, equipment or parking spaces already occupied.
- Rotating assignments or client portfolios within a team.
- Kidney exchange between incompatible pairs — the application that won a Nobel.
Limits and pitfalls
- Nobody ends up worse than at the start
- Ranking sincerely is always best
- Every win-win trade gets made
- Everyone needs a starting possession
- Exactly as many things as people
- The outcome depends heavily on endowments
Frequently asked questions
Can I end up worse off than I am now?
No, never, and it is proved: individual rationality is a proven property of the algorithm. If no trade suits you, you keep your endowment — that is the self-loop.
Should I misreport my preference order?
No. The mechanism is strategy-proof: lying cannot improve your outcome, and may cost you a cycle that suited you.
What if nobody wants to trade?
Everyone points at their own good, every cycle is a self-loop, and nothing moves. That result is valid: it says the current arrangement is already optimal.