It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.
[1]: 30–31 The basic TTC algorithm is illustrated by the following house allocation problem.
The goal is to find a core-stable allocation – a re-allocation of houses to students, such that all mutually-beneficial exchanges have been realized (i.e., no group of students can together improve their situation by exchanging their houses).
The algorithm must terminate, since in each iteration we remove at least one agent.
It can be proved that this algorithm leads to a core-stable allocation.
For example,[2]: 223–224 suppose the agents' preference ordering is as follows (where only the at most 4 top choices are relevant): In the first iteration, the only top-trading-cycle is {3} (it is a cycle of length 1), so agent 3 keeps his current house and leaves the market.
In the third iteration, the top-trading-cycle {4,6} is, so agents 4 and 6 exchange their houses.
The TTC algorithm can be used here to attain a maximal mutually-beneficial exchange.
Moreover, with strict preferences, there is a unique core-stable allocation, and it is the one found by TTC.
In the strict preferences domain, TTC is the only mechanism that satisfies Individual rationality, Pareto efficiency and Strategy-proofness.
[4][5] The original TTC algorithm assumed that the preferences are strict, so that each agent always has a single top house.
The selection rule should satisfy several conditions:[9] If the selection rule satisfies Uniqueness and Termination, the resulting mechanism yields an allocation that is Pareto-efficient and in the weak core (no subset of agents can get a strictly better house for all of them by trading among themselves).
If, in addition, the selection rule satisfies Persistence, Independence of unsatisfied agents, and some other technical conditions, the resulting mechanism is strategyproof.
The rule guarantees that, at each iteration, all cycles contain at least one unsatisfied agent.
The kidney exchange setting: Top Trading Cycles and Chains (TTCC).