Top trading cycle
The Top Trading Cycle (TTC) is an algorithm for trading indivisible goods without the use of money. It was developed by David Gale and introduced by Herbert Scarf and Lloyd Shapley .
Housing market
The basic TTC algorithm can be illustrated with the following situation in the housing market: n Students live in dormitories. Each student lives in one apartment. Every student has a preference relation for the apartments. Now it can happen that some students find another student's apartment better than their own, which can make an exchange for mutual benefit possible. For example, if Student 1 prefers Student 2's apartment, and vice versa, then both will benefit from swapping apartments. The goal is to find an assignment in which there is no further exchange that puts everyone involved in a better position. Such an association is said to be at the core because no group of students can collectively improve their situation by exchanging apartments again.
The algorithm works as follows:
- Each participant points to the participant who lives in their favorite apartment.
- Now there has to be at least one circle. It can be the case that this circle has the length 1, i.e. a participant points to himself because he already lives in his favorite apartment.
- Implement the exchange associated with the circle, so give all participants in the circle the apartment they are pointing to and remove these participants from the diagram.
- If there are still participants left, go back to step 1, with each participant now pointing to the remaining participant who lives in their remaining favorite apartment.
The algorithm has to end because in each repetition a circle consisting of at least one participant is removed. It can be shown that this algorithm leads to an allocation that is in the core.
Example: The participants have the following preferences about the available apartments, whereby only a maximum of the top four preferences of a participant regarding the apartments are relevant.
| Attendees | 1 | 2 | 3 | 4th | 5 | 6th |
|---|---|---|---|---|---|---|
| Initial wish | 3 | 3 | 3 | 2 | 1 | 2 |
| Second wish | 2 | 5 | 1 | 5 | 3 | 4th |
| Third request | 4th | 6th | 6th | 2 | 5 | |
| Fourth wish | 1 | 4th | 6th |
In the first round there is only one circle. In this case, participant 3 points to itself and there is the TTC {3}.
After participant 3 has left the market, round 2. Now participant 1 points to participant 2, participant 2 to participant 5 and participant 5 to participant 1, so that again a circle results, the TTC {1,2,5}. These three participants swap their apartments accordingly and leave the market.
In the third round, participant 4 points to participant 6 and vice versa, resulting in the TTC {4,6}. Because there are no participants left, it's game over. The final allocation is as follows:
| Attendees | 1 | 2 | 3 | 4th | 5 | 6th |
|---|---|---|---|---|---|---|
| flat | 2 | 5 | 3 | 6th | 1 | 4th |
This allocation is at the core, as no group of participants can improve their situation through mutual exchange.
The same algorithm can be used in other situations. For example, suppose there are seven doctors, each assigned to one night shift per week. Some doctors prefer the shifts given to other doctors. The TTC algorithm can be used here to achieve the most advantageous exchange for everyone.
Further developments
The TTC algorithm is the only mechanism that meets the requirements of individual rationality, Pareto efficiency and strategy security in the classic Shapley-Scarf model. This makes it the logical choice for similar situations. Here are some important enhancements to the TTC:
- The TTC algorithm was further developed for a situation in which, in addition to the students already living in the apartments, there are also new students without houses and empty apartments without students.
- The TTC algorithm was further developed for school selection. A school district in New Orleans (Recovery School District) adopted a school electoral version of the TTC in 2012.
- The TTC algorithm was further developed as part of the kidney swap. The advanced algorithm is called Top Trading Cycles and Chains (TTCC).
Implementation in software packages
-
R : The TTC algorithm for the housing market problem is
matchingMarketsimplemented in the package . - API : The MatchingTools API makes the TTC algorithm available via a free programming interface.
Individual evidence
- ^ Lloyd Shapley, Herbert Scarf: On cores and indivisibility . In: Journal of Mathematical Economics . 1, 1974, p. 23. doi : 10.1016 / 0304-4068 (74) 90033-0 .
- ^ Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231 .
- ^ Atila Abdulkadiroğlu, Tayfun Sönmez: House Allocation with Existing Tenants . In: Journal of Economic Theory . 88, No. 2, 1999, pp. 233-260. doi : 10.1006 / jeth.1999.2553 . See also presentation by Katharina Schaar .
- ^ Atila Abdulkadiroğlu, Tayfun Sönmez: School Choice: A Mechanism Design Approach . In: American Economic Review . 93, No. 3, 2003, pp. 729-747. doi : 10.1257 / 000282803322157061 .
- ↑ Andres Vanacore: Centralized enrollment in Recovery School District gets first tryout . In: The Times-Picayune , April 16, 2012.
- ↑ Alvin Roth, Tayfun Sönmez, M. Utku Unver: Kidney Exchange . In: Quarterly Journal of Economics . 119, No. 2, 2004, pp. 457-488. doi : 10.1162 / 0033553041382157 .
- ^ Thilo Klein: Analysis of Stable Matchings in R: Package matchingMarkets . In: Vignette to R Package matchingMarkets . 2015.
- ^ MatchingMarkets: Analysis of Stable Matchings . In: R Project .
- ↑ MatchingTools API .