in the reduced graph obtained by the rule, each directed path ending at an unsatisfied agent i (an agent who does not hold a top house) is persistent - the path remains in the graph until agent i leaves the market or trades his house. Independence of unsatisfied agents: if agent i is unsatisfied, and two TTC graphs only differ in the edges outgoing from i, then the reduced TTC graphs only differ in the edge outgoing from i. If the selection rule satisfies Uniqueness and Termination, the resulting mechanism yields an allocation that is Pareto-efficient and in the weak core (no subset of agents can get a strictly better house for all of them by trading among themselves). Weak core also implies that it is individually-rational. If, in addition, the selection rule satisfies Persistence, Independence of unsatisfied agents, and some other technical conditions, the resulting mechanism is strategyproof. A particular selection rule that satisfies these conditions is the Highest Priority Object (HPO) rule. It assumes a pre-determined priority-ordering on the houses. It works as follows. (a) Every unsatisfied agent points to the owner of the highest-priority house among his top houses. All unsatisfied agents are labeled. (b) From the unlabeled agents, consider the ones that have a top house owned by a labeled agent. Among them, pick the agent i who owns the highest-priority house. Make i point to a highest-priority house owned by a labeled agent. Label agent i. (c) If there are unlabeled agents, go back to (b). When the rule terminates, each all agents are labeled, and every labeled agent has a unique outgoing edge. The rule guarantees that, at each iteration, all cycles contain at least one unsatisfied agent. Therefore, in each iteration, at least one new agent becomes satisfied. Therefore, the algorithm ends after at most n iterations. The run-time of each iteration is , where is the maximum size of an indifference class. Therefore, the total run-time is . Other extensions The TTC algorithm has been extended in various ways. 1. A setting in which, in addition to students already living in houses, there are also new students without a house, and vacant houses without a student. 2. The school choice setting. The New Orleans Recovery School District adopted school choice version of TTC in 2012. 3. The kidney exchange setting: Top Trading Cycles and Chains (TTCC). Implementation in software packages R: The