crossmatch, effectively rules out transplantation. When a cadaveric kidney becomes available for transplantation, the priority of each patient on the waiting list is determined by a point system based on factors including the blood type, HLA antigen-match, time spent on the waiting list, the region the kidney is harvested, etc. and the kidney is offered to the patient with the highest priority. If that patient declines, the kidney is offered to the patient with the next highest priority, and so on. Living donor kidney grafts have superior survival rates (and their availability can also avoid the long waiting time for a cadaver kidney). However, potential living donors can be eliminated from consideration due to incompatibility of the potential donor kidney with the intended recipient. To minimize the elimination of physically eligible volunteer kidney donors on the basis of immunologic incompatibilities, Rapaport [1986] proposed the creation of a living donor pool for paired exchange. Ross et al. [1997] again proposed to increase the supply of living kidney donations by using kidneys from living incompatible donors through an exchange arrangement between two pairs. In 2000, UNOS initiated pilot testing of such programs. Another exchange program is the indirect exchange program [Ross and Woodle 2000]: a potential donor who is incompatible with his intended recipient donates his kidney to the cadaveric waiting list, and his paired recipient will receive priority for the next compatible cadaveric kidney. There is widespread agreement in the transplantation community that indirect exchange can harm type O patients who have no living donors. First, they will be losing their priority to type O patients whose incompatible donors donate to the cadaveric pool, and second, very few type O living kidneys will be offered to their pool since a type O donor can KIDNEY EXCHANGE 461 directly donate to his intended recipient unless there is a positive crossmatch. Despite this widespread concern, many transplant centers have also cautiously started pilot indirect exchange programs since 2000. For example, in UNOS Region 1 (New England), consisting of fourteen transplant centers and two Organ Procurement Organizations, four paired exchanges and seventeen indirect exchanges have been conducted from 2001 through 2003 (personal communication). II.B. Mechanism Design We will extend results in the mechanism design literature, which we first quickly review. Shapley and Scarf [1974] modeled a “housing market” consisting of n agents each of whom is endowed with an indivisible good, a “house.” Each agent has preferences over all the houses, and there is no money in the market, trade is feasible only in houses. They attribute to David Gale the “top trading cycle” algorithm that produces a house allocation in the core of the market. The algorithm works as follows: each agent points to her most preferred house (and each house points to its owner). There is at least one cycle in the resulting directed graph. In each such cycle, the corresponding trades are carried out, i.e., each agent in the cycle receives the house she is pointing to, and these agents and houses are removed from the market. The process continues (with each agent pointing to her most preferred house that remains on the market) until no agents remain, and the final allocation is the one in which each agent receives the house with which she left the market. When all preferences are strict, the procedure yields a unique outcome [Roth and Postlewaite 1977], and truthful preference revelation is a dominant strategy [Roth 1982]. Note that paired kidney exchanges similarly seek the gains from trade among patients with willing donors, but (with the recent Johns Hopkins three-pair exchange being a notable exception) mostly among just two pairs. In the kidney exchange to be considered below, if we consider exchange only among patients with donors, the properties of the housing market model essentially carry over unchanged, if we assume that donors’ preferences are aligned with those of their intended recipient. We will also assume that all surgeries in a given cycle are carried out simultaneously, which is the current practice, since a donor’s willingness to donate a kidney might change once her intended recipient received a transplant. 462 QUARTERLY JOURNAL OF ECONOMICS However, the kidney transplant environment consists not just of patients with donors, but also patients without donors, and cadaver kidneys not tied to any specific patient. Abdulkadirogˇlu and So¨nmez [1999] studied housing allocation on college campuses, which is in some respects similar: a set of rooms must be allocated to a set of students by a centralized housing office. Some of the students are existing tenants each of whom already occupies a room, and the rest of the students are newcomers. In addition to occupied rooms, there are vacant rooms. Existing tenants are entitled to keep their current rooms but may also apply for other rooms. Mechanisms used on a number of college campuses do not ensure the participation of existing tenants, and result in efficiency loss. This is the motivation for the generalization of the top trading cycles (TTC) mechanism proposed by Abdulkadirogˇlu and So¨nmez [1999], which they called you request my house—I get your turn (YRMH-IGYT): each student reports his strict