Top trading cycle is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.
Housing market
The basic TTC algorithm is illustrated by the following housing market situation. There are students living in the student dormitories. Each student lives in a single house. Each student has a preference relation on the houses, and some students prefer the houses assigned to other students. This may lead to mutually-beneficial exchanges. For example, if student 1 prefers the house allocated to student 2 and vice versa, both of them will benefit by exchanging their houses. 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. The algorithm works as follows.
Ask each agent to indicate his "top" house.
Draw an arrow from each agent to the agent, denoted, who holds the top house of.
Note that there must be at least one cycle in the graph. Implement the trade indicated by this cycle, and remove all the involved agents from the graph.
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, suppose the agents' preference ordering is as follows :
Agent:
1
2
3
4
5
6
1st choice:
3
3
3
2
1
2
2nd choice:
2
5
1
5
3
4
3rd choice:
4
6
...
6
2
5
4th choice:
1
...
...
4
...
6
...
...
...
...
...
...
...
In the first iteration, the only top-trading-cycle is , so agent 3 keeps his current house and leaves the market. In the second iteration, agent 1's top house is 2. Similarly, agent 2's top house is 5 and agent 5's top house is 1. Hence, is a top-trading-cycle. It is implemented: agent 1 gets house 2, agent 2 gets house 5 and agent 5 gets house 1. These three agents leave the market. In the third iteration, the top-trading-cycle is, so agents 4 and 6 exchange their houses. There are no more agents left, so the game is over. The final allocation is:
Agent:
1
2
3
4
5
6
House:
2
5
3
6
1
4
This allocation is core-stable, since no coalition can improve its situation by mutual exchange. The same algorithm can be used in other situations, for example: suppose there are 7 doctors that are assigned to night-shifts; each doctor is assigned to a night-shift in one day of the week. Some doctors prefer the shifts given to other doctors. The TTC algorithm can be used here to attain a maximal mutually-beneficial exchange.
The TTC algorithm is the only mechanism that satisfies Individual rationality, Pareto efficiency and Strategy-proofness for the classic Shapley-Scarf model. This makes the TTC a natural choice for other related situations. Here are some important extensions of the TTC. 1. The TTC algorithm has been extended to a situation in which, in addition to students already living in houses, there are also new students without a house, and vacant houses without a student. 2. The TTC algorithm has been extended to the school choice setting. The New OrleansRecovery School District adopted school choice version of TTC in 2012. 3. The TTC algorithm has been extended to the kidney exchange setting. The extended algorithm is called Top Trading Cycles and Chains.
