t3. 470 QUARTERLY JOURNAL OF ECONOMICS d. (e.) Prioritize patient-donor pairs in a single list. Choose the w-chain starting with the highest priority pair, and remove it (keep it). A w-chain that is formed at an interim step of the procedure may grow at subsequent steps unless it is removed; hence the immediate removal of w-chains has a potential efficiency cost. Therefore, the following “hybrid” of chain selection rules d and e may appeal to those who wish to moderate the efficiency loss while increasing the inflow of type O living kidneys to the cadaveric waiting list. f. Prioritize the patient-donor pairs so that pairs with type O donor have higher priorities than those who do not. Choose the w-chain starting with the highest priority pair; remove it in case the pair has a type O donor, but keep it otherwise. III.C. Efficiency and Incentives In what follows, we will speak of Pareto efficiency in terms of the agents in the kidney exchange problem, namely the paired FIGURE II Example 1, Round 2 Upon removing cycle C1, a new cycle C2 (k7,t7,k6,t6,k5,t5) forms. Remove it by assigning k7 to t5, k6 to t7, and k5 to t6. KIDNEY EXCHANGE 471 patients and donors who are available to participate in the kidney exchange. Given a kidney exchange problem, a matching is Pareto efficient if there is no other matching that is weakly preferred by all patients and donors and strictly preferred by at least one patient-donor pair. A kidney exchange mechanism is efficient if it always selects a Pareto efficient matching among the participants present at any given time. THEOREM 1. Consider a chain selection rule such that any w-chain selected at a nonterminal round remains in the procedure, and thus the kidney at its tail remains available for the next round. The TTCC mechanism, implemented with any such chain selection rule, is efficient. Chain selection rules that remove a selected w-chain before terFIGURE III Example 1, Round 3 No new cycle forms, and hence each kidney-patient pair starts a w-chain. The longest w-chains are W1 (k8,t8,k4,t4,k9,t9) and W2 (k10,t10,k1,t1,k9,t9). Since t1, the highest priority patient, is in W2 but not in W1, choose and fix W2. Assign w to t9, k9 to t1, and k1 to t10 but do not remove them. Kidney k10, the kidney at the tail of W2, remains available for the next round. 472 QUARTERLY JOURNAL OF ECONOMICS mination of the algorithm, on the contrary, may yield Paretoinefficient outcomes. Roth [1982] showed for the housing model that truthful preference revelation is a dominant strategy of the preference revelation game induced by the TTC mechanism, and hence an agent can never profit by misrepresenting his preferences. Recall that, in the absence of indirect exchanges, the static kidney exchange problem is a housing market, and therefore the Roth [1982] result immediately applies.6 When indirect exchanges are allowed, 6. That is, at any specific time, a patient cannot receive a more preferred kidney by misrepresenting his preferences, which include his option value for the possibility that his donor’s kidney can be used in a future exchange. We emphasize that of course we speak of strategy-proofness in the limited strategy space, the space of stated preferences, we have modeled for the kidney exchange problem. There may remain strategic issues associated with other aspects of the organ transplant process, such as being registered at multiple transplant centers and hence appearing on multiple regional waiting lists. FIGURE IV Example 1, Round 4 Upon fixing the w-chain W2, a new cycle C3 (k4,t4,k8,t8) forms. Remove it by assigning k4 to t8 and k8 to t4. KIDNEY EXCHANGE 473 whether the TTCC mechanism is strategy-proof depends on the choice of the chain selection rule. THEOREM 2. Consider the chain selection rules a, d, e, and f. The TTCC mechanism, implemented with any of these chain selection rules, is strategy-proof. Among these four chain selection rules, the last two are especially appealing: Rule e yields an efficient and strategy-proof mechanism, whereas Rule f gives up efficiency in order to increase the inflow of type O kidneys to the cadaveric waiting list. On the negative side, strategy-proofness of TTCC is lost if one adopts a chain selection rule that chooses among the longest w-chains. EXAMPLE 2. Consider the problem in Example 1, but suppose that patient t4 misrepresents his preferences as P 4 FIGURE V Example 1, Round 5 No new cycles form, and the pair (k12,t12) “joins” W2 from its tail to form the longest w-chain W3 (k12,t12,k10,t10,k1,t1,k9,t9). Fix W3, and assign k10 to t12. Since no patient is left, w-chain W3 is removed, and kidney k12 at its tail is offered to the highest priority patient at the cadaveric waiting list. 474 QUARTERLY JOURNAL OF ECONOMICS k5,k1,k9,... improving the ranking of kidney k1. While Round 1 and Round 2 remain as in Example 1, Round 3 changes, and this time the longest w-chain at Round 3 is W4 (k8,t8,k4,t4,k1,t1,k9,t9). Therefore, patient t4 is assigned kidney k1 instead of kidney k8, making his preference misrepresentation profitable. IV. SIMULATIONS The theoretical treatment of the TTCC mechanism makes clear that larger exchanges may yield welfare gains, but it gives no idea of their magnitude. The following simulations are meant as a first step in that direction, and as a “proof of concept” to demonstrate that the gains are potentially substantial. We