Analysing and optimising kidney paired donation

分析和优化肾脏配对捐赠

• 批准号: 1896139
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-1896139
• 关键词: Analysing; 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.

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