Suppose you and your friends are unhappy with your dormitory houses. Each one of you lives in a single house (endowments) but you may prefer the houses assigned to other students. How do you find a mutually-beneficial exchange of houses such that 1) the final allocation is the best for everyone and 2) every student is guaranteed nothing worse than his current house, and 3) no sub-groups of students can together exchange their houses and receive better houses?
*s1 = student 1, h1 = house 1
1. Each participant indicates his/her top choice.
2. Draw an arrow from each participant i to the participant who owns his/her top choice
3. There must be at least one cycle. It can be a single cycle which means that the participant points to himself/herself.
4. Allocate houses to the participants when they are in cycle, and remove them from the graph.
5. Iterate their preferences and go back to step 1.
Suppose you and your friends are unhappy with your dormitory rooms. Each one of you lives in a single room (endowments) but you may prefer the rooms assigned to other students. How do you find a mutually-beneficial exchange of rooms such that 1) the final allocation is the best for everyone and 2) every student is guaranteed nothing worse than his current room, and 3) no sub-groups of students can together exchange their rooms and receive better rooms?
Our solution guarantees the following properties:
Top trading cycle (TTC) is an algorithm for trading indivisible items without using money, e.g. allocating goods by exchanging, which was developed by David Gale and published by Herbert Scarf and Lloyd Shapley. Every room is initially owned by a student who lives in it. Each agent points at another agent who currently lives in his most preferred room. TTC guarantees that at least one cycle forms involving a subset of students. Students exchange their rooms across the cycle and leave. The remaining students repeat the above process, until no agent remains.
The algorithm guarantees that (Pareto) optimality, meaning that no reallocation of rooms exists that makes some agents better off without making at least one agent worse off. TTC also guarantees that no agent receives a worse outcome by participating in the mutually-beneficial exchanges.
On cores and indivisibility
By: Lloyd Shapley and Herbert Scarf
Incentive compatibility in a market with indivisible goods
By: Alvin E Roth
Strategy-proofness and the strict core in a market with
indivisibilities
By: Jinpeng Ma