preferences over all rooms, and an ordering of agents is randomly chosen. For any given preference list and ordering, the outcome is obtained as follows. (1) Assign the first student his top choice, the second student his top choice among the remaining rooms, and so on, until someone requests the room of an existing tenant who is yet to be served. (2) Whenever that happens, modify the remainder of the ordering by moving the existing tenant to the beginning of the line, and proceed with the procedure. (3) If at any point a cycle forms, it is formed exclusively by existing tenants, and each of them requests the room of the tenant who is next in the cycle. In such cases remove all students in the cycle by assigning them the rooms they request, and proceed with the procedure. The key innovation here is that an existing tenant whose current room is requested is upgraded to the first place in the line of agents remaining unassigned, before his room is allocated. As a result, the YRMH-IGYT mechanism assures every existing tenant a room that is no worse than his own. Therefore, existing tenants do not have any reason not to enter the market, and consequently the eventual allocation is Pareto efficient. Note that the idea of upgrading an existing tenant whose current room is requested to the top of the line was also invented by the transplantation community in the form of an indirect exchange program: when a potential donor donates his kidney to the highest priority patient on the waiting list, his intended recipient is upgraded to the top of the waiting list. Note again that what prompted the introduction of simple KIDNEY EXCHANGE 463 kidney exchange programs was the loss of volunteer kidney donors because of immunologic incompatibilities. Under these exchange programs, a potential donor who is incompatible with his intended recipient is given the incentive to go ahead with the donation, because his donation makes it possible for his intended recipient to receive a compatible kidney. Similarly, the potential efficiency loss in the campus housing problem is that some rooms might fail to be traded, even when welfare-enhancing trades are possible. The YRMH-IGYT is an attempt to address that problem in the housing context. We next consider how it must be adapted to kidney exchange. III. KIDNEY EXCHANGE AND THE TOP TRADING CYCLES AND CHAINS (TTCC) MECHANISM While there are clear similarities between house allocation and kidney exchange, there are also important differences. The counterpart of an existing tenant and his room is a donor-recipient pair, which we denote by (ki,ti). We will often refer to donor ki as kidney ki, and recipient ti as patient ti. In the context of house allocation with existing tenants, there are also newcomers, none of whom owns a specific house, and vacant houses, none of which is owned by a specific student. The counterpart of newcomers are patients who have no living donors, and the counterpart of vacant houses are cadaveric kidneys that are not targeted for specific patients. This analogy reveals one important difference between the two models: in the house allocation model, the set of vacant houses is known. In the kidney exchange problem, it is not clear which cadaveric kidneys will be available, when they will be available, etc. Therefore, while occupied houses and vacant houses are simultaneously allocated under the YRMH-IGYT mechanism, this is not possible in the context of kidney exchange. Instead, patients with live donors who are not themselves allocated a live donor kidney will be assigned to the cadaver queue (with a priority reflecting whether their donor’s kidney was donated to someone on the queue). Let K denote the set of living donor kidneys at a particular time. While patients and their doctors may define their preferences over kidneys as they wish, here we consider, for specificity, the preferences that come from maximizing the probability of a successful transplant. Given any patient, part of K is outside the feasible set due to ABO blood-type incompatibility or a positive 464 QUARTERLY JOURNAL OF ECONOMICS crossmatch. Among feasible kidneys, HLA match [Opelz 1997], donor age, kidney size, etc. play a significant role in the graft survival. Therefore patients have heterogeneous preferences over compatible kidneys. In what follows, we will consider all preferences to be strict. If only direct exchanges among donor-recipient pairs are considered, one can directly use Gale’s Top Trading Cycles mechanism. However, this will not allow for indirect exchanges. We will need to modify the model and the mechanism to allow for this possibility. Since the supply of specific cadaveric donor kidneys is not predictable, a patient who wishes to trade his donor’s kidney in return for a priority in the cadaveric kidney waiting list is receiving a lottery. Taking this into consideration, the patient, doctor, and donor can decide whether this option is acceptable and, if so, where it ranks in the patient’s preferences. Given a patient ti, let Ki K denote the set of living donor kidneys that are compatible with patient ti. Let w denote the option of entering the waiting list with priority reflecting the donation of his donor’s kidney ki, and Pi denote his strict preferences over Ki {ki,w}. For our purposes the relevant part of Pi is the ranking up to kidney ki or w, whichever ranks higher. If patient ti ranks kidney ki at the top of his