Kidney Exchange: an Application of Matching Theory and Mechanism Design

Printer-friendly version
image
From theory to application
Author/s: 
Jordi Massó
Issue number: 
0 - March 2012
Series: 
From Theory to Application
Year: 
2012
There are two treatments for patients with renal disease: dialysis and transplantation. Because dialysis requires a strong dependence and has many side effects (physical as well as psychological), transplantation is considered the best treatment. Kidneys for transplantation come from either deceased or living donors. The first successful kidney transplantation took place on December 23, 1954 in Boston. It was done between two identical twins (to eliminate the immune reaction) and performed, among others, by J. Murray (who received the Nobel Prize for Medicine in 1990), J.H. Harrison, and J.P. Merrill. The patient survived eight years after the transplantation. At the end of the last century, and after the improvement in immunosuppressive therapies, the majority of transplanted kidneys in many countries were from deceased donors; for instance, in 1999 in Spain less than 1% of all kidney transplants were from living donors (only 17 among 2023). However, there is a unanimous agreement that the quality and success-rate of kidney transplants from living donors are greater than those of deceased ones. In particular, the likelihood that the transplanted kidney survives 5 years is 0.87 if it comes from live donors and 0.80 if it comes from deceased donors, and the likelihood that the recipient will survive 5 years is 0.93 and 0.86, respectively. Furthermore, promoting the donation of kidneys from living donors may help solve the shortage of kidneys for transplantation. Indeed, all countries with active transplantation programs suffer from shortage of kidneys. Almost everywhere the average time that a patient has to stay in the waiting list for a kidney transplant is well above two years. In addition, increasing life expectancy as well as the decrease in mortality due to car and motorcycle accidents has made the shortage even more severe. For all these reasons, in the last ten years, many countries are promoting living donation; for instance, in 2010 in Spain already more than 10% of all kidney transplants were from living donors (240 among 2225).
In the direct donation, the patient receives, if compatible, one of the two kidneys from a relative or friend (usually, the spouse and siblings of the patient). The most basic incompatibilities are blood and tissue type (the later is related to genetics that produce immune reaction), although the age of the kidney is also relevant for the graft kidney survival. But if the kidney is not compatible, the transplant is not possible and the donor's kidney is removed from the system. It is estimated that approximately one third of patients with a friend or family donor are excluded from the system due to different incompatibilities. Until very recently this was the only live donation that was taking place, and there was no system to take advantage of rejected donors, which were simply sent home. In 1986, the doctor F.T. Rapaport was the first to propose kidney exchanges from living donors. The idea is simple. Suppose that one day a nephrologist receives a patient accompanied by a relative who is willing to donate a kidney. Unfortunately, the analysis show that they are incompatible. The next day, the same doctor receives another patient-donor pair who are also incompatible. But each patient is compatible with the donor of the other pair, and hence, a kidney exchange is possible (a cycle of length two). Or even longer cycles involving three or more incompatible patient-donor pairs could be undertaken.

A kidney exchange problem consists of a set of incompatible patient-donor pairs together with a profile of ordered lists of all donors' kidneys, one list for each patient. A patient's ordered list of all kidneys (from the best to the worse) reflects, according to the patient's nephrologist, the ex-ante ordinal quality of the match between each kidney and the patient. The mechanism design question is to determine a systematic way of selecting, for each kidney exchange problem, a set of compatible transplants with desirable properties. Three economists, A. Roth (at Harvard University), T. Sönmez, and U. Ünver (both at Boston College), published in 2004 a paper in The Quarterly Journal of Economics studying the kidney exchange problem and proposing an adaptation of an already known algorithm in matching theory to solve all kidney exchange problems. The algorithm is known as the Gale's Top Trading Cycle Algorithm, and I will refer to it as the TTC algorithm.

Given a kidney exchange problem (remember, a set of incompatible patient-donor pairs and a profile of patients' lists, each list ordering all present donor's kidneys) the TTC algorithm solves the problem (i.e., proposes a set of compatible transplants) in stages. At each stage, the TTC algorithm roughly works as follows. (1) It constructs a graph whose nodes are the patient-donor pairs that have not yet been matched in the previous stages; (2) it directs the graph (a single arrow leaves from each node pointing to another node) by making that the patient points to the best kidney (according to his ordered list of kidneys) among those still present in the stage; (3) it identifies the nodes on the cycles of the directed graph; and (4) it satisfies the cycles, matching each patient of the nodes of the cycles to his pointed kidney.

The TTC algorithm keeps identifying and satisfying successively the cycles along the stages. Note that in each stage, there is always at least one cycle, if there are several cycles they do not intersect each other and a cycle may have a single node whose patient points to the kidney of his donor (obviously, since they are not compatible, the patient in this case will not be transplanted and the patient will remain under dialysis). Thus, the input of the TTC algorithm is an instance of a kidney exchange problem and its output is a solution of the problem that consists of a proposal of transplants based on the cycles identified along its stages. The TTC algorithm has many desirable properties. First, it is individually rational: every patient that receives a kidney at the outcome of the TTC algorithm prefers this situation rather than not receiving a kidney and remaining under dialysis. Second, it is efficient: all patients can not improve simultaneously; that is, if there is another set of transplants where one patient receives a strictly better kidney then, there must exist another patient that receives a strictly worse kidney. Third, the output of the TTC algorithm belongs to the Core of the kidney exchange problem: there is no subset of patient-donor pairs that, by reassigning the kidneys of the donors only among the patients in the subset, can obtain better kidneys; that is, no group of patient-donor pairs (for example those from a hospital, a city or a region) can object unanimously to the output of the TTC algorithm. Moreover, the Core of each kidney exchange problem is unique and coincides with the output of the TTC algorithm. Fourth, the mechanism associated to the TTC algorithm is strategy-proof: no patient could obtain a strictly better kidney by reporting (in fact, his nephrologist) a false ordered list of kidneys. Furthermore, the mechanism that, for each kidney exchange problem, selects the output of the TTC algorithm is the unique individually rational, efficient, and strategy-proof mechanism. Finally, the quality of the kidney received by each patient in the output of the TTC algorithm depends positively on the quality of his kidney's donor.

Finally, Roth, Sönmez, and Ünver (QJE, 2004) also reports some simulations suggesting that the TTC algorithm performs well and that it can be applied to real kidney exchange problems, and indeed it is now used in most countries with kidney exchange programs. But in addition, the paper has also triggered an already long list of papers studying different issues related to the specific nature of the kidney exchange problem that may require to adapt the TTC algorithm. For instance, (1) to deal with the increasing number of altruistic donors (called "good samaritans"), whose kidney can be used to initiate chains (instead of cycles) of transplants; The New York Times, on February 18, 2012 contained an article entitled 60 Lives, 30 Kidneys, All Linked describing a chain of 30 transplants initiated one year earlier by a good samaritan. (2) The consequences of requiring alternative incentive properties (weaker than strategy-proofness) when patients (their nephrologists) submit the ranked list of all donors' kidneys. (3) The presence of patients with several potential donors. (4) Ethical issues related with the ex-ante worse situation faced by O blood type patients since they can only receive kidneys from O blood type donors. (5) The effects of considering explicitly the dynamic feature of the problem, where the database of pairs keeps changing by the entrance and exit of patient-donor pairs.

In any case, kidney exchange has become a natural and successful application of Matching Theory and Mechanism Design to help human beings to live longer and better. 

 

About the Author

Jordi Massó Carreras is a Professor of Economics at the Universitat Autònoma de Barcelona and a member of Markets, Organizations and Votes in Economics (MOVE) since 2009.

Jordi Massó works on Mechanism Design, a research area in the intersection of Game Theory and Social Choice Theory, which deals with the study and design of institutions (mechanisms) with the aim of helping societies to take collective decisions. The emphasis is not only on the normative properties of the mechanism (for instance efficiency and equity) but also on the strategic incentives they induce on agents. Recently, he has been applying mechanism design tools to study three different classes of problems: matching, voting, and the allocation of a divisible good.

Contact: jordi.masso@uab.es

 
 
Tags: 
Matching
Developed by Paolo Gittoi