Top trading cycle

Top trading cycle, often shortened to 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. In the basic housing market form, each student already lives in one house and ranks all the houses. Every agent points to the owner of the house they like best, which must create at least one cycle; the trades indicated by a cycle are carried out, the agents involved leave the market, and the step repeats until nobody is left. The result is a core-stable allocation, and with strict preferences it is unique and Pareto efficient. TTC is a truthful mechanism, a property proved by Alvin Roth, and with strict preferences it is the only mechanism that is individually rational, Pareto efficient and strategy-proof. Extensions handle ties in preferences, school choice, where New Orleans adopted a version in 2012, and kidney exchange.