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.[1]:30–31

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 (i.e., no group of students can together improve their situation by exchanging their houses).

The algorithm works as follows.

  1. Ask each agent to indicate his "top" (most preferred) house.
  2. Draw an arrow from each agent to the agent, denoted , who holds the top house of .
  3. Note that there must be at least one cycle in the graph (this might be a cycle of length 1, if some agent currently holds his own top house). Implement the trade indicated by this cycle (i.e., reallocate each house to the agent pointing to it), and remove all the involved agents from the graph.
  4. If there are remaining agents, go back to step 1.

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):

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 {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:

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:[2] 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.

Extensions

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.[3]

2. The TTC algorithm has been extended to the school choice setting.[4] The New Orleans Recovery School District adopted school choice version of TTC in 2012.[5]

3. The TTC algorithm has been extended to the kidney exchange setting. The extended algorithm is called Top Trading Cycles and Chains (TTCC).[6]

Implementation in software package

References

  1. ↑ Shapley, Lloyd; Scarf, Herbert (1974). "On cores and indivisibility". Journal of Mathematical Economics. 1: 23. doi:10.1016/0304-4068(74)90033-0.
  2. 1 2 Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
  3. ↑ Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999). "House Allocation with Existing Tenants". Journal of Economic Theory. 88 (2): 233–260. doi:10.1006/jeth.1999.2553.. See also Presentation by Katharina Schaar.
  4. ↑ Abdulkadiroğlu, Atila; Sönmez, Tayfun (2003). "School Choice: A Mechanism Design Approach". American Economic Review. 93 (3): 729–747. doi:10.1257/000282803322157061.
  5. ↑ Vanacore, Andres (April 16, 2012). "Centralized enrollment in Recovery School District gets first tryout". The Times-Picayune. New Orleans. Retrieved April 4, 2016.
  6. ↑ Roth, Alvin; Sönmez, Tayfun; Unver, M. Utku (2004). "Kidney Exchange". Quarterly Journal of Economics. 119 (2): 457–488. doi:10.1162/0033553041382157.
  7. ↑ Klein, T. (2015). "Analysis of Stable Matchings in R: Package matchingMarkets" (PDF). Vignette to R Package matchingMarkets.
  8. ↑ "matchingMarkets: Analysis of Stable Matchings". R Project.
This article is issued from Wikipedia - version of the 8/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.