This post is about my research visit to Carnegie Mellon University (in Pittsburgh, Pennsylvania) during Fall 2015 semester. The visit was organized under the Indo-US Joint Center for Advanced Research in Machine Learning, Game Theory and Optimization supported by the Indo-US Science and Technology Forum. My host faculty for this visit was Prof. Avrim Blum.
The broad theme of our work was designing algorithms for joint-decision making in multiagent systems. In particular, we focused on the problem of kidney exchange. This problem arises in settings where patients with kidney disease manage to find a friend/relative/spouse who is willing to donate a kidney to them but is medically incompatible (say due to blood-type or tissue-type mismatch). In such a scenario, a transplant can still be carried out via a 2-way exchange, i.e. bringing together two such willing-but-incompatible donor-patient pairs (that happen to be cross-compatible) and having the donor from each pair donate a kidney to a patient from the other pair. In this case, all four surgeries (one each for the donor and patient from each pair) need to be conducted simultaneously in order to keep any of the donors from backing out. Nowadays, more complex cyclic exchanges (like 3-way and 4-way) are fast becoming common.
In its early stages, the task of matching donor-patient pairs was performed either by individual hospitals or by a team of locally connected hospitals. Recent years, however, have seen the emergence of centrally organized exchanges such as APKD, NKR and UNOS in the US, NLDKSS in the UK, ACCORD in the European Union etc. In a centralized kidney exchange, incompatible donor-patient pairs are revealed to the central exchange by the participating hospitals. A matching mechanism then operates on this pool of revealed donor-patient pairs to find as many opportunities for 2-way (or 3 or 4-way) exchange as possible, thereby maximizing social welfare (and the number of lives saved). Hospitals might find it in their selfish interest to conceal certain easy-to-match donor-patient pairs and perform the surgeries in-house, thereby benefiting both from internal matches and the matches suggested by the centralized exchange. There is growing theoretical and empirical evidence to suggest that strategic behavior on the part of the hospitals leads to significant inefficiencies in the overall social welfare. Besides, even in the absence of strategic considerations, the matching problem itself tends to become computationally intractable when 3-way (or larger) exchanges are allowed. The challenge facing an algorithm designer, therefore, is threefold – namely, to design a matching mechanism that (a) incentivizes the agents (in this case, the hospitals) to reveal complete information about their donor-patient pairs, (b) is computationally efficient and (c) minimizes the loss in efficiency. This thread was the subject of our research.
Pioneered by South Korea in 1991, kidney exchange has grown immensely ever since. In fact, the eminent Stanford economist Prof. Alvin E. Roth was awarded the Nobel Memorial Prize in Economic Sciences 2012 (along with Lloyd S. Shapley) in part for his pioneering contributions to the theory and practice of kidney exchange. Check out his talk at Simons Institute (where he discusses the above mentioned issues in greater detail) and his ever active blog.
A recent innovation in the practice of kidney exchange is that of altruistic donation. This refers to the situation when a generous donor simply wants to donate a kidney without any particular recipient in mind. Such donors are extremely valuable in kickstarting an altruistic donor chain, where the altruistic donor donates a kidney to a patient in need, whose willing-but-incompatible donor can in turn donate to another patient in need and so on. These chains are especially useful since they bypass the requirement of conducting all the surgeries simultaneously as with cyclic exchanges. The longest chains till date have been sixty humans long or more!
If you would like to know more, feel free to get in touch!