Kidney exchange and market design

Recent Nobel Prize winner Alvin Roth gives a brief summary of work on "Kidney Exchanges" in the NBER Reporter: Number 4, 2012.

More than 90,000 patients are on the U.S. waiting list for a kidney transplant from a deceased donor, and only 11,000 or so such transplants are accomplished each year. So, the waiting is long and costly, sometime fatally so. But healthy people have two kidneys and can remain healthy with only one, which also makes it possible to receive a kidney from a living donor -- around 6,000 such transplants were accomplished in 2011. Nevertheless, someone who is healthy enough to donate a kidney may be unable to donate to his or her intended recipient because of various types of donor-recipient incompatibility. This is the origin of kidney exchange. In the simplest case, two incompatible patient-donor pairs exchange kidneys, with each patient receiving a compatible kidney from the other’s donor. The first kidney exchange in the United States was performed at the Rhode Island Hospital in 2000, when doctors there noticed two incompatible patient-donor pairs who could benefit from exchange. Shortly after that, Tayfun Sonmez, Utku Unver, and I proposed a way to organize a multi-hospital kidney exchange clearinghouse(1), and began discussions with Dr. Frank Delmonico of Harvard Medical School, that soon led to the founding of the New England Program for Kidney Exchange.(2)Together with Itai Ashlagi, we have since assisted in the formation and operation of other kidney exchange networks operating around the country.

In the United States and most of the world it is illegal to buy or sell organs for transplant.(3) As Jevons (1876)(4) noted, one obstacle to two-way barter exchange is the need to find a counterparty who has what you want and also wants what you have. One way to reduce the difficulty of finding these double coincidences is to assemble a large database of interested patient-donor pairs. Another is to consider a larger variety of exchanges than those between just two pairs: for example, a cycle of exchange among three pairs, or a chain that begins with a donation by a non-directed donor (such as a deceased donor, or an altruistic living donor) to the patient in an incompatible patient donor pair, whose donor "passes it forward" to another such pair or ends the chain with a donation to someone on the waiting list for a deceased donor (that is, the chain ends when a donation is made to a patient who does not have a willing but incompatible live donor).

Our 2003 paper proposed kidney exchange that integrated cyclic exchanges of all sizes and chains beginning with a non-directed donor and ending with a donation to someone without a living donor. We focused on two kinds of incentive issues that seemed likely to be important in a mature system of kidney exchange, both concerned with aligning incentives so as to make it safe and simple to participate. First, we showed how exchanges could be arranged so that they would be in the core of the game, which means that no coalition of patient-donor pairs could go off on their own, or to a competing exchange, and do better than to accept the proposed exchanges. Second, we showed how this could be accomplished in a way that made it a dominant strategy for patients (and their surgeons) to reveal the medical information that determined the desirability of each potential transplant. It is worth noting that the tools we used built on theory that was initially proposed in a very abstract setting: Shapley and Scarf (1974) studied a "top trading cycle" algorithm for trading indivisible goods without money and showed that it produced an allocation in the core(5) , and Roth (1982)(6) showed that the top trading cycle algorithm made it a dominant strategy for traders to reveal their true preferences. Abdulkadiroglu and Sonmez (1999)(7) extended this model to deal with assignment of dormitory rooms when some students already had rooms, some did not, and some rooms might be vacant, so that assignment would involve chains as well as cycles.

We observed that the efficient chains and cycles in kidney exchange mostly would be short but occasionally would be long, which presented a logistical problem, since, for incentive reasons, all surgeries in a given exchange would be performed simultaneously (because contracts can't be written on kidneys). This means that even an exchange between two pairs requires four operating rooms and surgical teams, for the two nephrectomies (kidney removal from the donor) and two transplants. A three-way exchange would require six. When we presented this initial proposal to our surgical colleagues, led by Frank Delmonico, they felt it was a critical problem - the prospect of four simultaneous surgeries was daunting enough. They asked us to present a proposal with the more modest aim of organizing exchanges involving only two-way exchanges.

Our new, more limited proposal(8) and the accompanying software formed the basis for organizing the New England Program for Kidney Exchange,(9) and was widely shared and explained and soon adapted for use elsewhere. Almost simultaneously, we began exploring with our surgical colleagues the possibilities of including larger exchanges and chains.(10, 11, 12) (It speaks volumes about the relative publishing speed of Economics and Medicine to note that the follow-up paper which reported in the American Journal of Transplantation how longer exchanges actually had been carried out was published a year later than the publication of the original 2005 NBER Working Paper analyzing such exchanges.)

Although the three-way chain reported in that AJT paper was performed simultaneously (and hence involved six operating rooms and surgical teams), the paper also proposed that chains that begin with a non-directed donor might not need to be performed simultaneously. The argument was a simple cost-benefit analysis. The reason that cyclic exchanges are performed simultaneously is that if they were not, some patient-donor pair would have to give a kidney before getting one, and if the cycle were to be broken subsequently, that pair would suffer a grievous loss. The donor in the pair would have undergone a nephrectomy that yielded no benefit to the recipient in the pair, and there would no longer be a kidney with which to participate in a future exchange.

Now consider a chain that begins with a non-directed donor, who donates to some incompatible patient-donor pair under the understanding that they will subsequently donate to another, and so on. Every pair in this chain will receive a kidney before they donate one. If the chain is broken, then the pair that was scheduled but fails to receive a kidney will be disappointed, but not grievously harmed. They are not worse off than they were before the non-directed donor came forward, and, in particular, they still have a kidney with which to participate in some future exchange. Hence the cost of a broken link in a chain initiated by a non-directed donor is much less than that of a broken link in an exchange among a cycle of patient-donor pairs.

In 2007, Mike Rees, a pioneer of kidney exchange and the founder of the Alliance for Paired Donation, which is one of the most active networks, began the first such non-simultaneous chain. It was reported on in Rees et al. (2009), at which point it had accomplished ten transplants (and 20 surgeries), many more than could have been done simultaneously. (13) Since then, non-simultaneous non-directed donor chains have become the fastest growing part of kidney exchange, even though the number of non-directed donors is small. In some cases a non-directed donor has initiated a chain of more than 30 transplants.

Ashlagi and I have worked to understand why long chains are so useful, and how to structure them. As kidney exchange has grown and become a standard tool of transplantation, hospitals are more able to do some exchanges among their own patients. This means the players in the kidney exchange game have changed: where it used to be enough to think of the incentives of patients and donors and their surgeons, now the directors of transplant centers are players, and they see many patient-donor pairs. Their strategy sets now include which pairs to show to a centralized exchange. The present organization of kidney exchanges gives them some incentives to withhold their easy-to-match pairs. This could be fixed by taking account of which hospitals enrolled easy-to-match pairs and using this information (in a sort of "frequent flier program") to give some increased probability of matching to patients at those hospitals.(14) But this faces important political obstacles and has so far not been adopted. Partly as a result of the withholding of easy-to-match pairs, the percentage of patients enrolled in kidney exchange networks that are hard to match, even to a blood-type compatible donor, has skyrocketed.

We can organize patient and donor data in a compatibility graph, in which each node represents a patient and her incompatible donor(s), and an edge goes from one node to another whenever the donor in the first node is compatible with the patient in the second node. As patients have become harder to match, the compatibility graphs have become sparser, that is, they contain fewer edges. When we look at the data of the kidney exchange networks with which we work, there is a densely connected sub-graph of the relatively few fairly easy-to-match pairs, and a sparse sub-graph of many hard-to-match pairs (this is joint work with David Gamarnik and Mike Rees). Within the easy-to-match sub-graph, many patients could be transplanted with the aid of two-way or three-way exchanges, but within the sub-graph of hard-to-match pairs, only long chains offer the chance of transplanting many patients.(15) Non-directed donors have a chance of starting those long chains, and the presence of easy-to-match pairs allows more hard-to-match pairs to be included.

Despite the growing success that kidney exchange has had in facilitating transplants from living donors, the list of people waiting for kidney transplants from deceased donors continues to grow. Deceased donor organs are a scarce resource of an unusual kind, because their supply depends on decisions to donate made by potential donors (while still living) and their next of kin (immediately afterwards). Consequently there are market design issues associated with how donations are solicited, and how organs are allocated, both of which may influence the donation decision and hence the supply. Judd Kessler and I have begun to investigate this:(16) we begin with an experimental investigation motivated by a priority allocation scheme just put into place in Israel, in which people who have registered as donors will be given some priority in case they need to receive an organ for transplant, and so will members of their immediate family.

While it is natural that economists should investigate institutions that facilitate exchange, many people (including some economists) find it surprising that economists should be helping to design the institutions of kidney exchange. This is a natural outgrowth, however, of two strands in modern economics: market design in general (17), and the study of matching markets. Matching markets are those in which price does not do all the work of determining who gets what, and they include some of the important passages in our lives, from school choice and college admissions to marriage and labor markets. In none of these can you simply choose what you want - you also have to be chosen. In some of these, economists have begun to help design the matching institutions.

For the references follow the link at the top of the message.