Analysing and optimising kidney paired donation

This project falls within the EPSRC Operational Research research area. Operational Research has transformed the way many markets have been conducted. One such example is Kidney Paired Donation (KPD), a novel mechanism that facilitates kidney transplantations for patients suffering from end stage kidney disease. Patients with a willing but incompatible donor (e.g.a friend or family member) join a KPD market as a pair and exchange kidneys with other such pairs. KPD programmes have been established in many countries around the world, including South Korea, the US and the UK.

So far, KPD has already given thousands of patients a new chance at life. In addition, cost analysis conducted suggests that KPD programmes in the US alone could save at least $750 million yearly. Similar results can be expected in other countries with KPD programmes. Furthermore, research on KPD can benefit other areas of market theory and operational research, as kidney markets can be viewed as examples of barter markets where agents (patient-donor pairs) enter a market with the aim of swapping items (the incompatible kidney) for another item (a compatible kidney).

Initially, KPD programmes only allowed for two-way exchanges that were allocated ad-hoc on a greedy basis. Soon after, however, programmes started collaborating with researchers from computer science, economics and mathematics. As a result, a significant body of academic literature on KPD has emerged that utilises sophisticated mathematical modelling and optimisation techniques to determine desirable organ allocation procedures. The predominant approach among programmes today is to take snapshots of the market at regular time intervals. For each snapshot, integer linear programming techniques or graph-theoretical algorithms are used to determine optimal organ assignments, subject to optimality criteria defined by the programme in question. Nowadays, programmes commonly go beyond two-way exchanges, allowing multiple pairs to exchange kidneys in such a way that every pair that donates also receives an organ. In addition, some programmes also allow so-called altruistic donors to start off domino-chain donations.

The aim of this project is to pursue a novel approach to the KPD matching problem that promises to yield significantly better results. Instead of approaching the market as a series of snapshot or offline problems, Akbarpour, Li and Gharan in a working paper introduce a model that explicitly accounts for the fact that agents join and leave the market stochastically. In addition, they make the plausible assumption that the central market planner has short-term knowledge of when agents are about to depart. footnote{To the best of our knowledge, no other paper models KPD in this way.} Dynamic markets are inherently more complex to analyse than their static or offline counterparts, necessitating the use of various tools from probability theory to make the analysis of dynamic algorithms tractable. While the paper by Akbarpour et al.~makes a strong heuristic case in favour of adopting dynamic algorithms for KPD, treatment of such markets as a bona-fide dynamic problem is still in its infancy and much further work is needed to establish whether the current preliminary results translate to viable algorithms in practice. As part of a conclusive answer to these questions, we plan to implement a realistic market simulation that allows us directly compare the performance of various offline and dynamic algorithms when run on historical datasets that mimic the current market situation. In conclusion, we believe that a dynamic approach to KPD promises to develop improved organ allocation procedures that will save more lives and effect greater cost savings in healthcare.