The final allocation is: 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: 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. Properties TTC is a truthful mechanism. This was proved by Alvin Roth. When the preferences are strict (there are no indifferences), TTC always finds a Pareto-efficient allocation. Moreover, it always finds a core-stable allocation. Moreover, with strict preferences, there is a unique core-stable allocation, and it is the one found by TTC. In the strict preferences domain, TTC is the only mechanism that satisfies Individual rationality, Pareto efficiency and Strategy-proofness. Preferences with indifferences The original TTC algorithm assumed that the preferences are strict, so that each agent always has a single top house. In realistic settings, agents may be indifferent between houses, and an agent may have two or more top houses. Several different algorithms have been suggested for this setting. They were later generalized in several ways. The general scheme is as follows. Ask each agent to indicate all his top houses. Construct the TTC-graph G: a directed graph in which each agent points to all agents who hold his top houses. Repeat: Analyze the strongly connected components of G. Identify the sinks - the components with no outgoing edges (there is at least one). Identify the terminal sinks - the sinks in which each agent owns one of his top choices. If there are no terminal sinks - break and go to step 4. Otherwise, for each terminal sink S: permanently assign each agent in S to his current house, remove them from the market, update the TTC graph, and go back to step 3. Select a set of disjoint trading cycles, using a pre-determined selection rule. Implement the trade indicated by these cycles, and remove them from the market. If there are remaining agents, go back to step 1. The mechanisms differ in the selection rule used in Step 4. The selection rule should satisfy several conditions: Uniqueness: the rule selects, for each agent, a unique house from among his top houses. Termination: the algorithm using the rule is guaranteed to terminate. Persistence: