Top trading cycle
Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.
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 (i.e., no group of students can together improve their situation by exchanging their houses).
The algorithm works as follows.
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 (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 second iteration, agent 1's top house is 2 (since house 3 is unavailable). Similarly, agent 2's top house is 5 and agent 5's top house is 1. Hence, {1,2,5} 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 {4,6} is, so agents 4 and 6 exchange their houses. There are no more agents left, so the game is over. The final allocation is:
This allocation is core-stable, since no coalition can improve its situation by mutual exchange.
...
Wikipedia