Analysing and optimising kidney paired donation

该项目属于EPSRC运筹学研究领域。运筹学改变了许多市场的运作方式。一个这样的例子是肾脏配对捐赠(KPD)，这是一种新的机制，有助于终末期肾病患者的肾脏移植。有自愿但配型不合的捐献者(例如朋友或家人)的患者以配对的形式加入KPD市场，并与其他此类配对交换肾脏。KPD计划已经在世界上许多国家建立，包括韩国、美国和英国。到目前为止，KPD已经给成千上万的患者带来了新的生活机会。此外，进行的成本分析表明，仅在美国，KPD项目每年就可以节省至少7.5亿美元。在实施KPD方案的其他国家，预期也会有类似的结果。此外，对KPD的研究可以帮助市场理论和运筹学的其他领域，因为肾脏市场可以被视为易货市场的例子，在这种市场中，代理人(患者-捐赠者对)进入市场，目的是用物品(不相容的肾脏)交换另一个物品(相容的肾脏)。最初，KPD计划只允许双向交换，这些交换是在贪婪的基础上临时分配的。然而，不久之后，项目开始与来自计算机科学、经济学和数学的研究人员合作。因此，出现了大量关于KPD的学术文献，它们利用复杂的数学建模和优化技术来确定理想的器官分配程序。如今，节目的主要方式是定期对市场进行快照。对于每个快照，都使用整数线性规划技术或图论算法来确定最佳器官分配，但要遵守有关方案确定的最佳标准。如今，项目通常超越了双向交换，允许多个配对以这样一种方式交换肾脏，即每一对捐赠者也获得一个器官。此外，一些方案还允许所谓的利他主义捐赠者开始多米诺骨牌连锁捐赠。该项目的目的是寻求一种新的方法来解决KPD匹配问题，并承诺产生显著更好的结果。阿克巴普尔、李和加兰在一篇工作论文中引入了一个模型，明确解释了代理人随机加入和离开市场的事实，而不是将市场视为一系列快照或离线问题。此外，他们提出了一个看似合理的假设，即中央市场规划者对代理人即将离开的时间有短期了解。脚注{据我们所知，没有其他论文以这种方式建立KPD模型。}动态市场天生比它们的静态或离线市场更难分析，这就需要使用概率论的各种工具来使动态算法的分析变得容易。虽然Akbarour等人的论文提出了一个强有力的启发式案例，支持对KPD采用动态算法，但将此类市场视为真正的动态问题仍处于起步阶段，需要做更多的工作来确定当前的初步结果是否在实践中转化为可行的算法。作为对这些问题的确凿答案的一部分，我们计划实施一个现实的市场模拟，使我们能够直接比较各种离线和动态算法在模拟当前市场情况的历史数据集上运行时的性能。总而言之，我们相信，对KPD采取动态方法有望开发出改进的器官分配程序，从而挽救更多的生命，并在医疗保健方面实现更大的成本节约。

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.